Print

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

[dreiche2]

I imagine that one of the biggest problems with pathfinding is pathing over stairs in multi-level fortresses.

Take the following example (based on my interpretation of A*): Assume a dwarf is on the surface and wants to haul back a log of wood to a stockpile which is, say, directly on a tile one level below the dwarf. Let's say the fortress entrance/stairs to level below are somewhere in the distance. Now, the current algorithm has no a priori knowledge about the stairs. It usually tries to path following the direction to the goal, which in this case would be "down", being blocked.  Thus, the only thing it can do is to spread out into all directions, "filling" the surrounding areas until it accidentally hits some stairs.

Now, assume the goal is actually several levels below, then I would imagine that after the algorithm found the top most stairs, the algorithm would potentially fill the next level below in a similar fashion before going another stairs down, and again for each subsequent level (!). This should happen even if it's just one large staircase, as long as the goal is more distant in the horizontal than in the vertical from the stairs. Basically, the algorithm would then not follow the stairs down to the correct level before walking off, but instead on each level leave the stairs because it decreases the distance to the goal more than going down.

Any more complex algorithm that handles something like way points or choke points, preferably automatically, might be able to handle this situation. In particularly, in the case of stairs/ramps the transition points are actually known in advance (i.e. you could maintain a list of stairs). So whereas you don't know in advance where the choke points are on the same z level (doors are potential choke points, but there might just be an unblocked passage nearby), in between z levels you know that all passages *must* be stairs/ramps (for non-flying creatures).

Hence, it might be worthwhile to treat stairs/ramps explicitly, in particularly maintaining a list of them, and this should be worthwhile doing as long as the number of stairs/ramps is small compared to the number of total tiles.

For example, take the algorithm referenced here. It divides the maps into blocks (possibly in multiple hierarchical levels) and passages in between the blocks. The pathfinding searches on the graph defined by the blocks, and then locally in the blocks. This type of algorithm might handle stairs naturally.

Alternatively, you could concentrate just on the stairs and similarly to what the above algorithm does construct an abstract graph that represents areas connected via stairs. Then you should be able to do A* on that graph first to identify which stairs you need to follow along the route, and then A* to path in between the stairs (or potentially cache these paths).

Now, I am no expert but this seems feasible. I actually intended to code up a toy program (say a graphical representation of a multi-level map with pathing units) to be able to play around with different algorithm, but seems like I'm a lazy arse. If anyone else wants to do it...

[Vigilant]

You can do this now: set the "high" designation to be cost 0, and things should work themselves out. While it has a "high" designation to follow, it won't follow anything else.

Are you sure? I tried this out, first I had to set it to 0 in the init file, wouldn't work manually. And when I tinkered with it, the dwarf seemed to fairly obey the path, but not entirely. I had an interesting spiral path just to see how blindly they'd obey a high desgination of cost 0, and the dwarf generally follows the path, but if he sees he can jump a small gap in it to get closer to his destination faster, he does that. So I'm not sure whether this means it's working the way you think it does.

[illusori]

I imagine that one of the biggest problems with pathfinding is pathing over stairs in multi-level fortresses.

Snipping lots to just keep to the relevent bits for my reply.

as long as the goal is more distant in the horizontal than in the vertical from the stairs. Basically, the algorithm would then not follow the stairs down to the correct level before walking off, but instead on each level leave the stairs because it decreases the distance to the goal more than going down.

This is based on a common misunderstanding of A* that it is based on distance, it isn't, A* is based on cost.  You're perfectly free to adjust the cost of movement in any direction, this means that you can tweak matters so that cost of horizontal movement is higher (how much higher is a matter of "suck it and see") than that of vertical, that means that staircases become "sticky", once you path onto them you'll prioritize them as a prefered search path.

This is only a partial solution although it does address the problem of backtracking across intermediate levels when you need to go up/down further and can do on the current stair.

Adjusting the movement cost is probably how the traffic areas are implemented, although as a professional coder I'm hesitent to guess how any bit of code is implemented with only a view from the outside.

But basically, my main point is that A* prioritizes the next node to search down based on cost to get there so far and estimated cost to get from there to the destination, and there's lots of ways you can tweak those costing formula that isn't just linear distance, and for most implementations you probably should tweak them, and spend more time doing that than writing your A* search in the first place.

Hence, it might be worthwhile to treat stairs/ramps explicitly, in particularly maintaining a list of them, and this should be worthwhile doing as long as the number of stairs/ramps is small compared to the number of total tiles.

This rapidly becomes problematic if you have unconnected areas on the same level, each with their own stairs to levels that may or may not be connected - you cannot assume that you can path entirely within a single level even if start and destination are on the same level.

Also, even if you can, if you have for example a large U shape and need to path from one end to the other, you will traverse the length of the U even if there is a shorter path linking the two directly down some stairs, across, then back up.

In practice, you can't do this sort of hierarchical pathfinding without a lot of oddities unless you go with a full-blown implementation where you're working on generic clusters of tiles with bottlenecks between them and accepting the fact that estimating cost of traversal of a cluster can be problematic enough that you're going to get noticably odder results than A* produces on its own, and you're going to be making your implementation significantly more complicated and potentially be trading off more (in a dynamic environment) keeping your list of clusters up to date than just pathing the 'simple' way.

(or potentially cache these paths).

