Sign in to follow this  
raigan

Generating an AABB-based navmesh

Recommended Posts

hey,
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!

thanks,
Raigan

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this