Pathfinding

Verified against Minecraft 26.3 · Part VI · A mob walks into a fence, stands there, and then wanders off — a hundred ticks after a behaviour told it where to go.

A behaviour has produced a position and stopped caring. Everything between that position and a mob leaning into a direction is this page: one A* search over a snapshot of already-loaded chunks, a Path of nodes, and a control that has to be told again every single tick. The part of it people recognise is the failure. Giving up is machinery, not an absence of it — every node the mob is walking towards carries a timeout computed from its distance and the mob’s current speed, three times over that budget abandons the path outright, and a separate check every hundred ticks asks whether the mob has covered a quarter of the ground its speed says it should have. The mob you watch walk into a wall and then wander off is running a scheduled surrender.

Above the waterline is goals and brains, which decides where; this page is how, and it is the same machinery whichever decision system asked.

The cast

Nothing here is asynchronous. There is not a future, an executor or a thread anywhere in the pathfinder, and every entry point takes a ServerLevel or a Mob on one. Nothing crosses the network either, except when a debug client has subscribed.

The pipeline

Two ways in, one gate, and three ways the navigation ends it by itself (a caller can stop it too). What happens between the gate and the ending is the search, which has a figure of its own:

flowchart TD
    WANT["a goal or a behaviour: PathNavigation.moveTo, or PathNavigation.createPath"]
    WORLD["the world: PathNavigation.recomputePath, after a block update"]
    GATE{"any of the early exits?"}
    NULL["null, or the existing path unchanged"]
    RUN["the search, then the follow, one node at a time"]
    GIVEUP{"arrived, stuck for 100 ticks, or the node timed out?"}
    DONE["PathNavigation.isDone, and the caller finds out next evaluation"]

    WANT --> GATE
    WORLD --> GATE
    GATE -- "yes" --> NULL
    GATE -- "no" --> RUN
    RUN --> GIVEUP
    GIVEUP -- "yes" --> DONE
    GIVEUP -- "no" --> RUN

The page’s ways in and the navigation’s own ways out. The second entrance is the one to notice: the world pushes a recompute in after a block changes, and it is the only arrow on this page that does not start with a mob wanting something.

Asking: the ways a search does not happen

PathNavigation.createPath refuses before it does anything expensive. It returns null on an empty target set, on a mob below Level.getMinY, and on PathNavigation.canUpdatePath — which for GroundPathNavigation means on the ground, in liquid, or riding something, so an airborne mob simply cannot ask. The fourth exit is the interesting one: if there is already a path that is not done and the target of the navigation’s last search is among the requested targets, the existing path is returned unchanged. Re-asking PathNavigation.createPath for a destination you are already walking to costs nothing and changes nothing. And GroundPathNavigation, the navigation most mobs have, puts a fifth in front of the four for a request of one position or one entity: a target whose chunk is not loaded returns null at once.

Most callers never name it: PathNavigation.moveTo is what a goal or a behaviour reaches for, and its position and entity overloads call PathNavigation.createPath themselves and hand the result to the overload that takes a Path. Find a route and start walking it are one call from outside, with the early exits still in front of them, and that last overload restarts the stuck check even when the path is the one already being walked.

PathNavigation.recomputePath is the other entrance, and it is rate-limited rather than refused. More often than every twenty game ticks, or with PathNavigation.canUpdatePath false, it sets a flag instead and the next PathNavigation.tick tries again. That deferral is what keeps a mob standing in a doorway from re-searching twenty times a second.

The budget, which is also the map

One number governs both how hard the search may work and how much world it may look at, and it is worth naming before anything is built out of it. Call it the maximum path length: the larger of the mob’s follow range and its required path length, in blocks. PathNavigation.setRequiredPathLength sets the second half — 16 by default, raised in seven classes, all of them in the mob’s constructor or its navigation: 48 for Villager, Allay, Bee, CopperGolem and a baby HappyGhast’s navigation, 40 for Llama, 32 for Fox.

The node budget is that length times sixteen. PathNavigation builds its PathFinder with Attributes.FOLLOW_RANGE’s base value times sixteen, and PathNavigation.updatePathfinderMaxVisitedNodes later recomputes it against the modified follow range (attributes owns the difference between the two). The recompute has two triggers: PathNavigation.setRequiredPathLength itself, and Mob.onAttributeUpdated, which calls it when either Attributes.FOLLOW_RANGE or Attributes.TEMPT_RANGE changes — though only the follow range goes into the number, and nothing the game itself does changes it after the spawn-time bonus. PathNavigation.setMaxVisitedNodesMultiplier scales the result, and keeps scaling it until PathNavigation.resetMaxVisitedNodesMultiplier puts it back: Bee is the only class that touches either.

And the same length is the map

The same maximum path length — the blocks figure, not the node budget — becomes the radius of the PathNavigationRegion, plus an offset of 8 or 16 depending on which PathNavigation.createPath overload was used, and inside the search it appears twice more: as a test on the current node’s distance from the start and on each neighbour’s walked distance. A villager can find a bed 48 blocks away because its constructor set its required path length to 48, and the larger of the two numbers wins; it cannot find one 60 blocks away no matter how open the ground is. That is the budget behind a villager claiming a bed, whose scan radius is the same 48 for exactly this reason.

