Pathfinding becomes expensive when the navigation representation describes the world at the same resolution everywhere.

That is manageable on a small two-dimensional grid. It becomes much less attractive in a genuinely three-dimensional space. A volume that is 256 cells wide, 256 cells deep, and 64 cells high contains more than four million cells before the search has expanded a single node. Most of those cells may describe empty air, yet they still consume memory and enlarge the graph.

An octree attacks the representation problem first. Instead of dividing the whole world into equally sized cells, it keeps large cells where the space is simple and subdivides only where more detail is needed. A hangar can become a handful of large navigable regions while the geometry around beams, doors, and machinery receives finer cells.

A* does not become a different algorithm. It simply searches a smaller, adaptive graph.

An adaptive octree turns open volume into a small navigation graph while retaining fine cells around obstacles.

Why a uniform 3D grid wastes work

A uniform grid has useful properties. Every cell has the same size, indexing is straightforward, and finding a neighbour is often a small coordinate calculation. Those advantages make grids a strong choice for tile maps and constrained tactical spaces.

The cost is that resolution is global. If a narrow doorway needs half-metre cells, the entire search volume pays for half-metre cells. Large open chambers, empty sky, and long tunnels are all represented with the same density as the doorway.

Doubling resolution along one axis doubles the cell count in two dimensions. In three dimensions it affects the volume. Halving the cell width can produce roughly eight times as many cells because twice as many cells are needed along each of the three axes.

That growth affects more than storage:

  • A* may place more nodes in its open and closed sets.
  • Building connectivity takes longer.
  • Dynamic obstacle updates touch more cells.
  • Per-cell clearance, cost, or tactical data consumes more memory.
  • Cache behaviour worsens when the search jumps through a large node set.

A better priority queue cannot erase a graph that is unnecessarily large. The strongest optimisation may be to stop creating so many equivalent nodes.

What an octree represents

An octree starts with one axis-aligned cube covering the navigable world. That cube is the root. When the root needs more detail, it is divided into eight equal children: lower and upper halves along the x, y, and z axes.

Each child can be divided again. The process continues until a cell is simple enough to keep or reaches the chosen minimum size.

For navigation, a node commonly receives one of three classifications:

  • Free: the volume can be traversed.
  • Blocked: the volume cannot be traversed.
  • Mixed: it contains both free space and obstacle geometry, so it may need subdivision.

Only the leaves matter to the final navigation graph. A large free leaf represents a large open volume. A cluster of small leaves represents detailed space near geometry. Blocked leaves are omitted from the traversable graph.

This gives the octree its main advantage: spatial resolution follows geometric complexity rather than world size.

The classification test must account for the moving agent, not only point occupancy. A cell that does not intersect a wall may still be too close to the wall for a wide drone. One practical method is to expand obstacles by the agent radius before classifying cells. Another is to store clearance and reject leaves or transitions that do not meet the current agent’s requirements.

The first method produces a graph tailored to one agent size. The second can support several sizes but makes queries and edge validation more involved.

The octree is not yet a pathfinding graph

Subdivision answers where free space exists. A pathfinder also needs connections.

Create a graph node for each traversable leaf, then connect leaves that share a passable boundary. This sounds simple until adjacent leaves have different sizes. One large leaf may touch four or sixteen smaller leaves across one face. A fixed six-neighbour lookup is no longer enough.

A robust edge-building pass needs to answer three questions:

  1. Do the leaf bounds touch on a face rather than only at an edge or corner?
  2. Does the shared face contain enough open area for the agent to cross?
  3. Is the movement valid under the game’s rules for slope, clearance, gravity, and direction?

For a flying agent, any clear shared face may be usable. A walking character usually needs a support surface, acceptable vertical change, and enough headroom. An underwater vehicle may need turning clearance in addition to body clearance.

This distinction matters because “3D pathfinding” covers very different movement models. An octree is a spatial representation, not permission to move freely in every direction.

Neighbour links can be built eagerly after the tree is generated or discovered lazily during search. Eager links make queries cheaper and easier to inspect, but rebuilding them can be expensive when the world changes. Lazy discovery reduces stored edges and can suit sparse queries, but neighbour lookup must be efficient or it simply moves the cost into A*.

