Print

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

[shadow_slicer]

@Sunken:
I'm not saying we're calculating everything on demand. What I mean is that the client program defines a movement class with a function instead of a capabilities bit-vector. Everything else is pretty much the same. This means that when the client creates a movement class, we make the connectivity map for this class (or adapt our connectivity map to support this class). The client will still need to notify us of tile changes so we can update our connectivity map. The primary advantage is not having to store as much per-tile information (which would be duplicated from the client).

As Shades mentioned, the biggest drawback of this method is that it makes things more complicated for algorithms that combine movement types. Though, I think with as few movement types as we are dealing with, it might not make sense to focus on optimizing that.

@qwertyuiopas:
What I described should work as an external library. I've worked with libraries that do the same thing (standard C library, C++ STL, Boost, glib, gtk), so I don't expect that to be a problem.

[Shades]

I'm not saying we're calculating everything on demand. What I mean is that the client program defines a movement class with a function instead of a capabilities bit-vector.

Can you expand upon that? The programic side of passing such things is simple but for actual path-finding I don't see how that works if your not calculating on demand, if you can expand upon that so I can understand what you mean it would be most helpful

[Sunken]

I suppose he's saying that the code that determines whether a given unit can move through a given tile or not should be modular, so that it can be abstracted away from and exchanged (and all other advantages of modularity). This only tells you how the code is called, not when. It could be called for each tile of the map in advance for common unit types and "cached", and on demand for uncommon unit types.

If this is what he means I sort of agree, but also point out that connectivity is not local in nature and it might be hard to maintain efficiency if that, too, is made modular.

[Shades]

He was passing it in the GetPath function which I assume returns a path. If you wanted to do any precalc you'd have to pass it in some form of setup, which I agree would lead to the modularity you mentioned.

[shadow_slicer]

@Shades: It was passed in the GetPath function only to get uncached paths. The cached paths use a movementclass which was set up using PathLibrary::CreateMovementClass. CreateMovementClass will set everything up.

@Sunken: Yes, you seem to understand my idea. I'm not sure what you mean though about "connectivity is not local". I'm only proposing to use the callback to obtain information on local connectivity. Obviously the library will need to maintain some state for connectivity between zones or whatever, but this is going to be built on the local connectivity information regardless of how this local information is obtained.

[Shades]

@Shades: It was passed in the GetPath function only to get uncached paths. The cached paths use a movementclass which was set up using PathLibrary::CreateMovementClass. CreateMovementClass will set everything up.

So assuming you needed a local cache of routes of any potential request coming later how do you interrogate the movement class to see what is possible. Or would it return some array of all possible distance calculations between whichever squares the local zone needs to check?

[numerobis]

Why bother with movement types at all? Why can't we just use a callback function to determine the cost/if pathable of some opaque movement class?

Different movement types imply different hierarchies for running the pathfinding over.  Until we know how to compute the cost, we can't build anything and we're stuck with the basic A*.

[shadow_slicer]

@Shades: I'm not sure I understand what you mean. The movement class is really opaque to the library, and it really defined through a callback function. The library can use the callback function to determine the cost between any two adjacent tiles. The alternative would be for the client to provide the library with a gigantic connectivity/movement cost table. Really the question you're asking seems to be independent of whether we use a cost table or cost function, but I'll try to answer the best I can.

If the library needs to generate a cache of any potential path requests that may come later, then it would use some pathing algorithm (could be HAA*, A*, HHA*, etc) and the cost data from the callback to generate the paths.
If the client needs to generate a cache of potential paths, then it would call getPath for each of the paths it needs.

@numeroids: What I meant by not having movement types was not having a bitvector that determines whether a tile is passable or not by creatures with certain movement capabilities as was previously discussed. Instead, both the movement type and creature capability are wrapped into the result of a single function call, which also returns the cost. Since we know the cost, we can build whatever zones or hierarchies we want. I think that this is better than the alternative of storing the capabilities and costs for moving any of the roughly 27 possible directions from each of the tiles on the map, we only need to store a function pointer and simply ask the client every time we need it (since presumably the client can calculate it quickly).

