[HN Gopher] Pathfinding
___________________________________________________________________
Pathfinding
Author : sebg
Score : 103 points
Date : 2025-05-15 12:32 UTC (10 hours ago)
(HTM) web link (juhrjuhr.itch.io)
(TXT) w3m dump (juhrjuhr.itch.io)
| ninetyninenine wrote:
| One efficiency update you can make is that if background objects
| don't move, then you don't need to recalculate the path. So check
| if anything moved before recalculating.
| inetknght wrote:
| That's true until the map itself changes, eg other objects
| moving around in the calculated path
| ninetyninenine wrote:
| Yeah I said that. If nothing moves. No need to change.
| blt wrote:
| Sure, but in games sometimes improving the average case is less
| important than the worst case.
| ninetyninenine wrote:
| So you're saying everything always moves all the time so it's
| more efficient to just never check and have the algorithm
| assume something moved always.
| Maxatar wrote:
| For most real time systems, including many games, it
| doesn't matter if one is more efficient than another
| because what matters is the predictability that comes from
| always rendering a complete frame in 1/60th of a second.
|
| In many cases checking if absolutely nothing changed in a
| system isn't trivial either. You either have very fine
| grained tracking which involves a great deal of complexity
| and increased memory cost, or very broad tracking which
| results in a lot of false positives.
| stonemetal12 wrote:
| No, if it takes 1 ms to check if things have moved, and 5
| ms to do the pathfinding then the worst case is 6ms when
| something moves. A guarantied 5 makes for a more stable
| frame rate than a sometimes 1ms, sometimes 6ms calculation.
| Often times 60 FPS average with high variability feels
| worse than 30 FPS with low variability.
| chrisdalke wrote:
| Writing path planning code is one of the most enjoyable
| programming tasks. Love the visualizations.
|
| The path following code is also interesting because I bet you'll
| run into some corner cases where the A* path thinks a path is
| feasible, but the vehicle overshoots and hits something. Although
| in a game I guess that adds to the fun & chaos.
| wduquette wrote:
| Re: visualizations, yeah, it's really easy to caught up in
| playing with the algorithm just to watch it run rather than
| using it in your project. Been there, did that. For two
| distinct projects.
| juhrjuhr wrote:
| This definitely happens! Mostly it's from the NPC taking a
| corner a little too quickly when there's obstacles around. I've
| added data to the resulting path so that the NPC can know how
| far each path step is from an obstacle so that it can slow
| itself down first.
|
| Like you said, it adds a lot to the fun so I'm only trying to
| smooth out those cases that look stupid.
| johnh-hn wrote:
| Indeed. There is something satisfying about building these and
| watching them in full flow.
|
| A couple of years ago, I completed a pathfinding assignment
| designed by David Churchill
| (https://www.cs.mun.ca/~dchurchill/) for his Algorithmic
| Techniques for AI course. I'm not a student, and only his
| students have access to the actual assignment files, so I made
| a faithful recreation of it by looking at slides he had on a
| video at the time. The assignment is about pathfinding on a 2D
| grid. That's fun enough, but I've wanted to put my own spin on
| it.
|
| Over the past few weeks, I revisited this and applied it to
| real-world mapping data from OpenStreetMap instead. It uses
| OverPass API (https://dev.overpass-api.de/) to fetch the data,
| which is free to use. The data loading times can be a little
| unpredictable, especially for larger search areas, but I'm
| happy with it how it turned out. You can find it here if you're
| interested: https://johnh.co/projects/openstreetmap-
| pathfinding/
| porphyra wrote:
| You might be able to add velocity information when doing the A*
| search, as well as use minkowski sum to make sure that it never
| tries to squeeze through too tiny a gap.
| jvanderbot wrote:
| Take it from an old hand: you want to add a tad of circular
| margin to your obstacles via minkowski sum.
| andrewmcwatters wrote:
| I remember fondly messing around with some pathfinding with some
| friends in my 20s and adding random amounts of cost to nearby
| nodes. This has the distinct effect of making NPCs meander
| around, or follow a "drunken path."
| dgb23 wrote:
| I like this idea. One could imagine certain types to skew the
| costs for interesting reasons. Small animals might want to move
| in a sort of scanning, zig-zag way for example.
| andrewmcwatters wrote:
| Yes! Very creative thought. I hadn't tried abstracting the
| idea to other types of "effort."
| 90s_dev wrote:
| See also
| https://www.redblobgames.com/pathfinding/a-star/introduction...
|
| One of the first games I ever played was Warcraft I, and it was
| one of the games I always wanted to make but never could. One of
| the missing pieces of the puzzle was path finding. I still don't
| understand it, but at least now I have two resources that I can
| read when I'm done building my game maker and ready to make my
| game!
| dgb23 wrote:
| WC1 has fairly blocky movement and is grid based. It seems like
| units literally move from tile to tile so to speak.
|
| If this is actually the case, you could try the Lee algorithm:
| https://en.wikipedia.org/wiki/Lee_algorithm. It's extremely
| simple and effective.
|
| You might want to try adjusting it for diagonal movement and
| you probably don't want to store obsolete path sections, but
| only turns.
| dgb23 wrote:
| Neat article!
|
| This will depend on the type of game or application, but one
| thing I've been doing is to do the more rigorous pathfinding when
| the environment (collision map) changes in order to generate a
| sort of precomputed pathfinding map (grid, or graph). When I
| search a path, or route for an entity, then it's on that
| pathfinding map.
|
| Again, it depends on how that simulation fundamentally works.
| Some have natural POIs, crossroads and corners that one can work
| with. Others might need some heuristics to determine those or
| merge together paths. It might also be worth trying to use a very
| coarse logic for gross movement but adjust the actual path moment
| to moment, but that's just an idea that I never tried.
|
| The approach in the article is of course very dynamic, which has
| the advantage of being excellent at trying stuff out and
| visualizing it.
|
| I personally never tried out the space partitioning mentioned in
| the article and don't understand it fully. But there might be
| strong similarities to what I described above.
| Sharlin wrote:
| What you refer to is commonly called a navigation mesh:
| https://en.wikipedia.org/wiki/Navigation_mesh
| dgb23 wrote:
| Conceptually yes, thanks! But it seems like my implementation
| is more basic than that. I'm only using the graph part so to
| speak, because of other constraints.
| Sohcahtoa82 wrote:
| I'm surprised it takes several milliseconds to find a path.
|
| We've been using A* to find paths in games for over 20 years now.
| We did it on CPUs with speeds measured in Mhz. Higher clocks and
| architecture improvements mean we're a couple orders of magnitude
| faster. How is it that it takes so long to operate on modern
| hardware?
| paulddraper wrote:
| I'm guessing it might be multiple paths for multiple NPCs. But
| not sure.
|
| And if you were performance conscious, you certainly would not
| do lots of pathfinding from scratch on every frame.
| munificent wrote:
| Games typically precomputed much of the pathfinding information
| and assumed a non-destructible world. The whole thing in the
| article about recomputing the blocked/non-blocked state is a
| thing many games with pathfinding simply didn't do at runtime
| at all.
|
| They usually pathfinding on a larger granularity with more of
| the world aligned to a larger grid. Since asteroids are so
| organically shaped and freely movable in this case, it
| necessitates a finer pathfinding grid. It looks like they're
| roughly 6-8 pixels here. In an older game, it could easily be
| 16 or more. Pathfinding cost scales quadratically as the grid
| gets finer.
|
| Also, while CPU speeds have increased, RAM access rates have
| not kept up. It's quite hard to actually keep the CPU busy and
| not have it stalled waiting for memory very often. "Data-
| oriented design" is a whole little subfield dedicated to
| dealing with this problem.
| juhrjuhr wrote:
| Hey, I'm the developer of the game in the blog post. What takes
| several milliseconds is the number of world queries that need
| to be made to detect blocking objects and also object
| proximity. This is why I went with a quad tree to try to speed
| that part of things up.
|
| Once those queries have been made the actual search is very
| fast. The problem then is that those queries need to be made
| again due to the dynamic nature of the game world.
| stefan_ wrote:
| You probably realized its absurd to have 50000 square nodes in
| your pathfinding graph and instead divided the area into 50
| convex polygons (if that). Convex polygons being the basic
| shape because you can go directly from every point within to
| every other point within.
| porphyra wrote:
| Yeah generally you'd use a visibility graph/navmesh. I don't
| know why people keep trying to do path finding on a dense
| grid --- even with quadtree-based space partitioning, you
| might still end up with a complexity dependent on how far
| apart things are, rather than how many things there are.
| munificent wrote:
| "This kind of efficiency problem is something that looks ripe for
| multi-threading, but the main problem I had here is that all the
| world state of the game is held on the main thread and in
| complicated structures"
|
| Crazy idea but I wonder if it would be worth it to have the
| pathfinding thread simply have its entire own copy of the mutable
| world state. Then when anything changes the world, both copies
| are updated roughly in parallel.
|
| It would be a ton of duplicate work, but if you're on a machine
| with cores sitting there doing nothing... why not?
| juhrjuhr wrote:
| Hello!
|
| I'm the developer of this game. Thanks very much for your
| interest and discussion here :)
|
| I'm starting to feel like I didn't go into enough detail with my
| post, since there's a lot I could talk about and also a lot I
| could benchmark to give you some actual numbers on performance.
| But maybe I'll leave that for a different post in the future.
|
| The game I'm developing is a commercial project, so it would be
| silly to be on the front page of HN and not try to direct people
| towards the commercial side of things. Here is the link to the
| game's steam page, you can wishlist and maybe buy the game when
| it's released so I can afford living expenses and expensive
| coffee beans:
| https://store.steampowered.com/app/3656660/Deep_Space_Exploi...
|
| Thank you! :)
| malux85 wrote:
| Great particle effects! Wishlisted and waiting!
| tavianator wrote:
| You may want to look into improvements to A* for grids, like
| Rectangular Symmetry Reduction.
| taneq wrote:
| Also jump point search: https://zerowidth.com/2013/a-visual-
| explanation-of-jump-poin...
| johnh-hn wrote:
| This is a cool concept. How long have you been working on it?
| And do you have a rough idea of when you'll release it?
| juhrjuhr wrote:
| Thank you! At the moment, about 7 months (I originally
| thought it would take 4-6 months haha). I'm really hoping to
| release it in the next couple of months, but my ability to
| estimate these things is obviously lacking.
| johnh-hn wrote:
| You're being consistent and that's the most important
| thing. I hope we see it again here once it's complete. Good
| luck!
___________________________________________________________________
(page generated 2025-05-15 23:00 UTC)