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:
- Large graph size local to player (1000x1000 - too large for procedural grid)
- Terrain is generated procedurally in chunks - really what we are trying to achieve is a guarantee that any loaded chunk has some path system
- Infinitely generated terrain/navmesh
- Ability to modify the graph (navmesh cutting looks perfect for what we want here)
Things that make these requirements easier:
- Graph doesn’t need to be precise everywhere - only close to the player
- 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 . 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 :).