How to handle large amounts of NavigationAgents / pathfinding?

Lethn

I'd like to collaborate on this a bit because this is something I've been thinking about a lot, it seems likely we're both going to have to learn multi-threading in Godot for the examples you're talking about as I'd like to have a bunch of villagers all on the same island wondering about and playing animations.

https://docs.godotengine.org/en/stable/tutorials/performance/threads/using_multiple_threads.html

Apparently Godot 4 will have features put in to deal with this better but as always coding knowledge on this will go a long way, do let me know if you come across anything. I think I know exactly the type of game you're probably going for.

Lightsheik

Lethn I've been doing some research and I don't know if the navigation server is meant to handle that many agents. What I did find however is that there is a concept called flowfield or vector fields in which you create a grid in which you calculate all shortest path to your target from all the squares on the grid and then you basically assign a vector to it. Once a unit is on a certain square, it does not have to calculate the next path, it only has to move in the direction of the precalculated vector. I am currently trying to figure out how to implement it but I'm far from being an expert at coding.

I did see videos of unity nav mesh system handling many agents and still having good performances so I'm not quite ready to give up on the Godot navigation system just yet, but knowing Godot is still early in its development I'm afraid that the performance I'm looking for might not be achievable with the navmesh system in the near future, even with threading. Not even sure if flowfields can do it either to be honest. Maybe GDScript is too slow for this kind of thing and we have to create a GDExtension to take care of it.

My specs are:
CPU: Intel i5-12600k
GPU: RTX2080
RAM: 32 GB

Lethn

You should also post your exact specs so we know what you're working with, here's mine:

CPU: AMD Ryzen 5 2600
Graphics Card: Nvidia GeForce GTX 1660 Super 8GB Asus
RAM: 16GB

MagickPanda

There is an option in 4.0, which could enable Physics frame to run at a dedicated thread, but the drawback is all physics related stuff need to be called inside _physics_process function.

In RTS the path-planning is limited to 'max calls per second', you can't just let all units to plan a path in one frame immediately, instead, you need a data structure to store and queue them and limit path-planning per second to an acceptable interval, w/o too much impact on CPU frame time.

Lightsheik

MagickPanda How would someone go about limiting or queuing the calls? I tried putting the get_next_lcoation() on a timer because I thought maybe it would have that effect but it makes the agents act crazy and stutter.

MagickPanda

Lightsheik

You need to limit number of movement update or move 'order' per a fixed interval, some pseudo code:

const MAX_PATHFINDING = 30 # max pathfinding request per frame
const MIN_RECALC = 300 # in ms

var last_stamp = -1


func move(delta):
        var curr_stamp = get_current_engine_time_in_ms()
        if last_stamp < 0:
          last_stamp = curr_stamp 
       
        var elapsed =  curr_stamp - last_stamp
        if elapsed  >= MIN_RECALC:
	   nav_agent.set_target_location(destination)
           global_count  += 1
	velocity = translation.direction_to(nav_agent.get_next_location()) * speed
	self.translation += velocity * d

#in other script
var global_count = 0

func update_unit_moves(delta):
  global_count = 0
  for u in units:
     u.move(delta)

Lightsheik

MagickPanda

Oh my god..... I see it now... I was calling set_target_location at every physics frame, recalculating the whole nav path every time. I feel so dumb lol now everything works so smoothly! Thanks for your help! Now I can run a few thousands agents at a time with no frame drop! Batching the nav path calculation should allow me to go even higher.

Thanks a lot for your help, I appreciate it!

Lethn

Lightsheik I feel like it's also worth pointing out that the 3.5 version of the navmesh agent has some very helpful built in signals to have things calculate once the agent's path is finished or it's reached a point in the path so you may want to try experimenting with that as well for optimisation, the signals in Godot are very useful once you get used to how they work and they cut out a lot of reliance on using physics process for everything.

Lightsheik

Lethn As of now performance don't seem to be too much of an issue. I've had 2000 agents pathfinding at the same time and FPS were at 140 with no drops.

My concern now is avoidance behaviour but that's another story completely. The builtin system doesn't seem to be that great when working with crowds in close quarters so I might have to figure out a custom way of doing it. Would you happen to know good resources on this subject?

Lethn

Lightsheik Not on obstacle avoidance specifically know but I do know that there's a radius setting for the navmesh agent so it could be worth doing some tweaks on that for avoidance, you can also tweak the amount of times the agent calculates for a path I believe in the settings as well. For me it's been dealing with the accuracy of the damn navmesh baking, I've just found out that for some bizarre reason when I directly create a navigation mesh from my custom landscape that I've brought in from blender all of a sudden it bakes perfectly yet when I make a navmesh child by itself and then bake that to the landscape that's where I've run into tons of problems.

Alternatively, I've seen examples in 2D but even 3D does this where they use raycasts to detect obstacles around an agent and that's firing off constantly to have the avoidance be more accurate, might be worth tweaking the built in settings first though before any of that. Using raycasts to make vehicle AI 'see' in front of themselves is a very common trick.

Lightsheik

Lethn Should have specified, I meant avoidance of other agents. But yeah the agents don't seem to follow the navmesh perfectly and will clip through walls when rounding corners, even when the agent size setting is set above its actual size and rebaked the mesh. I don't know if the problem is with the navmesh itself or the agents. I tried many different settings combination but it's still not great. If I can't figure out a good way of making them behave nicely I might just try implementing flowfields instead. All the examples I've seen online seems to be working a lot better than what I've been achieving with the Navigation Server. But at the same time I feel like there is something I'm doing wrong...

I also tried using CharacterBody3D with move_and_slide but for some reason it still clips through walls and on top of that performance drops significantly. I wish there was an easy way of forcing the agents to remain on the navmesh and forcing other agents avoidance behaviour to compensate for that instead of pushing other agents through walls. I might have to code agent avoidance myself, maybe using raycast like you suggested.

Timmy_theBarbarian

If the problem is that when they bunch up is making them act silly then I suggest adding a collision shape as a child of the root node that your agent is on, then allocate a collision layer specifically for that specific unit type's collision with each other, and have the layer and mask for that layer set to true on the agent's parent.

This makes it so they don't overlap. they bunch up. make the collision shape a circle and half the diameter of the width of the agent's sprite. this makes them half overlap each other and actually looks pretty cool.

As far as path finding being jittery due to multiple agents interacting with each other I'd remove their ability to consider eachother's positions and bodies in your pathfinding. just have them barrel at their target. the collision layer implementation I suggested makes them bunch up nice like a little hoard all respectfully trying to reach their destinations.

after that the focus would be fixing the wall clipping. I have no fixed this yet.

I still haven't found how to make nav agents work properly in Godot 4 yet and I too am making a game with potential for MANY agents chasing the player through winding environments.

Ill post any findings I have in the future.

hope this is helpful.

Im using TileMap nav painting for my navmesh.

Mackbook air m1
16 GB ram