Dynamic walkable objects (walls, towers) for RTS game

Hi, I’m using the pro version for navigating agents on a recast graph. It’s kind of a RTS game and the map can be quite large (1000x1000) or more. The recast graph can manage this well so far (2-5 seconds at startup maybe).

An important part of the game is the construction/demolition of buildings, some of them walkable, like walls or towers, which creates the need to update the graph.

I played around with DynamicGridObstacles and while the navmesh result is good, performance is not. I get huge frame drops over several seconds and the time until the part of the navmesh is recalculated varies greatly between a few seconds to 10s of seconds.
I also tried with NavmeshCut and NavmeshAdd components. While performance is good, it’s nearly impossible to move agents from one wall to the next or to the ground. Solving this through node links has shown to be highly impractical, as walls and towers can change shape, depending on neighboring objects, and pathfinding does not look natural with node links as it breaks up agent formations.

From your experience, what is the most promising approach here? Any advice would be highly appreciated.

I use tags for a similar scenario, started using tags after this answer:

you can also search for nodes with tags, and raycast has a component that allows you to apply tags to very unique shapes

Thanks for your reply. Good to know as I might run into the same problem at some point. But for now, I can’t see how this is related to making dynamically created buildings walkable. As I see it, it would require to either re-scan parts of the graph (slow), merge different navmesh parts (terrain + building) or create/manipulate navmesh vertices in some other way.

I’ve read in another thread about RecastMeshObj but unsure how it’s supposed to work as I was not able to notice any effect by it. The docs are a bit vague what this is actually doing.

Progress has been made.

I realized, DynamicGridObstacle can actually be decently fast with recast graphs if switching to colliders(!), not meshes and using a tiled recast graph.
I furthermore realized a big issue seems to be that the default DynamicGridObstacle does not let you specify, which graph it should update, but instead updates all?
I have several graphs (one for terrain, one for shallow water and one for deep water). So apparently it tried to update all of them which caused the big lag.
Will investigate further and report, so at least others might not fall into the same trap.

Hey in my game the buildings just have tags, some tags are walkable, some tags are not, so I thought that may help based on what you describe (just set the tag to walkable or not depending on the type of building, for what I read you currently have all your buildings as obstacles right?), you do seem to need tags for the water situation though, my understanding is that having more than one grid is not recommended, I also can’t imagine a situation where that would be needed, I do have different terrains too and those terrains are just tags, the tag also affects how easy it is to walk on them, the more I read it the more I think you would benefit from using that (Working with tags - A* Pathfinding Project), but I’m not an expert at all!

Thanks for the suggestions.
I currently have 3 recast graphs, one for land/terrain, on shallow water and one deep water. The shallow water graph allows infantry to jump onto boats and cross the ocean. The deep water one is several meters below the ocean surface, so that large ships cannot approach islands or regions with shallow water too much.
Possibly I could use tags to avoid splitting shallow water and land, I’ll look into that. For the deep water graph I’m not sure yet how else I could deal with shallows. But well that#s a different story.

For the buildings - they are constructed by workers at runtime - I experimented with DynamicGridObstacles and with recasttileupdate yesterday evening. The thing is, it’s not enough to just cut the navmesh and insert an obstacle, but to rescan the nodes where the building has been placed and insert new navmesh nodes accordingly. Pretty much like this:

recasttileupdate looks actually quite promising, but for whatever reason seems slower than dynamicgridobstacle.

For whatever graph update, I wonder two things:

  1. Can it be done async? I don’t care if it takes 5 seconds to rescan the local nodes, it just may not cause any noticeable frame drops.
  2. A (local) graph update stops all ongoing pathfinding. Agents that are far away stop until the update is done and then resume their path. That seems hardly justified if they are on nodes far away from where the update happens. Can this be avoided?


Have you checked out the beta?
Recast graph updates are done asynchronously in the beta, and they should be faster too.

It cannot, I’m afraid. It is very hard to know if a pathfinding request would be affected by the graph update until it is done.

Thanks for the reply.
I was able to optimize the update process quite a lot, converting every graph to colliders, adjusting tile sizes etc. Yet a graph update still causes a tiny spike:

Apparently I have some other issues there as well, so the spike is only partially caused by the graph update.
In the shown case, I instantiate 3 fairly simple objects at once, each one using a mesh collider and having a dynamic grid obstacle assigned.

As you wrote in another thread, you’d recommend me to get rid of the dynamic grid obstacle and use a RecastMeshObj instead? But since these objects are constructed and destroyed at runtime, I’d have to trigger a graph update either way somehow. Or did I understand something wrong?

Maybe check out the beta version. Graph updates for recast graphs are a lot faster in the beta.

Yeah, you’d require a RecastMeshObj and a DynamicGridObstacle/manual graph update.

Thanks, I am on the latest beta.

I tried with recastmeshobject, but I could not notice any difference in performance to just using a dynamic grid obstacle alone. Am I missing something?

Can you expand that profiler output a bit? So I can see what’s going on.

The recastMeshobj component does not affect performance. The RecastMeshObj is purely for robustness, to make sure things don’t overwrite each other.

Sure, here is a snapshot:

Ah. As you can see, the spike comes from garbage collection, not really from the A* Pathfinding Project itself.
It does allocate quite a lot of memory, though. But I think that’s unavoidable, as the unity terrain api does not let the scripts access the heightmap without allocating.

I see.
Well, I was able to further ease the spike by decoupling the instantiation of the objects from the graph update, so that the graph update happens a bit later. Guess I can get away with the remaining mini-lag.

Thanks a lot for your help.