That region is built by asking ChunkSource.getChunkNow for every chunk in the cube. A path search never loads a chunk and never blocks — an absent chunk is a null entry that reads as air. This is the same discipline Entity.move uses for collisions, and it is why a search cannot stall a tick waiting for a chunk.

What a block is

NodeEvaluator answers what is this position, to this mob with a PathType: 27 constants, each carrying a default cost, and a negative cost means impassable, not expensive. Nine of the twenty-seven are −1 — PathType.BLOCKED, PathType.LAVA, PathType.FENCE, PathType.LEAVES, PathType.POWDER_SNOW, PathType.DAMAGING, PathType.UNPASSABLE_RAIL and the two closed doors; PathType.WATER is 8, PathType.FIRE 16, PathType.OPEN and PathType.WALKABLE 0. A mob overrides any of them for itself with Mob.setPathfindingMalus, read back through Mob.getPathfindingMalus — which is how the same lava is free ground to a Strider, merely expensive to a ZombifiedPiglin, and a wall to the ordinary Piglin that never overrides it. The question a block is asked is narrower than the answer: PathComputationType has three values — land, water and air — and a block’s own pathability hook sees only which of the three is being planned, never which mob is planning it.

Four evaluators in the pathfinder package cover the movement modes: WalkNodeEvaluator, and the three that specialise it or replace it — FlyNodeEvaluator and AmphibiousNodeEvaluator extend the walker, SwimNodeEvaluator extends NodeEvaluator directly. Two mobs subclass one further for themselves, Frog and Creaking. Each PathNavigation subclass chooses one: GroundPathNavigation, FlyingPathNavigation, WaterBoundPathNavigation, AmphibiousPathNavigation, and WallClimberNavigation on top of the ground one.

Classifying a block is expensive enough to memo. PathTypeCache is a fixed 4,096-entry table owned by ServerLevel, consulted through PathfindingContext — which attaches it only on a ServerLevel and falls back to computing the type from scratch otherwise. It is invalidated one position at a time from ServerLevel.sendBlockUpdated, which is the subject of the last section.

The search

PathFinder.findPath is plain A* over a BinaryHeap of Nodes — one per candidate block position, carrying its PathType and its costs — with the destinations held separately as Targets, a Node subclass that also records whether anything reached it. Three details of the search decide what mobs feel like.

It is bounded twice: by a node count and by a distance. The loop breaks as soon as its visit counter reaches the budget — PathFinder.setMaxVisitedNodes, scaled by the multiplier — and inside the loop the maximum path length is the second bound, gating which nodes are expanded and which neighbours are admitted at all. Under the node budget alone a search through open ground would reach much further than the same budget spends in a maze; the distance bound is what stops it.

The heuristic is inflated. Each neighbour’s h is the best straight-line estimate multiplied by 1.5, which makes the search greedy: it finds a route sooner and the route it finds is not guaranteed to be the shortest. When several targets were reached, the winner is simply the path with the fewest nodes; when none was, it is the path that ends closest to a target, with fewest nodes as the tie-break.

A failed search still returns a path. If no target came within the reach range — measured as a Manhattan distance from the popped node — the finder reconstructs a path to the closest node it managed to reach and marks it not reached. That is what Path.canReach reports, and it is the number that matters rather than “was a path found”: AcquirePoi tests it before claiming a point of interest, and MoveToTargetSink turns a false into a cannot reach memory. A null from PathNavigation.createPath means one of the early exits rather than a search that came back empty-handed — the finder always has a best node to reconstruct towards.

One more thing the search does not do unless asked: it accumulates its closed set, and attaches it to the Path, only while something is subscribed to DebugSubscriptions.ENTITY_PATHS. PathNavigation installs that predicate in its constructor, off the server’s ServerDebugSubscribers. Path has a stream codec for exactly this and no gameplay reason.

sequenceDiagram
    participant MTS as MoveToTargetSink
    participant PN as PathNavigation
    participant PNR as PathNavigationRegion
    participant NE as NodeEvaluator
    participant PF as PathFinder
    participant MoveC as MoveControl

    MTS->>PN: createPath to the walk target, then moveTo with a speed modifier
    PN->>PN: the early exits, then push the pathfind profiler section
    PN->>PNR: build a cube of maxPathLength plus the offset, with getChunkNow
    PN->>PF: findPath — region, mob, targets, maxPathLength, reachRange, multiplier
    PF->>NE: getStart, then getNeighbors per popped node
    NE->>PNR: getBlockState, through PathfindingContext
    Note over NE,PNR: PathTypeCache memoises the PathType per position, on a server level
    PF-->>PN: a Path, reached or best-effort, with canReach set accordingly
    PN->>PN: trimPath, record the stuck-check position, keep the node index
    Note over PN,MoveC: every tick from here
    PN->>MoveC: setWantedPosition for the next node, at speedModifier
    MoveC->>MoveC: tick — the operation back to WAIT, then the yaw and the speed

