Stitching Recastgraphs

General Recast graph
#1

Hi Aron,

I’m editing this as to not start a new thread, my old question about deserialization and my solution
are below. Anyway, my current issue is with stitching via UpdateGraphs() on recastgraphs.

So, I still need to break up the world into serialized recastgraphs. No problems streaming them in, but still wrapping my head around stitching them together. My process is convoluted and I’m wondering if there’s a better way.

So, I create and serialize the recastgraph chunks. On each chunk I line the border with a large number of node2 objects. This is tedious and time consuming, considering the scale of each graph. I also worry about all the added transforms piling on the performance

Question 1) Is this process of adding a ton of node2s ill-advised? Are there runtime performance issues with having so many nodes?

During runtime I load the graphs, then I do an UpdateGraphs() across the border where the nodes are. This is always where it hitches up (both to initiate the update and then on the queued update itself).

Question 2) Is there a better way to update? I don’t need to actually modify the graphs at runtime, I only need to update the walkability of these nodes. I’ve attempted to disable ‘rasterize terrains’ but then it screws up the serialized graph, which was originally conformed to the terrain. Right now the performance hitch is unacceptable.

Question 3) There’s an issue whenever one of these recastgraphs is loaded, a separate PointGraph is added. The problem is that when I unload the recastgraph, the PointGraph remains. With enough time it’s possible to pile on a massive number of unused PointGraphs in the scene. Is this a performance issue, and are there ways around it? Thanks.

Old question, solved by threading and so far seems stable as long as I’m pausing pathfinding:

I’m having a bit of a performance issue with DeserializeGraphs and am wondering if I’m approaching this wrong.

I’ve broken up my world into 2048 chunks and am creating/saving a recast graph for each into a .byte file. Ideally I’d be working with settings that create roughly a 1.5mb byte file, and I have no problem streaming it in with (TextAsset)Resources.Load.

However there’s a noticeable hitch when I use DeserializeGraphsData or DeserializeGraphsAdditive. Even if I get the byte file size down to say, around 300k, I’m still seeing a hitch. Is there any way to avoid this? Perhaps by pausing the rest of Astar? Or perhaps there’s a threading setting I’m missing? Many thanks for any advice.

#2

Hi

Just to get some background info. Is there a reason you cannot have the pathfinding graph for the whole world loaded at once? (see also my suggestions in your first thread Best practice for raycastgraph on dynamic/additively loaded scenes).

#3

I’ve tried it, and while I could potentially get it all in memory (around 20 - 40mb, depending on graph complexity), there seems to be some really bad performance in the pathfinding as the graph gets that large. At any one times it’s possible to have around 20 characters calling seeker.StartPath at varying intervals.

This world is pretty large, around 16000 units squared, and I’m finding that a cell count of .5 with tiles at 128 seems to be acceptable for detail.

I’m actually leaning towards skipping the stitching entirely, but even then I still get a minor hitch in even the tiniest GraphUpdate, which is necessary to register the jump nodes I’m using.

#4

Have you tried this with a recent version? Version 4.2 improved the performance of graph updates on very large graphs significantly. In 4.2+ pathfinding performance should only be affected in rare cases when a path has to search the whole graph. This can happen if you are using tags and the end node of a path is not reachable from the start node using the allowed tags.

Relevant changelog quote:

Improved performance of small graph updates on large graphs by a very large amount. Previously when making a small update to a large graph, updating the connected components of the graph using a flood fill has been the thing which took the longest time by far. Using a new internal hierarchical graph it is now possible to update large graphs much faster. For example making a small update to a 1024*1024 grid graph is on the order of 30 times faster and is now perfectly reasonable to do in real time (slightly depending on how the graph looks and its settings). The cost of the flood fill was previously offloaded to a separate thread, so it would not always be noticed in the Unity profiler, but it was there and could affect the performance of the game in strange ways. The performance of scanning a graph or updating the whole graph remains roughly the same. For more information about how this works, see Pathfinding.HierarchicalGraph.

#5

