Choosing the right approach for the walker/crawler agent

Hi, Aron!

We want a very specific thing from A* and we ran into a lot of problems trying to achieve that. Because of the multi-level scenes with larger volumes we have to use the recast graph. What do we want – our enemies can crawl or walk (dismembered leg makes it a crawler) and we would like them to be able to squeeze in spaces walker cannot fit in. Walker could also decide that it would like to crawl through a lowered space rather than walk around. For that we need penalties and tags.

Right now we also have navmesh cuts for doors and other dynamic obstacles and that is where our problems begin. We know, that using navmesh cuts discards tag and penalty data we attributed to navmesh triangles during baking phase before the level kicks in.

Another problem is – even if we’ll manage to get through the issue with discarded triangle properties – that we have to get triangle generation under control to be able to use this approach. If we use some viable tile size, navmesh triangles are generated and marked with the crawler tag in a way that is not always very logical. Some of them run across perfectly walkable floors.

Semi-ideal solution would be having dual navmesh cuts run only during scan phase for us to be able to cut the navmesh in ways that are practical – that way we could use tags to manage if doors are open or closed. With dynamic obstacles, we could make some adjustments of the concept so we could live with the case where dynamic navmesh cuts are out of the question.

But I just provided you with the context, now let’s get to the actual question :slight_smile:

Could you please help us with the fitting concept or approach to utilize Astar for this purpose?

And just to recapitulate:

  • Generally, enemies need to be able to decide to go prone and crawl if the path through the lowered space is more viable to them.
  • We need some way to pre-cut some places on navmesh to have triangles covering the areas precisely wehre we want them to, without losing the tag and/or penalty data. Performance of this taks is not a problem for us because all will be pre-baked.
  • (Optional) We need navmesh under the dynamic obstacles like doors and oil barrels to be unwalkable.


It sounds like a much simpler solution in this case would be to just use two different graphs.
Take a look at this tutorial:

Do you think that could be a solution for you?

We thought about this option but this approach has some disadvantages.
In this configuration, our agents should be able to use both graphs and decide which path is more viable. We would have to find both paths on both graphs at the same time and compare the results somehow. As far as we know there is no simple and cheap way to check what path is closer to the destination (and we would also need to add some bias to that decision, like with the penalty property on nodes).

There is also a need to decide for our enemies when to lay down and start crawling, and the ideal solution would seem to be setting some number of nodes before the crawl tag to be the threshold.

Our agents have complete physical bodies with complex interaction with the player‘s presence in virtual reality, so they are quite expensive performance wise, so we need to find the cheapest approach possible.

We noticed that if we use navmesh cuts all of the graph‘s pre-baked tags and penalties get discarded at initialization time, so we need to add them again once this happens But as far as we know there is no event for updating the navmesh after initialization is done working ( or after navmeshcut discarding all node tags in the process) for us to be able to start our own custom „augmentation“ of the nodes and assign correct tags and penalties. Knowing when exactly it‘s safe to do this would allow us to have only one graph, and we would only have to make sure there are no crawler tags in the same tile as the navmesh cut.

Also for the dynamic obstacles (using navmesh cuts) there is another problem – because if we use navmeshcut event „UsedForCut“ to reapply tag on nodes in affected tiles using GraphUpdateScene object, infinite graph update loop kicks in. We have found on forum some way to avoid this, but it‘s using the obsolete api that is no longer available (Recast graph loses penalty after NavmeshCut) - This renders usage of navmeshcut and graphupdatescene combination (mentioned in the “navmesh cutting” docs) impossible.

Maybe solving these two issues would help us find a correct solution for our needs.

1 Like

Hi Aron, I apologize for daring to just bump this thread… But we’d really need your opinion on this one :slight_smile:

I don’t think the api mentioned in that post has been removed?

Hmmm… Is it strictly necessary for you to use a recast graph? I think for this a layered grid graph would work much more easily. Right now I think the api is a bit limited when it comes to recast graph and it’s going to be tricky to make everything work.

Unfortunately, we have tested LayeredGridGraph and the size and complexity of scene is simply too much for it.
We’ve tried to find issue with your code from Recast graph loses penalty after NavmeshCut

there was a typo that mislead us to think it’s gone. So

If I call
( as Pathfinding.IUpdatableGraph).UpdateArea(guo);

alone, it throws an error saying that I must call UpdateAreaInit(), which as I understand the code, forces me to call UpdateAreaPost() after i’m done. I think that UsedForCut() is called from that UpdateAreaPost() so there it sometimes ends in infinite loop. (I think it’s “sometimes” due to multithreaded nature of updates, happens when i move transform of that component in scene view with mouse during play)
here is full code

it uses NavmeshCut’s code to create GraphUpdateShape and applies tag on it when UsedForCut is called. There is some debounce to update only once for more than one tile being updated at once. But even if it does not end in infinite loop, no tags are applied :frowning:

Hi and let me bump this one once again :smile:

If you want to update a specific graph I would create a GraphUpdateObject with a specific graphmask instead.

GraphUpdateObject guo = new GraphUpdateObject(bounds);
// Set additional options here
guo.... = ...;
// Update only the first graph
guo.graphMask = 1 << 0;;

But as I said before, I think a recast graph will work pretty badly for this.

But that doesn’t work. We are using Astar Pro and in that version GraphUpdateObject doesn’t contain the graphMask property.

Just to be sure we’re on the same page, this is how it goes on:
1 Initialization (Assigning Tags and Priority)
2 Applying Navmesh Cut (Tags discarded)
3 Calling UpdateGraphs() (To reassign Tags and Priorities on affected tiles)
2 Applying Navmesh Cut (Again)
3 Calling UpdateGraphs() (And then 2, 3, 2, 3, again for the rest of eternity)

Because the graph has been updated, it falls back to the 2. point, as Navmesh Cuts are reapplied automatically after the graph has been updated.

And really, because of the structure of our levels there is no better option for us than the Recast Graph.

By Priority we mean Penalty of course :slight_smile:

Could you please look at it Aron? It really doesn’t work. Recast is needed for our levels because we make a VR project with a great deal of freedom of movement, and fully physical enemies, with dismemberment. Levels need to have very detailed navmeshes, because our enemies can get stuck easily with grids of any kind (unless we’d have a really dense grid, but that is not optimal, recast is the best for us). Getting this to work would add a lot of fun to the interactions with our agents, and maybe you could provide a quick fix. We can work around the drawbacks, we just need it to work in the way you intended it to work.

ah sorry, the property is graphUpdateObject.nnConstraint.graphMask.

In the latest beta version (4.3.43) I have implemented support for tags on RecastMeshObj components. So now you can take any object, add a RecastMeshObj component to it, and specify which tag surfaces on top of that object should have. Would that work for you? Note that navmesh cuts will still clear tags.

Hello and thank you for the answer. Unfortunately, when we got to test it out again, we foundout that it works only with Unity 2020 – and since we are using OpenVR in our project, we are unable to use newer versions of unity. We are forced to stay on 2019.4. Do you think there is a way to make it work on older versions too?

Unlikely I’m afraid since it depends on a bunch of burst compiler changes which are not available in those older versions.