3D pathfinding in Unity: octrees, A* and local avoidance explained

Why 3D is not 2D with an extra axis

Pathfinding on a plane is a solved, teachable problem: lay a grid or a navigation mesh over the walkable surface, run A* across it, smooth the result. Every part of that survives the move into three dimensions. What does not survive is the arithmetic.

A 100 × 100 metre level at one-metre resolution is ten thousand cells in 2D. Give it fifty metres of usable height and fill it with a uniform 3D grid, and it is five hundred thousand. Halve the cell size — because your agent has to fit through a half-metre gap — and a 2D grid grows by four, while a 3D grid grows by eight. Both the memory and the number of nodes A* has to look at follow that curve.

So the first question any volumetric navigation system answers is not “which search algorithm” — it is how do we avoid storing the empty sky at the resolution of the tight corridor. Everything below is downstream of that.

The second difference is more pleasant. On a surface there is exactly one way past an obstacle: around it. In a volume there are also over and under, which gives both the search and the collision-avoidance layer a freedom they do not have in the plane — and, as it turns out, fewer of the deadlocks that planar crowds are famous for.

Step 1 — turning space into something searchable

A search algorithm needs a graph. The job of this stage is to turn a continuous volume full of triangles into a finite set of nodes that are certainly free, plus the adjacency between them. The usual candidates:

• Uniform voxel grid — trivially simple, trivially indexed, and the arithmetic above kills it on anything larger than a room.
• Waypoint graph — hand-placed nodes and links. Cheap and completely controllable, but it is level design work that has to be redone every time the level changes, and agents can only ever travel where somebody drew a line.
• Tetrahedralisation of the free space — the volumetric analogue of a navigation mesh. Compact and elegant; the construction is fragile on the messy, self-intersecting, non-manifold geometry that real game scenes are made of.
• Sparse octree — recursive subdivision that only goes deep where something is there to describe. Robust against whatever geometry it is handed, and it never pays for empty volume at the resolution the tight places need. It is what Nav3D is built on, and the rest of this article follows that choice.

How an octree keeps the cost down

Start with one big cube over the region of interest. Subdivide a cell into eight children only if geometry actually occupies it and it has not yet hit its depth limit. A cell with nothing in it is never split: it stays whole and becomes a leaf — one node of the search graph, regardless of how large a piece of the world it covers.

The consequence is the whole point of the structure. Open sky is a handful of enormous nodes. A cluttered corner is many small ones. Resolution is spent exactly where movement is tight, and nowhere else. In Nav3D the tree is not even instantiated in parts of the world no obstacle reaches — empty regions hold no cells at all, only the knowledge that they are empty.

Free leaves record which other free leaves they touch, and that adjacency is the graph the pathfinder walks. It is also the part most worth being suspicious of in any implementation: neighbour links between cells of different sizes, maintained incrementally as the world changes, are where connectivity bugs live — a route that exists on screen but not in the graph, or worse, one that exists in the graph and passes through a wall.

One thing “free” does not mean on its own: roomy enough for a particular body. Occupancy is a geometric test — a cell is occupied when triangles cross it and free otherwise — so a free cell the size of a fist is still free. Fit is settled a level up, when the world is built: you declare the size range of the agents the world is for, and that, with the finest cell size, fixes how thick the resolved band of free space alongside a surface actually is. Ask for agents fatter than that band and no amount of searching will find them a way through — it was decided at construction.

Step 2 — searching a volume with A*

A* itself does not change. Keep a frontier of nodes ordered by (cost so far + estimated cost to the goal), pop the cheapest, expand its neighbours, stop when the goal comes off the frontier. Straight-line distance to the goal is the natural estimate in a volume, and paired with edge costs that are themselves straight-line distances it is not merely admissible but consistent — the triangle inequality sees to that — which is what lets the search close a node once and never have to reopen it.

What changes is what “expand its neighbours” should mean. Crossing two hundred metres of empty sky by hopping from cell to cell is arithmetic in service of nothing: in open space the answer is always a straight line, and a search that rediscovers that fact node by node is burning its budget on the easy part of the problem.

Two kinds of successor

Nav3D gives a node two different ways to have neighbours, and lets A* choose between them:

