A* Pathfinding Project

How to enhance GraphUpdateObject precision on RecastGraph?


#1

How can I increase the precision of the GraphUpdateObject in a RecastGraph?

I used a shape to try and improve precision, but it didn’t change anything because the problem is probably the graph itself and not the shape.
I assume I could get a better result if I changed my graph to a grid one but I would rather avoid this.
What can I do to make the cutting in the graph be more precise?

The wall shown in the picture is subdivided in many box colliders, it can appear/disappear.
As the wall appears or disppears, the graph should update and allow/disallow passage.

I used the GraphUpdateObject to make the ground underneath be walkable or unwalkable using the “setWalkability”

private void UpdatePathfinding()
{
// var shape = Box.GetColliderVertexPositions(false);
// var mat = Box.transform.localToWorldMatrix * Matrix4x4.TRS(Vector3.zero, Quaternion.Euler(-90, 0, 0), Vector3.one);
GraphUpdateObject guo = new GraphUpdateObject(Box.bounds)
{
updatePhysics = false,
setWalkability = Box.isTrigger == false,
modifyWalkability = true,
// shape = new GraphUpdateShape(shape, false, mat, Box.size.y),
};

    AstarPath.active.UpdateGraphs(guo);
}

#2

Hi

If you just want to allow/not allow passage I would recommend using a navmesh cut component instead.
It will work a lot better out of the box. See https://arongranberg.com/astar/docs/navmeshcutting.html

Otherwise you can use a RecastMeshObj to insert a split in the navmesh there. See https://arongranberg.com/astar/docs/recastmeshobj.html#area


#3

I would like to update the graph only whenever I am changing a BoxCollider’s isTrigger to true/false.
My wall has many BoxColliders, I would rather avoid creating 1 component for 1 box collider.
The wall’s box colliders’ isTrigger changes based on if it’s overlapping with circular colliders (they hide or reveal the wall).

Is it possible that I can create by code a shape for each of the BoxColliders, those would get updated manually when the isTrigger is modified (with either Recast or NavmeshCutting)?

Here’s a scenario for my wall, some if it blocks the way and the rest does not:

The wall has many colliders on a single gameobject: https://i.imgur.com/wb0spSz.png

Now previously with Unity’s standard NavMesh system I created many gameobjects and each had their NavMeshObstacle component but I would rather like to avoid doing that again.


#4

Hmm…

So there are some options you have

  1. Use a navmesh cut on each box
  2. Do some processing in code to figure out the footprint of the wall and adjust a single navmesh cut to fit that
  3. Use a GraphUpdateObject to recalculate the whole tile (modifyWalkability=false, updatePhysics=true) and include the box colliders in the rasterization. This may be too slow for your game though, but it’s not that slow. It definitely has the highest quality.
  4. You can theoretically use a navmesh cut with the ‘dual’ option enabled (which will make it keep the inside of the navmesh cut) and then use a graph update object to modify the walkability. However this is a pretty brittle solution and I would not recommend it.
  5. Use a grid graph instead :stuck_out_tongue:

#5

Thanks for the information :slight_smile:

I tested out method 1 out of simplicity. I put the NavmeshCut for every collider of the wall due to not being sure where a wall will meet the navmesh.

I have put all the components on a single gameObject.
I made a few tests: You can imagine that those walls I’m creating can end up having lots of colliders because each box collider occupies only 1x1x1 unit.

Using Unity’s native NavMesh system I was forced to create new gameobjects for the NavMeshObstacles.
With your system it appears I can stay on gameObject and put all the components there.

Compared to Unity’s NavMeshObstacle the performance is significantly worse.
However if I could somehow give the NavmeshCut knowledge of when to update I think it would make a big difference instead of updating based on a frequency.
===> How can I achieve this?
I simply want to turn on/off the cutting.

Everything worked fine on a most walls but some cause errors to pop up. I made a test with and without creating new gameobjects to put the component on but the error pops up just the same, it’s not related.