[numerobis]

@shadow_slicer: my confusion was that you seemed to be arguing that we shouldn't have movement types, but now I see that you're ok with movement types, just as long as we don't explicitly represent the edges between grid squares.  I don't think anyone has actually argued that we should represent those edges; what we probably can't get away from representing explicitly are the edges in the abstracted graphs.  Said edges must encode what movement types they allow, one way or another -- either as labels (presumably bitvectors) on the edges, labels on the vertices, or by having multiple graphs over the grid.

[shadow_slicer]

@numerobis:
I actually do think we should explicitly represent all 26 of the edges between grid squares. If you don't then it becomes more difficult to figure out which directions are allowed. Suppose you have a path under a cliff. Both the ground under the cliff and the top of the cliff are passable for walkers, but walkers shouldn't be allowed to "teleport" up to the top of the cliff. You could try restricting this movement to special cases, but that simply makes it more difficult to model jumping off ledges, climbing ramps, and numerous other movements. Jumping off ledges is a particularly strong example: you need to allow the path to go diagonally down, but going diagonally down probably needs to have a different cost and require different capabilities than going to the next tile over horizontally. You can't add this information to the tile at the bottom because it only should effect paths that jump down from the ledge. You could handle it as a special case, but that seems messy. In summary, if you do not explicitly represent all the edges, it is extremely difficult to apply different costs and requirements to different directions, and simply putting the cost and requirements inside the tile is not flexible enough to handle many cases that we need to support without ugly hacks.

As you said though, in the abstract graph movement types would need to be represented on the edges unless we have separate abstract graphs for each movement type.

[Mike Mayday]

EDIT: nvm, I can see something like my idea has already been suggested

[Mel_Vixen]

xcuse my absence here (i was formaly invited) But i had no web connection in the last 1 1/2 months and will not have one for the nexttime. I also post now before having read the thread to the end because i dont know how much time i have.

[edit]By the way i think a platform independend implementation would be needed.

 The "world-tiles" should be modify-able in a way that new "flags" can be added flexible. The flags would be handled like in a sql DB with "type" and "set" attributes plus the id of the tile as primary key. This could be very handy for new travel methods and new obstacle variants.

 [/edit]

Not only are rectangles the most common thing people build in DF their also efficient at covering the unmodified terrain as well and are much simpler to set up and can aid in doing multi-tile creatures as we can be assured that a creature thats longest dimention is shorter then the rects shortest can move through the rectangle.

Rectangles also would support a simple idea i had a bit Better. A little discussion about shading gave me it. Idealy The shortest connection between two (not moving) points is a straight line. Since we know the accesnodes between two mapchunks/Leaves we could use Bresenhams algorithm to calculate The shortest way in a leave betwee two nodes. If a soft obstacle, like a dorf is on the path we can use at this point a short A* to path around the obstacle to continue the precalculated path or we just dodge (1 step forward in a certain angle) and use a bresenham again.

3D paths ("cubes" instead rectangles) like for swimmers/flyers can also make great us of that because the bresenham would return a (in 99% a good part of cases perfect) valid path in the box/rectangle which should be in 90% of all cases faster calculated then a path by a* . Apart from bresenham we could also use bezier curves for a more natural flight/swim behavior.

qoute by DeathofRats

That's part of the problem, and why I'd say it's important for whatever algorithm is chosen to have two characteristics: that segmentation works locally (i.e., I just mined a tile, I don't have to recalculate all the pathing for the whole damn world), and that different areas can be re-zoned (divided or merged). If those two criteria are met, it shouldn't be a problem to deal with terrain modifications.

In my opinion we should implement apart from heuristics multiple takes on (in mapchunk) pathing because depending on the pathing task and outer influences (like the sidelenghts/radius of a mapchunk) a different pathing variant could be more efficient then the usual one. For example bresenham might be enought to traverse 3 mapchunks and in the 4rd a A* might be needed.