Running A* over octree leaves

Once free leaves and valid transitions exist, ordinary A* can search them. The open set still prioritises the node with the smallest estimated total cost:

f(n) = g(n) + h(n)

g(n) is the cost paid from the start. h(n) estimates the cost from the current leaf to the goal.

For free-flying movement with distance-based costs, Euclidean distance between positions is an admissible heuristic. The simplest positions are leaf centres, but centre-to-centre costs can produce awkward routes when cell sizes differ. A route may enter a large cell near one corner and be charged as if it travelled through the centre.

There are several ways to improve this:

  • Keep leaf centres for the search, then smooth the resulting route.
  • Place transition portals on shared faces and evaluate movement between portals.
  • Estimate edge cost from the closest valid points on neighbouring cell bounds.
  • Use the centre graph only for the high-level route, then refine movement locally.

The centre-and-smooth approach is a useful starting point. Portal-based search is more precise, especially where large cells meet narrow passages, but it requires more geometry work.

If the heuristic never overestimates the remaining cost, A* retains its optimality guarantee relative to the graph it was given. That final phrase is important. A* can find the cheapest route through an imperfect octree graph and still produce a poor world-space path. Search quality cannot exceed representation quality.

For a fuller explanation of open sets, heuristics, and path reconstruction, see A* Pathfinding: A Practical Guide for Game Developers.

Where the speedup comes from

The useful comparison is not “octree lookup versus array lookup.” Array lookup will often be cheaper.

The octree wins when fewer nodes and edges compensate for more complicated spatial operations. A large free region that would occupy thousands of voxel cells may become one leaf. A* can cross that region in one graph step instead of expanding a wave through every voxel.

Suppose a warehouse contains open air around a few shelves and gantries. A dense voxel graph spends most of its memory proving that empty space is empty. An octree keeps large leaves in the clear volume and refines around shelf edges, the floor, and narrow routes. Search effort becomes concentrated around decisions rather than distance alone.

That does not mean the route should jump directly from the centre of one large cell to another. The graph route identifies a corridor of free leaves. A smoothing or portal pass then finds a better polyline through that corridor.

Three measurements usually reveal whether the representation is helping:

  • total traversable leaf count compared with uniform-grid cell count
  • nodes expanded per representative query
  • end-to-end query time, including neighbour discovery and smoothing

Memory use and rebuild time should be recorded as well. A fast query structure that takes too long to update may be unsuitable for a destructible world.

A practical build pipeline

A navigation octree can be built with a compact recursive process:

Build(cell, depth):
    occupancy = Classify(cell)

    if occupancy is Free:
        emit traversable leaf
        return

    if occupancy is Blocked:
        emit blocked leaf
        return

    if depth == maxDepth:
        apply conservative fallback
        return

    for each of the cell's eight children:
        Build(child, depth + 1)

The conservative fallback normally marks an unresolved mixed cell as blocked. That may remove valid space, but it prevents the pathfinder from routing an agent through geometry the representation could not resolve. If valid passages disappear, the correct response is to increase local resolution or improve classification rather than pretend the cell is free.

After subdivision:

  1. collect free leaves
  2. build or prepare neighbour lookup
  3. locate the leaves containing the start and goal
  4. run A* over free leaves
  5. reconstruct the leaf corridor
  6. convert the corridor to world-space points
  7. smooth the points while preserving collision clearance

Keeping these stages separate makes the system easier to profile. It also prevents an expensive smoothing pass from being blamed on the octree search itself.

Finding neighbours without scanning every leaf

The naive neighbour algorithm compares every leaf with every other leaf. It is easy to understand and becomes unusable as the leaf count grows.

The tree already contains the information needed for a better lookup. A face-neighbour query can move upward until it finds an ancestor with space across the requested face, step into the sibling on that side, then descend into children touching the opposite face. The result may be one leaf of the same size, one larger leaf, or a set of smaller leaves.