This error pops up depending on what type of walls I built. I’m not sure yet what the reason for this is.

Too many perturbations aborting.
This may cause a tile in the navmesh to become empty. Try to see see if any of your NavmeshCut or NavmeshAdd components use invalid custom meshes.
UnityEngine.Debug:LogError(Object)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:420)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.TileHandler:CutPoly(Int3[], Int32[], Int3[], GraphTransform, IntRect, CutMode, Int32) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:682)
Pathfinding.Util.<>c__DisplayClass41_0:<LoadTile>b__0(IWorkItemContext, Boolean) (at Assets/ASSET STORE/AstarPathfindingProject/Generators/Utilities/TileHandler.cs:1188)
Pathfinding.WorkItemProcessor:ProcessWorkItems(Boolean) (at Assets/ASSET STORE/AstarPathfindingProject/Core/Misc/WorkItemProcessor.cs:299)
AstarPath:PerformBlockingActions(Boolean) (at Assets/ASSET STORE/AstarPathfindingProject/Core/AstarPath.cs:881)
AstarPath:Update() (at Assets/ASSET STORE/AstarPathfindingProject/Core/AstarPath.cs:864)

Here is how I build the NavmeshCut on new gameobjects. I find it weird that this could cause any errors seeing as they’re just the same measurements as the BoxCollider.

    private NavmeshCut CreateNavmeshCut(BoxCollider _box, string _index)
    {
        var newGo = new GameObject($"NavMeshCut {_index}");
        newGo.transform.SetParent(this.transform);
        newGo.transform.localPosition = Vector3.zero;
        newGo.transform.localRotation = Quaternion.identity;

//        var newGo = this.gameObject;

        var obstacle = newGo.AddComponent<NavmeshCut>();
        obstacle.type = NavmeshCut.MeshType.Rectangle;
        obstacle.center = _box.center;
        obstacle.height = _box.size.y;
        obstacle.rectangleSize = new Vector2(_box.size.x, _box.size.z);
        obstacle.useRotationAndScale = true;

        return obstacle;
    }

#6

I tried method 5 (using grid graph), it does a good job for the issue at hand but it fails in other regards:

I removed the RVOController/RichAI and replaced it with the AIPath. But some of my units get stuck on walls and never get to destination.

Even when fiddling with thick raycasts, it’s just not precise enough compared to the recast graph.

I’m interested in method 3 but how can I include the Box Colliders from the wall in the rasterization?


#7

You seem to have configured the graph so that there is no clearance at all for the character. The graph surface are all the points where the character’s center should be able to be. However in your case it looks like there are a lot of valid points very close to the wall. I would recommend lowering the node size and having some amount of margin to the wall.

Right… Due to a 3rd party library I’m using sometimes having many navmesh cuts that have overlapping vertices or edges (when seen from above) can cause issues (performance issues normally, but sometimes it just cannot resolve the issue and will give up. That’s the error you are seeing).

I think I’d recommend option 2 for best performance and robustness.

The navmesh cut will only actually cut the navmesh when anything inside that tile has changed. During other frames the overhead should be very small as it only checks for e.g. if the navmesh cut has moved. Are you seeing a greater overhead?

Also. May I ask what the reason is behind you wanting so many colliders on each wall?


#8

They are walls that appear/disappear allowing/disallowing the player or anyone else to go through them depending on the if there is a light source nearby.
The wall is composed of multiple box colliders that change their isTrigger state based on if its within a light’s radius


About option 2 -> it’s not simple because there might be more than 1 light interacting with a wall + I need to know which colliders are in contact with the ground too (it could be over 2 levels of ground etc…). I think it’s best I don’t go there.

Are you seeing a greater overhead?
-> I saw some spikes and I had none compared to when I tried it with the NavMeshObstacle component but I didn’t do any thorough test. Maybe it’s because I have no Unity Navmesh terrain that there is nothing to compute too.
I will let you know more when I know more.