Jump to content
  • Advertisement
Sign in to follow this  

Generating an AABB-based navmesh

This topic is 2556 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to figure out the best way to generate an AABB-based navmesh (as used in e.g Left For Dead) at runtime.

My world is very simple, just a set of solid AABBs, and my goal is to generate an explicit representation of the empty space around these obstacles as a navmesh where each node is an AABB-shaped region of empty space.

The obstacles are moving each frame. Ideally the solution would be amenable to incremental updating OR just cheap enough to update each frame. There will be hundreds of objects in total; I'm not sure if it's relevant, but the world is partitioned into a set of static rooms so that there are no more than a few dozen obstacles in a given room at once (i.e there may be e.g 10 rooms each filled with 20 objects, rather than 200 objects all in the same room).

The most straightforward approach I could think of was to start with a single empty region which spans the whole world, and then iteratively do:
-find empty regions touching obstacle
-split empty regions by bounding planes of obstacle
-(coalesce/merge regions if possible)

So, the first obstacle would split the initial empty region into 8 empty regions (using the numpad as an example, if the obstacle was 5 then there would be empty AABB-shaped regions at 7/8/9/4/6/1/2/3). This would be repeated until all obstacles had been inserted.

I'm not sure if it makes sense to try to merge per-insert or just wait until all obstacles are inserted and then merge. Also I have no idea how this merging process would even work -- probably it would have to be incremental, possibly in the form of a sweep along x and then along y?

Anyway, this "solution" seems like a non-starter -- it's way too complex and slow (in order to answer "find empty regions touching obstacle" I would need e.g a grid or similar spatial database), especially since it can generate tons of tiny/sliver nodes which then need to be merged.

Another idea would be to discretize the world into a grid; using a bitmap as a metaphor, start with a white bitmap and then for each obstacle blit a black rectangle into the bitmap. Then, we could generate a navmesh by merging adjacent white pixels into as-big-as-possible AABBs. I think this is more or less how e.g Recast works, but they're not doing it each frame.

Also, with any approach involving merging neighboring AABBs, I'm wary that the "merge" step seems like it would be tricky or maybe even NP-hard to find the "best" (minimum number) set of AABBs.

Anyway... in case you can't tell I've never had to deal with pathfinding before :) so any tips or pointers would be much appreciated!


Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!