[Mauzen]

@pamdex: Are you still working on this?

I experimented a bit with this. Using a buffered mapandreas mode instead of the nobuffer one at least doubles the speed (tested on a ssd). For slower HDDs the effect is even greater.
I also experimented with a pretty new in science A* subtype and managed to get speeds 4-5 times faster than with the standard one using buffered mode, so a 10x speed boost is realistic. Had some problems with the algorithm though, it is not suitable for release.