There are lots of variants of A* that depend on what you can assume about your graph, whether you can preprocess, how often the graph changes, etc. Contraction

There are lots of variants of A* that depend on what you can assume about your graph, whether you can preprocess, how often the graph changes, etc. Contraction hierarchies, subgoals, bidirectional A*, hierarchical search, all-pairs compression, moving obstacles, group movement, coordinated movement, landmarks, labeling algorithms, transit nodes, arc flags, cluster distances, vertex separators, reach, highway hiearchies, etc. Differential heuristics are my favorite for "bang for the buck", as they are fairly low effort (maybe <20 lines of code) for good speedup (3-5X on my game map tests [1]). There's lots of research papers out there, especially for road maps. I tried keeping track of them all and gave up :-( But you might find these two papers useful: * https://arxiv.org/pdf/1504.05140.pdf https://arxiv.org/pdf/1504.05140.pdf * https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.pdf https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.p... [1] https://www.redblobgames.com/pathfinding/heuristics/differential.html https://www.redblobgames.com/pathfinding/heuristics/differen...