Yes, was just about to post, "Exact Routing in Large Road Networks Using Contraction Hierarchies" which, after a one-time pre-processing step returns an optimal route on a continent-scale network in milliseconds.

http://dl.acm.org/citation.cfm?id=2351896

What's the memory usage there? Is it on the order of what can be used for games? Often memory is even more constrained than CPU time

Hannah Bast knows a lot about route planning. Here is one of her courses containing some important ideas:

https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...

Use Floyd Warshall if you can pre-compute.

It pre-computes all the paths from all nodes to all nodes, and it's incredibly efficient.

Most awesome algorithm ever :D

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorit...

And if you need dynamic graph with variable weighting and nodes, that's a case for D*

Mostly used for drone/rover/robot navigation in open environments, with the graphs evolving as the robot discover the environment.

https://en.wikipedia.org/wiki/D*

Only if the area changing is near the start of the search, not near the goal. (i.e. near the sensors of a mobile robot, rather than near the destination far from the robot).

D* can be pathologically slower than repeated A* searches under such conditions.

I've been using a modified D*. It increases the grid size as the path moves out of the robot's observable area. This allows a fast search even when the goal is in a environment with known dynamic obstacles.

Ideally speaking, you need to plan in higher dimensions to get an optimal path in dynamic environments

Pearl, J. (1984), Heuristics, Addison-Wesley. In this text, Pearl proves that for a given heuristic, A* will perform computations on fewer (or the same number of) nodes than any other graph algorithm using the same heuristic.

The pre-computation JPS(+) does is cheating because it's essentially providing a quicker-to-evaluate heuristic than A* gets to use.

So yes, I agree - the title is misleading! However, it's still a pretty cool efficiency for situations where it's applicable.

It's misleading indeed. This version of JPS+ is basically a preprocessing optimization - does graph compacting offline to compute a smaller representation that's faster to run guided search on.

And of course there's a serious down-side: if the graph changes at runtime (eg. player builds a new door, or blows away a bridge) the preprocessing has to be redone, and it's not cheap.

Oh man, Baldur's Gate pathing was abysmal, and not just because of moving obstacles (including the 6 members of your party interfering with each other while all moving greedily-not in formation-to the same general area).

With respect to the techniques that require precomputation, however, I wonder how they perform with such moving obstacles. Potentially quite terribly, I imagine.

A technique that is reportedly useful for dynamic situations is D*, since 90% of the world is static and most dynamic content is clustered, you could probably get away with using that in a radius and then devolve to the precomputed technique outside of that