Print

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

[Lummox JR]

Apologies if this overlaps with anything discussed before. I found it hard to find anything similar and very hard to find concrete details on DF's modified A* pathfinding. All I know for sure is that the modified pathfinding uses some caching.

It seems to me that one of the most direct ways to improve pathfinding is to break the map into "areas", where every tile in an area can reach every other tile in that area. These would be considered waypoints in A* pathfinding so if a creature has a destination in another area, they would try to find a path via areas instead of via direct tile-based A*. If they're in the same area, they'd fall back on A*.

The concept as I see it is like this: The map is broken down into NxNx1 blocks, where N is a power of 2 for simplicity. 16x16 would probably improve pathfinding a lot, but 32x32 might be better in some cases (and, perhaps, worse in others). An area belongs to one and only one block, but you can have multiple areas per block.

Each area has a list of which other areas it connects to. There could be a simple fixed list of NSEWUD directions for basic cases, but that could be overridden as needed for multiple-area connections. This part refers simply to what's accessible via open tiles, ramps, or stairs. For most areas, there would probably be only one neighbor area in any given direction; only a few would need more complex handling. There would also be a list of door-based connections, e.g. area 517 connects to area 689 via three possible doors, and if those doors are passable then that's a valid route. This would include lever-controlled doors and hatches, and bars, anything destructible, so that a building destroyer could use this information the same way a dwarf or a cat or a thief would, just with different rules.

Every time terrain is changed within a block, the block is recalculated. It's broken into areas again, preserving existing areas if possible, and redoes any connections. (Liquids might be a slight problem for this but I see that as surmountable. Plus, you could always allow that any amount of liquid equals an area unto itself, so fluctuations between passable and swim depths wouldn't be critical.) Bridges opening or closing would be part of this.

For pathing costs, any area-based A* pathing would use the average cost of every tile in the area. This might be a little biased against small areas like a corner connecting two hallways, but it's not a big deal.

I do know breaking down the map into areas has been suggested, but I don't know if the idea of confining areas to NxNx1 blocks ever came into play. It seems to me like a sensible solution to a potentially difficult problem. You'd still be able to use A* because areas would be laid out in a grid, albeit with some areas sharing the same grid square (block).

[edit]
I forgot to mention that part of breaking the block down into multiple areas would be the use of disjoint set forests. It should be quick to break a block down into areas that way, and then it'd just be a matter of reconciling that with already-existing areas to prevent a lot of memory churn.

[Bumber]

AFAIK, it already works this way to check connectivity. It's not used in the pathfinding algorithm itself due to z-levels, I think.

There was an AMA response by Toady regarding subregion graphs:

No time to follow links during an AMA, but various subregion approaches have been tried (either by me or by people trying to help out). They've all failed based on the time it takes to recalculate regions after digging, flooding, etc. With a 200x200x200 map or whatever, it gets prohibitive. But sure, any new approach there that calcs the regions/graph super super fast would be useful.

[Lummox JR]

Disjoint set forests should do the area calculations in a short time, so that could work, plus in cases like digging or flooding you could delay the update, marking a block "dirty" but not actually recalculating, for several ticks--since the block-level algorithm wouldn't need a great deal of accuracy and it wouldn't hurt anything for it to be briefly wrong.

[GoblinCookie]

Does it not work to temporarily use the older, less efficient algorithm if anything happens in your area that would potentially interfere with the situation?

[PatrikLundell]

Does it not work to temporarily use the older, less efficient algorithm if anything happens in your area that would potentially interfere with the situation?

Only if the older algorithm uses exactly the same data structure (or a subset of it), as building and maintaining a fallback structure is bound to be costly, and thus most likely not worth it. I would guess detecting cases of pathing through dirty regions and prompt an immediate reevaluation would be a better way to handle the cases where the old path might not be valid.

Regardless, any new algorithm will have to be tested and shown to be more efficient in practice, so there's quite some way to go before we even know if Toady hasn't tried it already and whether it actually is more efficient in practice.

[GoblinCookie]

Only if the older algorithm uses exactly the same data structure (or a subset of it), as building and maintaining a fallback structure is bound to be costly, and thus most likely not worth it. I would guess detecting cases of pathing through dirty regions and prompt an immediate reevaluation would be a better way to handle the cases where the old path might not be valid.

Regardless, any new algorithm will have to be tested and shown to be more efficient in practice, so there's quite some way to go before we even know if Toady hasn't tried it already and whether it actually is more efficient in practice.

A lot of hinges on how the game actually works exactly, which we don't actually know.  It just seemed to me that it would be a simple thing to record certain types of events which would disrupt the areas system, maybe that is not the case. 

[bloop_bleep]

Each df::map_block struct represents a 16x16x1 area, and contains a ‘walkable’ data member which is a 16x16 array of unsigned ints (uint16_ts, I think?) that represents subregions within that area (i.e., two tiles with the same positive walkable value are connected, whereas ones with a walkable value of zero can’t be walked upon.) So this approach is at least partially implemented, I suppose.

[GoblinCookie]

Each df::map_block struct represents a 16x16x1 area, and contains a ‘walkable’ data member which is a 16x16 array of unsigned ints (uint16_ts, I think?) that represents subregions within that area (i.e., two tiles with the same positive walkable value are connected, whereas ones with a walkable value of zero can’t be walked upon.) So this approach is at least partially implemented, I suppose.

I think this is only used when the map is offloaded.  When the map is loaded they don't use the normal pathfinding system but a more memory hungry one. 

[Putnam]

map_blocks are definitely used when the map is loaded, and determines a lot of stuff; for example, liquids exist exclusively in the map blocks structure iirc