The next big advance after A* is something called [contraction hierarchies](https://en.m.wikipedia.org/wiki/Contraction_hierarchies)

I’d love to see a “part 2” of this resource or similar that explains those in this kind of Laymans terms. There were some white papers but then I suspect the big tech companies started to guard this research a little more closely once its potential to give a commercial edge became apparent.

See also Time-Dependent Contraction Hierarchies (2008) [pdf] https://algo2.iti.kit.edu/documents/routeplanning/tch_alenex...

Oh the fun of cobbling heuristic algorithms to work in the real-world where precise algorithms are big-O too slow.

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://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.p...

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

Those seem a little outdated, there has been a ton of work since then :) A bit more updated reference is https://arxiv.org/pdf/1504.05140.pdf, and http://www.sommer.jp/spq-survey.pdf is great!

There are also Prof. Hannah Bast's lectures (https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...) and her talk at ICAPS (https://www.youtube.com/watch?v=B3wKfJAVRkg), both excellent :)