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! :)
tavianator · 1h ago
You may want to look into improvements to A* for grids, like Rectangular Symmetry Reduction.
johnh-hn · 1h ago
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?
malux85 · 1h ago
Great particle effects! Wishlisted and waiting!
chrisdalke · 5h ago
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.
porphyra · 42s ago
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.
johnh-hn · 1h ago
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/
wduquette · 5h ago
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 · 2h ago
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.
munificent · 2h ago
"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?
Sohcahtoa82 · 3h ago
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?
munificent · 2h ago
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 · 2h ago
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_ · 1h ago
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 · 10m ago
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.
paulddraper · 3h ago
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.
dgb23 · 4h ago
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.
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 · 4h ago
WC1 has fairly blocky movement and is grid based. It seems like units literally move from tile to tile so to speak.
You might want to try adjusting it for diagonal movement and you probably don't want to store obsolete path sections, but only turns.
andrewmcwatters · 5h ago
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 · 4h ago
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 · 3h ago
Yes! Very creative thought. I hadn't tried abstracting the idea to other types of "effort."
ninetyninenine · 6h ago
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.
blt · 4h ago
Sure, but in games sometimes improving the average case is less important than the worst case.
ninetyninenine · 3h ago
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 · 3h ago
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 · 2h ago
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.
inetknght · 6h ago
That's true until the map itself changes, eg other objects moving around in the calculated path
ninetyninenine · 6h ago
Yeah I said that. If nothing moves. No need to change.
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! :)
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.
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/
Like you said, it adds a lot to the fun so I'm only trying to smooth out those cases that look stupid.
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?
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?
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.
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.
And if you were performance conscious, you certainly would not do lots of pathfinding from scratch on every frame.
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.
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!
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.
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.