pton_xd 1 day ago

Nice! There's a few techniques that I remember when doing something similar. Subgoal graphs [0], using precalculated landmarks in the heuristic [1], and theta* [2] may be worth looking into. A bunch of other variations and techniques are on the Red Blob Games site [3]. Also the priority queue implementation you use can really impact performance if it's not done well.

[0] https://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter15_Su...

[1] https://www.redblobgames.com/pathfinding/heuristics/differen...

[2] https://web.archive.org/web/20190717211246/http://aigamedev....

[3] https://theory.stanford.edu/~amitp/GameProgramming/

1
dietr1ch 1 day ago

True, but mind the search space size.

You can go through 50-80k search nodes in 10ms in a modern CPU, so even using Dijkstra seems feasible on a decent implementation as the grid used in the animations seems to have 100x80 nodes.

If I was making a game I'd focus on gameplay first, since giving the game some life by conditioning the paths seems more important to have a good game than achieving 200μs search times. Luckily, I'm not making a game :P, my current side-project is writing my own pathfinding playground to explore optimisation techniques and tools.