Another practical option is a hash map keyed by coordinates at the finest resolution. A leaf registers the range or boundary keys it occupies, and a face query retrieves candidates from adjacent keys. This spends extra memory to simplify lookup.

There is no universal winner. Tree-walking keeps the data structure self-contained. Spatial hashing can be easier to debug and faster for frequent queries. Eager adjacency is the simplest runtime option when the octree is mostly static.

Whichever method is chosen, neighbour results should be cached if repeated searches traverse the same static tree. Repeating the same hierarchical lookup for every agent throws away much of the benefit of preprocessing.

Searching leaf nodes directly is already adaptive, but the hierarchy can do more.

A coarse-to-fine pathfinder first finds a broad route through higher-level regions, then refines only the parts that need detail. This resembles hierarchical pathfinding on grids: solve the large-scale routing problem before spending time on local geometry.

One approach is to create entrances between sibling regions and search an abstract graph of those entrances. Another is to allow high-level free nodes to participate directly while mixed regions expose lower-level descendants.

The gain is largest in wide worlds with long routes. A path from one end of a space station to the other should not inspect every maintenance duct between them. The high-level search can choose a sequence of sectors, then detailed searches can connect the relevant entrances.

The tradeoff is complexity and path quality. Abstract edges need useful costs. If they ignore local congestion or narrow passages, the high-level route may choose a region that looks short but refines poorly. Start with free-leaf A*. Add another hierarchy only after profiles show that leaf-level searches are still too expensive.

Dynamic obstacles and partial rebuilding

Octrees are often described as ideal for dynamic worlds because branches can be updated independently. That is directionally true, not automatic.

When an obstacle changes, find the affected leaves, reclassify the overlapping region, split cells that became mixed, and attempt to merge sibling leaves that became uniformly free or blocked. Then repair adjacency around the changed boundary.

The merge rule is important. Eight sibling leaves with the same classification can collapse into their parent only if doing so preserves required metadata such as clearance, traversal cost, or ownership. Without merging, repeated edits gradually leave the tree over-subdivided.

Dynamic updates also introduce consistency problems. A query must not traverse half-rebuilt connectivity. Common solutions include:

  • rebuilding a small region synchronously before allowing new queries
  • swapping in an immutable rebuilt branch
  • versioning nodes and rejecting stale paths
  • queuing path requests until an update completes

Moving characters should rarely cause structural octree edits. Treating every NPC as permanent blocked geometry creates constant churn and can eliminate routes in crowded spaces. Use local avoidance, reservation systems, or time-aware planning for transient agents. Reserve octree updates for geometry or obstacles that remain relevant long enough to justify rebuilding navigation data.

Path smoothing is not optional polish

An adaptive graph often creates a more obvious need for smoothing than a uniform grid. Leaf centres can zigzag as the path crosses differently sized cells. The route is valid but may look mechanical and travel farther than necessary.

A simple string-pulling pass starts at one waypoint and tests whether a later waypoint can be reached directly. If the swept agent shape stays inside free space, intermediate points can be removed. Repeat until no more points can be skipped.

Use a volume cast or clearance-aware segment test rather than a zero-width ray. A ray can pass through a gap that the agent cannot.

For a corridor represented by shared face portals, a funnel-style algorithm can produce a cleaner path, although a general three-dimensional funnel is less straightforward than its navmesh counterpart. Many games use a simpler compromise: derive candidate points from portals, apply collision-aware shortcutting, and let steering handle small deviations.

Smoothing must use the same agent assumptions as graph construction. If the octree was built for a sphere with radius 0.5 metres, the shortcut test must not validate a centre line with no radius.

Traversal costs still matter

Fewer nodes do not mean all free space is equivalent.

A leaf can carry costs for slope, exposure, terrain, current, noise, or threat. Large leaves need care because one value describes more volume. If a large cell contains meaningful cost variation, it may need subdivision even when it is geometrically free.

This extends the split criterion beyond collision:

split when geometry is mixed
or traversal cost varies too much
or tactical data needs more detail

