Flow field pathfinding

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.

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.

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:

Leave a Comment