Layered graph vs Recast graph

Hi there,

I bought the A* project pro and I am currently investigating the API possibilities. For the game that I want to make I landed on either using a Layered graph or a recast graph and I would like some advice on which one to use.

The game is a strategy game that allows the creation of cities. These cities can have walkable walls, bridges build during runtime. Meaning that I require a part of the navmesh/grid to be updated during runtime. Since characters can walk on 2 levels of height (say the ground and the bridge floating above it) I think I can make use of the layered gridgraph or the recast graph. For the latter one, I wonder if it is possible to update a part of the recast graph (the api/examples describes an RecastTileUpdate method) and which technique would be better suited for this scenario.

Eagerly awaiting your answer.
Jorn

This topic might be of help. Will have to check it out. Creating a Recast Graph Tile by Tile

Hi

Mainly the differences relevant for you are

  • Recast graphs are slower to update. You cannot use navmesh cutting for the bridges because you add new surfaces, not just remove them. The graph updates do happen in a separate thread mostly, but there is still some time in which no pathfinding can be done.
  • Layered grid graphs cannot support very large worlds. If your world is small-ish, then it will work fine, but if it is too large then it will simply use too much memory to be useful.
  • Pathfinding is faster on recast graphs. Since recast graphs can cover large regions with fewer nodes it can find paths in the graph faster.

When you create a new bridge (or some other thing) you can update the graph like this

 // Find the bounding box of the bridge somehow, doesn't have to be from the collider
 var bounds = bridge.GetComponent<Collider>().bounds;
 AstarPath.active.UpdateGraphs(bounds);

Some important notes for performance

  • The cell size in the recast graph affects the performance when updating the graph a lot. A lower cell size will give you a higher quality navmesh, but it will be slower to update.
  • Recast graphs can only be updated by recalculating a set of tiles, so make sure the tile size in the recast graph is set small enough that you don’t have to update a very large region every time and large enough that you don’t have to update too many tiles at a time (there is some extra overhead for each tile). You can see how large the tiles are by viewing the graph in the scene view, you should see that it is divided into square chunks. This can be tricky to set, but as a rule of thumb I would suggest setting them to a size similar to the objects that you update the graph with, but no smaller than 64 voxels (the field in the graph inspector is in voxels).
  • For a layered grid graph. The node size also has a high impact on performance. A lower node size will give you a higher quality graph, but it will be slower to update.
1 Like

Thank you for your answer. This answers the questions that I currently have. Recast graph seems the way to go since I have relative large terrains and a recalculation delay is perfectly acceptable.

1 Like

Ok :slight_smile: Let me know if you have any more questions.

1 Like

If you have large terrains, make sure that you use 4.0.9 or later as that version improves the performance when updating individual recast tiles and there are large terrains in the scene.

1 Like