Splitting navmesh = path finding performance increase?

Questions & Answers
1

Does being able to have multiple navmeshs with navmesh links make path finding faster?

What sort of difference to path finding performance does it make?

Background: I’m currently using Unity Free and the Unity navmesh stuff is great. The NavAgents move well etc., lovely. The only trouble is the time it takes to calculate a path. I want to have lots of AIs which I can do but they currently spend most of their time idle waiting for a new path to finish being calculated so it kills the game play I wish to implement. I have tried some of the nav/path finding alternatives but, so far, the ones I’ve tried are too buggy or can’t cope with really complicated scenes. I have a massive test scene and because I’m using the free version of Unity I have the whole scene using 1 very complicated navmesh.

I am hoping that someone is able to give me a guide as to the performance improvements they’ve seen of being able to divide the navmesh into multiple “zones” (that I can’t do in Unity free as you have no navmeshlink ability). Does being able to have multiple navmeshs with navmesh links make path finding faster than 1 navmesh covering the same area? Is it faster by much?

For Example: If I split my navmesh into, say 10 “zones”, the path between any points in different zones typically just needs to work out how to get to the off mesh link you start from, traversal across any other zone could be pre-calculated by the Unity navmesh code, (I don’t know if it does), it then just needs to calculate from the arrival off mesh link to the position that you want to get to in that zone. Or perhaps it just adds overhead and the navmeshagent path is no faster to calculate?

2

Ok sorry that I’m bringing up dead posts, but I thought I’d add this in to help anyone else who finds this thread.

Of course it depends how the pathfinding is implemented, however I’d say it would largely increase it in the vast majority of cases. Assuming you find an effective way to determine which of the divided maps you need, it should largely decrease the pathfinding time because by searching two chunks of (for example) a 100x100 grid map as opposed to the entire map, you’re only searching 20% of all the possible nodes.

Taking into account map size has a negative exponential effect on pathing time it’ll definitely be much faster.

Assuming you can further optimise it and find the optimal locations where the subdivided maps link to each other for pathfinding, all you actually need to do is find the route to that links from the unit’s start location to that link, and then follow a pre-computed path from each entry point of one chunk to the next until you reach the chunk containing the target node and find the path from the entry of that chunk to the target.

Tl;dr - yes, dividing it into chunks with an optimal algorithm to effectively utilise the chunk system should in most cases show a significant increase.