Infinite Procedurally Generated Graph

Beginner Questions
#1

Sorry for the long text dump - the TL;DR:

  • Trying to do pathfinding on large, procedural, infinite world with unknown (static) terrain
  • Considering:
    • Updating the entire recast graph (large) despite speed issues if there is a multithreading option
    • Using recast tiling if there is a way to expand the bounds (or have it be large enough it’s basically infinite from user perspective)
    • Using multiple recast graphs (per chunk)
    • Using multiple graphs (local recast graphs and distant point graphs)
    • Manually creating graph gradually per chunk

I’ve found many similar topics talking about different procedural generation problems/solutions but nothing matches explicitly what I’m trying to solve. I hope I get some guidance on where to start and what system might be best for what I’m trying to achieve.

Some high-level info about desired requirements:

  1. Large graph size local to player (1000x1000 - too large for procedural grid)
  2. Terrain is generated procedurally in chunks - really what we are trying to achieve is a guarantee that any loaded chunk has some path system
  3. Infinitely generated terrain/navmesh
  4. Ability to modify the graph (navmesh cutting looks perfect for what we want here)

Things that make these requirements easier:

  1. Graph doesn’t need to be precise everywhere - only close to the player
  2. Time is not a major concern - the player will be far enough away from the farthest chunk that it is ok if it takes a little while to load (up to maybe like 10sec? - not sure what exactly). It’s far more important the loading doesn’t affect framerate (which should be fine with the multithreading).

I’m new to the A* project, but did a quick test using AstarPath.active.ScanAsync(graph) (in a coroutine) which took ~2sec every call (no tweaking or anything - just a quick and dirty test). When I found this function I was thrilled because I thought all my problems were over, no need to post :grin:. Unfortunately, since it cannot guarantee consistent fps (and it completely tanks - dropping to <1 fps without gizmos) this doesn’t work (unless you have suggestions to make it more consistent?). I’d much rather extend that time to like 5sec and have the fps stay consistent but I’m not sure this would be possible without a major refactor of when scan yields control.

In all of the threads I’ve read, you consistently warn against using multiple graphs. Can I ask for some details why? It seems like it would fit this scenario perfectly where I’m loading chunks - is it really that difficult to connect them together? I’ve seen the solution to lots of people’s problems posts is to use the tiling features to dynamically load little by little. This makes me wonder what a maximum size could be for a tiled recast? I’m wondering if I can practically make it large enough that a player would never practically reach an edge (keeping in mind 1000x1000 could be traversed with no gameplay in <5min) - or at least only like once every hour. However, I imagine this would get into problems with floating-point precision at this scale?

Another solution I’m thinking about is manually generating the graph when creating chunks. However, my concern with this is losing the ability to do NavMesh cutting. Is it possible to manually create a NavMesh (of changing node size) and still have cutting? Or to do NavMesh cutting on a manually created graph?

One more point I want to ask about are point graphs. I think these could be a good solution for updating far away chunks and then having some other more accurate type (probably Recast mesh - for cutting). Would it be possible to connect these farther away point graphs to closer recast graphs?

As a small side note, there may be multiple players - but they will all be close enough to where they can be considered to be at one central location.

I’ve looked at the following posts, many of which seem super close to what I’m trying but are slightly different or won’t work for particular reasons (unless I’m wrong - in which case please tell me :D).

Some particular comments of note I found hopeful what I’m trying to do is possible:

This post, in particular, seems particularly promising: Procedural graph mover for RecastGraph - #6 by chanfort

Thanks for making this awesome package! I’ve just started getting my teeth into it but looks like it’s going to be a lot of fun to work with :).

1 Like
#2

Hi

I think a decent solution to this would be:

  1. Create a large recast graph where the bounding box is large enough to cover the whole playable area. I realize this is impossible for an infinite play area, but possibly you could update the graph in another way if the player goes too far away.
  2. Disable A* Inspector → Settings → Scan On Awake.
  3. When starting the game, set AstarPath.active.data.recastGraph.scanEmptyGraph = true. And then call AstarPath.active.Scan(). This will make it initialize the whole graph to just empty tiles.
  4. For all initial chunks (and subsequently when a new chunk is generated) you call AstarPath.active.UpdateGraphs(bounding box) with the bounding box of the new chunk(s). This will recalculate the recast tiles touching those chunks asynchronously.
  5. Use the beta version for best results, recast graph scanning has been rewritten to use burst and is quite a lot faster.

You probably want to keep the player within 15000 world units from the origin to avoid floating point precision issues. It is possible to move an existing recast graph using NavmeshBase - A* Pathfinding Project

Yes. A recast graph requires knowledge about some parts outside the graph to be able to generate the edge properly. So you cannot scan one graph for a single chunk independently, it will need to take its neighbours into account. Anyway, the tile solution mentioned above will take care of this.

Navmesh cutting on a manually created navmesh graph is possible.

#3

So with some basic testing this seems to work well. Without any optimization or tweaking of settings, it can maintain acceptable fps so I’m confident this will work down the line if I need to spend some time really getting it optimized. However, I doubt that level of detail will be necessary based off this initial stuff which is great!

A couple of follow-up questions:

Is this for precision? Like if we create a new graph far away from the origin have it calculate in local space and then use this to move before? So would we calculate in world space (because that’s where the mesh is?) and then transform? Or transform and then calculate? Just not sure how this fits in with the recast when calling updates on tiles.

I imagine we could do this by creating another large recast graph at runtime and switching when get close enough or something? Or is there a different way this could be done better? Like moving the original recast graph and moving the tiles forward (discarding ones that are now out of the bounds). Is that what you’re referring to with the calculation of moving an existing recast graph?

#4

Yeah. I am not sure if you’ll need that right now, but I thought it might be useful for you to know about.

Yeah, could work. The easiest solution is to just move the existing graph and the world back close to the origin and then re-scan the whole thing. But switching more gradually between the two graphs might be worth it if it takes a long time to re-scan the whole graph.