Jump to content
  • Advertisement

Pathfinding Eikonal vs Grass Fire Algorithm

Recommended Posts

Hi, I was reading Game AI Pro how they implemented Supreme Commander path finding and came to one question.

For the integration of cost field they are using Eikonal equation for traversing the areas.
They recommended Fast Iterative Method and it's parallel version for solving this equation.
However in all basic tutorials of flow field navigation that I found  for integrating of the cost field is used simple grass/brush fire algorithm.

My question is what would be the difference if they used in the game just grass fire algorithm?

I guess the reason was some quality/performance trade of.
Fortunately the Fast Iterative Method is very easy to implement so I can compare the performance, but what I don't understand is, what is the "quality" benefit.

Edited by gamer9xxx

Share this post

Link to post
Share on other sites
On 15/7/2017 at 0:10 PM, gamer9xxx said:

For the integration of cost field they are using Eikonal equation for traversing the areas.

No, the eikonal equation defines what is a shortest path. "Traversing the areas" is what algorithms that compute solutions of the eikonal equation, i.e. shortest paths, need to do somehow.  In the case of chapter 23 of Game AI Pro:


We are now ready for cost field integration. As with the LOS pass, we start with the active
wave front list. This active wave front comes from the list of “Wave Front Blocked” loca-
tions from the previous LOS pass. In this way we only integrate locations that are not
visible from the goal.
We integrate this wave front out until it stops moving by hitting a wall or a sector
border. At each grid location we compute the integrated cost by adding the cheapest cost
field and integrated cost field’s up, down, left, or right neighbors together. Then repeat this
Eikonal equation process again and again, moving the wave front outward toward each
location’s un-integrated, non-walled neighbors.

Maintaining a list of active wavefront cells looks definitely like a "brushfire" algorithm.

Are you confusing this basic building block of multiple source/single destination grid-based pathfinding with the full pathfinding solution described in the book (tile-based architecture, portals, caching, LOS special case, specific flags and data structures, etc.)?

Share this post

Link to post
Share on other sites

Hi, thx for the explanation, yes it was just a confusion what eikonal equation is, since they added the whitepaper that describes how to solve it with the Fast Iterative Method, but apparently they didn't use it at all, but what they wrote in your quoted part, it's simple "brushfire" alg.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!