NavMesh, A* and flow fields: 200 agents without the jam

Two hundred agents stuck at one gate

Late last year I was working on a siege scene: one castle gate and 200 NavMeshAgent instances running at it. Navigation in game AI falls apart in exactly this kind of scene. The recording QA attached to the nightly build always froze at the same spot: fifteen metres short of the gate, around sixty agents were grinding against each other and shivering, some of them walking backwards. In the first ten seconds only about forty of them made it into the courtyard behind the gate.

Frame time was 11 ms while the agents were far away and climbed to 26 ms as they closed on the gate. My first guess was that A* had blown up. The profiler disagreed: NavMesh.CalculatePath summed to 3,2 ms while NavMeshAgent's own internal update sat at 9,8 ms. So the bottleneck was not in the search, it was in the work each agent does every frame.

Two separate problems were showing up at once and had been mistaken for one: the cost of computing the global path, and how the agents behave relative to each other. Any discussion that files those under a single heading stalls, because the fixes live in completely different places. Until you separate them you can never tell which knob moved which number. For us the split started with one habit: tracking the search line and the agent-update line separately in the profiler.

Where the NavMesh actually looks

A NavMesh is a triangle mesh baked from the walkable surface of your scene, pulled in from every edge by the agent radius. The area an agent can walk on is not the floor you see in the viewport. When a stuck-agent report lands, the first thing to do is make the mesh visible in the Navigation window and measure how many centimetres of corridor actually survive at the door threshold. With the default Voxel Size of 0,166 m I have watched individual polygons vanish at tight corners more than once.

Our gate opening was 1,6 m and Agent Radius was 0,5 m, leaving a single 0,6 m lane: one agent fits, two do not. Dropping the radius to 0,35 looked like the easy fix, but it let agents clip into walls across the whole map. Widening the gate to 2,4 m on the level side was the correct change. Agent radius is not a cosmetic setting; it is the base unit of your entire navigation.

The second classic trap is a destination that sits off the mesh. SetDestination returns false in that case and nobody checks the return value, or the path arrives as NavMeshPathStatus.PathPartial, so the agent walks to the nearest reachable point and waits there. From the outside that reads as "stuck". Snapping every destination onto the mesh with NavMesh.SamplePosition within a 2 m radius closed most of those reports. Apply the same check to spawn points; an agent born off the mesh is lost from its first frame.

Discontinuities such as stairs, gaps and doorways need off-mesh links. Hand-placed OffMeshLink components behave far more predictably than auto-generated ones. With the default cost of 1.0, 140 of our 200 agents tried to funnel through a single 1,2 m gap; setting costOverride to 5.0 pushed most of them onto the longer but open route. Keep both ends of a link on the mesh; a link with one end hanging in the air is silently ignored.

The cost of A* and hierarchical pathfinding

A* pathfinding cost scales with the number of nodes it expands. On a 41.000-polygon NavMesh, one request from one end of the map to the other took 0,35 ms. Two hundred agents asking in the same frame would be 70 ms, but you never see a hitch like that: Unity queues the requests, the path arrives three or four frames late, and the agents keep running the old heading meanwhile. The symptom is not a stall, it is a late turn.

Hierarchical pathfinding cuts that cost in half twice over. You split the map into regions and write the transitions between them into a portal graph; the search runs first on a coarse graph of 30-40 nodes (0,02 ms), then a detailed A* runs only as far as the next portal. Our average request dropped from 0,35 ms to 0,06 ms, and a full agent path was never computed in one go again. The coarse graph is built once at bake time and only updated at runtime when a dynamic obstacle closes a portal.

The alternative we tried and dropped was a shared path cache. We rounded destinations to 4 m cells and handed one path to every agent heading for the same cell. Hit rate was 70% against static targets but fell to 18% while chasing the player, and the invalidation logic gave back more than the cache saved. We deleted the code. Path sharing only earns its place where the destination holds still for tens of frames.

One flow field for the whole crowd

If 200 agents share a destination, running 200 separate searches makes no sense. A flow field runs a single cost propagation backwards from the goal, then writes into every cell a direction vector pointing at its cheapest neighbour. Ours was a 128x128 grid at 0,5 m per cell, and a full rebuild took 4,1 ms. The propagation fills every cell in one pass, so the cost is entirely independent of how many agents you have.

What matters is that the 4,1 ms is paid when the goal cell changes, not every frame. While the player was running that happened three or four times a second, so roughly 14 ms per second. Per-agent cost collapses to two bilinear samples: 0,004 ms, or 0,8 ms across 200 agents. The same crowd cost 12 ms through hierarchical A*.

The limit is sharp: every distinct destination means another field. Past three or four goals, memory and rebuild cost overtake A*. So we stayed hybrid, with named NPCs and boss agents on A* and the crowd simulation on the flow field. Both stand on the same NavMesh triangles; only the source of the heading differs. The split lives in a single bool in code, and a designer can flip it on the prefab.

Local avoidance is not global navigation

RVO, and ORCA that derives from it, does one thing: each agent reads the position and velocity of its neighbours, cuts away the velocities that lead to a collision using half-planes, and picks whatever is closest to its preferred velocity in what remains. Its horizon is a second or two and it knows nothing about level geometry. It is a heading correction, not navigation. Leave an agent alone with it and RVO will never take it to the goal.

That is why expecting a global solution from local avoidance is wrong from the start. Against a U-shaped courtyard wall, RVO pins the agent to the wall and two agents meeting head-on deadlock. Setting obstacleAvoidanceType to HighQuality does not fix it; it just eats 6,2 of the 9,8 ms across 200 agents. Dropping to Good brought that to 3,9 ms with no difference visible at camera distance.

The real win was in the avoidancePriority field. With every agent on the default value of 50, the situation stays symmetric and nobody yields. Handing out a random priority between 0 and 99 at spawn cut the jam at the gate from 4,2 seconds to 1,1 seconds. It was a one-line change.

Dynamic obstacles and the path request budget

Dynamic obstacles use NavMeshObstacle with carving, but carving re-bakes the tile on every move. With 12 rolling barrels in the scene we were seeing regular 5,8 ms spikes. Raising carvingMoveThreshold to 0,5 m and enabling carveOnlyStationary brought the same scene down to 0,9 ms. Never make a continuously moving thing an obstacle; those belong to local avoidance.

The budget part is simple: fix the number of full path requests allowed per frame. Ours is 12. Agents ask on a 0,45 second interval plus a random 0-0,15 second offset, because without that jitter the spawn wave lands every request in the same frame. When the budget is full the request is not cancelled, it slides to the next frame, and nobody notices because the agent keeps walking its existing path in the meantime. Measure that budget on your target hardware; the 12 we use on console sits comfortably at 30 on desktop.

In this scene total frame time went from 26 ms to 13,4 ms and pathfinding's share from 13 ms to 2,1 ms, and the cheapest win inside that was the one-line priority change. Order the work this way: verify the NavMesh geometry with your eyes first, then put a per-frame request budget in place, then move the crowd onto a flow field, and touch local avoidance settings last. Go in the reverse order and hours disappear into ORCA parameters while the 0,6 metre doorway stays exactly where it was. Do not change a setting you have not measured; every number here came out of the profiler, none of them out of a guess.