The call chain is the thing to read: the navigation never talks to the evaluator, the finder does. Below the band, one search has become a position re-issued every tick for as long as the path lasts.

Following it, one tick at a time

PathNavigation.tick advances the node index and calls MoveControl.setWantedPosition with the next node and the speed modifier. It has to do that every tick, because MoveControl.tick sets its own MoveControl.Operation back to MoveControl.Operation.WAIT as it handles the move — the control is a one-shot instruction, not a destination it remembers.

MoveControl.setWantedPosition is the main way a decision, goal or brain, becomes movement, but it is neither the only method nor a single call site. MoveControl.strafe is a second entrance, used by RangedBowAttackGoal and the brain behaviour BackUpIfTooClose; MoveControl.setWait is a third. MoveControl.setWantedPosition itself has twelve callers outside the navigations, in eight classes: the shared goals TemptGoal.ForNonPathfinders and TryFindLiquidGoal, the per-mob goals of Bee, Blaze, Ghast and Vex, Rabbit from the mob itself rather than from a goal, and Fox to pin a sleeping fox where it lies. The first of those is why a happy ghast follows a held item in a straight line through terrain a path search would have routed around: an adult has a navigation like any mob, and none of its goals uses it. An ordinary tempted cow runs the base TemptGoal, which calls the navigation like anything else.

The three controls beside it

Three more controls sit beside it and are the rest of what turns a decision into a pose — all four implementing Control, and the move and look controls re-specialised by movement mode the way the evaluators are, so a SmoothSwimmingMoveControl or a FlyingMoveControl is the same object with different arithmetic. LookControl aims the head, JumpControl fires a jump the mover then executes, and BodyRotationControl keeps the body under the head: while the mob moves it sets the body to the mob’s own yaw, and while it stands still a head that swings more than fifteen degrees drags the body only far enough to stay within Mob.getMaxHeadYRot of it, and a head held still for ten ticks has the body turn to face it over the next ten. BodyRotationControl.clientTick is a leftover name: LivingEntity.tick calls Mob.tickHeadTurn with no side check at all, so it runs on both sides every tick.

The mover itself is Part VI’s movement and collision — the control sets the yaw and calls Mob.setSpeed, which writes LivingEntity.zza with it, and LivingEntity.travel does the rest. For a mob, LivingEntity.xxa is written with anything but zero only by the strafe branch, which pathfinding never takes.

Giving up

PathNavigation.doStuckDetection runs two independent timers, and they answer different questions.

The first half runs every hundred ticks: it compares where the mob is with where it was at the last check or the last PathNavigation.moveTo, against a threshold of the mob’s effective speed times 100 times 0.25 — a quarter of the ground the speed claims. Below that, PathNavigation.isStuck is set and the path is stopped. The effective speed is the speed itself at 1.0 or above and the square of it below, which quietly makes the threshold far more forgiving for slow mobs.

The second half is per node. When the next node changes, the navigation computes a time budget for it — the distance to that node divided by the mob’s speed, times twenty — and holds it against the real ticks counted since the last search that found a path, or the last time out, a count the change of node does not clear, so a clear path walked long enough times out too. Past three times that budget, PathNavigation.timeoutPath resets the counters and stops. This one catches a mob whose path is fine and whose route is blocked by something the search could not see, where the stuck check has not caught it first.

Both endings are the same ending from outside: PathNavigation.isDone becomes true, and whichever behaviour or goal was waiting on the path finds out on its next evaluation.

The one place the world pushes back

Everything above is AI asking the world questions. ServerLevel.sendBlockUpdated is the single call in the other direction. It invalidates the changed position in the path-type cache unconditionally, and then — only if Shapes.joinIsNotEmpty says the collision shape actually changed — walks ServerLevel.navigatingMobs, every mob in the level whether it has a path or not and unbounded by distance, asks each navigation PathNavigation.shouldRecomputePath about the position, and calls PathNavigation.recomputePath on the ones that say yes. That last loop — and only that loop — is wrapped in a re-entrancy flag, which a nested block update or a mob joining or leaving the set checks; either, arriving while the flag is set, logs and, in a development environment, pauses.

That is why closing a door in front of a mob re-routes it and repainting a block does not.

Where to look

PathNavigation is the spine and almost every question on this page is one of its methods: PathNavigation.createPath for the four early exits (and GroundPathNavigation.createPath for the fifth), PathNavigation.updatePathfinderMaxVisitedNodes for the budget, PathNavigation.tick for the following and PathNavigation.doStuckDetection for both timers. Then PathFinder.findPath, which is the A* itself and shorter than you expect, and NodeEvaluator — start with WalkNodeEvaluator, since two of the other three specialise it — for what a block is to a mob. PathType is the 27 constants and their costs, and Mob.getPathfindingMalus is how one mob disagrees with them. MoveControl.setWantedPosition is the seam where a path becomes a direction. Two doors: PathTypeCache, the 4,096-entry memo that makes the classification affordable, and ServerLevel.sendBlockUpdated, the one call in the whole system that runs the other way.

Rules: names, never code · how the system works, not how the code reads · newest version only · every backticked name passes tools/verify_names.py.