AI settlements will need to be generated with their own set of room definitions, traffic designations, etc.. That will break save compatibility again, so it's not trivial - but something like that has to happen if the townsfolk ever are not to act like they all suffer from terrible amnesia, don't really know what they're doing there, and just amble around wondering whether they are just a randomly generated npc in a big simulation.

Actually the save-comp doesnt need to be destroyed. IIrc for villages the "room-devs" already exist and the "paths" could be saved in a own file which actually would also benefit the ADV mode because then the paths for the Ai-Agents "ofscreen" can be still calculated without loading the entire junk of data like objects (not needed items, animals, etc.).

Since the rooms already exists the routes could be caculated on the first load of an old save-file.

[...] more in a bit, feel free to discuss in between. thats it for now

[shadow_slicer]

quote by Heph:

Rectangles also would support a simple idea i had a bit Better. A little discussion about shading gave me it. Idealy The shortest connection between two (not moving) points is a straight line. Since we know the accesnodes between two mapchunks/Leaves we could use Bresenhams algorithm to calculate The shortest way in a leave betwee two nodes. If a soft obstacle, like a dorf is on the path we can use at this point a short A* to path around the obstacle to continue the precalculated path or we just dodge (1 step forward in a certain angle) and use a bresenham again.

Actually I think A* with a good heuristic should be equivalent (in both result and computational cost) to Bresenhams algorithm for the case where that algorithm is applicable. As long as the heuristic is such that a straight-line is always seen as better than the curve, A* will not explore any of the "off line" paths. Since diagonal travel is allowed, a good "remaining cost" heuristic is "max(dx,dy,dz)". Additionally, if you use a straight-line technique until you hit an obstacle, there is no way to ensure optimality of the resulting path. If you look into the literature on "Greedy Geographic Routing", which is a somewhat similar idea, you'll find the worst-case (and in result the average-case) performance is very poor. Also, I'm not sure there's a good way to change back from A* after getting around the obstacle. There are two problems: 1) how will you know when you've gotten around an obstacle 2) which candidate next step from A* should you start with? Really just using A* is significantly simpler, and shouldn't be that much more costly.

As for using bezier curves or other algorithms to represent behavior, I don't think the pathing library should be responsible for handling AI.

quote by Heph:
In my opinion we should implement apart from heuristics multiple takes on (in mapchunk) pathing because depending on the pathing task and outer influences (like the sidelenghts/radius of a mapchunk) a different pathing variant could be more efficient then the usual one. For example bresenham might be enought to traverse 3 mapchunks and in the 4rd a A* might be needed.

While this is definitely possible to use different pathing algorithms in different zones, but I'm still not convinced we need something other than A*.

[Sunken]

The Bresenham algorithm is fundamentally aesthetic in nature and doesn't help you find the shortest way between points in any meaningful way. Sure, it might look better if creatures moved in what looks like straight lines towards their goal in open areas, but it has no effect on the cost of the path, and it is more expensive in implementation than just "if x < targetx && y < targety then up-right" (since Bresenham would require storing extra values and performing computations slightly more complex than the above, each step).

The Bresenham algorithm also wouldn't work with TCZs, as a side note ; )

[qwertyuiopas]

Earlier all-edge comment:

The cliff case is meaningless: You could have a tile group for the upper path, and one for the lower. Where the edges of the groups cross, you could describe the movement costs between them. The advantage is that you don't have to store the data of every identical sky tile in an empty 10x10x10 cube, only where it connects to other groupings. When breaking up the grouping, you simply transfer the edge data, either to the tile itself(unlikely) or to the new edge.

Also, a suggestion: maybe put a slight extra weight against direction changes? Not tile-based, but a flier going up over a mountain wouldn't follow the ground exactly... (Of course, such behaviour might develop naturally...)