Save Modified Recast Graph nodes


#1

Hello all.

So far the Recast Graph has been really useful, except it also creates NavMesh underneath a lot of the props we use to block out our level. We’ve tried a variety of settings but basically came to the conclusion that a custom script would be more efficient.

The script currently iterates over all nodes, checks which area they make up and indexes them according to that Area ID. When that is finished it checks which areas has the most nodes. We’re only interested in the one big NavMesh for our game. Everything else is irrelevant but we use quite a few NavMeshCuts and entities can get pushed out of bounds. We have enabled the setting so units will walk back to the nearest valid NavMesh and those tiny navmeshes are also valid so they get stuck.

Once everything is nice and filtered I check all nodes and if they don’t belong to the largest area then I set them as non-walkable.

Now in-editor this updates nicely. The nodes change colour to red. I then save this “Filtered Navmesh” through the normal AStar object in the scene without rescanning to keep the filtered version. Loading it also seems to work fine.

Yet when I start the game it simply sets all the nodes back to walkable again as if the filter was never applied. Do I need to modify the script to also handle saving when it is done with setting nodes as non-walkable or is something else causing the reset?

I know it’s possible to apply the filter when the game is running but it seems an unnecessary waste of resources.

Any help is appreciated.


#2

Hi

How do you load it during runtime? The graph is normally scanned when the game is started (if Settings -> Scan On Awake is enabled and cached startup is not used). I would recommend that you enable cached startup in the Save & Load tab for this to work well. See https://www.arongranberg.com/astar/docs/save-load-graphs.php.

There is also a built in partial solution to this. You can place a RelevantGraphSurface component somewhere in the region you want to keep, and then set ‘Relevant Graph Surface Mode’ to ‘Require For All’. This will work best if your graph does not use tiling however, otherwise you will need to place a RelevantGraphSurface component in every tile, which can be quite tedious.
See https://arongranberg.com/astar/docs/recastgraph.html#relevantGraphSurfaceMode


#3

“Scan on Awake” was indeed enabled and so was “Cached Startup”. I disabled the “Scan on Awake” :sweat_smile:

Just tested again and it seems to be working much better but not 100%. Seems that certain nodes get reset to Walkable when we cut in the NavMesh. It’s an RTS game so we cut constantly when the player places buildings or if objects get spawned when the level loads. Any way to control this?

We’ve tried the RelevantGraphSurface component but due to the size of the Navmesh Area it wasn’t really feasable unfortunately.

Thanks for the very quick reply.


#4

Ah wait. You are using navmesh cutting.
Due to how navmesh cutting modifies the graph, there is simply no way to always preserve the walkability flag.
It could be the case that an unwalkable node gets combined with a walkable node when say a navmesh cut moves away or something, or that the node changes shape. It is not really possible to have a well defined way to combine them in those cases.

How does your filtering script work? I think it should be possible to do it in another way so that it actually removes those triangles from the navmesh instead of just making them unwalkable. That will avoid the hairy issue of preserving the flag when navmesh cutting.


#5

Ah. I did some research on the topic and found similar questions to be usually answered that removing the nodes wasn’t possible but to use “Non-Walkable” instead. Then again these topics were from 3 years ago and could be meant for real-time editing.

