Best practice for raycastgraph on dynamic/additively loaded scenes

Hi Aron. I’ve been happy with your asset (I used it last year to ship a Switch title, Never Stop Sneakin’), and was wondering if I could get some advice for a new project.

I’ve got a good handle on A* for small static areas, but am having a bit of trouble wrapping my head around best practices for a large scale world.

Right now I’m breaking up a fairly large open world into a number of scenes that are dynamically and additively loaded. These scenes generally contain a terrain component, with some additional structures. Let’s say each scene is 1024x1024 units wide and are loaded as you approach them.

So, it’s my understanding that there should only be a single AstarPath script component in the entire scene, so this resides in the dontdestroy’ed scene manager. It’s prohibitive to create a single massive raycast graph for the entire world, this is where I’m a bit lost:

  1. Should I pre-generate the graph for each scene, ‘save to file’ in the editor, and then load it along with the scene at runtime?

1a. If so, how would I stitch/merge it to the existing terrain? Right now there doesn’t seem to be way have an AI negotiate separate graphs, and it’s my understanding you shouldn’t have more than one anyway.

1b. I see there’s something about updating tiles, but I’m having trouble understanding how this works. Also, it seems you can only update tiles that have already been created upon initialization, rather than add to the graph? Again it seems prohibitive to define tiles for the entire span of the world.

  1. Or should I be generating the graph at runtime, moving the center along with the player and updating at regular intervals? Can the center and edges of the graph be moved, and is this in any way efficient? My early tests suggests the only way to do this is to move the forcedBoundsCenter, but then I have to update with a .Scan() which is inefficient. Is there a way to update a raycastgraph like the GridGraph procedural example?

Thanks for any advice.

Hey, congratulations on shipping Never Stop Sneakin’! I try to stay active on the forums and answer questions (if you can’t explain it to others, you probably don’t understand it yourself!), but this is a bit outside my depth. You probably know more about A* than I do, so apologies if this is in no way helpful!

In my game I stitch a graph to… itself using a two-way connection:

node1.AddConnection(node2, 1000);
node2.AddConnection(node1, 1000);

but this may also work for connecting multiple disparate graphs once they’re loaded into the scene. Assuming they’re contiguous along the adjacent edges (peaks meet peaks, valleys meet valleys), it shouldn’t look weird as agents traverse across graphs.

Then there’s the mysterious EdgeNode property https://arongranberg.com/astar/docs/gridnode.html#EdgeNode … which may or may not be intended to identify/stitch graph edges together, but it’s only for GridNodes? ¯\_(ツ)_/¯

Do you have a Twitter handle so I can follow your new game? :slight_smile:

Thanks Torgie. I’m actually NoogyTweet on twitter if you’re interested, although I don’t post very often.

So yeah, I’m still having a bit of trouble with this. I understand the nodes system now, would it be prohibitive to add potentially hundreds of NodeLink2s to stitch up the various level chunks? From what I can tell there’s no additional updating happening when they are added.

I’m also still confused as to how I should be additively loading new areas. I’m assuming I generate/save each raycastGraph in the editor… and then at runtime, when I load in a new level chunk I should (via script) create a new raycastGraph, populate the data from the saved graph file, add it to my Astar.active.data, and then populate/scan with nodelink2s? Does this seem terribly inefficient/the wrong way to go about it?

Ok, I think I’m starting to figure things out.

Save pre-generated graphs, and then do a DeserializeGraphsAdditive at runtime to add the byte data to my Astar project. Then RemoveGraph when the asset is no longer necessary.

I see that this will create a null in the graph array, and unfortunately it doesn’t seem to be reusing null spots, rather it just keeps adding to the array. So running back and forth will rack up the array length.

Also a bit confused with how to handle node data. It seems that you will always need to save a pointgraph alongside the raycastGraph (I’m using special jump hotspots for the AI) , and I’m still figuring out how to stitch the graphs together for the AI.

Hi

If at all possible, I would recommend that in unity editor, you load all the terrains into a single scene at the same time and then scan the graph and save it to a file/cache it. This will allow you to use a single graph for your game without having to care about loading/unloading different parts of it, pathfinding will also work over much larger distances. Make sure that ‘Use Tiles’ is enabled on the recast graph (this is the default).
Recast graphs use a comparatively small amount of memory even for large worlds (this does of course depends on the world complexity), so this should hopefully not cause any issues memory-wise.

If this is not possible (e.g. due to memory constraints of having everything loaded at once) you could try an alternative approach where you scan an empty graph for your whole world, then load a 3x3 group of terrains around a single terrain and the recalculate the graph around the middle terrain, then you move to the next and so on, unloading/loading terrains as you go (the 3x3 group is required because when recalculating the part in the center, it needs to know how it joins up with its neighbors). When you are done you will have a scanned graph of your whole world which you can save to a file for example. This is slightly trickier to do unfortunately.

You can stitch graphs together using node links as you do, but I don’t recommend it because it losses some information when crossing from one graph to the next (the funnel modifier for example will have to fall back to moving from node-center to node-center where it crosses from one graph to the next).

Recalculating recast graph tiles is quite slow, so usually it is desirable to avoid recalculating large parts of it during runtime. For grid graphs (like in the procedural example) it works well because grid graphs are relatively fast to recalculate.

Yes, the recast graph has a fixed size, but you can recalculate any tiles within it. If you really want to, it is possible with some code to add new tiles dynamically to it, but usually that’s not something you would do.