Pathfinding to a moving target in evolving terrain
holm.dog73 points by friendshaver 6 months ago
73 points by friendshaver 6 months ago
Pathfinding is a profoundly interesting problem. I think it is very impressive that Starcraft II still has amazing lag-free pathfinding that beats or matches basically every game out there, including very recent RTS games like Stormgate and Zerospace that have a specific emphasis on smooth mechanics for competitive play. Like you can build all kinds of buildings and a zillion zerglings will instantly go around them.
I wonder if there are any constraints on the buildings etc that make this easier.
The way I remember it: A* can find shortest path between any two given points; Djikstras can precompute the shortest path between a single point and all other points; And Floyd-Warshall can precompute the shortest path between all possible pairs of points.
The author starts with Djikstras and updates the precomputed path-map every frame that either the players location changes or an obstacle is added.
Maybe some more performance can be squeezed out. If the player's location changes more frequently than obstacles are added, it may be worthwhile to precompute the all-pairs-shortest-path (floyd-warshall) which would instead only need to be updated on obstacle additions. The precomputed path map would no longer need to be updated on player location changes.
A similar trick can probably be used to efficiently update the precomputed APSP path-map in these cases, since only a single obstacle is added at a time.
Though if obstacles are added fairly frequently relative to player location changes, this is probably not worthwhile.
Couldn’t you just do a breadth first flood fill from the player every time the environment changes? Would be O(n) where n is total number of cells, which would be fast on any hardware or in the browser.
You’d still want to use the directional chart idea.
Or when player moves. But this is also something that came to my mind. They acknowledge this in a footnote:
[3] The approach I ended up using is very similar to a Dijkstra map, a pathfinding tool from roguelike games, which I discovered as I was writing this. As far as I could tell, my approach extends a Dijkstra map to handle minimal updates as the target moves and obstacles update
Can’t you just use web workers to offload A* path finding to a separate thread and expose results to the main thread through shared array buffers?
>just use web workers to offload A* ... shared buffers
That's a huge overkill. A single dijkstra per game tick (or even only when map changes or player moves) is enough.