Awaitable Asynchronous Bounded single graph update


#1

It looks like it is not possible to update a specific grid graph only within bounds and have it awaitable?
I’ve read Update single graph using GraphUpdateObject but I am not sure if this would be applicable in our case?

I want to asynchronous update a specific graph only in specific bounds. It looks like only ScanAsync is awaitable (sidenote: via e.g. UniRx calling the method in a [micro]-coroutine and wrapping it inside an Observable). Is there any way to update async within bounds (e.g. inside of a coroutine)?


#2

Hi

Currently this is not possible.
Grid graph updates do in any case have to run on the main thread. Is it the frame-rate loss that you want to avoid? I.e you want to spread the update out over several frames to limit the fps drop?


#3

Exactly. We require a bit over 100 different agent radiuses and therefore the same number of Recast Graphs. We are not using A*PP in a game enviroment, and therefore our use-case is clearly different from what most people likely ever require.

To achieve our goal, we require a lot of control on when and what to update and want to use as much paralellization as possible.

Why do we want awaitable/async/coroutine updates? Because it allows as to async call the update on a few thousand different areas (e.g. 100 graphs x 100 small - compared to the whole graph - objects). We would like to be able to run those updates and join them with WhenAll. As soon as we are able to run the individual updates either via async or coroutine we are able to spread them over multiple frames and conver them to Observables via UniRx. From there on it is not relatively easy to work on sets of graph updates and join them via Observable.WhenAll and start the next batch of parallell computation and calculate new paths depending on the result of such a batch.

Why do we want bounded updates compared to the provided ScanGraphAsync? Because the individual graph occupation of changes is relatively small and does not happen frame to frame. Between those relatively small changes lie our heavy computations.

Why do we want single graph updates? Because of those 100 graphs we only require updates to subsets depending on the current state and results. Think of it figuratively as a DivideAndConquer approach from Merge-Sort for navigation problems. Every graph will require an update somewhere along the calculations.


#4

Whoa. 100 graphs? Are you sure you need all of those radiuses? Can’t you merge them together into a smaller number of groups?

If you are looking for a way to wait until the graph updates are finished you can use

AstarPath.FlushGraphUpdates()

See https://arongranberg.com/astar/docs/astarpath.html#FlushGraphUpdates

Currently updates on different recast graphs run in serial, not in parallel.
You could do a custom script for graph updates to make them run in parallel (this is not possible by default because different graph updates may interfere).

Essentially you have to do this:

List<GraphUpdateObject> graphUpdates = ...;
// Make sure pathfinding is paused when the graph updates run
var graphLock = AstarPath.active.PausePathfinding();

var graphs = AstarPath.active.astarData.graphs;
for (int i = 0; i < graphUpdates.Count; i++) {
	var update = graphUpdates[i];
	Queue<RecastGraph> recastGraphs = new Queue<RecastGraph>();
	for (int j = 0; j < graphs.Count; j++) {
		var graph = graphs[j] as RecastGraph;
		if (graph == null) continue;
		// SOme initialization code that needs to run on the Unity thread
		graph.UpdateAreaInit(update);
		recastGraphs.Enqueue(graph);
	}

	// Essentially a wrapper around a thread pool
	var workQueue = new ParallelWorkQueue(recastGraphs);
	workQueue.action = (RecastGraph graph, int threadIndex) => {
		graph.UpdateArea(graph, threadIndex);
	};

	// Report progress roughly every 50 milliseconds
	int progressTimeoutMillis = 50;
	foreach (var progress in workQueue.Run(progressTimeoutMillis)) {
		Debug.Log("Completed " + progress + " items");

		// You could yield here for example
		yield return null;
	}

	for (int j = 0; j < graphs.Count; j++) {
		var graph = graphs[j] as RecastGraph;
		if (graph == null) continue;

		// Some post-processing code that needs to run on the Unity thread
		graph.UpdateAreaPost(update);
	}
}

// Update some metadata required for pathfinding
AstarPath.active.FloodFill();
graphLock.release();

You will also have to make a minor modification to the RecastGraph to support this. I have posted the diff here: https://pastebin.com/1trDvgh7

I haven’t tested this code at all, but I think it should work for you. It will update all graphs in parallel with a single graph update object at a time (which if you have 100 graphs should be plenty of parallelization).

Note that the FloodFill call at the end may be relatively heavy in your case. So you do not want to do one of those for every single graph update if you can avoid it. If this method turns out to take a lot of time to execute, then there are some simple ways to disable that functionality with some simple code changes (but it has some effect on pathfinding if the goal of the path could not be reached, but this may not be important for you).