3 ms·

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*

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_Subgoal_Graphs_for_Fast_Optimal_Pathfinding.pdf https://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter15_Su... [1] https://www.redblobgames.com/pathfinding/heuristics/differential.html https://www.redblobgames.com/pathfinding/heuristics/differen... [2] https://web.archive.org/web/20190717211246/http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/ https://web.archive.org/web/20190717211246/http://aigamedev.... [3] https://theory.stanford.edu/~amitp/GameProgramming/ https://theory.stanford.edu/~amitp/GameProgramming/

dietr1ch 1y 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.