This can be a big win, especially if you cache on destination and then check for partial matches within your A*, ie I've pathed this far and I've reached somewhere that I've already pathed to the destination I want already.

Problem with caching is selectively invalidating routes based on dynamic events, but you can usually get away with just traversing the returned path and checking for accessibility at each step of the route, and invalidating then.

[NeedsDF2GetThruWorkingDay]

you can tweak matters so that cost of horizontal movement is higher than that of vertical, that means that staircases become "sticky", once you path onto them you'll prioritize them as a prefered search path.

Is this something that can currently be configured? I don't see it in the init file.

[sweitx]

(or potentially cache these paths).

This can be a big win, especially if you cache on destination and then check for partial matches within your A*, ie I've pathed this far and I've reached somewhere that I've already pathed to the destination I want already.

Problem with caching is selectively invalidating routes based on dynamic events, but you can usually get away with just traversing the returned path and checking for accessibility at each step of the route, and invalidating then.

Caching route can also be invalidated as new routes are discovered.  Namely the system will sequential through the list of route for a route that has "died of old age" while aging each route that it has checked.
Example, route ages...

Code: [Select]

Step 1: Start from route 1
23101221
^
Step 2: Decrement each non-zero route by 1 as it advances, until seeing a route with 0
13101221
 ^
12101221
  ^
12001221
   ^
Step 3: Replace route with new route and reset route's "age"
12031221
    ^
The next cache search continues from the "^" mark.  Also, if no suitable route is found for X advances, stop caching the current route.
Some variation can be made.
1. Reset routes "age" everytime it gets use.
2. Tweak how large an age value to use (large age = longer time to die and more static, but may keep good path indefinitely).
3. Tweak the limit to number of routes to check for replacement (smaller = faster but more static).

[dreiche2]

This is based on a common misunderstanding of A* that it is based on distance, it isn't, A* is based on cost. 

I was aware of that. Like you said, decreasing the cost of traversing stairs is only a partial solution. Moreover, it only partially solves the specific problem I stated, and might worsen others, e.g. when there are two staircases, only one leading to the intended goal, and the dwarf is one the wrong staircase.

Adjusting the movement cost is probably how the traffic areas are implemented, although as a professional coder I'm hesitent to guess how any bit of code is implemented with only a view from the outside.

Yes, this seems to be common knowledge around here, I think Toady might have mentioned it somewhere.

Hence, it might be worthwhile to treat stairs/ramps explicitly, in particularly maintaining a list of them, and this should be worthwhile doing as long as the number of stairs/ramps is small compared to the number of total tiles.

This rapidly becomes problematic if you have unconnected areas on the same level, each with their own stairs to levels that may or may not be connected - you cannot assume that you can path entirely within a single level even if start and destination are on the same level.

No, the idea was to make a graph of areas connected via stairs, thus you would know if the stairs are connected beforehand. Yes, that involves additional computations, but it might be better than having a dwarf search "blindly" *every* time he wants to path in between the disconnected locations on a level (you could say that the dwarf makes the connection assumption initially, every time).

In practice, you can't do this sort of hierarchical pathfinding without a lot of oddities unless you go with a full-blown implementation where you're working on generic clusters of tiles with bottlenecks between them and accepting the fact that estimating cost of traversal of a cluster can be problematic enough that you're going to get noticably odder results than A* produces on its own, and you're going to be making your implementation significantly more complicated and potentially be trading off more (in a dynamic environment) keeping your list of clusters up to date than just pathing the 'simple' way.

Yes the paper I linked does something like this, and I could imagine the situation is simpler if you just consider stairs, not connections between blocks of tiles in general. Yes, it would be more complicated, and if it would really be more efficient in the end, I don't know. But I think it has potential. Also note that, if I remember correctly, Toady already tracks which areas are connected overall (otherwise, if you were to try to path between two disconnected tiles, A* would have to look through every single tile connected to the starting point to find out that goal and start are disconnected). Hence, it might be possible to use the same technique on a per level basis, tracking the stair connections in between...

[illusori]

you can tweak matters so that cost of horizontal movement is higher than that of vertical, that means that staircases become "sticky", once you path onto them you'll prioritize them as a prefered search path.

Is this something that can currently be configured? I don't see it in the init file.

I mean "you" as in the person writing an A* pathfinding implementation, not specifically dwarf fortress, or someone running it.

[illusori]

I was aware of that. Like you said, decreasing the cost of traversing stairs is only a partial solution. Moreover, it only partially solves the specific problem I stated, and might worsen others, e.g. when there are two staircases, only one leading to the intended goal, and the dwarf is one the wrong staircase.

Failure cases are always going to be more expensive, however it's a matter of tweaking things so that you hit the failure cases less often: unless you've got a pathological fortress you're going to have more tiles that only have horizontal routes than tiles that only have vertical routes.

No, the idea was to make a graph of areas connected via stairs, thus you would know if the stairs are connected beforehand.

Sorry, this wasn't clear from your original post, and was the point I was trying to make, that you'd need to compute the graph, which is a minor (optimized) step away from a general purpose tile clustering method.

[dreiche2]

Yeah, I'm often not very clear.

Yeah, the whole more complicated clustering stuff seems like a potential headache. On the other hand, in the current situation a multi-level fortress could be a constant headache for the dwarves, too, and especially with stairs it just seems like the necessary information is already there, so it really calls for utilization... oh well.