One possible RTS game solution with agile graph update

#1

Hi, I’m working on an RTS game. I need 4 graphs for 4 different sized unit types. I tried the grid graph and the re-cast graph, both have the same issue.
Im using for local avoidance purposes the GraphUpdate method to make under a unity the graph available for pathfinding or not. I have about 10 GraphUpdate calls in 2-3 seconds, where some of the units collides with each other for testing purposes. The graphs are default re-cast graps, just the player margin size is different. The GraphUpdate calls delays, block the pathfinding calculation, and so they comes through after 10s to 30s, depends on how much GraphUpdates are in the queue.

This 4 graph configuration works with 250x250 grid graphs, but that I cannot apply for a 2000x2000 terrain. It would be very inaccurate. With 4 grid graps with the resolution 1000x1000 the GraphUpdates are by far worser.

Not sure how to use this pathfinding solution for my needs. I need to move 4 different sized unit types, for that reason I created the 4 different graphs (known solution for this issue). Maybe the multiple graphs are not well updated, maybe it causes some kind of redundant calculations?

I’m using the following code:

if (gameObject.layer != toLayer) {

			    //GraphUpdateObject guo = new GraphUpdateObject(this.GetComponent<BoxCollider>().bounds);
			    // Check the new layer.
			    Bounds bounds = GetComponent<Collider>().bounds;
			    if (toLayer == UnitsLayer) {
				    GraphUpdateObject guo = new GraphUpdateObject(bounds);
				    AstarPath.active.UpdateGraphs(guo);
			    } else {
				    exactBlockedBounds = bounds;
				    GraphUpdateObject guo = new GraphUpdateObject(exactBlockedBounds);
				    AstarPath.active.UpdateGraphs(guo);
			    }

			    gameObject.layer = toLayer;
#2

Hi

Recast graph updates are very slow. They are recalculated on a tile by tile basis, so you can reduce the region that is updated by lowering the tile size (for best performance it should be a bit larger than the objects you are moving around).
However for recast graphs you may want to check out navmesh cutting instead. It is more limited, but a lot faster. See https://arongranberg.com/astar/docs/navmeshcutting.php

#3

Hi,

the problem I have is that the TileHandlerHelper just updates one NavMesh based graph:

if (AstarPath.active != null) {
				var graph = AstarPath.active.data.FindGraphWhichInheritsFrom(typeof(NavmeshBase)) as NavmeshBase;
				if (graph != null) {

If I understand it correctly, I have to cut in all the 4 graphs and I have then additionally add the different unit size-type margin for the different graphs. That’s not implemented in the TileHandlerHelper, but that I can do. Is this the correct way for my issue?

#4

Hi

Ah. Yeah currently that is not exposed in the Unity inspector. You can create them from script to allow this:

var graphs = AstarPath.active.graphs;
for (int i = 0; i < graphs.Length; i++) {
     if (graphs[i] is NavmeshBase) {
         var handler = new TileHandler(graphs[i] as NavmeshBase);
         gameObject.AddComponent<TileHandlerHelper>().UseSpecifiedHandler(handler);
         handler.CreateTileTypesFromGraph();
     }
}
#5

Hi,

I hacked around your code and made NavmeshCut working for multiple graphs with different unit margin. I added dictionary (for each graph an entry) for lastPosition and lastRotation in NavmeshCut and I send the index of the graph to the callbacks. For RequiresUpdate I send additionally the scale to have a different unit margin size depends on which graph the units are (RequiresUpdate (int graphIndex, float scale)).
The TileHandlerHelper got a GridIndex (index of the graph) and an ExtendBorder (for scale the margin) attributes and I have for 4 graphs 4 TileHandlerHelper instances.

It works fast, but I saw in the profiler that the calculation is made on the main CPU core, not in a thread. So I got spikes in each update where the units (10 units, 0.4m update distance) were moving. However, with the GraphUpdates I just made the graph unwalkable, when the unit stopped, yet at each 0.4m range I make the terrain unwalkable. So, the NavmeshCut is a big improvement!

Also generating the graph with re-cast graph takes a bit too long for the 4 graphs, 160s. I have to cache it, but here multithreding could break it down to 160/4 seconds. Maybe you have time for such optimization…

#6

I see, all the cores working…

#7

Hi,

it was a bit complicated to propagate the unique border for each graph. At the end the NavmeshCut GetContour method must get the border extension value. It looks like so:

3GraphWithUniqueBorder.jpg995×576 217 KB

Tree graphs are cutted with different border. The only one issue is, that cutting the mesh causes a high load on the main CPU core, that shouldn’t be I guess. Could this cutting run on thread, or is there something that makes it impossible yet?

#8

Hello again, I have a performance issue with the navmesh cut solution. After rebuilding the Library cache I have now a performence spike periodically, if I move only one of my units. The spike is at “recalculate connected components”. I had a spike before, but that was low, I guess under 5 ms. It is also pretty independent of how many units are moving by navmesh cut. Do you have any idea how to fix this, or what could be the source of this spike? Is this 50 ms a normal value for navmesh cut on an I7/Xeon CPU?

bandicam 2018-06-05 20-01-19-506.jpg983×573 119 KB

#9

Hi

Which version are you using? How many graphs do you have and how many nodes are there in those graphs (you can click the small ‘info’ button in the top right corner of the graph inspector)?

#10

Unity 5.6.6f2, A* 4.1.2, All 4 Navmesh Graphs: width/depth = 4000, cell size 0.5, Tile size 64.

Hi, I still uses my solution, where I have 4 TileHandlerHelper for 4 Navmesh graphs. The implementation is straight forward, it works. The one unit cuts in 4 graphs.
If you could move the calculation for flooding in a thread it wouldn’t be an issue, at least it would not eat the main thread.

I made a change in your code, in AstarPath.cs, uncommented the graphUpdates.FloodFill(), that brings then a much more better performance. Still the calculation should be in a thread. (Moved 6 units, not 1. The 1 unit needs in this way 4.2 ms instead of more then 52ms and still correctly updates the graphs.)

public void FloodFill () {
	Profiler.BeginSample("Recalculate Connected Components");
	//graphUpdates.FloodFill();
	workItems.OnFloodFill();
	Profiler.EndSample();
}

bandicam 2018-06-05 20-55-13-979.jpg997×536 142 KB

Found it, nodes by info, the 4 graphs: 24286, 56688, 33955, 24286

Edit: I don’t use any graph update. Debuged the AstarPaths.cs UpdateGraphs methods.

Edit: If it could be fully run on a different core, then I could run about 200 active navmesh cutting agent, that would be enough. At all, if just one graph would be used, about 800 agents could run on a core, with a cutting distance of 4 and update rotation of 10, on a pretty large navmesh!

#11

How many nodes are there in those graphs (you can click the small ‘info’ button in the top right corner of the graph inspector)?

The spike should be roughly proportional to the total number of nodes in all your graphs, with a spike like that I would expect more than 50000 nodes in your graphs. It does seem like a large spike. [edit] Yeah, you seem to have 139215 nodes in your graphs, and it needs to iterate through all of them. It is a very very fast inner loop, but 139215 items is still a lot.

I would strongly recommend that you increase the tile size that you are using. From you screenshot it looks like a single tile is around the same size as a single character, in which case you are essentially emulating a grid graph. This will reduce the number of nodes in your graph drastically.

There is also a way to disable flood filling completely, however this has some side effects. If you try to search for a path to a part of the graph that the agent cannot reach, then it will have to search through every single node it can reach in order to determine that there is no way to the goal. And this can be pretty slow. However your game may not have any such regions, so it may be ok.

#12

Thank you for your proposal. I will made them tiles larger.