11–20 of 48 posts
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.
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."
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?
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.
Sure, but in games sometimes improving the average case is less important than the worst case.
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 P…
Earlier quoted context omitted.
Sure, but in games sometimes improving the average case is less important than the worst case.
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.
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.
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?
And if you were performance conscious, you certainly would not do lots of pathfinding from scratch on every frame.
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."
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.
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 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?
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.