Flow Field Pathfinding

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

by ingve • 2 years ago

165 26 2 years ago

This website has a ton of amazing examples of systems that might be useful in games. Incredibly educational and well-done.

kevindamm• 2 years ago

Ah, redblobgames! I remember their hexagonal coordinate system post from many years ago:

https://www.redblobgames.com/grids/hexagons/

An excellent example of their more interactive posts and great for those interested in hex-grid rendering and navigating.

edit: wow, over 10 years ago and the content has been updated but the look and feel is much as I remember it. This was before reactive systems took over the web, too, so the 'toggle selection here, see updates everywhere' was quite notable for the time.

On the actual topic of the post.. I think flow fields easily get overshadowed by waypoints and other hierarchical approaches. Or, folded into the heuristic function for A*.

amitp5• 2 years ago

Thanks! Yes, I've been making interactive diagrams for a long time. I wrote about my motivation in 2007 [1]. In the early 2000s it was Java applets, and then I switched to Flash applets, and then HTML5 in 2011. That was also around the time I ran out of disk space on my stanford site (they give me 100MB) so I bought a domain name, redblobgames.com. That was also around the time there was enough cross-browser support for me to switch to HTML5. And then in 2014 Bret Victor wrote about "explorable explanations" — that's when I felt like I wasn't alone in wanting this type of thing.

[1] https://simblob.blogspot.com/2007/07/interactive-illustratio...

chainingsolid• 2 years ago

Would just like to thank you for having an interactive site that runs fast on my Pinephone despite its lackluster SOC. Checking the weather ended up giving Mozilla an automated crash report this morning....

Heliosmaster• 2 years ago

That post has sit on my browser bar for.. well over a decade at this point. I've read it once, found it neat and put it there. Never really looked at it again, but i see the favicon every day since years and years. At this point it's part of the furniture. Anyhow, funny how stuff becomes "home" for sometimes the most random reason...

DylanSp• 2 years ago

I was looking at that exact post yesterday - I'm currently working on implementing a board game that uses a hex grid, so it should be very useful, particularly the info on coordinate systems and finding neighbors/distances.

The interactive diagrams are exceptional even by current standards, they must have been mind-blowing a decade ago. They're smooth and lightweight, and very informative without detracting from the rest of the content.

amitp5• 2 years ago

Author here. A surprise seeing this on HN!

The context: I'm writing my own blog software for various reasons [1], including my desire to post less to social media. As much as possible I'm trying to reuse the build system for the rest of the site, including the template. I have worked on and off on this for the past two months and I expect to keep adding features for another month or two. I'm currently adding categories not only for the blog but to the whole site. After that I'll work on archives by month. And I want to import the 21 years of old blog content [2] which is stored on blogger.com, and put it on the new blog, which is just a folder [3] on my existing site.

I'm writing some blog posts to test out the workflow (integrating into emacs, my build script, an internal status page) and also various content types (images, video, source code, figures, links). Each time I post I find some more things to tweak.

This post to HN made me realize that it's not labeled as a blog post. Oops. I guess that's one of the downsides of reusing the exact same template! So another tweak coming…

[1] https://www.redblobgames.com/blog/2024-03-08-new-blog/

[2] https://simblob.blogspot.com/

[3] https://www.redblobgames.com/blog/

djur• 2 years ago

Thank you! Your work really helped fuel my interest in programming, and it's always stood as my exemplar for how to explain a concept efficiently.

munificent• 2 years ago

I'm writing my own blog software for various reasons [1], including my desire to post less to social media. As much as possible I'm trying to reuse the build system for the rest of the site, including the template.

After I finished Crafting Interpreters, I took the build system I wrote for that and wrote a static site generator for my blog using it. It's so much better than what I was using before (Jekyll). The performance is literally 100x faster. It produces exactly the output I want.

I realize "write your own static site generator" isn't the right answer for lots of people, but given how much existing technology you already have for your main site, Amit, I bet it's definitely the right answer for you.

DougMerritt• 2 years ago

Hi there, long time.

I'm a big believer in crafting whatever you personally need, whether interpreters or generators.

amitp5• 2 years ago

That's great to hear! Thanks!

dirkt• 2 years ago

In the early days of the World Wide Web I wrote a static site generator using makefiles. Because there was nothing ready-made for that.

