NavmeshCut Performance

So I have around 100 moving creatures at the moment in a scene with a NavmeshCut component,

I have the tile handler set to update once a second currently, although I’d probably prefer that to be higher. When this runs the framerate drops from 60+ down to 20-30 for that frame. I’m a bit concerned about the dropped frames for it, especially on a slower computer than mine. Is there anything I can do to improve this? Am I going the wrong route trying to have many NavmeshCut’s?

You can try to reduce the size of the recast tiles. That can help if it means a lower number of triangles have to be updated (if a tile has to be updated, all triangles in that tile have to be updated).
You can try to increase the ‘update distance’ for all navmesh cuts but lower the ‘updateInterval’ on the TileHandlerHelper. Hopefully it will then only update a few tiles per frame (when an update happens) instead of most tiles. I.e the tile updates will be more spread out.

Also using a rectangle instead of a circle will be marginally faster I think.

I thought the benefit of using a NavmeshCut instead of just updating the graph was that it only updates the changed area, instead of having to rebuild the whole tile? Did I misunderstand that?

Hmm that makes sense for spreading it out, I’m guessing a higher interval means a higher cost if it moves between several tiles during that update.

Unrelated to this, but if the tile handler component is added after the navmesh cut components, then they don’t update the navmesh. Is that intentional? In my case, since I need to scan the navmesh after everything is loaded in, and the tile handler component throws an error if its added before the navmesh is scanned, it caused some issues for me. I had to reorder how I was loading some things, which I’d prefer not to if there’s another way to handle it.

Ok, so rebuild was maybe a bad word choice on my part. It has to go through all the triangles in the affected tiles and cut them up using the NavmeshCut components.

It doesn’t matter much how far they have moved. The only thing that matters is that if a navmesh cut has moved more than ‘updateDistance’ units it will mark the tiles it was in previously as dirty as well as the new tiles it is in now. Then those tiles will be updated. If you have a single tile with 10 navmesh cuts in it, the cost is the same if one of them moves as if all of them move (assuming they don’t have to mark any other tiles as dirty).

Yeah I suppose that’s what happens now. It’s not optimal I agree.

So I decreased tile size to 64, increased update rate to 20 times per second, and increased distance to 1. I also changed them to rectangles. That made my framerate worse, did I not use good numbers?

Hard to say.
There are a lot of things that impact how long it takes. Really the only thing I can suggest it to continue trying to tweak the numbers.

Well, do you know what kind of performance I should expect? So I’m not tweaking to something that’s impossible.

100 continuously moving navmesh cuts is a bit on the high side I would say.
Could you try something like only enabling the navmesh cuts for creatures that are close to any pathfinding agent (e.g the player) and disable them otherwise?

I intend to do something like that eventually, but the problem is that this is a multiplayer open world game. Potentially all AI could be visible to at least one player. And I intend to have around 500 AI in a scene. So I might just have to deal with having AI able to walk through other AI.

Ok.

Could you use local avoidance for the creatures instead? (hard to say if this would be applicable without knowing the specifics about the game).

I potentially could try it out and see if the performance would be better, but last time I tried it the local avoidance is more to keep something from clipping than it is to come up with a path around it. Is there a way to do local avoidance with it coming up with a path around it instead of just trying to slide along it?

What could be very useful would be a component that marks nodes as unavailable or something while another fauna is standing on it, which then updates any path calculations. That’s kinda what I’m going for with the navmesh cutting it seems like.

Not really with the current local avoidance system.

That is possible, but I don’t think you would want to do that. The reason is that nodes in a recast graph have a large variety of sizes, so your creature could be blocking a 10x10 meter area of just a 0.1x0.1 meter area depending on how the nodes where laid out.

Right, I meant it’d somehow have to take into account the shape of the thing blocking the node.

Are there any plans for a local avoidance system that does that, or something like I suggested for marking an area as unavailable?

Well, that would require changing the graph and then you are pretty much back to navmesh cutting.

Not at the moment. I did a few experiments a while back with a local avoidance system that was a bit smarter than the current one in terms being able to escape local minima, but it didn’t pan out that well (mostly because of performance issues if I recall correctly).

I probably have absolutely no idea what I’m talking about, but would something like this be possible for you to do in a performant way for calculating a path? Instead of doing the navmesh cutting which updates the graph, instead keep a list of unavailable areas, which includes the size/shape of them. When a path is being calculated, lookup if the point is going to be inside of one of those areas, and if so try to use a point next to it instead?

Sorry, that’s unfortunately not easily doable when considering how the pathfinding algorithm works.
You can make a set of nodes unwalkable, but as mentioned before they may have varying sizes.
If you are interested you can read this page: https://en.wikipedia.org/wiki/A*_search_algorithm

So something like that would probably work well for the grid graph, but not a recast graph? Too bad I can’t use a grid graph then lol.

Exactly. When updating grid graphs one typically only recalculates if nodes should be walkable or unwalkable.

Is there anyway to get a grid graph to be able to support large terrains?

Technically the 1000x1000 limit is only artificial, but you would run into massive memory and performance issues if you tried to use it for a very large world.
Even a 1000x1000 contains 1000000 nodes, so even just the references to each node (8 bytes on a 64-bit system) would require 8 MB to store.

In an ideal world this package would have support for quadtree graphs (see https://en.wikipedia.org/wiki/Quadtree) which are sort of a mix between grid graphs and navmesh graphs and they would potentially have better performance. But unfortunately it does not.

Actually, one thing you could try is to disable area calculation completely. After each graph update the areas (connected components, visualized as different colors in the scene view) of the graph have to be recalculated which can be quite slow for larger graphs. If you disable it then if you try to request a path from one node to another node when there is no valid path between them it will have to search the whole graph for a path, which can be quite slow. Also methods like PathUtilities.IsPathPossible will no longer work (they will just think there is always a valid path).

In the GraphUpdateProcessor class, find the FloodFill() method with no parameters. Add a ‘return’ statement at the top of the method.

public void FloodFill () {
    return;
    ...
}