Support Forum

SECTR 2019 + A* Pathfinding Project

Hi,

we want to have a loading screen free game + smarter AI that is better aware of it’s whereabouts and surroundings. We use SECTR for these purposes, which means we are splitting the game world into smaller, more manageable chunks and streaming those runtime.

There is one problem with that - the initialization time for each map sector as it’s loaded must be as small as possible to prevent freezes, which means that rebaking one huge graph for all currently loaded sectors every time a sector is loaded or unloaded would be just unpleasant from the performance perspective.

I tried pre-baking multiple recast graphs editor time (one per each sector) and create connections between those (where the doors and hallways would be for example) so that NPCs can cross the boundaries of those sectors.
NodeLink3 component looks like a perfect match, but I can’t get our RichAI agents to seek path through it, let alone cross it. Should I use it the same way NodeLink2 is used in the ‘RecastExample2’ scene?
I suppose the problem is the graphs either overlap a little or don’t really “touch”. But then… I would have to bake graphs with zero character radius, which would lead to other issues.

Does anybody here have any tips for me?
Am I even following a good lead?

EDIT1:
Here you can see how the agent properly seeks a path through the NodeLink2 but doesn’t actually go through.
When the recast graphs overlap like in this image, I though it would be nice if I could make the agent use the Link for pathfinding only. Then somehow ignore the link when he arrives near it and switch current graph based on richAi.desiredVelocity for example - so that he would continue onward to his target.
Does this seem right?

EDIT2:
As it turns out, the path query fails when the NodeLink2 is placed in an area where the graphs overlap… well… it seems my solution from EDIT1 might not be that amazing as I hoped :smiley:

Hi

Would it be possible for you to bake the whole map (with all sectors loaded) in the editor? You could then save that as a cached graph or save it to a file. Unless your world is enormous keeping the graph in memory should not be a problem.

Thanks for the quick reply :slight_smile:

Well, I thought of that, but I noticed we get the best pathfinding and RVO quality when we use tiles and set the tile size to a lower value (like 8 for example). Our world is also quite big. So I’m not really sure how that would work out.

But maybe… maybe I could do the following I think:

  • At every place where there will be enemies that need the graph - a place where each enemy needs to be able to walk from one side of the graph all the way to the other - I will bake one graph with it’s unique identifier (that should give us 32 graphs total, according to Seeker::Traversable Graphs field)
  • After baking all those graphs editor time, I will save each one to a separate file.
  • I will create a scriptable object that will hold references to sector and graphs combo (example: graph 1 spreads across sector A, B and C)
  • Runtime when player is closing in on the sector B for example, I will see what graphs, if any, have to be loaded. Usually one or none if there are no enemies there.
  • Similar applies to unloading graphs that are not needed anymore since the last of their assigned sectors has been unloaded

Comparison to one huge graph for the entire world follows:

PROS:

  • Shorter startup time
  • More freedom with runtime graph updates if ever needed
  • Better performance in pathfinding worst case scenarios when the entire graph would have to be searched
  • Definitely not a RAM killer
  • More freedom with settings, since we don’t have to worry about performance that much
  • Safer on level changes and subsequent graph rebaking. Rebaking the whole world at the same time, all the time, can lead to bugs. Specially after A*PP updates that might influence the baking process/algorithm.

CONS:

  • We might encounter a huge master location graph that spreads across multiple sectors and is… well… huge. And that loading it at runtime could lead to a freeze. That could be solved by loading the graph on a worker thread though. I hope :smiley:
  • Requires some manual work and scripting and will be prone to human error. But it should get the job done I think.

If this seems plausible to you and you don’t see any caveats I might have missed, I will go for this solution.
Also any tips on cool API methods or something like that would be endlessly appreciated :slight_smile:

That’s really low. I usually don’t use a tile size lower than 32 or 64.
Make sure you have funnel simplification enabled on the RichAI script to improve the path quality.