• Adjacent free cells — the ordinary graph edges. This is how a route negotiates its way around, over or through a piece of geometry, and it only matters near geometry, because that is the only place the tree is subdivided.
• A straight shot toward the goal — offered by a cell that sits on the boundary of a subdivided region and whose face toward the goal opens onto open space. If the line to the goal is clear, that single edge ends the search. If something is in the way, the edge instead delivers the route to the last free cell before that obstacle, where the neighbour edges take over.

Both kinds sit on the same frontier and are priced the same way, so the algorithm never branches on “am I in open space or not”. Open volumes cost almost nothing; detail is paid for only around obstacles. And because leaving an obstacle is just another edge competing on cost, the point at which a route breaks away and heads for the goal is chosen across the whole search rather than fixed in advance.

That last property is worth dwelling on, because it is the usual failure of a hand-rolled system. It is tempting to march a straight line, and whenever it hits something, run a local search from where the line entered the obstacle to where it left. That is a different problem: it fixes the exit before it knows what the detour costs, and the answer it produces is locally reasonable and globally wrong — most visibly when the cheap way past something is to go over the top rather than to rejoin the original line.

Worth stating precisely, because it is routinely overstated: what comes back is the cheapest route through the graph the octree defines. That is not the same thing as the shortest collision-free curve through the continuous scene — no discretisation can promise that, and the gap between the two is exactly what the resolution setting buys or gives away.

Step 3 — from a graph path to a flight line

Whatever the search returns is a chain of cell centres. It is a valid route through free space and it looks terrible: stair-stepped, visibly aligned to the tree, with right-angle corners no bird or aircraft would ever fly. Post-processing turns it into a trajectory, in two passes whose order matters.

• Shortening — walk the chain and drop any waypoint that can be skipped: if the segment from the point before it to the point after it does not touch occupied space, the middle point was an artefact of the grid, not of the world. It is the volumetric analogue of the line-of-sight “string pulling” a navigation mesh applies inside its corridor — greedier than the funnel algorithm proper, and it removes most of the staircase.
• Smoothing — run a Catmull-Rom spline through the survivors so the route bends instead of turning. Corners get extra control points first, at the finest cell size, so that a tight turn has enough of them to curve rather than being cut across.

Doing it the other way round — bending first, then trying to shorten — moves the curve much further from the original chain, because the stair-step corners it is bending through are exactly the points that were about to be deleted. Shorten, then bend.

And then check. This is the step that is easy to skip and expensive to skip: a spline drawn through collision-free points is not itself collision-free. A cubic curve overshoots on the outside of a turn, and what it overshoots into is precisely the corner the route was hugging. So every generated sample is tested against occupied space, and wherever a stretch of curve would cross something, extra control points are inserted there and that stretch is drawn again — tighter, closer to the polyline it came from. What reaches the agent is a curve that has been argued with, not one assumed to be safe because its control points were.

Step 4 — the other agents

A path is a plan against a static world. It says nothing about the forty other agents converging on the same gap, and re-planning is far too slow to be the answer — the situation changes every frame. This is a separate problem, solved separately, every tick: local avoidance.

A well-established answer, in the plane and in the volume alike, is ORCA — optimal reciprocal collision avoidance. The idea in one paragraph: for each nearby neighbour, the set of relative velocities that would lead to a collision forms a cone — truncated, because you look a fixed few seconds ahead and a collision beyond that horizon is not yet your problem. ORCA turns that cone into a single linear constraint on my velocity — a half-space of velocities I may still choose — with each of the two parties taking half of the correction. Every neighbour contributes one such half-space, while my own maximum speed bounds the whole feasible set to a ball, and I then pick the velocity closest to the one my path asked for that lies inside all of it. That is a small linear program, solved once per agent per tick.

The elegant part is that nobody communicates. Both agents in a pair see the same relative position and the same relative velocity, both take their half, and the two independently-computed answers are compatible by construction. Static geometry joins the same picture as constraints of its own: a nearby surface says “do not approach me faster than the clearance between us allows”.

With one condition attached, and it is the condition every crowd eventually violates: the guarantee holds while some velocity satisfies every constraint at once. Pack agents tightly enough and none does — the half-spaces stop having common ground. At that point the promise lapses and the solver is choosing the least-bad velocity rather than a safe one, which is where implementations differ from one another and where the character of a dense crowd is really decided.

