What is the difference between Djikstra and flow fields?

Question

I understand flow field pathfinding (as illustrated in recent Gas Powered Games titles) consists of 1) computing a vector field covering the map for a given destination, 2) deriving unit directions from their position on that field, and 3) recomputing it at each frame to take dynamic obstacles into account.

I was wondering if the very same steps could be used, but by computing the vector field simply with Dijkstra. After all, if you apply Dijkstra in reverse (from the destination), and continue until you've covered the whole map, you end up with a vector field giving the best direction for each unit trying to get to that destination. If you recompute it each frame, don't you end up with the same behavior and efficiency as flow field, only without the math I don't understand?

Answer 1

The Fast Marching method for solving the *Eikonal Equation is in fact based on Dijkstra's algorithm. It has O(N log(N)) performance, which is fine for small grids but can be improved on for larger grids by employing either the Fast Iterative or Fast Sweeping methods.

As noted in your link:

More importantly, the Fast Marching Method uses a binary heap, which means it's not straightforward to parallelize, and has poor cache coherency. The Fast Sweeping Method has the potential to perform better, yet is slowed down by any direction changes that could happen, say, in the case of a winding maze. The Fast Iterative Method is a pretty good compromise between these two, working pretty well in winding mazes, being somewhat amenable to parallelization, and having good cache coherency.

This link contains additional references on use of Dijkstra in solving the Eikonal Equation.

The particular technique most applicable to any particular situation is a meta-decision that the program designer must make, or direct the application itself to make.

In my Hex-Grid game engine I use two separate path-finding algorithms: one for short distances that does not utilize road movement, and employs a tie-breaker heuristic for improved visual aesthetics, but is prohibitively slow for long distances; and a second that uses a much more efficient heuristic and does employ road movement, but is visually unaesthetic. The game engine chooses between the two based on the as-the-crow-flies distance from origin to target.