AstarPath.Scan over multiple frames


#1

Good Evening,

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.

Thanks!
E


#2

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;
        }
    }

#3

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 :

 yield return StartCoroutine(graph.ScanInternalRoutine(delegate() {
                Debug.Log("Finished ScanInternalRoutine");
            }));

I did a similar thing to FloodFill as well.

Thanks!
E


#4

Hi

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


#5

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.


#6

Hi Aron,

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.

Thanks,
E


#7

Hi Aron,

Was there any progress made on the scanning / building Recast graphs over multiple frames?

Many thanks

Robin


#8

Hi

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.


#9

Nice thread! Didn’t seen it before. I discussed basically the same problem here http://forum.arongranberg.com/t/procedural-graph-mover-for-recastgraph just in “different words”. I was also getting ~20s scanning times for my 2000x2000 voxels size RecastGraph’s

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.


#10

Nice! I’ll give that a go :slight_smile: Thanks for the help, looking forward to seeing async in officially!


#11

Hi,

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 :slight_smile:


#12

That’d be incredibly helpful! I’ve just got around to trying Aron’s update solution with no success. If you could post your changes that’d be awesome :slight_smile:

Aron: which version are you planning on putting this into?

Many thanks

Robin


#13

Hi Robin,

So here is my ScanInternal for RecastGenerator.cs http://pastebin.com/8UaNKz9Y

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());


bool finishedScan = false;
IEnumerator Scan()
{
finishedScan = false;
foreach (var p in m_gameController.AStarScript.ScanLoop())
{
Debug.Log§;
yield return null;
}
finishedScan = true;
}

and I can easily check finishedScan to know the state of the scan :slight_smile:
Hopefully that helps, even if it is from 3.7.x and not 3.8.2.

Let me know how it goes,
Erin


AstarPath.active.Scan() Async alternative?
#14

Awesome! Thank you! Will plug that in later :slight_smile:


#15

I am also looking for the same solution for 3.8.2

Anyone has modified script that I can use?

I have tried the code above, but it doesn’t seem to compile…


#16

Any idea Aron? Did anything improve in this matter?


#17

Hi

I have this implemented in my dev version. I could send you a preview version if you want.


#18

Yeap ofcourse! It will really help! you can send it to [email removed] if you want.


#19

nice… NICE! … AWESOME!

Thanks! It does what I need to do perfectly!


#20

Awesome!
I’m glad it works well!

Btw, if you like the package, a rating and/or a review on the Unity Asset Store is a great way to support it :slight_smile: