7
« on: September 30, 2008, 09:54:05 am »
Has Toady ever said that he's using A* for pathfinding? I've heard him mention that his pathfinding could use some more optimization, but never any mention of the exact algorithm.
Assuming that Dwarf Fortress uses A* or something similar, it's not necessarily a big performance hit to create large open areas. If that were the case then you'd expect to see huge framerate problems on almost all above-ground fortresses. The A* algorithm does not consider every possible route to the destination unless it has to. In fact, by open areas you actually reduce the number of iterations that A* must perform before finding the optimal path.
The thing that will really kill your pathfinding performance is having a bottleneck (door, stair, etc...) between two points in an unexpected location. For example, consider a dwarf who wants to go to the dining room. The dining room is west of his position and two levels up. The A* algorithm will try to "guess" the best route to the dining room by assuming that he needs to go west.
But what if the staircase is actually east? That can slow down the pathfinding in a big way, since it won't even try going east until it has exhausted most of the possibilities on the west side. Centralized staircases, despite their popularity, are a good example of how to drive the A* algorithm nuts. Fortunately most forts which use centralized staircases tend to use only a small area on each level.
Note that if Dwarf Fortress does NOT use A* then all of the above is moot, and open areas may indeed cause pathfinding lag.