There is flying pathfinding. There isn't flying connectivity.
A* is the pathfinding algorithm. It's a very efficient algorithm that works for ANY connectivity map. DF uses it for all movement. When flying, it enables creatures to quickly find the shortest distance between two points. Same with swimming. Same with everything.
A* has major advantages over Dijkstra's algorithm, which will also find the shortest distance between two points, but does so by first calculating EVERY path, including paths that go the opposite direction. In an open field, Dijkstra is ASTRONOMICALLY slow. It tests EVERY path. Every combination of paths. Every variation of paths.
A*, in the worst case scenario, is equivalent to Dijkstra's algorithm, which is very slow. One of these worst case scenarios is the case where the two points CANNOT be reached, ever, because they are not connected.
Now, there are two ways to handle this problem. The first is to make it a non-issue. Most games do this. Simply make it so that there is nowhere that is unconnected. The other is to use a different algorithm to calculate connectivity, the "flood-fill" method, which is pretty fast (you use it every time you use the paintbucket in MSPaint) and store what areas are connected in an array, and then when a pathfind request is made, check if it's connected first and THEN use A*. DF does this. It has to, because a cavein, construction, or flow could cut off movement at any time.
But, DF does this ONLY for walking. It makes a connectivity map for every location it is possible to walk to. All pathfinding checks connectivity first, and then uses A* to get to where it's trying to get. ALL pathfinding. There isn't a separate connectivity map for flight, and there isn't a separate map for swimming either.
So if it's possible to walk there, you can fly there (and will fly there via the fastest flight route possible, not the walk route). If you can't walk there, the game can't tell that you can't get there at all.
So, why can't we just test for flight, water-swimming, and magma-swimming? And for combinations thereof? Partly because of memory and diskspace concerns. The connectivity maps have to be stored as part of the map data, and EVERY BIT COUNTS. Consider how many tiles you have in a standard map, particularly one with a lot of Z-levels. Multiply that by the number of bits you need to add. It adds up, rapidly, especially with everything else the game needs to keep track of.
It's probably important enough to do at some point though, and Toady probably will. But my understanding is that it's non-trivial. He's working on other things at the moment. He knows about it though.
Author
Topic: Flying races (Read 826 times)