What the third dimension changes

In the plane, each constraint cuts the velocity plane in half, and the resolutions available are left, right and slower. In a volume, each constraint cuts velocity space in half, and an entire family of solutions appears that has no planar equivalent: up and over. Two agents on a head-on course in a corridor can settle it by one taking the high line. A crowd funnelling through a single opening spreads into a cone rather than a queue.

The rule is identical; the solution space is larger. Where there is genuinely room to manoeuvre vertically, that shows up as fewer standoffs, less of the side-to-side jitter planar avoidance produces in tight places, and crowds that read as flocks rather than as traffic. In a corridor with a ceiling on it the extra freedom is not there to be used, and neither is the benefit.

Step 5 — keeping it true while the world moves

Everything above describes a static scene, and a static scene can be baked: build the tree once, serialise it, and load it in a fraction of the time a rebuild would take. Real levels are not static. A door opens, a structure collapses, a freighter parks in the lane, an asteroid drifts across the route.

Three things have to happen, and each is harder than it sounds:

• Rebuild only what changed. The volume the obstacle touched has to be re-subdivided against the new geometry — and, when the obstacle leaves, coarsened back. Rebuilding the whole tree is correct and unusable; rebuilding a patch is fast and is where the connectivity bugs come from.
• Publish it atomically. Searches run on worker threads while this is going on. A rebuilt region has to become visible to them in one step, never half-updated, or a path is planned across a graph that never existed.
• Work out who cares. Only the agents whose routes cross the changed volume need re-planning. Nav3D keeps the live paths in a spatial index for exactly this, so an obstacle appearing in one corner of the map does not cost anything to the agents flying in another.

What adaptive resolution buys

One number governs the memory and the bake time of the whole system: the smallest cell the tree is allowed to produce. It also governs what your agents can fit through, so it is under permanent pressure from both sides — and every step finer deepens the tree along every surface in the world, including the thousands of square metres of surface nothing will ever fly near.

Which is the argument for making it local rather than global. A resolution region is a box with its own minimum cell size: inside it the tree keeps subdividing, outside it stops at the base resolution. The hangar interior, the canyon, the docking bay get the detail they need; the square kilometres of open sky around them do not pay for it. On a large map that is the difference between a bake you can ship and one you cannot.

Where the frame time actually goes

Worth being precise about, because the marketing shorthand in this category (“multithreaded, so navigation is free”) is not true of any system and is not true of this one.

The expensive, bursty work — searches, and the octree rebuilds that a moving obstacle triggers — runs on worker threads. It is asynchronous by nature: baking a large scene is seconds, not milliseconds, so those operations report progress and can be cancelled rather than pretending to be instant.

The per-tick work — avoidance and agent stepping — runs on the main thread, deliberately. Each agent-tick is small, and handing thousands of tiny independent jobs to a scheduler costs about as much as doing them; that trade only turns over at agent counts most games never reach. So navigation does spend frame time. The design decides which part of it does, not whether any of it does.

If you are building this yourself

A sparse octree and an A* over its free leaves is a weekend, and it is a genuinely good weekend — if you want to understand the problem, build that. Everything in this article up to the end of step 2 is within reach of one person and a clear head.

The months are in the rest: incremental rebuilds that stay correct in both directions; publishing a rebuilt region to searches that are already running; neighbour links between cells of different sizes that never lie; an avoidance solver that still returns something sensible when agents are packed tighter than the constraints allow; smoothing that is validated against the geometry rather than trusted; a serialised format so that levels load rather than bake. Every one of those is tractable in isolation, and every one of them is a class of bug that only shows up at scale, in someone else’s scene, a week before a milestone.

That is a legitimate thing to build — plenty of studios have. It is also, precisely, what Nav3D is.

Further reading

• Nav3D vs Unity NavMesh — the same material as a decision, including where NavMesh is the right answer
• Can a NavMeshAgent fly? — the five NavMesh-side workarounds and their range of validity
• Flying AI pathfinding for Unity — capability, setup and per-agent tuning
• Nav3D documentation — the agent API, the obstacle types and every setting named above
• Nav3D on Unity Discussions — questions about the mechanism are welcome there, buying something is not a prerequisite