https://www.redblobgames.com/blog/2024-04-27-flow-field-pathfinding/

Flow field pathfinding

 from Red Blob Games's Blog

  * Home
  * Blog
  * Links
  * Twitter
  * About
  *  
  * [        ]


27 Apr 2024

You may know me for my interactive tutorials. But before that, I was
writing visual but non-interactive tutorials. In particular, there
wasn't a lot of information about A* on the web, so I decided to
collect all my notes about pathfinding^[1] together in one place in
the 1990s. But then in the 2010s I started making interactive pages.
The newer pages are narrower in scope; I covered a broader set of
topics on the older pages. I maintain both sets now.

Over the years people have asked me about "flow field pathfinding". I
felt like the early papers about it conflated the flow fields with
hierarchical pathfinding, but I wasn't sure, and I didn't want to
write about it until I was sure.

[flow-field]Flow field

But it's been many years now and I would like to write something even
if it's not complete. My understanding so far is:

 1. flow fields are a vector field that tells agents from any
    location what direction to move to find a single destination
 2. optionally, agents that are in between locations on the
    pathfinding graph can interpolate between the vectors in the flow
    field
 3. optionally, a hierarchy of coarse and fine stepped fields can
    speed up pathfinding

In addition, there are distance fields which are themselves
interesting for things like "Dijsktra maps^[2]" in roguelike games
and "influence maps^[3]" in strategy games. Distance fields can also
be used for 3d modeling^[4] and font rendering. The flow fields and
distance fields are related: in vector calculus, the gradient ([?]) of
the distance field produces the flow field.

[distance-f]Distance field

The graph-based pathfinding algorithms I cover on my A* page^[5]
output both distance fields and flow fields, in the cost_so_far and
came_from outputs. I updated my pages to mention both flow and
distance fields:

  * I added a new section to my older pathfinding notes^[6].
  * I updated my tower defense pathfinding page^[7].

Although I mention hierarchical pathfinding^[8] in these notes, I
don't cover it in detail. Maybe I will do so one day, but I don't
have to wait until then before publish the pages. That's one of the
advantages of web pages over textbooks or academic papers. I can
update my pages as I learn more. I still update my pathfinding pages
that I started in 1997, and I still update my interactive pathfinding
pages that I started in 2014.

Email me redblobgames@gmail.com, or tweet @redblobgames, or comment:

Endnotes

 1. [1]: http://theory.stanford.edu/~amitp/GameProgramming/
 2. [2]: https://www.roguebasin.com/index.php/
    Dijkstra_Maps_Visualized
 3. [3]: https://www.gamedev.net/tutorials/programming/
    artificial-intelligence/
    the-core-mechanics-of-influence-mapping-r2799/
 4. [4]: https://iquilezles.org/articles/distfunctions/
 5. [5]: https://www.redblobgames.com/pathfinding/a-star/
    introduction.html
 6. [6]: https://theory.stanford.edu/~amitp/GameProgramming/
    Variations.html#flow-fields
 7. [7]: https://www.redblobgames.com/pathfinding/tower-defense/
 8. [8]: https://theory.stanford.edu/~amitp/GameProgramming/
    MapRepresentations.html#hierarchical

Load comments
View the discussion thread.

Copyright (c) 2024 Red Blob Games
RSS Feed
 Created 27 Apr 2024;  Last modified: 27 Apr 2024