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?

  • \$\begingroup\$ Check out this abstract, for a more detailed summary of research into this question:mit.edu/~jnt/dijkstra.html. The Fast Marching techniques for solving the Eikonal Equation are in fact based on Dijkstra-like techniques. \$\endgroup\$ Jun 14, 2015 at 19:06

1 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.

  • \$\begingroup\$ What is the advantage or different property of a vector field obtained through solving the Eikonal equation vs obtaining it with Dijkstra? I guess that's what the crux of my question is. \$\endgroup\$
    – Asik
    Jun 16, 2015 at 18:48
  • \$\begingroup\$ @Asik: A solution is a solution; though performance differences as noted above exist. Do you want a simpler implementation for small grids or a fast one for large grids, or a bit of both? \$\endgroup\$ Jun 16, 2015 at 22:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .