Procedural graph mover for RecastGraph

I am currently looking for a possibility to use RecastGraph in a similar way like it is done for ProceduralGridMover. I noticed that large grid graphs (i.e. 1000x1000) takes almost the same time to scan as grid graphs. However, I am not sure if I can scan just a few tiles of RecastGraph, which “appears” in camera horizon when camera moves. If I use AstarPath.active.Scan() it always scans all tiles rather than just these ones which I would need to generate in the direction where camera moves. Any tips?

Hi

Well, this is technically possible, but I don’t think you would want that because it would be very slow. Recast graphs are very slow to scan (check the scan time in the console), so I would not recommend it.

Ok, so I checked some numbers and here is how it calculates on my machine: 1000x1000 grid takes ~21000 ms while 1000x1000 voxels RecastGraph with 128 size tiles takes ~25000 ms, what was quite similar. Scanning the whole 4000x4000 voxels RecastGraph took me 228 seconds to complete, while grid graph didn’t allowed to chose such high resolution. I think there would be problems coming up with memory as 4000x4000 grids would take 16 million points, while RecastGraph looks much more friendly here :).

However, these 228 seconds may get reduced 3 times (a bit above 1 minute) if I would run scan only on relevant tiles. These 4000x4000 coverage contains 3x3 or 9 terrain chunks. As camera moves one way, when I reach the edge, I would need to bake tiles only for 3 new terrain chunks rather than for all 9 chunks. That would speed up a lot.

When talking about practical use I noticed that there are some games, which has very long “Loading next level” messages, so at the beginning I am thinking to letting players to experience that.

Another think is that camera and units are moving at finite speed, so there can be reasonable to run baking calculation slower in background, while player slowly moves its troop along the terrain. So as for a longer term I was thinking something like progressive graph scanning. At the moment when scan starts, the game freezes and player needs to wait until the scan is complete. I was thinking something like adding thread sleepers inside deepest threaded loops, something like this:
int j=0;
for(int i=0; i<n; i++){
// do calculations
j++;
if(j>500){
j = 0;
// for threads
thread.Sleep(50);
// for coroutines
// yield return WaitForSeconds(0.05f);
}
}
where every 500 iterations each thread (or coroutine) would sleep for 50 ms (depends on situation) allowing player to play at lower FPS rates…

However, back to original question, I am a bit confused about how to work properly with individual NavMeshTile’s, i.e. creating new ones, adding (removing) to the graph, shifting indices when bounds are changed, etc. So can somebody shed a bit more light here :sunny:

Hi

Just a question, is your world procedural or is it known beforehand?

It’s procedural, each terrain chunk is being calculated from perlin noises at runtime. I would start RecastGraph tile calculations just after perlin noises completes and terrain is ready.

P.S. my terrain calculations are based on this tutorial:
http://code-phi.com/infinite-terrain-generation-in-unity-3d/

It looks like I managed to work out at least partially the problem. The solution is quite complex, but I will try to explain.

  1. I used complete RecastGraph scan on all terrain tiles each time camera crosses tile boundaries. I tried to scan each tile individually as a new graph and only scan relevant tiles in the direction, where camera moves. However, even tiles were scanned and at the end merged onto final graph correctly, the scanning time is almost the same as the complete scan of all 9 terrain tiles.
  2. I reduced resolution that there would be 2000x2000 voxels and it takes about 20 seconds for scan to complete. This was quite good approach as my terrains are quite flat with large affective areas, so no high resolution is needed.
  3. I am duplicating and storing NavmeshTile arrays into a cache for previously scanned graphs in the case if player turns backwards. Then terrains are not scanned, but graphs are being loaded from this cache. So moving back and forth between tiles does requires to scan only once.
  4. If player moves extremely far, i.e. 10 tiles from the first one, NavmeshTile arrays cache is being unset to free up memory (otherwise it would only load more and more data if player would be moving infinitely far to one direction).
  5. As NavmeshGraphs contains very small amount of data compared to grid graphs, I can store large number of graphs in the cache.
  6. I managed to work out by using only public functions and variables, i.e. without changing the code. However, I needed to comment out one throw exception (“Trying to initialize a node when it is not safe to initialize any nodes…”) in line 1909 of AstarPath.cs, which was coming when I was using ReplaceTile() function to load tiles from cache.

As a result things work very nicely with my systems and I made a YouTube trailer of rider going to one direction over procedural terrain where RecastGraph is used on the top:

I continue to work on this to make it as a proper extension. However, I am still thinking about possibility to make scans progressively. i.e. that scans would be running with thread sleepers or coroutine waiters somewhere deep in voxelize or other heavy functions in order to bring seamless gameplay. As Navmeshes are memory friendly, it could probably be stored tens or hundreds of scanned graphs, eventually obtained by slowly scanning more distant chunks while player plays on a single terrain chunk. I think if times and speeds are well balanced, this could remove force scan latency completely.

Hi

Great that you managed to make it work! :smile:

You probably want to wrap the part that got the exception in

 AstarPath.RegisterSafeUpdate(() => {
      // Do stuff here
 }

To avoid interfering with pathfinding that could be running at the same time.

It is technically possible to run it in another thread. If you want to have a go at it, check out the UpdateArea method in the recast graph, much of that code could run without pathfinding being paused.