The script was meant for in-editor and now that I’m looking at it again I believe I could skip a useless step that isn’t really necessary and was included as part of me figuring out the system.

  • I get the active RecastGraph, iterate over all the tiles and get all the nodes from those tiles. (I should just loop over the nodes since the tiles aren’t really used).

  • I then check every node for their Area and save nodes with the same Areas in lists.

  • I loop over the list of Areas and find the one containing the most nodes.

  • Loop over all nodes again and if their area doesn’t match the largest area, set the node as non-walkable.

      SetLargestAsWalkable myTarget = (SetLargestAsWalkable) target;
    
      if(GUILayout.Button(new GUIContent("Find Active AStarGraph","Sets the variable for the active AStar Recast Graph")))
      {
          myTarget.RG = AstarPath.active.data.recastGraph;
      }
      GUILayout.Space(5);
      if (GUILayout.Button(new GUIContent("Filter nodes to Area", "Iterates over all nodes in the Graph and stores them based on the area the make up.")))
      {
          for (int x = 0; x < myTarget.RG.tileXCount; ++x)
          {
              for (int z = 0; z < myTarget.RG.tileZCount; ++z)
              {
                  var tile = myTarget.RG.GetTile(x, z);
                  foreach(var node in tile.nodes)
                  {
                      //Create area if empty
                      if(myTarget.Areas.Count == 0)
                      {
                          myTarget.Areas.Add(new NamedAreaNodes() { Name = node.Area, AreaNodes = new List<TriangleMeshNode>() { node } });
                      }
                      else
                      {
                          //Check if it belongs to a previously found area
                          bool areaFound = false;
                          foreach(var area in myTarget.Areas)
                          {
                              //Add the node to the area if it's a match.
                              if(node.Area == area.Name)
                              {
                                  areaFound = true;
                                  area.AreaNodes.Add(node);
                                  break;
                              }
                          }
                          //Create new area if it doesn't exist yet.
                          if(!areaFound)
                          {
                              myTarget.Areas.Add(new NamedAreaNodes() { Name = node.Area, AreaNodes = new List<TriangleMeshNode>() { node } });
                          }
                      }
                  }
              }
          }
    
    
      }
      GUILayout.Space(5);
      if (GUILayout.Button(new GUIContent("Set Smaller Areas as Unwalkable", "Checks which area is largest and sets all nodes that do not belong to this area as non-walkable")))
      {
          NamedAreaNodes largestArea = null;
          foreach (var area in myTarget.Areas)
          {
              if (largestArea == null)
              {
                  largestArea = area;
              }
              else if (area.AreaNodes.Count > largestArea.AreaNodes.Count)
              {
                  largestArea = area;
              }
          }
    
          if (largestArea != null)
          {
              //Loop over all the nodes in the Graph
              myTarget.RG.GetNodes(node =>
              {
                  if (node.Area != largestArea.Name)
                  {
                      node.Walkable = false;
                  }
              });
    
              AstarPath.active.FloodFill();
          }
      }
      GUILayout.Space(15);
      if (GUILayout.Button("Print Current Area information"))
      {
          Debug.Log("Found the following " + myTarget.Areas.Count + " Areas: ");
          foreach (var area in myTarget.Areas)
          {
              Debug.Log("Area " + area.Name + ": " + area.AreaNodes.Count + " nodes.");
          }
      }
    

    }

I tried straight up destroying the nodes but it started throwing NulLRefExceptions in the editors since AStar struggled to render the destroyed nodes.

Again, thanks for the swift replies.


#6

Ok.

Yeah, so navmesh/recast graphs aren’t really designed to be able to have nodes destroyed like that. But in this case you really do need it.

I think this code should work for removing a node safely (I haven’t tried it myself, but I think it should work)

void FilterNodes (NavmeshBase graph) {
	AstarPath.active.AddWorkItem(ctx => {
		foreach (NavmeshTile tile in graph.GetTiles()) {
			// Filter the node and triangle arrays and keep only the nodes that you want to keep
			var newNodes = new List<GraphNode>();
			var newTris = new List<int>();
			for (int i = tile.nodes.Length - 1; i >= 0; i--) {
				// Do whatever check you want here
				if (shouldNodeBeDestroyed) {
					tile.nodes[i].Destroy();
				} else {
					// Keep this node
					newNodes.Add(tile.nodes[i]);
					newTris.Add(tile.tris[i*3+0]);
					newTris.Add(tile.tris[i*3+1]);
					newTris.Add(tile.tris[i*3+2]);
				}
			}

			tile.nodes = newNodes.ToArray();
			tile.tris = newTris.ToArray();
			tile.bbTree.RebuildFrom(tile.nodes);
		}

		ctx.QueueFloodFill();
	});
}

#7

Thank you, I will try it out tomorrow when I’m back in the office.

Much appreciated.


#8

Just tested the script, had to make one minor edit (List of Triangle Nodes instead of Graph Nodes works perfectly without a need for conversion afterwards) and all is working brilliantly!

This will save a lot of work in the future. Thanks you for the excellent support.


#9

Nice! Great that it is working!