That sounds like an issue (and a big issue at that) with the API your engine is providing to you, rather than an issue inherent in A*! Building/rebuilding a nav

That sounds like an issue (and a big issue at that) with the API your engine is providing to you, rather than an issue inherent in A*! Building/rebuilding a navmesh is the expensive bit, cell look-ups ought to be essentially 'free', performance-wise. In an engine like Unity a physics raycast is a super expensive call to make, so if that's also the case for your situation then that's a real shame, I hope you can work around that. If I'm doing regular "were are other objects relative to an object" I much prefer an ordered-spatially data structure like a quadtree, but doing a quick hash of the position and sticking it in a key based store works fine too. Again, that's one of those data structures that is expensive to build and cheap to query, so only building it once every x frames is probably a good idea. But again, not sure what your API is giving to you and how low level you get to work.