We need to generate a graph with navmesh at runtime. We only have 1 huge graph to generate which takes ~16s to Scan() on a beast of a PC. The problem is not that it takes 16 seconds, but that it blocks the main thread. I went in your code and added a coroutine friendly ScanInternal method on the RecastGraph. All runs well until I get to RecastGraph.BuildTileMesh(…). I would ideally like to yield after each BuildTileMesh, but I get this exception :
Exception: Trying to initialize a node when it is not safe to initialize any nodes. Must be done during a graph update
AstarPath.InitializeNode (Pathfinding.GraphNode node) (at Assets/AstarPathfindingProject/Core/AstarPath.cs:2035)
Pathfinding.GraphNode..ctor (.AstarPath astar) (at Assets/AstarPathfindingProject/Core/Nodes/GraphNode.cs:25)
Pathfinding.MeshNode..ctor (.AstarPath astar)
Pathfinding.TriangleMeshNode..ctor (.AstarPath astar)
Pathfinding.RecastGraph.CreateTile (Pathfinding.Voxels.Voxelize vox, VoxelMesh mesh, Int32 x, Int32 z) (at Assets/AstarPathfindingProject/Generators/RecastGenerator.cs:1752)
Pathfinding.RecastGraph.BuildTileMesh (Pathfinding.Voxels.Voxelize vox, Int32 x, Int32 z) (at Assets/AstarPathfindingProject/Generators/RecastGenerator.cs:1668)
Pathfinding.RecastGraph+<ScanInternalRoutine>c__Iterator1C.MoveNext () (at Assets/AstarPathfindingProject/Generators/RecastGenerator.cs:1339)
So my question is : Is their a way to explicitly tell your system that we are starting/ending a graph update? Or do you have any other idea how I could achieve a 1-graph scan over several frames.
Hey! I have done something similar but couldn’t quite get it to work the way you want it to work.
I made a copy of ScanLoop() in AstarPath.cs and I call BlockUntilPathQueueBlocked() after every yield, which gets rid of the error.
I only use this to let the progressbar on my loadscreen draw “naturally”, and the game is still blocked while each graph is scanning. If you manage to get it to scan smoothly in the background please share your code!
Official background scanning support would be great though.
public IEnumerator ScanLoopBackGround(OnScanStatus statusCallback)
{
if (graphs == null)
{
yield break;
}
isScanning = true;
euclideanEmbedding.dirty = false;
VerifyIntegrity();
BlockUntilPathQueueBlocked();
if (!Application.isPlaying)
{
GraphModifier.FindAllModifiers();
RelevantGraphSurface.FindAllGraphSurfaces();
}
RelevantGraphSurface.UpdateAllPositions();
astarData.UpdateShortcuts();
if (statusCallback != null)
{
statusCallback(new Progress(0.05F, "Pre processing graphs"));
yield return null;
BlockUntilPathQueueBlocked();
}
if (OnPreScan != null)
{
OnPreScan(this);
}
GraphModifier.TriggerEvent(GraphModifier.EventType.PreScan);
System.DateTime startTime = System.DateTime.UtcNow;
// Destroy previous nodes
for (int i = 0; i < graphs.Length; i++)
{
if (graphs[i] != null)
{
graphs[i].GetNodes(delegate(GraphNode node)
{
if (node != null) node.Destroy();
return true;
});
}
}
for (int i = 0; i < graphs.Length; i++)
{
NavGraph graph = graphs[i];
if (graph == null)
{
if (statusCallback != null)
{
statusCallback(new Progress(AstarMath.MapTo(0.05F, 0.7F, (float)(i + 0.5F) / (graphs.Length + 1)), "Skipping graph " + (i + 1) + " of " + graphs.Length + " because it is null"));
yield return null;
BlockUntilPathQueueBlocked();
}
continue;
}
if (OnGraphPreScan != null)
{
if (statusCallback != null)
{
statusCallback(new Progress(AstarMath.MapToRange(0.1F, 0.7F, (float)(i) / (graphs.Length)), "Scanning graph " + (i + 1) + " of " + graphs.Length + " - Pre processing"));
yield return null;
BlockUntilPathQueueBlocked();
}
OnGraphPreScan(graph);
}
float minp = AstarMath.MapToRange(0.1F, 0.7F, (float)(i) / (graphs.Length));
float maxp = AstarMath.MapToRange(0.1F, 0.7F, (float)(i + 0.95F) / (graphs.Length));
if (statusCallback != null)
{
statusCallback(new Progress(minp, "Scanning graph " + (i + 1) + " of " + graphs.Length));
yield return null;
BlockUntilPathQueueBlocked();
}
OnScanStatus info = null;
if (statusCallback != null)
{
info = delegate(Progress p)
{
p.progress = AstarMath.MapToRange(minp, maxp, p.progress);
statusCallback(p);
};
}
graph.ScanInternal(info);
// Assign the graph index to every node in the graph
graph.GetNodes(delegate(GraphNode node)
{
node.GraphIndex = (uint)i;
return true;
});
if (OnGraphPostScan != null)
{
if (statusCallback != null)
{
statusCallback(new Progress(AstarMath.MapToRange(0.1F, 0.7F, (float)(i + 0.95F) / (graphs.Length)), "Scanning graph " + (i + 1) + " of " + graphs.Length + " - Post processing"));
yield return null;
BlockUntilPathQueueBlocked();
}
OnGraphPostScan(graph);
}
}
if (statusCallback != null)
{
statusCallback(new Progress(0.8F, "Post processing graphs"));
yield return null;
BlockUntilPathQueueBlocked();
}
if (OnPostScan != null)
{
OnPostScan(this);
}
GraphModifier.TriggerEvent(GraphModifier.EventType.PostScan);
try
{
FlushWorkItems(false, true);
}
catch (System.Exception e)
{
Debug.LogException(e);
}
isScanning = false;
if (statusCallback != null)
{
statusCallback(new Progress(0.90F, "Computing areas"));
yield return null;
BlockUntilPathQueueBlocked();
}
FloodFill();
VerifyIntegrity();
if (statusCallback != null)
{
statusCallback(new Progress(0.95F, "Late post processing"));
yield return null;
BlockUntilPathQueueBlocked();
}
if (OnLatePostScan != null)
{
OnLatePostScan(this);
}
GraphModifier.TriggerEvent(GraphModifier.EventType.LatePostScan);
euclideanEmbedding.dirty = true;
euclideanEmbedding.RecalculatePivots();
//Perform any blocking actions and unblock (probably, some tasks might take a few frames)
PerformBlockingActions(true);
lastScanTime = (float)(System.DateTime.UtcNow - startTime).TotalSeconds;//Time.realtimeSinceStartup-startTime;
System.GC.Collect();
AstarLog("Scanning - Process took " + (lastScanTime * 1000).ToString("0") + " ms to complete");
if (statusCallback != null)
{
statusCallback(new Progress(1f, "Done"));
yield return null;
}
}
This works, thank you! Although it is not “smooth”, it is a major improvement. Here is what I have done.
First I copies AstarPath.ScanLoop as you did (I named it ScanLoopRoutine ). Second I defined an abstract method named ScanInternalRoutine in NavGraph (Base.cs) :
public abstract IEnumerator ScanInternalRoutine(System.Action statusCallback);
Then I implemented it in all of NavGraph’s subclasses (using stubs for the type of graphs I dont use )
In RecastGraph (RecastGenerator.cs) I inlined ScanAllTiles inside of the newly created ScanInternalRoutine method in order to be able to yield easily. The important part is where tile mesh is being built :
for (int z = 0; z < td; z++)
{
for (int x = 0; x < tw; x++)
{
int tileNum = z * tileXCount + x;
Debug.Log("Building Tile #" + tileNum);
BuildTileMesh(vox, x, z);
yield return null;
AstarPath.active.BlockUntilPathQueueBlocked();
}
}
Finally, here is how I use ScanInternalRoutine inside ScanLoopRoutine :
I have an experimental branch with support for this for grid graphs (support other graphs can be relatively easily implemented).
Here is the full diff for the required changes: http://pastebin.com/cwYX9nx7
Also. Know that you can calculate graphs in the editor and then cache them. That will give you a lot faster startup times if your world is not procedurally generated.
Most of the world is procedurally generated so we cannot pre-compute the navmesh. What would be grand in the future is to get threading support for scanning graphs.
I actually have async scanning working in my internal dev version (pathfinding is still paused when the graph is being scanned however). Graph updates on a recast graph are already async, so you can cheat a bit by first scanning the graph and making sure it detects no ground or obstacles (so it will be completely empty) and then request a graph update of the whole graph.
I suspect that to achieve more smooth, or as I calling progressive graph building it may need to make BuildTileMesh(vox, x, z) method itself as a separate coroutine with “yield return null” statement, which might be casted not on every single iteration, but lets say every 10th of 100th iterations.
I just wanted to say thanks for the pastebin it was super helpful and I was able to make my recast graph update async which really helps for building procedural levels. Now the scan can be done in the background which really improves loading between levels.
Thanks!
also gonzorob if Aron’s update solution didn’t work for you I’d be happy to post up what changes I added (although I am a bit behind 3.7.x not 3.8.2) Not sure if they will necessarily be what you’re looking for but it helped my project
I pretty much just followed everything else in Aron’s update solution. But for clarity, in the AstarPath.cs here is my ScanLoop() http://pastebin.com/sZNhFqGh
finally in my application code I have something like this
… where i used to have AstarPath.active.Scan ();
now i have
StartCoroutine(Scan());
Thanks for the help, looking forward to seeing async in officially!