I don't know if Kim Salo reads the BBS much now, but it would be interesting to find out what algorithm he uses. His empeg nav software does routing (including one-ways etc) and I seem to recall it already does real time rerouting if you take a wrong turn.

I'm using A*, which is one of the most commonly used algorithms for path finding. The accuracy and complexity of the algorithm can be controlled with the heuristic function.

However, the biggest design step is to make it memory friendly. In my implementation, I have five different buffers for the path finding which I can freely scale up or down, depending how much memory I want to spend vs. how fast it will be. In other words, what doesn't fit into memory will be swapped to the disk, but in a smart and efficient way.

Kim