I would really suggest to try out the “one huge navmesh” approach first. If it turns out to use too much RAM or something then sure, something else can be implemented. But this is by far the easiest and most robust solution and usually recast graphs do not use that much memory. This is assuming you increase the tile size up from 8 as that low number will cause the number of triangles and tiles in the navmesh to go up significantly.

Ok, I will listen to your advice.

That leaves one last thing - do you think the solution I suggested here is a safe bet as a plan B in case the one huge graph solution doesn’t work out? I mean… do I get your blessing for following that path if need be? :smiley:
Just so that I don’t have to reopen this topic in the future.

I’m not quite sure if the solution you are proposing requires different graphs to be connected using links?

Nope, the solution I meant is the one with the list of PROS and CONS. It pretty much means using graph per area with enemies. Area that the enemies will never leave anyway. Think of it as separate arenas.
There will be some peaceful (monster free) time between those arenas, dividing them for us nicely. No links will be involved. Connecting the graphs won’t be necessary. Each graph = single arena (that can consist of one to N sectors, but that’s not that important)

So we would be loading graphs for these arenas as the player comes near and unloading them as he leaves.
Each arena graph would be stored in a separate file.

If we would be utilizing multiple graphs (1 arena = 1 graph) like this from the very beginning, we could then switch to this more RAM friendly solution from the LOAD EVERYTHING ON STARTUP solution you suggested with ease (if need be). This sounds reasonable to me. Only downside is we have to be careful with the max graph count limit.

Okay. But if the player is only in one area at a time, wouldn’t at most one graph be loaded at a time?
So you wouldn’t have to worry about a graph limit.

Well… I’m using a single Pathfinder component as a singleton. Therefore if I bake all arenas into a single graph, I can’t easily split them up into multiple graphs (and files afterwards as a result) in the future.

I don’t think that answered what I was asking.

You seem concerned that you will into a graph limit. However since the player is only in one area at a time, only one graph should be loaded at a time, right?

I was concerned about the graph limit after seeing “Traversable Graphs” field of the Seeker component where it seems that each graph is clearly identified. This means that I will have a problem when creating arena 33+, right?
I’m not sure whether it implies some hard limit when everything will break, or just this graph mask feature will be bogged down a little.

The Traversable Graphs mask only supports up to 32 graphs, however the maximum number of graphs internally is actually 255.

Even when generating all the graphs you would only have to load a single graph though.
Since it would be a bit annoying to have to manually sync >32 graphs’ setting I would suggest that you use a script that has all bounding boxes for the areas you are interested in defined.
Then you would do something like

foreach (var b in bounds) {
    var graph = AstarPath.active.data.recastGraph;
    graph.forcedBoundsCenter = b.center;
    graph.forcedBoundsSize = b.size;
    AstarPath.active.Scan();
    var bytes = AstarPath.active.data.SerializeGraphs(new Pathfinding.Serialization.SerializeSettings { nodes = true });
    System.IO.File.WriteAllBytes(bytes, "some/save/path.binary");
}

Optionally you could scan the graph asynchronously to get some kind of progress bar while this script is running.

This is amazing, thanks! Exactly what will be needed. I will just modify it then to not use the first graph always, but all the relevant graphs instead.

Thanks for the support :slight_smile:

Hi

My intention with that script is that you would have one graph that you configure with the right settings and then that script could run and save out different versions of that graph. One version for each area that you have. During runtime you could then load the appropriate version depending on the player position.

Ooooooooooooooooooooooh… didn’t occur to me since I didn’t see any “graph.clear” methods called or anything like that.
This is even more amazing!

Thanks!

1 Like

fyi, it might be worth noting that AstarData.DeserializeGraphs will clear all current graphs (you have to explicitly call AstarData.DeserializeGraphsAdditive to keep the old ones)

And thanks for the heads up!

Oh how I love this plugin :smiley: Don’t want to even imagine trying to do half things I do with A* with unity native navigation.

1 Like

Thank you for the kind words! :slight_smile:

If you want to support the package even more a rating and/or review in the asset store helps a lot :slight_smile:

1 Like

A review it is :slight_smile:
Just let me…
aaaaaaaaaaaaaaand…

done!

1 Like