Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Reelya]

You'd still have to wrap it in structures to handle it and so a generic solution would still need to use more code and template metaprogramming. But from what I can see, would let you use light-weight structs and functions instead of heavier classes, like in the example with

Code: [Select]

struct mytype
{
    unsigned long long m;
};
So as I understand it you could define:

Code: [Select]

struct km { long double v; };
struct s { long double v; };
struct kmps {long double v; };

constexpr km  operator"" _km ( long double v ){ return km{v} }
constexpr km  operator"" _s ( long double v ){ return s{v} }

constexpr kmps operator/ (km k, s sec){ return kmps{(k / s)} }

...

kmps res = 5_km / 2_s


The only problem there is that you then have to also define all the possible combinations by hand, for example if you multiply velocity by time then you get the distance traveled, if you divide a velocity by time then you get acceleration, multiply a velocity by a distance and you get area over time, etc. So you'd have to hand-craft every possible combination of operations.

Remember, you also can't add two km structures without a special operator now. So you have to have a whole set of operators just for km-km conversions (add, subtract, multiply, divide) then you need to replicate that for s-s conversions, then you need km-s conversions for when km is on the left, and s-km conversions for when s is on the left. Then, you get second-order values: km^2, s^2, km*s, s/km, km/s. Now, you need the four operators for each of these new units by themselves, and they need operators to multiply and divide for each of the other operators, also duplicated just in case the LHS and RHS units are swapped in the equation. So for just two base units for second-order values you now have something like 7 different structs, 28 single-unit operators, and 42*4 = 168 two-unit operators. This is omitting the fact that many of those operators will need to generate third-order and fourth-order struct types to be consistent.

What you can do is combine this stuff here with what I posted back on march 14th and you get the best of both worlds: the same easy to use units but with the automatic type checking and conversions.

[mko]

My village/city simulator project (grows on its own, NOT designed manually by a player) moved forward a bit.

Currently I am working on adding paths. What, as expected, turns out to be more complicated than expected.

For additional fun I decided to have continuous terrain, without tiles what makes generating paths more complicated.

Spoiler (click to show/hide)

This path layout is reasonable purely by accident. Also, entire path rendering is currently a giant hack.

[bloop_bleep]

What are you using to generate paths? Minimum spanning tree algorithm?

[lethosor]

What you want is template meta-programming to make things like km/s work, btw remember I gave an example of working code for that a couple of pages back, which can take a km template and an s template, and spits out a novel km/s template representation, while also forcing type consistency, all at compile time, so no overhead. Or, you could come up with a runtime equivalent that would be more flexible but of course slower.

If anyone's interested, I ran into this units library recently; I haven't used it much, so I can't vouch for it, but it seems to be pretty full-featured.

[mko]

What are you using to generate paths? Minimum spanning tree algorithm?

Currently? Tragic hack not worth describing (select random point, make path from each house to this point). At best I get something close to the minimum spanning tree like here.

The plan?

I need to solve pathfinding quantization (discretizing pathfinding) that will not cause FPS death and will produce nicely looking paths.

Pathfinding is quite easy where movement is limited to tiles (like for example in Minecraft, HOMM III or whatever else). Obviously, with enough of required pathfinding or complexity it will trigger other difficulties (DF).

In my case I had weird idea that movement may be between any points. For example path may start at (1, 1) and lead to (10, 10) through points (1.2535, 3.282) and (8.37377, 6.9).

I hope that it will allow more natural-looking paths/roads compared to say Minecraft.

Such continuous search space makes impossible to check all possibilities, there is too many of them.

For bonus points  I want it also in context of terrain of varied height (path is not supposed to go through cliff if there is a way around, but if cliff is unavoidable then going through it is OK. Similarly for steep drops or other holes/ditches/etc).

I also want to support modifying terrain (building bridges, filling in holes, building stairs/modification of steep slopes to allow curved roads to be constructed).

First step will be without bridges, without terrain modification, without really considering terrain. But going around clear obstacles (implemented, but I need to redo this work) and reusing existing path (totally not implemented). Maybe also with quantization smarter than "build square grid" with clearly visible artefacts.

Spoiler (click to show/hide)

https://gamedev.stackexchange.com/questions/93764/path-finding-for-vector-based-system

https://stackoverflow.com/questions/33573553/a-orientation-discretization

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html

https://en.m.wikipedia.org/wiki/Navigation_mesh

https://web.archive.org/web/20150905073624/http://www.ai-blog.net/archives/000152.html

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#polygonal-maps

https://gamedev.stackexchange.com/questions/156985/how-do-you-handle-pathfinding-for-non-tilemap-2d-games

https://gamedev.stackexchange.com/questions/58963/pathfinding-with-2d-non-grid-based-movement-over-uniform-terrain

https://gamedev.stackexchange.com/questions/120021/a-pathfinding-takes-too-long-shortcuts-needed

http://www.red3d.com/cwr/steer/FlowFollow.html

http://www.red3d.com/cwr/steer/

http://aigamedev.com/open/tutorials/potential-fields/

[bloop_bleep]

I'm not sure if this has already been suggested in one of those links in your post, but how about creating a tile grid, snapping pathfinding sources/destinations to that grid, doing A* tile-based pathfinding, and then making the paths look more organic with B-splines or Bezier curves?

Also, the problem of creating many paths between many locations with minimum total walking distance isn't exactly pathfinding (shortest distance finding), it's minimum spanning tree construction. There's several well-known efficient algorithms for that, one of them being Jarnik's algorithm.

It won't be exactly MST construction, since you're only trying to span a subset of the vertices, but you could probably adapt it.

