#How do I get hundreds of NavMeshAgents to follow the player without bunching up?

1 messages · Page 1 of 1 (latest)

austere spire
#

I have a couple hundred NavMeshAgents that can follow the player. When they follow the player, they're all focusing on a single point, which gets messy to say the least. If the player stands still, they all bunch up into one blob, a blob that sends the player through the ground when touched. They also bunch up when moving if the player is far, since the paths all converge, so they clump up in transit. I want to avoid the bunching up, but have been struggling to find a method that doesn't have issues.

I started with the NavMeshAgent solutions first. I tried setting the distance tolerance higher, but this ends up with agents however far from the player, and bunching up on the border. I've also tried using the natural avoidance on the agents, setting the avoidance priority randomly. With this many agents though, it ends up doing nothing, and they still bunch up

I tried a boid system, but it doesn't seem to work too well for anything slightly more complex than a bird or a fish. I'm mostly using separation. Cohesion and alignment clash way too much with the NavAgents, and isn't really applicable anyways. I'm calling NavAgent.move() with the separation vector. It does work pretty well when they're in motion, but not so much when they get close to their destination. The agent and boid components clash, with agents trying to clump up, and boids trying to separate. The boids system also makes things pretty slow, even though I'm using 2d spatial hashing for finding neighbors

#

The method I've put the most time into has been a slot based system. I generate Fibonacci spiral slots around the player, updating slot positions each frame. Then each follower when close enough will request a slot to follow instead, calculating utility based on angle of approach and proximity to player. This has about a hundred problems, a new one popping up constantly. Latest problem being with any surface that isn't flat. Since the slots are the same height as the player, they can often be too far above or below the navmesh for agents to find. I did try sampling against the navmesh, which worked but was incredibly slow. I sampled against the terrain, which worked until there was any surface that wasn't terrain. The whole system is just laggy too because of how many constant calculations there are

I'm mostly at a loss at this point. I am new to NavMeshAgents, but they weren't complicated until I had hundreds of them. I don't know how to fix my issues. All I want is a bunch of followers that don't turn into an eldritch blob every chance they get. Is there a design pattern or sort of implementation that I can look into to accomplish what I'm wanting?

calm hamlet
#

Consider navmesh navigation as extremely dumb. Don't let it get into a situation where agents would overlap in the first place(at least when stationary).

austere spire
eternal sequoia
#

I can’t remember how much you get on the free tier

#

But it’s quite good

#

Try the astar path finding project

#

Otherwise you could try almost a boid-like approach

#

Where the agents rotate their direction of movement away from other nearby agents

#

Well, I suppose you do actually essentially want a boid actually

#

So maybe look into those

#

I’ve had a lot of success with 50-100ish things in a similar fashion with custom coded movement that I used with that approach for following the player, but they went through walls so it’s obviously a bit harder when you actually need them to pathfind

deep island
calm hamlet
austere spire
# calm hamlet Then debug your solution. What exactly didn't work well and why? As for performa...

I mentioned one of the reasons it didn't work. Having any verticality breaks it. Having any obstacles breaks it. The player moving too much breaks it. It doesn't even look good. I've optimized what I do have like crazy, and it's still laggy. The only ways I can imagine fixing it will increase the lag ten fold. It seems like I'm just using a poor solution. Seems you have a better solution in mind?

calm hamlet
#

Seems you have a better solution in mind?
Just like everyone else suggested - a boids like avoidance system.

Not sure what you mean by verticality. Navmesh is inherintly 2d navigation system(in the sense that the agents arem moving along the surface plane). If you need something like flying enemies, navigation entirely in 3d space, that would require a completely different approach or some faking.
"player moving too much breaks it", "doesn't look good", "still laggy", all sound like issues that can be fixed and debugger. If you need help with that you'll need to provide more details on what you actually have.

austere spire
#

I did already try a boids system. In general, it seems boids are meant for birds and fish, not anything that needs slight complexity. They fight with the navigation system. If I were to forgo automatic navmesh movement and opt to control transform movement entirely via the boids system, it seems it would still fight with itself. Its target is in one direction, but boid calculations want to push it in another. And I'd have to reimplement some navmesh features if I decide to not use its movement

The verticality issue I addressed in my main post. Player is on a slope. Slots are the height of the player. So now half of all slots are above ground, half are below, meaning agents can't navigate to them, and the path fails. I tried instead sampling the nearest navmesh position, but doing this is expensive, and ends up with slots overlapping on navmesh boundaries. I can sample terrain height, but it doesn't account for anything on top of the terrain.

The slot system is laggy because I have each agent finding the best slot for it, which is an n^2ish problem. I have made the searching more efficient so realistically each agent is only evaluating a handful of slots, but it still explodes in complexity fast.

If I don't have each agent evaluate a best slot, it looks bad because an agent can decide to pick a slot on the opposite end of the player. Since the slots move with the player, so do the agents. Even though they're already close. I tried fixing this by have slots lag behind the player a bit, but it still doesn't look great.

It's hundreds of agents doing calculations for hundreds of slots and all neighboring agents. It gets laggy fast with increasing amounts of agents

If boids is the way to go, is there a better way to implement it? I don't know how to make something that doesn't fall apart in some way

calm hamlet
# austere spire I did already try a boids system. In general, it seems boids are meant for birds...

Boids is just a concept that represents balancing of different forces or drives to determine the desired object velocity. Or position. If done correctly, your agents should stabilize without colliding.
As for fighting with the navigation system, I mentioned several times that your system needs to be on top and treat navmesh agent as a backend that moves the agent to resolved positions.

Regarding the verticallity issue, you don't really have a way but to sample a closest point on the navmesh, or trace vertically to find the closest surface point along the y axis. There's no going around it. Any solution I can think of would require doing that.
You should check if it's possible to sample the navmesh via jobs or on background threads. If not, then all you can do is optimize the sampling itself(by tweaking the call parameters), or split the work over several frames.

I can't say anything about your slots system optimization without seeing the implementation, but it sounds like "slot selecting" is kind of a redundant step that could be avoided.

And ultimately, yes. There would be a performance limitation of a somewhat complex system at scale. If nothing works, might want to consider dots(ecs or jobs and maybe burst) for your navigation system specifically.

foggy swan
#

I dont think you can do any navmesh stuff off main thread in Unity. Two cool peeps had to made a mod for lethal company that adds that by reverse engineering some of the c++ end for that specific unity version. Although I have seen a couple posts online talking about how you can do some of the work yourself in jobs etc. then pass it into the navmesh stuff in ways that reduce how much the main thread actually has to do

austere spire
#

Right now I am using a resolved position and telling the nav agent to move to that resolved position. Via the slots. I generate available slots around the player, then have those move with the player. If I don't have slot selection, then the slots will fill up in the order created. So filling in a spiral, which doesn't look right.

If I don't do that but instead rely completely on boids, how would I make that work? I can calculate the desired position from boids, but how would I get them to actually pathfind to the target? Would I have to calculate a path, then use the direction of the next point as part of the boid calculations before finally setting the destination to be that calculated point?

I could give this a shot tomorrow, but seems like that's calculating paths twice per agent per frame, on top of the other boid calculations unless I'm thinking the wrong way. And let's say I have a target distance of within 1 unit of the player, but so many agents that the farthest can only get 5 units away. Would this still resolve at the edge, or would I see the agent moving back and forth?

I did spent some time today just researching dots, and this might be a way to make things a lot quicker. Jobs and burst for sure. Ecs doesn't seem to have the best integration with NavAgents/navmeshes as far as I can tell, but I need to look into that more