That creates a navigation structure whose resolution follows decision complexity. A broad, safe chamber can stay coarse. A geometrically open kill zone with strong exposure gradients may need finer leaves so the pathfinder can distinguish the safer edge from the dangerous centre.

This idea connects naturally to layered spatial data. The earlier article Spatial Databases for Tactical AI discusses keeping signals such as visibility, cover, and occupancy separate. Those layers can influence octree subdivision or edge costs without collapsing every concern into the tree itself.

Keep the collision representation authoritative. Tactical layers may adjust preferences, but they should not quietly turn blocked space into a valid route.

A small C# data shape

The runtime node does not need to mirror every build-time detail. A compact leaf record can hold bounds, occupancy, and cached neighbours:

public sealed class OctreeLeaf
{
    public Bounds Bounds { get; }
    public bool IsTraversable { get; }
    public float TraversalMultiplier { get; }
    public IReadOnlyList<OctreeLeaf> Neighbours => neighbours;

    private readonly List<OctreeLeaf> neighbours = new();

    public OctreeLeaf(
        Bounds bounds,
        bool isTraversable,
        float traversalMultiplier = 1f)
    {
        Bounds = bounds;
        IsTraversable = isTraversable;
        TraversalMultiplier = traversalMultiplier;
    }

    public void Connect(OctreeLeaf other)
    {
        if (!IsTraversable || !other.IsTraversable || other == this)
            return;

        if (!neighbours.Contains(other))
            neighbours.Add(other);
    }
}

Production code may store indices instead of object references for denser memory and better cache behaviour. The important boundary is conceptual: subdivision builds leaves, connectivity validates transitions, and A* consumes the resulting graph. Keeping those jobs distinct makes each one testable.

At minimum, tests should cover:

  • a completely free root that remains one leaf
  • a blocked root with no traversable node
  • a mixed root that subdivides
  • a large leaf connected to several smaller leaves across one face
  • a narrow opening rejected for an oversized agent
  • an update that splits and later merges the same branch
  • a path whose smoothed segments retain clearance

The unequal-neighbour case deserves special attention. Many octree navigation bugs hide there because same-size cells work correctly during early prototypes.

When octrees are the wrong choice

Octrees are useful when the world is volumetric, sparse, and unevenly detailed. Flying agents, underwater vehicles, zero-gravity movement, voxel caves, and large destructible volumes are natural candidates.

They are less compelling when movement is constrained to surfaces. A navmesh usually represents walkable floors more directly and produces better paths with fewer special rules for support and slopes. A two-dimensional grid may be simpler for a tactics game whose height differences are discrete. A waypoint graph may be enough for a small authored level.

Octrees also lose some appeal when the environment is dense at every scale. If almost every cell remains mixed until the maximum depth, the tree approaches the leaf count of a uniform voxel grid while retaining more complicated neighbour logic and pointer overhead.

The decision should be driven by measurements from representative levels:

  1. Build a simple uniform baseline.
  2. Record memory, build time, node count, expansions, and query latency.
  3. Build the octree at equivalent minimum clearance.
  4. Include neighbour lookup and smoothing in the timing.
  5. Test short, long, open, narrow, and unreachable routes.
  6. Test representative world updates if geometry changes at runtime.

If the octree reduces expansions but total query time rises, neighbour discovery or memory layout may be the actual bottleneck. If queries are fast but updates hitch, partial rebuilding needs attention. If paths cut corners, the problem is likely transition validation or smoothing rather than A*.

Practical takeaway

Octrees optimise 3D pathfinding by reducing the graph before the search begins. Open volumes become large leaves. Detailed geometry receives small leaves. A* then spends its effort around obstacles and route choices instead of expanding thousands of equivalent empty voxels.

The design succeeds when four details are handled carefully:

  • free leaves are classified for the agent’s real volume
  • neighbours across unequal cell sizes are connected correctly
  • edge costs and heuristics match the movement model
  • the leaf corridor is converted into a clearance-safe world-space path

Start with leaf-level A*, cached adjacency, and collision-aware smoothing. Measure that version before adding coarse-to-fine abstractions or highly dynamic rebuilding. The octree already provides the largest structural gain: it lets simple space stay simple.