6
\$\begingroup\$

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?

\$\endgroup\$
  • \$\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\$ – Pieter Geerkens Jun 14 '15 at 19:06
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\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 '15 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\$ – Pieter Geerkens Jun 16 '15 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.