在前两篇专栏中，我们介绍了生物 AI 的两套系统。在这篇专栏中，将会介绍整个生物 AI 系统中的最后一部分：寻路系统。
一. 生物与寻路系统
在所有实体中，只有生物（Mob）具有寻路系统。根据实体继承树，可以看出各种生物都使用了怎样的寻路系统。
蝙蝠（直接继承 AmbientCreature，此类直接继承 Mob）不使用寻路系统，它们的飞行只考虑当前点和终点，尝试以直线飞行到终点，不计算中间经过的路径，所以它们根本不需要寻路系统。并且蝙蝠也没有使用任何生物 AI 系统。
FlyingMob（子类为恶魂和幻翼）也不使用寻路系统，它们飞行时也只考虑当前点和终点，而不计算中间路径，因此不需要寻路系统。与蝙蝠不同的是，它们使用了目标系统作为 AI 系统。
史莱姆和岩浆怪同样不使用寻路系统，也不计算中间路径。它们使用了目标系统。
末影龙具有复杂的寻路系统和 AI 系统，在这篇专栏内不会涉及。
其余所有生物都继承于 PathfinderMob，使用接下来所介绍的寻路系统。
二. 路径与路径节点
路径是决定生物移动的关键数据，也是寻路系统的计算结果。它具有下面这些字段：
target：路径的目标位置。
nodes：路径节点列表。
reached：这条路径是否能到达目标位置。
distToTarget：目标位置与路径终点的曼哈顿距离。如果整条路经不存在节点，则为单精度浮点数的最大值。
nextNodeIndex：下一个节点的位置。用于判断当前路径的走动过程和判断是否已经走完这条路径。
从字段定义中可以看出，路径的目标位置不一定是路径节点列表的终点。这是因为一条路径可以只需要到达目标位置的附近，而不需要最后完全站在目标点上。
路径由一个个的路径节点构成，节点包含下面的属性：
g（Yarn 名称为 penalizedPathLength）：从路径起点到本节点的寻路代价。
h（Yarn 名称为 distanceToNearestTarget）：本节点的启发函数值（Heuristic）。计算上是当前节点与最近目标位置的欧几里得距离或它的1.5倍，下文会详细解释。
f（Yarn 名称为 heapWeight）：本节点的综合优先级。计算上是节点在二叉堆内的权重，此项由前两项相加计算而来。为了节省计算资源，节点被存放到一个二叉堆（openSet）中，并且这个堆是一个小根堆。
x、y、z：节点的方块位置。
closed：本节点是否“闭合”，也就是是否已经计算过。
walkedDistance：从起点经路径到达此节点的距离。
costMalus：本节点的寻路代价。
type：本节点的方块路径类型。
cameFrom：本节点连接的上一个节点，主要用于重构路径。
heapIdx：节点在二叉堆中的序号，用于索引和检查是否在二叉堆内。如果在堆内，则不小于0。
hash：节点的哈希值。
简单介绍完这两种数据结构后，我们可以正式进入寻路计算的部分了。
三. 方块路径类型与方块寻路代价
世界上的方块情况是非常复杂的，为了减少计算，MC 把方块映射为了对应的方块路径类型并赋予了这些方块路径类型的寻路代价。
方块路径类型在 BlockPathTypes 中定义，每个枚举值都有其对应的基础寻路代价。
各种方块寻路类型及其代价
所有小于 0 的代价都代表生物不能跨越此方块进行寻路。有些生物会覆写某些方块路径类型的代价，从而使生物可以跨越这些方块。
方块对应的具体方块路径类型不仅由方块决定，还由生物本身决定。生物计算方块路径类型的方法是 NodeEvaluator::getBlockPathType，而这个方法是一个抽象方法，共有 5 个实现。接下来我们会一一介绍。
WalkNodeEvaluator::getBlockPathType
首先我们来介绍地面节点标记器，这个标记器是绝大部分生物使用的标记器。
protected static BlockPathTypes getBlockPathTypeRaw(BlockGetter level, BlockPos pos) {
BlockState state = level.getBlockState(pos);
Block block = state.getBlock();
if (state.isAir())
return BlockPathTypes.OPEN;
if (state.is(BlockTags.TRAPDOORS) || state.is(Blocks.LILY_PAD) || state.is(Blocks.BIG_DRIPLEAF))
return BlockPathTypes.TRAPDOOR;
if (state.is(Blocks.POWDER_SNOW))
return BlockPathTypes.POWDER_SNOW;
if (state.is(Blocks.CACTUS) || state.is(Blocks.SWEET_BERRY_BUSH))
return BlockPathTypes.DAMAGE_OTHER;
if (state.is(Blocks.HONEY_BLOCK))
return BlockPathTypes.STICKY_HONEY;
if (state.is(Blocks.COCOA))
return BlockPathTypes.COCOA;
if (state.is(Blocks.WITHER_ROSE) || state.is(Blocks.POINTED_DRIPSTONE))
return BlockPathTypes.DAMAGE_CAUTIOUS;
FluidState fluid = level.getFluidState(pos);
if (fluid.is(FluidTags.LAVA))
return BlockPathTypes.LAVA;
if (WalkNodeEvaluator.isBurningBlock(state))
return BlockPathTypes.DAMAGE_FIRE;
if (block instanceof DoorBlock door) {
if (state.getValue(DoorBlock.OPEN).booleanValue())
return BlockPathTypes.DOOR_OPEN;
return door.type().canOpenByHand() ? BlockPathTypes.DOOR_WOOD_CLOSED : BlockPathTypes.DOOR_IRON_CLOSED;
}
if (block instanceof BaseRailBlock)
return BlockPathTypes.RAIL;
if (block instanceof LeavesBlock)
return BlockPathTypes.LEAVES;
if (state.is(BlockTags.FENCES) || state.is(BlockTags.WALLS) || block instanceof FenceGateBlock && !state.getValue(FenceGateBlock.OPEN).booleanValue())
return BlockPathTypes.FENCE;
if (!state.isPathfindable(level, pos, PathComputationType.LAND))
return BlockPathTypes.BLOCKED;
if (fluid.is(FluidTags.WATER))
return BlockPathTypes.WATER;
return BlockPathTypes.OPEN;
}上面这段代码是方块与方块路径类型的初步映射，从这里我们可以看出下面的映射关系：
如果方块是空气，则为 OPEN。
如果方块是活版门/睡莲/大型垂滴叶，则为 TRAPDOOR。
如果方块是细雪，则为 POWDER_SNOW。
如果方块是仙人掌或甜浆果，则为 DAMAGE_OTHER。
如果方块是蜂蜜块，则为 STICKY_HONEY。
如果方块是可可果，则为 COCOA。
如果方块是凋零玫瑰和滴水石锥，则为 DAMAGE_CAUTIOUS。
如果方块是熔岩，则为 LAVA。
如果方块是火/灵魂火/岩浆块/点燃的（灵魂）营火/熔岩炼药锅，则为 DAMAGE_FIRE。
如果方块是门，则有三种情况：开着的门 -> DOOR_OPEN；关着的木门 -> DOOR_WOOD_CLOSED；关着的铁门 -> DOOR_IRON_CLOSED。
如果方块是任何一种铁轨，则为 RAIL。
如果方块是树叶，则为 LEAVES。
如果方块是栅栏/墙/关着的栅栏门，则为 FENCE。
如果方块不能地面寻路（绝大部分是碰撞箱完整方块，也有一些不完整方块比如铁砧等也是不能地面寻路的方块），则为 BLOCKED。
如果方块是水，则为 WATER。
如果不属于上面任何一种情况，为 OPEN。
初步确定方块路径类型后，还要再次检查这个方块下方和周围的方块以明确这个位置真正的方块路径类型。
public static BlockPathTypes getBlockPathTypeStatic(BlockGetter level, BlockPos.MutableBlockPos pos) {
int x = pos.getX();
int y = pos.getY();
int z = pos.getZ();
BlockPathTypes type = WalkNodeEvaluator.getBlockPathTypeRaw(level, pos);
if (type == BlockPathTypes.OPEN && y >= var0.getMinBuildHeight() + 1) {
BlockPathTypes below = WalkNodeEvaluator.getBlockPathTypeRaw(level, pos.set(x, y - 1, z));
type = below == BlockPathTypes.WALKABLE || below == BlockPathTypes.OPEN || below == BlockPathTypes.WATER || below == BlockPathTypes.LAVA ? BlockPathTypes.OPEN : BlockPathTypes.WALKABLE;
if (below == BlockPathTypes.DAMAGE_FIRE)
type = BlockPathTypes.DAMAGE_FIRE;
if (below == BlockPathTypes.DAMAGE_OTHER)
type = BlockPathTypes.DAMAGE_OTHER;
if (below == BlockPathTypes.STICKY_HONEY)
type = BlockPathTypes.STICKY_HONEY;
if (below == BlockPathTypes.POWDER_SNOW)
type = BlockPathTypes.DANGER_POWDER_SNOW;
if (below == BlockPathTypes.DAMAGE_CAUTIOUS)
type = BlockPathTypes.DAMAGE_CAUTIOUS;
}
if (type == BlockPathTypes.WALKABLE)
type = WalkNodeEvaluator.checkNeighbourBlocks(level, pos.set(x, y, z), type);
return type;
}可以看到一个方块位置的方块路径类型是这样计算的：
如果本方块位置的初始方块路径类型不是 OPEN，则采用本方块位置的初始方块路径类型作为最终的方块路径类型。
如果本方块位置的初始方块路径类型是 OPEN，则要检查下方方块：如果下方方块是 OPEN/WATER/LAVA，则最终类型为 OPEN。如果下方方块是 DAMAGE_FIRE/DAMAGE_OTHER/STICKY_HONEY/DAMAGE_CAUTIOUS，则与下方方块相同。如果下方方块是 POWDER_SNOW，则最终类型为 DANGER_POWDER_SNOW。其他情况，为 WALKABLE，但是要参与下面的周围方块额外检查。
如果本方块位置为 WALKABLE，则要进行周围3x3x3方块的额外检查。检查顺序是从 XYZ 最小的点开始，按照 ZYX 分别增大到 XYZ 最大点，检查到特殊情况就退出循环，如果没有遇到特殊情况就保持为 WALKABLE。特殊情况有：如果周围方块有仙人掌/甜浆果，则为 DANGER_OTHER。如果周围方块有火/灵魂火/岩浆块/点燃的（灵魂）营火/熔岩炼药锅，则为 DANGER_FIRE。如果周围方块有水，则为 WATER_BORDER。如果周围方块有凋零玫瑰和滴水石锥，则为 DAMAGE_CAUTIOUS。
public static BlockPathTypes checkNeighbourBlocks(BlockGetter level, BlockPos.MutableBlockPos pos, BlockPathTypes type) {
int x = pos.getX();
int y = pos.getY();
int z = pos.getZ();
for (int xOff = -1; xOff <= 1; ++xOff)
for (int yOff = -1; yOff <= 1; ++yOff)
for (int zOff = -1; zOff <= 1; ++zOff) {
if (xOff == 0 && zOff == 0)
continue;
pos.set(x + xOff, y + yOff, z + zOff);
BlockState state = level.getBlockState(pos);
if (state.is(Blocks.CACTUS) || state.is(Blocks.SWEET_BERRY_BUSH))
return BlockPathTypes.DANGER_OTHER;
if (WalkNodeEvaluator.isBurningBlock(state))
return BlockPathTypes.DANGER_FIRE;
if (level.getFluidState(pos).is(FluidTags.WATER))
return BlockPathTypes.WATER_BORDER;
if (state.is(Blocks.WITHER_ROSE) && state.is(Blocks.POINTED_DRIPSTONE))
return BlockPathTypes.DAMAGE_CAUTIOUS;
}
return type;
}由于生物本身具有大小，有些生物的宽度超过了 1 格，所以只计算一个方块位置的路径类型是不够的。getBlockPathTypes 方法给出了当前位置和生物可能接触位置的路径类型。
public BlockPathTypes getBlockPathTypes(BlockGetter level,
int x, int y, int z,
EnumSet<BlockPathTypes> types,
BlockPathTypes baseType,
BlockPos entityPos) {
for (int xOff = 0; xOff <entityWidth; ++xOff) {
for (int yOff = 0; yOff < entityHeight; ++yOff) {
for (int zOff = 0; zOff < entityDepth; ++zOff) {
int nowX = xOff + x;
int nowY = yOff + y;
int nowZ = zOff + z;
BlockPathTypes typeNow = getBlockPathType(level, nowX, nowY, nowZ);
typeNow = evaluateBlockPathType(level, entityPos, typeNow);
if (var7 == 0 && var8 == 0 && var9 == 0)
baseType = typeNow;
types.add(typeNow);
}
return baseType;
}在得到这些方块位置的路径类型后，还需要针对生物的特性进行路径类型的转换。
protected BlockPathTypes evaluateBlockPathType(BlockGetter level, BlockPos entityPos, BlockPathTypes type) {
boolean canPassDoors = canPassDoors();
if (type == BlockPathTypes.DOOR_WOOD_CLOSED && canOpenDoors() && canPassDoors)
type = BlockPathTypes.WALKABLE_DOOR;
if (type == BlockPathTypes.DOOR_OPEN && !canPassDoors)
type = BlockPathTypes.BLOCKED;
if (type == BlockPathTypes.RAIL && !(level.getBlockState(entityPos).getBlock() instanceof BaseRailBlock) && !(level.getBlockState(entityPos.below()).getBlock() instanceof BaseRailBlock)) {
type = BlockPathTypes.UNPASSABLE_RAIL;
return var2;
}上面代码的含义为：
如果生物可以打开门并且可以走过门，关着的木门会被转变为 WALKABLE_DOOR。
如果生物不可以走过门，则门会变为 BLOCKED。
如果方块位置上是铁轨类方块，并且生物对应的方块或它下面的方块不是铁轨类方块时，铁轨变为 UNPASSABLE_RAIL。
从这段代码中可以看出，如果生物正站在铁轨上，则所有的铁轨都会被认为可通过，而不是平常的不可通过。也就是说，这个可走过铁轨的判定不是这个方块周围的方块决定的，而是生物站的位置决定的。
在寻路开始时就站在铁轨上的僵尸，在寻路过程中会认为铁轨可以越过
最后，将代码整合起来就得到了生物用于寻路计算的方块路径类型。
@Override
public BlockPathTypes getBlockPathType(BlockGetter level, int x, int y, int z, Mob mob) {
EnumSet<BlockPathTypes> types = EnumSet.noneOf(BlockPathTypes.class);
BlockPathTypes baseType = BlockPathTypes.BLOCKED;
baseType = getBlockPathTypes(level, x, y, z, types, baseType, mob.blockPosition());
if (types.contains(BlockPathTypes.FENCE)) {
return BlockPathTypes.FENCE;
if (types.contains(BlockPathTypes.UNPASSABLE_RAIL)) {
return BlockPathTypes.UNPASSABLE_RAIL;
BlockPathTypes type = BlockPathTypes.BLOCKED;
for (BlockPathTypes nowType : types) {
if (mob.getPathfindingMalus(nowType) < 0.0f)
return nowType;
if (mob.getPathfindingMalus(nowType) >= mob.getPathfindingMalus(type))
type = nowType;
}
if (baseType == BlockPathTypes.OPEN && mob.getPathfindingMalus(type) == 0.0f && entityWidth <= 1)
return BlockPathTypes.OPEN;
return type;
}这段代码可以看出：
如果方块路径类型集合内含有 FENCE，则认为这个方块路径类型就是 FENCE。UNPASSABLE_RAIL 同理。
尝试找出拥有最大代价的方块路径类型作为最终路径类型。如果路径类型本身已经不可寻路（代价小于 0），则直接返回这个路径类型。
如果本方块位置上的类型是 OPEN、最大代价为 0 并且生物本身宽度小于 1，则返回 OPEN。
否则返回找到的拥有最大代价的路径类型。
FlyNodeEvaluator::getBlockPathType
这个类继承 WalkNodeEvaluator，与 WalkNodeEvaluator 计算的不同在于最后一步中不考虑 UNPASSABLE_RAIL 的直接返回判定，并且返回 OPEN 时不需要生物本身宽度小于 1。
AmphibiousNodeEvaluator/FrogNodeEvaluator::getBlockPathType
继承 WalkNodeEvaluator，代码也与 WalkNodeEvaluator 相同。
SwimNodeEvaluator::getBlockPathType
这个类用于完全的水生生物的寻路。它的计算要比前面几个更简单。
@Override
public BlockPathTypes getBlockPathType(BlockGetter level, int x, int y, int z, Mob mob) {
BlockPos.MutableBlockPos pos = new BlockPos.MutableBlockPos();
for (int nowX = x; nowX < x + entityWidth; ++nowX)
for (int nowY = y; nowY < y + entityHeight; ++nowY)
for (int nowZ = z; nowZ < z + entityDepth; ++nowZ) {
FluidState fluid = level.getFluidState(pos.set(nowX, nowY, nowZ));
BlockState state = level.getBlockState(pos.set(nowX, nowY, nowZ));
if (fluid.isEmpty() && state.isPathfindable(level, pos.below(), PathComputationType.WATER) && state.isAir())
return BlockPathTypes.BREACH;
if (!var9.is(FluidTags.WATER))
return BlockPathTypes.BLOCKED;
}
BlockState state = level.getBlockState(pos);
if (state.isPathfindable(level, pos, PathComputationType.WATER))
return BlockPathTypes.WATER;
return BlockPathTypes.BLOCKED;
}可以看到，水生生物寻路只有 3 种类型：
如果方块位置上实体范围内是空气并且下方可水体寻路（通常是含水方块），则为 BREACH。
如果方块位置上实体范围内含有不含水方块，则为 BLOCKED。
如果方块位置上本身可以水体寻路，则为 WATER。
否则，为 BLOCKED。
如果生物本身不覆写方块路径类型，则使用方块路径类型的基础代价。生物覆写方块路径类型由 setPathfindingMalus 方法决定。例如在监守者中：
public Warden(EntityType<? extends Monster> type, Level level) {
super(type, level);
dynamicGameEventListener = new DynamicGameEventListener<>(new VibrationListener(new EntityPositionSource(this, getEyeHeight()), this));
xpReward = 5;
getNavigation().setCanFloat(true);
setPathfindingMalus(BlockPathTypes.UNPASSABLE_RAIL, 0.0f);
setPathfindingMalus(BlockPathTypes.DAMAGE_OTHER, 8.0f);
setPathfindingMalus(BlockPathTypes.POWDER_SNOW, 8.0f);
setPathfindingMalus(BlockPathTypes.LAVA, 8.0f);
setPathfindingMalus(BlockPathTypes.DAMAGE_FIRE, 0.0f);
setPathfindingMalus(BlockPathTypes.DANGER_FIRE, 0.0f);
}监守者把 UNPASSABLE_RAIL 类型的代价调整到了 0，也就使得它可以跨越铁轨寻路。其他类型的代价也同样调低或者调整到 0 及以上，这使得它可以跨越比其他生物更多的方块类型。
监守者可以跨越所有铁轨
四. 生成路径
介绍方块路径类型和代价后，我们可以正式讲解生成路径的过程。
生成路径直接或间接使用了 PathNavigation::createPath，它有几个基本参数（此处使用 Yarn Mapping）：
positions：寻路目标列表。
range：寻路额外范围，防止寻路时节点超出寻路空间。
useHeadPos：使用生物的头部坐标寻路而不是使用脚部。
distance：路径终点与目标的距离。如果路径终点与目标的曼哈顿距离小于此值，则认为已经到达终点。
followRange：最大寻路半径，使用欧几里得距离。如果路径没有到达任何目标，并且终点已经超出这个半径，则路径无效。
这 5 个基本参数控制了生物寻路的范围和目标，这个方法的具体代码如下：
@Nullable
protected Path createPath(Set<BlockPos> position, int range, boolean useHeadPos, int distance, float followRange) {
if (position.isEmpty())
return null;
if (mob.getY() < level.getMinBuildHeight())
return null;
if (!canUpdatePath())
return null;
if (path != null && !path.isDone() && position.contains(targetPos))
return path;
level.getProfiler().push("pathfind");
BlockPos posStart = useHeadPos ? mob.blockPosition().above() : mob.blockPosition();
int radius = (int)(followRange + range);
PathNavigationRegion region = new PathNavigationRegion(level, posStart.offset(-radius, -radius, -radius), posStart.offset(radius, radius, radius));
Path pathNow = pathFinder.findPath(region, mob, position, followRange, distance, maxVisitedNodesMultiplier);
level.getProfiler().pop();
if (pathNow != null && pathNow.getTarget() != null) {
targetPos = pathNow.getTarget();
reachRange = distance;
resetStuckTimeout();
}
return pathNow;
}从上方代码中，可以看出：
如果目标为空，则直接返回空。
如果生物本身已经低于建筑高度，也不进行寻路。
如果寻路系统目前不能更新路径，则返回空。
如果当前正在执行路径，且生物还没有根据路径走到终点，如果之前的目标与现在的目标一致或含有之前的目标，则返回之前的路径进行复用。
如果不满足上面的情况，则开始一次寻路计算。
开始寻路计算，会先计算整个寻路空间的中心点，通常使用生物的脚部，也可以使用头部。寻路空间的半径由 range 和 followRange 相加得到，保证在寻路过程中不会出现路径节点超出寻路空间而造成错误计算（如果寻路超出寻路空间，寻路空间外的世界会被认为是平原空区块）。之后会将参数传入具体的 PathFinder 中具体计算路径。如果路径计算成功则设置当前的目标和路径。
PathFinder 是寻路的核心类，它只用于生成路径。被上方调用的方法代码如下：
@Nullable
public Path findPath(PathNavigationRegion level, Mob mob, Set<BlockPos> position, float followRange, int reachRange, float maxVisitedNodesMultiplier) {
openSet.clear();
nodeEvaluator.prepare(level, mob);
Node nodeStart = nodeEvaluator.getStart();
if (nodeStart == null)
return null;
Map<Target, BlockPos> targets = position.stream()
.collect(Collectors.toMap(p -> nodeEvaluator.getGoal(p.getX(), p.getY(), p.getZ()), Function.identity()));
Path path = findPath(level.getProfiler(), nodeStart, targets, followRange, reachRange, maxVisitedNodesMultiplier);
nodeEvaluator.done();
return path;
}寻路开始时，PathFinder 清空 openSet、重置 NodeEvaluator，并计算寻路起始点。不同的节点标记器会导致寻路起始点不同，以 WalkNodeEvaluator 举例：
@Override
public Node getStart() {
BlockPos.MutableBlockPos pos = new BlockPos.MutableBlockPos();
int y = mob.getBlockY();
BlockState state = level.getBlockState(pos.set(mob.getX(), y, mob.getZ()));
if (mob.canStandOnFluid(state.getFluidState())) {
while (mob.canStandOnFluid(state.getFluidState())) {
state = level.getBlockState(pos.set(mob.getX(), ++y, mob.getZ()));
--y;
} else if (canFloat() && mob.isInWater()) {
while (state.is(Blocks.WATER) || state.getFluidState() == Fluids.WATER.getSource(false))
state = level.getBlockState(pos.set(mob.getX(), ++y, mob.getZ()));
--y;
} else if (mob.isOnGround())
y = Mth.floor(mob.getY() + 0.5);
else {
BlockPos mobPos = mob.blockPosition();
while ((level.getBlockState(mobPos).isAir() ||
level.getBlockState(mobPos).isPathfindable(level, mobPos, PathComputationType.LAND)) &&
mobPos.getY() > mob.level.getMinBuildHeight())
mobPos = mobPos.below();
y = mobPos.above().getY();
}
BlockPos mobPos = mob.blockPosition();
if (!canStartAt(pos.set(mobPos.getX(), y, mobPos.getZ()))) {
AABB aabb = mob.getBoundingBox();
if (canStartAt(pos.set(aabb.minX, y, aabb.minZ)) ||
canStartAt(pos.set(aabb.minX, y, aabb.maxZ)) ||
canStartAt(pos.set(aabb.maxX, y, aabb.minZ)) ||
canStartAt(pos.set(aabb.maxX, y, aabb.maxZ)))
return getStartNode(pos);
}
return getStartNode(new BlockPos(mobPos.getX(), y, mobPos.getZ()));
}
protected Node getStartNode(BlockPos pos) {
Node node = getNode(pos);
node.type = getBlockPathType(mob, node.asBlockPos());
node.costMalus = mob.getPathfindingMalus(node.type);
return node;
}
protected boolean canStartAt(BlockPos pos) {
BlockPathTypes type = getBlockPathType(mob, pos);
return type != BlockPathTypes.OPEN && mob.getPathfindingMalus(type) >= 0.0f;
}根据上方的代码，可以看出：
如果生物可以站在某个流体上，并且生物就在这个流体内，则起始点向上移动到流体表面。
如果生物可以主动浮起并且生物在水中，则起始点向上移动到水体表面。
如果生物在地面上，则使用脚部方块位置。
如果生物位于空气或者可寻路方块中，则将起始点向下移动到最高不可地面寻路方块的上方。
如果起始点无效（对应方块类型是 OPEN 或寻路代价为 -1 使得不可寻路），则寻找生物脚下周围对应高度的方块，以找到的第一个有效点作为最终起始点。
如果前一个条件最终没有找到起始点或原起始点本身有效，则返回该起始点。
找到起始点后，就可以根据这个起点开始下面的寻路计算。
MC 使用的寻路算法是 A* 算法，它的算法是计算一个权重 f，每次寻路时找到拥有最小 f 值的节点进行尝试。f 的定义如下：
其中 g 是目前节点到起点的加权距离，h 是目前节点到最近终点的距离。这三个值分别对应了 Node 数据结构的三个字段 f、g、h。
寻路算法的核心代码位于 PathFinder::findPath 的一个重载方法，代码如下：
@Nullable
private Path findPath(ProfilerFiller profiler, Node nodeStart, Map<Target, BlockPos> targets, float maxDistance, int reachRange, float maxVisitedNodesMultiplier) {
profiler.push("find_path");
profiler.markForCharting(MetricCategory.PATH_FINDING);
Set<Target> targetSet = targets.keySet();
nodeStart.g = 0.0f;
nodeStart.f = nodeStart.h = getBestH(nodeStart, targetSet);
openSet.clear();
openSet.insert(nodeStart);
int nodeVisits = 0;
HashSet<Target> reachedTargets = Sets.newHashSetWithExpectedSize(targetSet.size());
int maxVisits = (int) (maxVisitedNodes * maxVisitedNodesMultiplier);
while (!openSet.isEmpty() && ++nodeVisits < maxVisits) {
Node nowNode = openSet.pop();
nowNode.closed = true;
for (Target target : targetSet) {
if (nowNode.distanceManhattan(target) <= reachRange) {
target.setReached();
reachedTargets.add(target);
}
if (!reachedTargets.isEmpty())
break;
if (nowNode.distanceTo(nodeStart) >= maxDistance)
continue;
int neighborsCount = nodeEvaluator.getNeighbors(neighbors, nowNode);
for (int neighborIndex = 0; neighborIndex < neighborsCount; ++neighborIndex) {
Node neighbor = neighbors[neighborIndex];
float distanceNeighbor = distance(nowNode, neighbor);
neighbor.walkedDistance = nowNode.walkedDistance + distanceNeighbor;
float cost = nowNode.g + distanceNeighbor + neighbor.costMalus;
if (!(neighbor.walkedDistance < maxDistance) || neighbor.inOpenSet() && !(cost < neighbor.g))
continue;
neighbor.cameFrom = nowNode;
neighbor.g = cost;
neighbor.h = getBestH(neighbor, targetSet) * 1.5f;
if (neighbor.inOpenSet())
openSet.changeCost(neighbor, neighbor.g + neighbor.h);
else {
neighbor.f = neighbor.g + neighbor.h;
openSet.insert(neighbor);
}
}
}
Optional<Path> optionalPath = !reachedTargets.isEmpty() ?
reachedTargets.stream()
.map(target -> reconstructPath(target.getBestNode(), targets.get(target), true))
.min(Comparator.comparingInt(Path::getNodeCount)) :
targetSet.stream()
.map(target -> reconstructPath(target.getBestNode(), targets.get(target), false))
.min(Comparator.comparingDouble(Path::getDistToTarget).thenComparingInt(Path::getNodeCount));
profiler.pop();
if (!optionalPath.isPresent())
return null;
Path path = optionalPath.get();
return path;
}
private float getBestH(Node node, Set<Target> targets) {
float minH = Float.MAX_VALUE;
for (Target target : targets) {
float distance = node.distanceTo(target);
target.updateBest(distance, node);
minH = Math.min(distance, minH);
}
return minH;
}
private Path reconstructPath(Node endNode, BlockPos pos, boolean reached) {
ArrayList<Node> nodeList = Lists.newArrayList();
Node nowNode = endNode;
nodeList.add(0, nowNode);
while (nowNode.cameFrom != null) {
nowNode = nowNode.cameFrom;
nodeList.add(0, nowNode);
}
return new Path(nodeList, pos, reached);
}根据上方的代码，可以看出这个寻路算法的流程：
初始化起点，将起点节点的 g 设置为 0，h 设置为到最近目标的欧几里得距离。
重置 openSet，在 openSet 中放入起点。
设置边界条件访问节点最大数量，这个值通常是跟随距离的 16 倍。
开始循环。
从二叉堆 openSet 中取出 f 值最小的节点，并闭合这个节点（防止二次访问）。检查节点是不是已经处于某个目标的可达范围内。如果是，将目标的终点节点设置为本节点，并把可达目标放入 reachedTargets。
如果 reachedTargets 不为空，结束循环。
如果节点与初始节点的欧几里得距离超出了跟随距离，则此节点无效，继续循环。
计算节点旁边的可达节点（邻居）。对于每个邻居，将它们的节点 walkedDistance 设置为本节点与邻居距离和本节点 walkedDistance 的和。并计算到达邻居的代价，即本节点的代价、节点间的距离和邻居节点方块路径代价的总和。如果邻居节点超出了跟随距离，则邻居节点无效；如果邻居节点已经被记录在二叉堆中，而邻居节点原先的 g 小于从现在节点计算的代价，则也不进行接下来的邻居节点更新。
如果邻居节点满足上一条所有条件，则将邻居节点的 g 设置为当前代价，将邻居节点的来源节点设置为本节点，将邻居节点的 h 设置为邻居节点和最近目标欧几里得距离的 1.5 倍。更新各个目标的最佳终点节点，计算邻居节点的 f，如果邻居节点已经在 openSet 中，则修改堆内权重，否则将邻居节点放入二叉堆中。
循环结束后，如果有到达的目标，则重建所有已到达目标的路径，并挑选节点数量最少的路径作为最终路径；如果没有到达任何目标，重建所有目标的路径，挑选距离目标最近且节点数量最少的路径作为最终路径。
可以看到，启发函数值 h 大于真实距离值 50%，这代表了这个寻路算法不一定能找到最优解，但速度会更快。
邻居节点的选择取决于节点评估器，计算节点周围 8 个位置是否可用。以地面节点评估器举例，对于一个方向上的邻居节点它是这样计算的：
@Nullable
protected Node findAcceptedNode(int x, int y, int z, int maxUp, double nowFloorLevel, Direction walkDir, BlockPathTypes nowType) {
Node node = null;
BlockPos.MutableBlockPos pos = new BlockPos.MutableBlockPos();
double floorLevel = getFloorLevel(pos.set(x, y, z));
if (floorLevel - nowFloorLevel > getMobJumpHeight())
return null;
BlockPathTypes type = getCachedBlockType(mob, x, y, z);
float typeMalus = mob.getPathfindingMalus(type);
double halfWidth = mob.getBbWidth() / 2.0;
if (typeMalus >= 0.0f) {
node = getNodeAndUpdateCostToMax(x, y, z, type, typeMalus);
if (doesBlockHavePartialCollision(nowType) && node != null &&
node.costMalus >= 0.0f && !canReachWithoutCollision(node))
node = null;
if (type == BlockPathTypes.WALKABLE || isAmphibious() && type == BlockPathTypes.WATER)
return node;
double collisionCenterX = x - walkDir.getStepX() + 0.5;
double collisionCenterZ = z - walkDir.getStepZ() + 0.5;
if ((type == null || node.costMalus < 0.0f) &&
maxUp > 0 &&
(type != BlockPathTypes.FENCE || canWalkOverFences()) &&
type != BlockPathTypes.UNPASSABLE_RAIL &&
type != BlockPathTypes.TRAPDOOR &&
type != BlockPathTypes.POWDER_SNOW &&
(node = findAcceptedNode(x, y + 1, z, maxUp - 1, nowFloorLevel, walkDir, nowType)) != null &&
(node.type == BlockPathTypes.OPEN || node.type == BlockPathTypes.WALKABLE) &&
mob.getBbWidth() < 1.0f &&
hasCollisions(new AABB(collisionCenterX - halfWidth, getFloorLevel(pos.set(collisionCenterX, y + 1, collisionCenterZ)) + 0.001, collisionCenterZ - halfWidth,
collisionCenterX + halfWidth, mob.getBbHeight() + getFloorLevel(pos.set(node.x, node.y, node.z)) - 0.002, collisionCenterZ + halfWidth)))
node = null;
if (!isAmphibious() && type == BlockPathTypes.WATER && !canFloat()) {
if (getCachedBlockType(mob, x, y - 1, z) != BlockPathTypes.WATER)
return node;
while (y > mob.level.getMinBuildHeight()) {
if ((type = getCachedBlockType(mob, x, --y, z) == BlockPathTypes.WATER)
node = getNodeAndUpdateCostToMax(x, y, z, type, mob.getPathfindingMalus(type));
else
return node;
}
}
if (type == BlockPathTypes.OPEN) {
int fallDistance = 0;
int oldY = y;
while (type == BlockPathTypes.OPEN) {
if (--y < mob.level.getMinBuildHeight())
return getBlockedNode(x, oldY, z);
if (fallDistance++ >= mob.getMaxFallDistance())
return getBlockedNode(x, y, z);
type = getCachedBlockType(mob, x, y, z);
typeMalus = mob.getPathfindingMalus(type);
if (type != BlockPathTypes.OPEN && typeMalus >= 0.0f) {
node = getNodeAndUpdateCostToMax(x, y, z, type, typeMalus);
break;
}
if (typeMalus < 0.0f)
return getBlockedNode(x, y, z);
}
}
if (doesBlockHavePartialCollision(type) && node == null) {
node = getNode(x, y, z);
node.closed = true;
node.type = type;
node.costMalus = type.getMalus();
}
return node;
}
private double getMobJumpHeight() {
return Math.max(1.125, mob.maxUpStep());
}
private Node getNodeAndUpdateCostToMax(int x, int y, int z, BlockPathTypes type, float var4) {
Node node = getNode(x, y, z);
var5.type = type;
var5.costMalus = Math.max(var5.costMalus, var4);
return node;
}
private Node getBlockedNode(int x, int y, int z) {
Node node = getNode(x, y, z);
node.type = BlockPathTypes.BLOCKED;
node.costMalus = -1.0f;
return node;
}
private boolean hasCollisions(AABB aabb) {
return collisionCache.computeIfAbsent(aabb, key -> !level.noCollision(mob, aabb));
}
protected double getFloorLevel(BlockPos pos) {
if ((canFloat() || isAmphibious()) && level.getFluidState(pos).is(FluidTags.WATER))
return pos.getY() + 0.5;
return getFloorLevel(level, pos);
}
public static double getFloorLevel(BlockGetter level, BlockPos pos) {
BlockPos below = pos.below();
VoxelShape shape = level.getBlockState(var2).getCollisionShape(level, below);
return below.getY() + (shape.isEmpty() ? 0.0 : shape.max(Direction.Axis.Y));
}
private static boolean doesBlockHavePartialCollision(BlockPathTypes type) {
return type == BlockPathTypes.FENCE || type == BlockPathTypes.DOOR_WOOD_CLOSED || type == BlockPathTypes.DOOR_IRON_CLOSED;
}
private boolean canReachWithoutCollision(Node node) {
AABB aabb = mob.getBoundingBox();
Vec3 vec = new Vec3(node.x - mob.getX() + aabb.getXsize() / 2.0,
node.y - mob.getY() + aabb.getYsize() / 2.0,
node.z - mob.getZ() + aabb.getZsize() / 2.0);
int check = Mth.ceil(vec.length() / aabb.getSize());
vec = vec.scale(1.0f / check);
for (int move = 1; move <= check; ++move)
if (hasCollisions(aabb = aabb.move(vec)))
return false;
return true;
}上面的代码中，xyz 代表的是要进行评估的邻居位置；maxUp 是生物一次性能上升的最大高度，如果当前路径类型不是 STICKY_HONEY 并且节点上方方块的路径类型代价大于 0，则为 1 与生物 maxUpStep 的较大值，否则为 0；nowFloorLevel 是当前节点位置的地面高度，如果方块没有碰撞箱则为 0，否则为碰撞箱高度；walkDir 是从当前节点走向邻居节点的方向，正方向的邻居使用对应的正方向，斜向的邻居只使用南北方向；nowType 是当前节点的路径类型。这个方法的具体流程是这样的：
如果当前检查节点的上表面高度与当前地面高度的差大于生物能跳起的高度，直接返回 null。生物能跳起的高度为 1.125 与生物 maxUpStep 的较大值。
如果当前检查节点的寻路代价不小于 0，则设置为邻居节点。
如果路径类型是 FENCE、DOOR_WOOD_CLOSED 或 DOOR_IRON_CLOSED 这些有碰撞的路径类型，并且生物到邻居节点会被这些方块的碰撞箱阻挡，则将邻居节点设置为空。生物被阻挡的条件是：节点的最小点与生物的最小点连线，测试生物在这条线上是否会与方块碰撞箱碰撞（具体代码 canReachWithoutCollision）。下图给出了僵尸（宽度 0.6）和关闭的门的碰撞示例。
棕色：门碰撞箱；绿色：僵尸碰撞箱；射线为最小点连线
从这张图中可以看出向北、西、南的射线都被门碰撞箱阻挡，所以这三个方向不能作为僵尸的有效邻居节点。当僵尸向东走动一点，就有可能使射线碰撞范围离开门的碰撞箱，从而使北面也变为有效，但由于这个计算本身是实体碰撞箱在某些位置上进行检测，所以实际移动范围比视觉上射线移动范围要更大。如果门换了一个方向，比如说换为东侧的门，这时候只有东面会被遮挡，其他三个方向都可以作为有效的节点。同时，因为这个计算是根据生物目前所在位置计算的，所以可能会造成一些寻路上的问题。
这个机制在 22w16a 时被修改为现在的行为，在此之前使用的是生物碰撞箱底面中心点，而不是最小点，并且在之前只有 FENCE 类型才有效。
由关闭的门造成僵尸（这个僵尸必须不会破门）无法寻路，具有方向性；僵尸另一侧的门可以换成可以遮挡住最小点的方块，比如一个完整方块等（手办制作方式+1）
如果上面计算出了不为空的邻居节点，则判断是否为 WALKABLE，对于两栖类生物还会额外检查是否为 WATER，如果通过，就返回这个邻居节点。
如果邻居节点现在为空，或者邻居节点的代价小于 0（不可寻路），并且满足下面所有条件：maxUp 大于 0（生物可以尝试向上查找可寻路方块）、生物可以跨越栅栏或邻居节点的类型不是 FENCE、邻居节点不是 UNPASSABLE_RAIL、TRAPDOOR 或 POWDER_SNOW，则检查现在节点位置的上方方块，递归查找。如果不满足以上条件，邻居节点设置为空。如果递归查找发现了合适的位置，并且不满足下面任意一条条件：发现的节点类型是 OPEN 或者 WALKABLE，生物宽度小于 1，生物会与上升路径中的方块碰撞，邻居节点就会被设置为查找到的位置，否则设置为空。
如果生物不是两栖生物，也不会自动飘浮，如果路径类型为 WATER，则尝试向下查找，直到找到一个类型不是 WATER 的节点返回。如果查找超出了建筑下限，则进入下一步。
如果路径类型是 OPEN，则尝试向下查找，查找的最大距离是生物可容许的最大下落高度。通常来说这个高度是 3，对于当前有攻击目标的生物是，其中 h 是当前生命值，h_max 是最大生命值，d 是数字形式的难度，和平到困难分别代表了 0-3，如果计算出来的值小于 3，则认为是 3。这个公式可以看出生物总是尝试让自己不会从能让自己受伤到三分之一血量的地方向下落，难度也影响了生物最大容许的下落高度。如果查找高度已经超过了容许下落高度，或查找到了建筑下限，则返回 BLOCKED 节点；如果找到了一个不是 OPEN 且代价不小于 0 的位置，则将邻居节点设置为这个位置；否则返回 BLOCKED 节点。
村民不会自动跳下，因为此处高度为 4，超出了最大容许下落高度
如果当前位置是路径类型是 FENCE、DOOR_WOOD_CLOSED 或 DOOR_IRON_CLOSED，并且邻居节点仍然为空，则返回已经闭合的节点。
最后，返回计算得出的邻居节点，无论是否为空。
获得邻居节点后，还要在判断一次这些节点是否有效。直接相邻的节点和对角相邻的节点判断不相同。
首先判断直接相邻的邻居节点：
protected boolean isNeighborValid(@Nullable Node neighbor, Node now) {
return neighbor != null && !neighbor.closed && (neighbor.costMalus >= 0.0f || now.costMalus < 0.0f);
}直接相邻的邻居节点必须是非空且非闭合的，并且要求邻居节点本身的代价不小于 0 可寻路或本节点本身不可寻路。如果不满足上面的条件，邻居节点无效并不会被计算。
由于这个方法内部允许了本节点不可寻路时会忽略邻居节点是否不可寻路，所以会造成下面的结果：生物检查下落时失败是在容许下落的最低位置上放置 BLOCKED 路径类型节点，而不是返回一个 null，这也就满足了第一个条件：非空非闭合。如果生物起点就已经是不可寻路的，即使下一个节点是 BLOCKED 生物也可以选择这个节点。同样，由于 BLOCKED 节点也不可寻路，它也会影响下一个节点的选取，如此循环，就让生物可以下落的高度不断叠加。
生物在不可寻路的节点上进行寻路
更一般的来说，如果起点不可寻路，那么之后的节点都可以是不可寻路的，直到遇到一个可寻路节点。
僵尸从不可寻路的 FENCE 走向同样不可寻路的 BLOCKED
之后判断对角相邻的邻居节点：
protected boolean isDiagonalValid(Node now, @Nullable Node neighbor1, @Nullable Node neighbor2, @Nullable Node diagonalNeighbor) {
if (diagonalNeighbor == null || neighbor1 == null || neighbor2 == null)
return false;
if (diagonalNeighbor.closed)
return false;
if (neighbor2.y > now.y || neighbor1.y > now.y)
return false;
if (neighbor1.type == BlockPathTypes.WALKABLE_DOOR ||
neighbor2.type == BlockPathTypes.WALKABLE_DOOR ||
diagonalNeighbor.type == BlockPathTypes.WALKABLE_DOOR)
return false;
boolean canPassFence = neighbor2.type == BlockPathTypes.FENCE &&
neighbor1.type == BlockPathTypes.FENCE &&
mob.getBbWidth() < 0.5;
return diagonalNeighbor.costMalus >= 0.0f &&
(neighbor2.y < now.y || neighbor2.costMalus >= 0.0f || canPassFence) &&
(neighbor1.y < now.y || neighbor1.costMalus >= 0.0f || canPassFence);
}对角相邻节点判断更加严格，对角方向上与本节点直接相邻的两个直接邻居节点也要被计算。如果这三个邻居节点有一个为空或为 WALKABLE_DOOR，那么对角节点就无效。如果对角节点本身闭合，也无效。如果对角节点本身不可寻路，节点无效。如果两个直接节点是 FENCE 并且生物本身宽度小于 0.5，则对角节点有效。两个直接节点高度小于本节点或本身可寻路时，对角节点也有效。
僵尸无法寻路到村民的位置，因为有一侧被栅栏阻挡；如果没有栅栏则可以正常寻路
五. 应用路径
现在我们已经了解了路径是怎么生成的了，那么这些路径是怎么应用的呢。
1. 生物行走
在各种 Goal 和 Behavior 中，如果生物需要走到什么地方，就会调用 PathNavigation::moveTo 方法。
public boolean moveTo(double x, double y, double z, double speedModifier) {
return moveTo(createPath(x, y, z, 1), speedModifier);
}
public boolean moveTo(Entity entity, double speedModifier) {
Path path = createPath(entity, 1);
return path != null && moveTo(path, speedModifier);
}
public boolean moveTo(@Nullable Path pathCreated, double speedModifier) {
if (pathCreated == null) {
path = null;
return false;
}
if (!pathCreated.sameAs(path))
path = pathCreated;
if (isDone())
return false;
trimPath();
if (path.getNodeCount() <= 0)
return false;
this.speedModifier = speedModifier;
Vec3 pos = getTempMobPos();
lastStuckCheck = tick;
lastStuckCheckPos = pos;
return true;
}绝大部分的走动寻路的到达半径都是 1。在路径创建后，如果生物是追踪一个方块位置寻路而没有任何路径可以到达，那么当前路径也会被打断。如果新的路径和当前路径不同，新的路径会替换当前的路径。如果当前路径已经结束（nextNodeIndex 大于等于节点数量），返回 false。接下来进行路径的二次处理，检查路径节点数量是否超过 0，设置当前的阻挡检查数据。路径的二次处理如下：
protected void trimPath() {
if (path == null)
return;
for (int index = 0; index < path.getNodeCount(); ++index) {
Node node1 = path.getNode(index);
Node node2 = index + 1 < path.getNodeCount() ? path.getNode(index + 1) : null;
BlockState state = level.getBlockState(new BlockPos(node1.x, node1.y, node1.z));
if (!state.is(BlockTags.CAULDRONS))
continue;
path.replaceNode(index, var1.cloneAndMove(node1.x, node1.y + 1, node1.z));
if (node2 == null || node1.y < node2.y)
continue;
path.replaceNode(index + 1, var1.cloneAndMove(node2.x, node1.y + 1, node2.z));
}
}路径二次处理主要是处理炼药锅的相关行为，让生物能正确的运动。在子类 GroundPathNavigation 中，还定义了躲避太阳的代码。如果会躲避太阳的生物（骷髅类，僵尸不会躲避太阳）的路径一部分的节点被太阳直射，则路径被切断。
在设置路径后，生物就可以按照这个路径每一刻计算怎么按照这个路径行走。
public void tick() {
++tick;
if (hasDelayedRecomputation)
recomputePath();
if (isDone())
return;
if (canUpdatePath()) {
followThePath();
} else if (path != null && !path.isDone()) {
Vec3 nowPos = getTempMobPos();
Vec3 nextPos = path.getNextEntityPos(mob);
if (nowPos.y > nextPos.y && !mob.isOnGround() && Mth.floor(nowPos.x) == Mth.floor(nextPos.x) && Mth.floor(nowPos.z) == Mth.floor(nextPos.z))
path.advance();
}
DebugPackets.sendPathFindingPacket(level, mob, path, maxDistanceToWaypoint);
if (isDone())
return;
Vec3 nextPos = path.getNextEntityPos(mob);
mob.getMoveControl().setWantedPosition(nextPos.x, getGroundY(nextPos), nextPos.z, speedModifier);
}在这里可以看出生物随着路径行走的逻辑：
如果路径需要被重新计算（路径上的方块发生了变化，并且上一次重新计算的时间大于 20tick），则重新计算一次路径。
检查路径是否不存在或者已经结束，如果是，则不进行下面的跟随。
如果生物可以更新路径（和前文创建路径是一个检查更新路径的方法，对于地面寻路的生物来说，条件是在地面上/水中或本生物是乘客），则跟随路径；否则，检查现在生物的位置是否高于下一个节点的路径，并且下一个节点的路径与现在生物的方块位置相同，如果是，路径节点前进一次。
再次检查生物路径是否已经结束，如果是，不进行下面的移动。
找到生物的下一个行走位置，并使用 MoveControl 执行对应的移动。
跟随路径是检查生物是否已经到达路径的下一个节点的方法，防止生物不知道现在在什么位置和下一个位置在哪里。
protected void followThePath() {
Vec3 pos = getTempMobPos();
maxDistanceToWaypoint = mob.getBbWidth() > 0.75f ? mob.getBbWidth() / 2.0f : 0.75f - mob.getBbWidth() / 2.0f;
BlockPos nextPos = path.getNextNodePos();
double xOff = Math.abs(mob.getX() - nextPos.getX() + 0.5);
double yOff = Math.abs(mob.getY() - nextPos.getY());
double zOff = Math.abs(mob.getZ() - nextPos.getZ() + 0.5);
boolean reachNextPos = xOff < maxDistanceToWaypoint && zOff < maxDistanceToWaypoint && yOff < 1.0;
if (reachNextPos || canCutCorner(path.getNextNode().type) && shouldTargetNextNodeInDirection(pos))
path.advance();
doStuckDetection(pos);
}
public boolean canCutCorner(BlockPathTypes type) {
return type != BlockPathTypes.DANGER_FIRE && type != BlockPathTypes.DANGER_OTHER && type != BlockPathTypes.WALKABLE_DOOR;
}
private boolean shouldTargetNextNodeInDirection(Vec3 nowPos) {
if (path.getNextNodeIndex() + 1 >= path.getNodeCount())
return false;
Vec3 nextPos = Vec3.atBottomCenterOf(path.getNextNodePos());
if (!nowPos.closerThan(nextPos, 2.0))
return false;
if (canMoveDirectly(nowPos, path.getNextEntityPos(mob)))
return true;
Vec3 nextNextPos = Vec3.atBottomCenterOf(path.getNodePos(path.getNextNodeIndex() + 1));
Vec3 toNext = nextPos.subtract(nowPos);
Vec3 toNextNext = nextNextPos.subtract(nowPos);
double lenToNext = toNext.lengthSqr();
double lenToNextNext = toNextNext.lengthSqr();
boolean shorterToNext = lenToNextNext < lenToNext;
boolean toNextLenShort = lenToNext < 0.5;
if (shorterToNext || toNextLenShort) {
Vec3 toNextVector = toNext.normalize();
Vec3 toNextNextVector = toNextNext.normalize();
return toNextNextVector.dot(toNextVector) < 0.0;
}
return false;
}生物当自身离下一个节点的水平方向上的切比雪夫距离小于一定值，且垂直差距不超过 1 格时会认为自身已经到达下一个节点。当生物宽度大于 0.75 时，这个距离是生物本身宽度的一半，否则为 0.75 减去生物本身宽度的一半。以僵尸举例，这个距离是 0.45。另一种到达下一个节点的方式是有限制的：下一个节点的类型不能是 DANGER_FIRE、DANGER_OTHER 或 WALKABLE_DOOR 且距离 2 格以内，生物可以直接移动到下一个节点，或下下个节点中心的距离小于下一个节点中心的距离/到下一个节点中心距离小于 0.5 并满足方向偏离超过 90 度。
满足跳转下个节点的两种特殊情况：第一种是距离下下个节点的距离更近，第二种是与下个节点的距离小于 0.5。这两种情况都要求其夹角大于 90 度。
检查是否到达下一个节点后，生物还要进行一次阻挡与超时检测。阻挡与超时检测是防止生物在无法到达的路径上一直尝试行走，造成其他 AI 行为停滞。
protected void doStuckDetection(Vec3 nowPos) {
if (tick - lastStuckCheck > 100) {
float speed = mob.getSpeed() >= 1.0f ? mob.getSpeed() : mob.getSpeed() * mob.getSpeed();
float minMoveDistance = speed * 100.0f * 0.25f;
if (var0.distanceToSqr(lastStuckCheckPos) < minMoveDistance * minMoveDistance) {
isStuck = true;
stop();
} else
isStuck = false;
lastStuckCheck = tick;
lastStuckCheckPos = nowPos;
}
if (path != null && !path.isDone()) {
BlockPos nextPos = path.getNextNodePos();
long gametime = level.getGameTime();
if (nextPos.equals(timeoutCachedNode))
timeoutTimer += gametime - lastTimeoutCheck;
else {
timeoutCachedNode = nextPos;
double distanceNext = nowPos.distanceTo(Vec3.atBottomCenterOf(timeoutCachedNode));
timeoutLimit = mob.getSpeed() > 0.0f ? distanceNext / mob.getSpeed() * 20.0 : 0.0;
}
if (timeoutLimit > 0.0 && timeoutTimer > timeoutLimit * 3.0)
timeoutPath();
lastTimeoutCheck = gametime;
}
}
private void timeoutPath() {
resetStuckTimeout();
stop();
}
private void resetStuckTimeout() {
timeoutCachedNode = Vec3i.ZERO;
timeoutTimer = 0L;
timeoutLimit = 0.0;
isStuck = false;
}阻挡检测每 100tick 执行一次，检测上次记录的位置和现在的位置是否没有太大的变化。如果是，则认为生物已经被不可跨越方块阻挡，路径被强制停止。
超时检测的计时器超时极限为 3 倍当前位置与下一个节点的位置的距离和速度的商。与阻挡检测类似，一旦生物在指定时间内没有到达下一个节点，则认为节点不可达，路径失效。
2. 检查有效路径
在一些行为中，生物需要检查自己是否能到达一个位置，这通常是一个行为的先决条件。检查是否有一条有效的路径需要直接调用上文已经详细说明的 PathNavigation::createPath，它的返回值代表了生物是否能成功找到有效路径：
如果返回为空，则说明不存在任何可达路径。
如果返回了 canReach 为 false 的路径，则说明能找到一条接近目标位置的路径，但是却没有办法达到目标的到达半径内。
如果返回了 canReach 为 true 的路径，说明能找到一条到达目标到达半径内的路径。
绝大多数行为只检查能不能找到路径，而不检查可达性。检查可达性的行为有：山羊的长跳和冲撞、村民繁殖、村民让出工作站点和嗅探兽挖掘，这些行为要求生物必须能走到/不能走到（实际上可以不走）对应位置才能执行。
到这里专栏的长度已经很长了，也基本说明了寻路系统的运作原理，比较详细的说明了地面寻路。对于其它的寻路，代码都和地面寻路相似，只是在邻居节点挑选、方块路径类型判定上等有差异。
有错误可以在下方指出。
源代码使用 Mojang Mapping，版本 1.19.4~23w14a，反编译器 CFR 0.152。
自动化反编译仓库：Nickid2018/GitMCDecomp。
