Obstacle Avoidance : RVO vs. Navmesh Cut vs. Tag Manipulation

Hey all,

What is the best way in Astar for 3D Obstacle Avoidance by AI? Seems there are 3 implementations I can go for; RVO, Navmesh Cut, Tag Manipulation. Here is my assessment, let me know if you know any better.

RVO : Not for large obstacle avoidance. More for avoiding other AI in the world and small objects. Need to add an obstacle “collider” to every object that could be an obstacle.

Navmesh Cut : Good for obstacle avoidance but might be expensive. Need to add an obstacle “collider” to every object that could be an obstacle.

Tag Manipulation : Good for obstacle avoidance. Don’t need to manage any obstacle “collider”. Better performance then Navmesh Cut.

Seems like tag manipulation is the best for performance reasons. I am using a Raycast Mesh in a 3D world in which there will be at most 20 AI active at a time and multiple dynamic objects that need be have AI avoidance. Any suggestions?


You are correct about RVO. It is primarily for agents avoiding other agents.

Navmesh cutting is usually the best option on recast graphs. It is relatively fast as long as most obstacles don’t move all the time. If the obstacles are static it has almost no overhead. Make sure that you use a decent tile size for the recast graph as updates are done on a tile-by-tile basis. Having an extremely large tile size or no tiles at all will require it to recreate a very large chunk of nodes every time a cut moves.

Tag manipulation unfortunately doesn’t work that well on recast graphs. The reason is that you can only change the tags on whole nodes, and the nodes in a recast graph rarely line up perfectly with the obstacles that you have. There are workarounds for this, but usually they are not worth it compared to navmesh cutting.

For recast graphs you can of course also recalculate whole tiles as if they had been scanned from scratch.
This is done using AstarPath.active.UpdateGraphs(bounding-box). As detailed in https://arongranberg.com/astar/docs/graph-updates.php. For recast graphs this is done in a separate thread (if multithreading is enabled) so it will not impact the frame rate a lot, however in absolute terms it is still a lot slower than navmesh cutting.

Thanks for the reply Aron.

I ended up trying tag manipulation as a first attempt. My solution does contain calls to AstarPath.active.UpdateGraphs(bounding-box). Good to know that UpdateGraphs is actually slower then navmesh cutting, I was thinking the opposite.

The tag manipulation is working okay, but its not perfect.

For navmesh cutting, is there a good way to have the navmesh cut “collider” match the existing collider on the object? Or if it is simpler have a navmesh cut rectangle match the collider bounds?

If you are only modifying the tag of the nodes (GraphUpdateObject.updatePhysics = false, which is not the default) then it will be faster. However with updatePhysics = true then it will recalculate the whole tile which is pretty slow.
Sorry about the confusing variable names btw, I need to redesign the GraphUpdateObject class at some point.

Sorry, not at the moment. You will have to configure the size of it manually.