Are large dynamic worlds with multi level constructions possible with this project?

General
1

I have been trying for a while now to get a suitable path finding solution that covers my idea.

The world has an adjustable height map terrain and then the player can build walls, stairs, ramps, floors, etc however they want. So a wall will block an area but allow something to walk on top of it. AI Units then live in said world. The world will be no larger than 2048x2048 tiles, and no higher than 255.

So I need a dynamic path map that supports multi level. The player may build houses like the Sims, or bridges, tunnels, fun houses, all sorts of weird shapes are potentially possible.

I currently do it with an odd method of what tiles can be deemed walkable and then having connecting path pieces to connect multiple height levels (like stairs).

It works but it is slow to path find on. However, other solutions I find are either baked/static or -very- slow to update dynamically.

Is this possible with any of the A* implementations in this package? The world is not procedural but it is highly dynamic. Changes won’t happen constantly though (no moving obstacles, just things being placed/removed).

I have tried the free demo package and none of them seem to deal with adding/removing obstacles at run time AND using multi level.

2

Hi

You either have to use a layered grid graph or a recast graph.
However since your world seems to be quite large, I would recommend a recast graph.
If you use tiling on your recast graph (where the tiles are relatively small), you can update only a single tile when anything inside it changes. The update will be offloaded to a separate thread, but it might still cause some lag. If you find that it does cause lag, you can modify a setting which is not exposed in the editor yet, right before the line which says

graphUpdateThread.Start()

in AstarPath.Awake add this line

graphUpdateThread.Priority = System.Threading.ThreadPriority.Lowest; // Or just BelowNormal

That will make the latency between the graph update and when the update is complete higher, but it will cause a smaller fps drop.
I cannot guarantee that this will work satisfactory, but I think there is a good probability that it will.

Both recast graphs and layered grid graphs are only available in the pro version.

3

Hey, thanks for the reply.

Will the recast graph work with multi layer, like multi-level houses for example? And how many agents do you think it would support?

As it’s pro only, I’'d need to be sure it’s suitable before purchasing! Though it is tempting as I have been going round in circles trying to do it myself.

4

Yes, recast graphs can handle multi-level environments.

It’s impossible to say how many agents it will support as it depends a lot on

  • Graph size and complexity
  • Average path length
  • Agent repath rate
  • And a few other factors

That said, recast graphs are usually faster than grid graphs and I have seen users use it with very large worlds (like 8*8 km)

5

Okay, that makes sense. I poked around in the docs and Recast graphs look really useful.

Regarding the updates happening on a thread - Do the agents carry on following a technically now impossible path? Or do the agents automatically handle things like their current path being blocked and re-pathing? I noticed it says it does it off level geometry which sounds crazy expensive in terms of recalculation? Currently, I use ‘close enough’ estimations using primitive colliders for everything to reduce cost - I assume there’s a config setting to use those over the level geometry?

Sorry for all the questions, trying to decide if this is what I need or not.

6

The included movement scripts automatically recalculate their paths regularly.
Yes there is an option to use colliders instead of meshes.