# 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](ai-goals-and-brains#what-decides), which decides *where*; this page is *how*, and it is the same machinery whichever decision system asked. ## The cast | class | what it decides | thread | |---|---|---| | `PathNavigation` | when to search, what budget to search with, when to give up | the Server thread | | `PathNavigationRegion` | which blocks the search is allowed to see — a snapshot, never a load | the Server thread | | `NodeEvaluator` | what a block *is* to this mob, as a `PathType` | the Server thread | | `PathTypeCache` | the 4,096-entry memo that makes that affordable | the Server thread, owned by `ServerLevel` | | `PathFinder` | the A\* itself, bounded by a node budget | the Server thread | | `Path` | the node list, and whether it reaches the target | the Server thread, with a stream codec for the debug channel only | | `MoveControl` | where a wanted position becomes a yaw and a speed, and forgets it again the same tick | the Server thread | 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](#the-search), which has a figure of its own: ```mermaid 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](attributes#the-instance-three-indices-and-one-cached-number) 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](../world/points-of-interest#noon-and-a-bed-forty-eight-blocks-away), 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 `Node`s — one per candidate block position, carrying its `PathType` and its costs — with the destinations held separately as `Target`s, 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. ```mermaid 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](movement-and-collision#building-the-delta) — 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`.*