[HN Gopher] Flow Field Pathfinding
___________________________________________________________________
Flow Field Pathfinding
Author : ingve
Score : 142 points
Date : 2024-04-28 09:48 UTC (13 hours ago)
(HTM) web link (www.redblobgames.com)
(TXT) w3m dump (www.redblobgames.com)
| Waterluvian wrote:
| This website has a ton of amazing examples of systems that might
| be useful in games. Incredibly educational and well-done.
| kevindamm wrote:
| 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*.
| amitp wrote:
| 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 wrote:
| 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 wrote:
| 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...
| amitp wrote:
| 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 wrote:
| 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 wrote:
| _> 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.
| adanto6840 wrote:
| 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 wrote:
| 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.
| forrestthewoods wrote:
| 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 wrote:
| 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 :)
| forrestthewoods wrote:
| 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 wrote:
| Could this also be used within neural networks?
| porphyra wrote:
| 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
| mikhmha wrote:
| 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 wrote:
| 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.
___________________________________________________________________
(page generated 2024-04-28 23:00 UTC)