A* Pathfinding Project

Recast scan with GraphUpdateShape incredibly slow


I have a Recast graph which is approximately 3sqkm. A bit less than half of this area is procedurally generated, and so I need for the graph to be rescanned at runtime.

The generation tool defines it’s area with a series of points, which seems to tie in perfectly with the ‘GraphUpdateShape’. The exact area of the shape is around 1sqkm.

With only the terrain in the scene, scanning using the GraphUpdateShape (AstarPath.active.UpdateGraphs(guo);) takes a very long time. I didn’t let it finish, but had passed well over 40 minutes.

On the other hand, if I simply click ‘Scan’ in the editor, after the procedural terrain has generated, I would assume it is doing more work (as it’s the full graph area, not just the shape). It completes however, in less than 3 minutes.

Should I be using a different method to scan the mesh in this situation? Are there any things I can do to increase the speed?



That’s odd.
Which version are you using?

Do you think you could use the profiler to check what part of the code is taking a long time?
Does the game freeze or does the game continue to run with the graph update happening in the background?

Do you think you could post a screenshot with your graph settings?

Best regards,
Aron Granberg


Thanks for the quick reply!

Here are my settings.
The game doesn’t freeze.

I haven’t got profiling data yet, but I know a vast majority of the time (90%+) is within the x/z for loops calling BuildTileMesh within RecastGraph.UpdateArea. Within that, vox.VoxelizeInput was the big culprit. I believe inputMeshes had around 5000 meshes, presumably all generated from the terrain, as there were no other colliers in the scene.


I am currently on 4.0.11, though downloaded the latest version and compared the two VoxelizeInput versions, which appears to be practically identical, although the temporary float arrays for rasterization were replaced with VoxelPolygonClippers.



Hmm… Yeah I looked at the code and when the whole graph is being scanned it more efficiently assigns the meshes to the tiles that need them. When updating the graph it will go through every mesh for every tile. That’s still only 7000 tiles times 5000 meshes though. It doesn’t feel like it would be that slow. But that’s the only difference I can find.

In my dev version I have made some changes to optimize this. I can probably release a new beta with the changes soon.


Thanks for checking it out. I’ll keep an eye out. In the meantime I might poke around a bit and see if I can reduce the meshes evaluated per tile to see if that improves things.



I have uploaded beta version 4.3.13 to https://www.arongranberg.com/astar/download which includes a fix for this. In my tests it is significantly faster.


Thanks, I will check it out :slight_smile:


Hi @aron_granberg, just to let you know, although I couldn’t upgrade my A* version at this stage, I did have success with simply adopting the PutMeshesIntoTileBuckets implementation into the version we have.

The speed improvement was phenomenal. Still around 5 minutes for the area I’m working with, so am now experimenting with baking in chunks regardless, but thank you so much for your help.