I just checked, I’m running 4.27.7. I actually upgraded because of my earlier deserialization issues which were fixed with some threading.

Are my graphs simply too big/detailed? Is it necessary to run UpdateGraphs() simply to register the walkability of node2s? Even if I do a minuscule update (with a bounds scale of .1f) there’s a noticeable hitch.

#6

Ok.
Make sure that when you are testing the performance, disable “show graphs” in the inspector. Redrawing the graph Gizmos can often be much slower than the update itself. Is it still slow? If so, do you think you could post a screenshot of the unity profiler for that frame? (with all relevant items expanded)

But yes. Using a ton of node links will be slow. Each nodelink2 component has to recalculate some data every time there is a graph update anywhere. This might be slow if you have a lot of them.

#7

Thanks yeah I’ve definitely disabled ‘show graphs’, and attempted any extra optimizations according to your docs. These hitches are noticeable in a final build as well.

I’ll attempt to get some data/screens for you. Even without nodes I’m getting these hitches. The only reason I’m ever running UpdateGraphs() was to register any jump/link nodes.

My runtime process is as follows:

  1. Load scene (which contains nodes) additvely into the open world.
  2. Load nav graph associated with this scene.
  3. Attempt to run a GraphUpdate on the border to link any edge nodes with adjacent graphs.
  4. Failing 3, I simply GraphUpdate within the proximity of a single node to register jump nodes on the graph. Even this tiny update causes a hitch.
#8

Hi

Ok. So my guess would be that all your NodeLink2 components is what causes the hitches. It’s hard to say without that profiler screenshot though.

My suggestion would still be to go with a single large graph. If you are seeing pathfinding performance problems due to a large graph, I think those are more easily fixed.

The best way to stream in recast graph chunks would be to use the RecastGraph.ReplaceTile api. This is kinda hard to use though as there are no pre-written scripts for this use case. It would automatically handle all the stitching at the tile borders though.

You do not need to run a GraphUpdate for the NodeLink2 component to be applied. Normally it is applied automatically when it is enabled, but possibly that doesn’t work in your game because of how you set it up. There is however an Apply function that you can use. The most efficient way would be something like:

AstarPath.active.AddWorkItem(() => {
    for each node link in all the ones you have just added {
        nodeLink.Apply(true)
     }
});
#9

Hi Aron, thanks for the suggestion.

So, I did have something working (I couldn’t see anything noticeable in the profiler btw, wasn’t sure of the best way to provide that info). For now I was completely ignoring stitching and only concerned with getting my jump nodes working.

The big change was to not use UpdateGraphs, but rather keep track of each new companion pointGraph that Astar was creating when I deserialized a recastGraph, and do a simple Scan() (which I’ll replace with your suggestion) on that particular graph. I would then remove that pointGraph alongside the recastGraph when the player was far enough away.

Unfortunately there was now an IndexOutOfRange in PathHandler/GetPathNode() after removing pointGraphs. However, it seems that if I have one master pointGraph in the scene on initialization, that never gets removed, I no longer have this issue.

So as of now I think it’s working? I’ll play with stitching next, and I’m still a bit concerned by all the null graphs that add up. In fact, does it even matter if I’m removing unused pointGraphs? Are these adding extra overhead? I did attempt to have one master pointGraph that is updated with all the nodeLink2s but I was having issues, and it wouldn’t solve all the generated pointGraphs that I’d have to remove anyways.

#10

Long story short, I think it’d be ideal if there was only a single pointGraph in the scene that contains all the nodeLink2 data, and as I’m deserializing/removing recastGraphs and loading/unloading scenes containing the nodeLinks, I just update this master pointGraph.

1 Like
#11

Hi

Sorry for the late answer.
I think what might improve things for you is to explicitly delete all the point graphs before your serialize the graphs (so that only the recast graph is serialized). There really should only be one of these point graphs in the scene, but due to saving and loading graphs it creates multiple ones. The node links will automatically create a new point graph when they are enabled if one does not exist, so that should still work.

That seems like a bug. Could you post exactly how you do this and the stacktrace that you get?