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.
Like you said, it adds a lot to the fun so I'm only trying to smooth out those cases that look stupid.
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/
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.
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.
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?
And if you were performance conscious, you certainly would not do lots of pathfinding from scratch on every frame.
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.
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?
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! :)
ninetyninenine•5h ago
inetknght•5h ago
ninetyninenine•5h ago
blt•3h ago
ninetyninenine•2h ago
Maxatar•2h ago
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•1h ago