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