EDIT: Sorry, that's the Steiner tree problem, which is NP-complete. Approximations or local maxima would probably be acceptable.

EDIT: I have an idea for what you should do! First, take the convex hull of your set of points, construct the polygon whose edge midpoints are the vertices of your convex hull (probably can be accomplished with some vector arithmetic) then construct a Voronoi diagram from the vertices of that polygon. The lines of the Voronoi diagram are your paths; make the lines that go through a vertex of the original convex hull stop at that vertex. Then add perpendiculars from each point inside your convex hull to the nearest existing path. Bam!

[mko]

I'm not sure if this has already been suggested in one of those links in your post, but how about creating a tile grid, snapping pathfinding sources/destinations to that grid, doing A* tile-based pathfinding, and then making the paths look more organic with B-splines or Bezier curves?

I have not really considered it, thanks for an idea. Though I expect that artifacts would be clearly visible or that after transformation it will clip impassable areas. In case of the initial attempt failing I will try this.

For now one heuristic is a total failure, one sometimes works.

I hope that it will allow also to reduce A* graph size. Current grid with size of 2m would blow up to 0.25 million vertices and million edges just for one square kilometer.

Even 10m grid size would have 10 000 vertices + 40 000 edges for every square kilometer.

I hope that with force field adjustment of more sparse grid I can get comparable or better results.

Also, the problem of creating many paths between many locations with minimum total walking distance isn't exactly pathfinding (shortest distance finding), it's minimum spanning tree construction. There's several well-known efficient algorithms for that, one of them being Jarnik's algorithm.

It won't be exactly MST construction, since you're only trying to span a subset of the vertices, but you could probably adapt it.

EDIT: Sorry, that's the Steiner tree problem, which is NP-complete. Approximations or local maxima would probably be acceptable.

I am not trying to build MST. The plan is to end with town/city simulator where roads are forming many cycles, and road/footway graph is not a tree.

I am certainly not looking for an optimal solution, "just" good enough and preferably not taking too much memory CPU.

I am calling it pathfinding as it will answer repeated queries "get me path between A and B", with possibility that part of all of it is not yet constructed.

[bloop_bleep]

I have added another possible idea in an edit of my above post, in case you missed it. I might post a picture indicating what I mean.

[mko]

It sounds like



from http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#hybrid-movement

(brownish areas - passable, otherwise impassable.)


(or maybe not, I am now going to a bed because I am no longer productive and I am not sure whatever I interpreted your post corrrectly)

[bloop_bleep]

Here ya go.

Spoiler: large image (click to show/hide)

A, B, C, D, E, F (blue points) are the destination points.

A, B, C, D, E is the convex hull. PQRST (gray points) is the polygon whose edge midpoints are A, B, C, D, E. (This polygon will be unique for odd numbers of convex hull vertices.) The solid gray line segments are a section of the Voronoi diagram created with the points P, Q, R, S, T; they are collectively your paths. Each of these solid gray line segments is a subset of a pairwise perpendicular bisector from the set {P, Q, R, S, T}. V0, V1, V2 (green points) are intermediate points on the paths. Since F was inside the convex hull, we must give it special consideration. W is the foot of the perpendicular from F to the nearest path segment. The line segment FW is added to the paths.

To prevent there being lots of points left inside the hull, instead of taking a convex hull, we can take some sort of "largest non-self-intersecting polygon hull," which is allowed to be concave. Or we can split the set of destination points into smaller chunks, do the above on each chunk, then link the paths created by each chunk.

It makes sense to do this anyway, since as your village/city grows, new locations would be added in incremental chunks, without the whole road plan being rebuilt each time.

(To choose chunks, we could say there should be about n locations in each chunk, calculate the approximate number of chunks from that, then do a K-means algorithm to choose chunks that are individually bunched up.)

This should also be generalizable to 3D.

[mko]

@bloop_bleep Note that some of this paths may be blocked and inaccessible (or going through a cliff), so for pathinding a bigger pool of alternative paths is needed.

This usually would not be a problem. But as result of "simulation, with progress directly visible" I cannot fit terrain/obstacles to the buildings like it would be possible for "generate an unchanging settlement".

In other words, after 10 hours of work my code is doing the same but significantly slower. And it IS a progress because now elements can be more easily upgraded/modified. For example, the N^2 priority queue.

[LoSboccacc]

how deep is this city simulation? does it have walkway separated from roadways and one way roads? are building on a grid or free form?

[mko]

how deep is this city simulation? does it have walkway separated from roadways and one way roads? are building on a grid or free form?

For now I have solely paths, without roads. Roads are planned.

Support for more modern stage of towns/cities with multi-lane roads, sidewalks, motorways, railways, one way roads etc is something that I want to include but it is months/years in future (assuming that project will continue).

I am placing objects without a grid - I hope for more realistic and organic structure but for now main effect is that everything is far more complicated. There is sadly a grid for a terrain, but I hope to remove it also here.

[Reelya]

So do you "grow" the town via simulation or do you "lay out" the town procedurally? What I think the best approach to take would be to grow the town as abstract "nodes" modelling links between nodes (localities) and abstracting-away the specifics of each locality, then you do a final pass laying out all the specific buildings and fixtures.

[mko]

So do you "grow" the town via simulation or do you "lay out" the town procedurally? What I think the best approach to take would be to grow the town as abstract "nodes" modelling links between nodes (localities) and abstracting-away the specifics of each locality, then you do a final pass laying out all the specific buildings and fixtures.

Simulation. The tricky part is that I want to simulate history, with town growing/shrinking/changing over time - rather than make a map of one specific point n the history. On the other hand I plan to simulat single location, not entire world. So other towns/cities may stay nearly completely abstract.