As "make" is intended to track changes and only update when dependencies have changed, it was very fast on the computers at that time (that we'd call slow now).

karussell• 2 years ago

minor typo: Dijsktra maps should be Dijkstra maps

Doxin• 2 years ago

It's from the word dijk and the suffix -stra, meaning roughly "In the neighborhood of a dike"

One can only presume his forebears in the Napoleonic era lived near a dike.

adanto6840• 2 years ago

Love it. SimAirport makes extensive use of flow fields -- they're one of the numerous different pathfinding/following systems we use in the game -- but a very important one as they obviously can scale extremely well with agent count.

In SimAirport they're used in a hierarchical way, primarily & specifically for "one level" of the game's overall hierarchical pathfinding systems (longer-distance paths), and they're critical to the game's ability to handle lots of agents.

Always love seeing your content here, Amit! :)

zamalek• 2 years ago

Whats really awesome about distance maps is that you can add/subtract in subsequent passes to make units avoid (but not be blocked by) or favor routes. E.g. you might add near player towers and subtract near resources.

forrestthewoods2• 2 years ago

Planetary Annihilation used voxel flow fields. I spent a LOT of time helping ship that system.

I feel like by the time the Titans expansion shipped it was a pretty good system. I occasionally see comments complaining about pathfinding being bad, but I’ve never seen specifics.

Seeing a mass of tanks stream into a stargate teleporter will never not be cool.

swaginator• 2 years ago

PA's pathfinding inspired me to write my own flow field pathfinding library in Unity. That was my first "big boy" programming project.

I also really liked your writeup on the Chrono Cam system that PA used. Just know if you ever decide to do another writeup on the tech of PA there will be one person that will eagerly read it :)

forrestthewoods2• 2 years ago

Ha. Sadly I no longer have access to PA source. A pathfinding post would be cool though. Unfortunately I’ve totally forgotten all the details!

punnerud• 2 years ago

Could this also be used within neural networks?

porphyra• 2 years ago

When you can go in any direction and not just constrained to up down left right, you'd want the fast marching method [1].

[1] https://en.wikipedia.org/wiki/Fast_marching_method

amitp5• 2 years ago

Thanks! I'll add a note about that.

mikhmha• 2 years ago

I'm using flow field pathing in the MMO game I'm making. It was surprisingly easy and intuitive to implement! And you can have huge gains if you cache paths to target cells and re-use them across different agents. Its kind of crazy how just a few lines of code can change your implementation from flow-field to A* to Dijkstra, or whatever. I think implementing these algorithms is a fun exercise in recursion it forces you to enter a different head space. Also some crazy overlap with other AI systems, as things like A* are used for goal planning. So its worth to learn all this stuff if you want to program game AI.

The backend of my game is written in Elixir. And the world grid used for path-finding is represented as a global shared ETS table (distributed data store) with 1 writer (world server) + multiple readers (ai unit controllers). It works so well, and I can even have sub processes that evict cached paths when dynamic "obstructions" like resources spawn into the world. The ETS table structure also can partition cells/grids/paths by "level/map" and server instance. And you can profile it in real-time and see how much memory the ETS table is using, time-to-pathfind, and other metrics.

netbioserror• 2 years ago

I remember when Supreme Commander 2 adopted flow field pathfinding. Even as someone who like SupCom1, I quite liked the game (it wasn't such an insane time sink or system hog). The pathfinding was part of the optimizations they made; it ended up that thousands of units could be onscreen in SupCom2 and not see the sorts of bottlenecking seen in the dual-threaded SupCom1. They also did some brilliant effects work, it ended up being a beautiful game.

Total shame that it got trashed for being a sequel, instead of the spiritual successor it probably should've been. In terms of "time to legions of giant robots slinging world-destroying explosives", SupCom2 takes the cake. It's an incredible beer-and-pretzels game.

scoopr• 2 years ago

The first I learned about flow field pathfinding, was when then colleague implemented it for a j2me game he was developing, called Turbo Camels[0].

I was quite young then (just joined my first "real job"), and was very impressed by the elegance of the solution, as it made the AI players always find the goal in the game, even when you are bouncing around. Even with the limitations of the time, almost 20 years ago! (64kb JAR files including all the game and resources, crappy java implementations on crappy phones, etc.)

I think I've heard of similar method used to emulate fluid dynamics, when full on simulation is a total overkill.

[0] https://www.youtube.com/watch?v=26dXgqPwupI

Flow Field Pathfinding

Related Stories