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
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:
flow fields are a vector field that tells agents from any location what direction to move to find a single destinationoptionally, agents that are in between locations on the pathfinding graph can interpolate between the vectors in the flow fieldoptionally, 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 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.
>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Hacker News – https://www.redblobgames.com/blog/2024-04-27-flow-field-pathfinding/
