Navmesh Obstacle avoidance

Just for context I’m creating a FPS.

So I’ve found through searching the forums and a bit of experimentation of my own that the navmesh generator doesn’t take into account static obstacles added to the map, so in my navigationControl class I’m seeking to add a bit of code to avoid obstacles I might have littered around (things like crates, furniture etc).

Now I have a proposed solution but something about it just seems inefficient and I’m wondering if there is a better approach.

So this is the approach I’m still in the process of implementing:

An arrayList of spatials is inputted containing all possible obstacles.
Clones of the bounding boxes of these spatials are then saved into a list with the radius of my NPCs collision shape added to the X and Z extent (an easy way to see if an object fits between two obstacles is checking for overlap - something I picked up from navigation in robotics).
A quick cycle through the list of bounding boxes merges any that overlap.

This is the initialisation phase. This list of bounding boxes may only have to be computed once depending on the flexibility of my scene. (Can I move chairs etc around? Is it going to be truly dynamic etc).

Now this is what will be done each time a path is computed.

A ray will be created between two adjacent waypoints and checked against all bounding boxes for an intersection. If there is an intersection create path around it.
Repeat for every adjacent waypoint pair.

Naturally I could optimise this by checking for bounding boxes in the cells of the navmesh between the two waypoints and by storing the bounding boxes using a data structure with spatial (in terms of space not the object) access methods but first step is to get it working before premature optimisations.

I know some people have had problems with obstacles and the navmesh and I was wondering if anyone had any better algorithms?

Daniel

NavMeshGenerator is a wrapper for critterai’s NavmeshGenerator… and it is not up-to-date with the current version. There are also issues with the path optimization, you’ll probably need to write your own.

Seeeeeeew… in the process of path optimization, you could ray cast and deviate the path around non-traversable objects that are not part of the original mesh. /shrug I’m sure there are other options… but this would work. The current implementation that I put together is knocking paths down to a 10th of the original size, accounting for obstacles that are not part of the navmesh and using splines to smooth cornering.

That is essentially my approach, I’m just raycasting between waypoints on the graph and merging boundingvolumes for obstacles the character couldn’t fit between to stop it trying.

I considered editing the navmeshgenerator and pathfinder but the source did not look the prettiest thing to try and play with.

EDIT: blonde moment my approach is different in that it’s using bounding volumes and will test the intersections on each one separately using a raycast but I using just a ray cast and walk around I felt more processing might be done finding obstacles on new route and it seemed a nicer solution to get around obstacles closed bunched together

I just realized that mentioning critterai didn’t make a ton of sense without explaining why I mentioned it!

Reason was it may help in tracking down relevant info that is not on the board here.

Question for you… are you generating the navmesh at runtime? or?

I’m not, and I’ve implemented the solution I detailed and it seemingly works well, later on I’ll do stress tests to find out how many entities or how complex the scenery has to be to cause lag.

1 Like