Pathfinding Eikonal vs Grass Fire Algorithm

This topic is 510 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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 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:

Quote

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

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633705
• Total Posts
3013463
×