Hacker News Reader

Comment by DizzyDoo | Hacker News Reader

I'm a bit confused by your comment, when you say that "testing if a cell is blocked has a sensing cost", do you mean the obstacle/wall is not in your graph at the point of search? A properly calculated navmesh by definition has the obstacle/wall 'cut out' of the mesh (or otherwise represented in a modifier area). Perhaps I've misunderstood you but it sounds like you're trying to build, at least partially, the navmesh as you search?

If you're rather talking about temporary obstacles like other nav agents that need to be avoided, there are a number of approaches to agent avoidance that work nicely on a subset of a navgraph.

View on HN

sounds like you're trying to build, at least partially, the navmesh as you search?

Yes. I'm coding non-player characters, using an API which lets them sense their surroundings by ray-casting but does not give them direct access to the system's world model. They're limited in what they can sense.

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.

I could go into more detail, but it would be off topic and lengthy. If you really are interested, see [1]

[1] https://github.com/John-Nagle/lslutils/blob/master/npc/READM...

I was genuinely interested, and, wow. It's been 15 years since I've tried Second Life but I'm not terribly surprised the scripting/modding looks like this, and all your comments about the exposed API make sense now.

Reply on news.ycombinator.com