13.2 寻路：A* 与导航网格
13.1 那只追击怪会朝玩家直线移动，这在一马平川的地图里没问题。但《方块冲刺》的关卡里有平台、箱子、陷阱，一旦玩家躲到墙后，直线追击就变成了「贴着墙来回蹭」——敌人永远够不到目标，玩家看着也觉得蠢。这一节给 mini2d 补上寻路：先在一个网格上实现 A*，再讨论怎么把折线路径磨平，最后给出导航网格（navmesh）的简化思路，末节对照 Cocos Creator 3.8 怎么把地图数据喂进来。
13.2.1 直线追不上：墙的介入
问题的本质是：两点之间的直线可能不可通行。最朴素的修法是「撞墙就换方向」，也就是所谓的转向行为（steering）——朝目标走，遇到障碍就沿切线滑开。这类做法在开阔场景里够用，但在地图有凹形结构时会卡在局部最优：敌人贴着凹槽的边来回震荡，永远绕不出去。真正的解法是先在全局规划出一条可行路径，再让敌人沿路径走，把「去哪」和「怎么迈步」分开。
// 转向行为：局部避障，全局会卡在凹形结构里
function steer(e: Enemy, target: Vec2, dt: number): void {
const desired = normalize(sub(target, e.pos));
const ahead = add(e.pos, scale(desired, PROBE_DIST));
if (isBlocked(ahead)) {
// 沿墙面切线滑动——凹槽里会震荡
e.pos = add(e.pos, scale(perp(desired), SLIDE_SPEED * dt));
return;
}
e.pos = add(e.pos, scale(desired, SPEED * dt));
}
所以本节的主线是全局路径规划。我们把它做成一个与渲染无关的纯函数：输入一张可通行网格、起点、终点，输出一串格子坐标。这样它既能给敌人用，也能给玩家自动寻路、给道具做可达性检查复用。
13.2.2 网格与可通行判定
寻路的第一步是把连续世界离散成网格。mini2d 里关卡本身就是格子化的，所以直接复用：
export interface WalkGrid {
width: number;
height: number;
/** 返回 true 表示该格不可通行 */
blocked(x: number, y: number): boolean;
}
/** 由关卡格子数组构造，1 表示障碍 */
export function gridFromRows(rows: string[]): WalkGrid {
const height = rows.length;
const width = rows[0]?.length ?? 0;
return {
width,
height,
blocked(x: number, y: number): boolean {
if (x < 0 || y < 0 || x >= width || y >= height) return true;
return rows[y][x] === '1';
},
};
}
越界一律当作障碍，这条规则省掉了大量边界判断——blocked 的调用方不用再关心坐标是否合法。网格的粒度是个权衡：格子越小路径越精确，但搜索空间越大；《方块冲刺》用的是 32 像素一格，与美术资源对齐，避免出现「半个身位过不去」的诡异卡点。
13.2.3 A*：开放集、关闭集与三份代价
A* 的核心是给每个待扩展的格子算一个分数 f，由两部分组成：g 是从起点走到这里的实际代价，h 是从这里到终点的估计代价。每次从开放集里取 f 最小的格子扩展，直到摸到终点。先定义节点与代价函数：
export interface SearchNode {
x: number;
y: number;
g: number;
f: number;
parent: SearchNode | null;
}
export type Heuristic = (x: number, y: number, gx: number, gy: number) => number;
const key = (x: number, y: number): number => y * 100000 + x;
/** 四邻域：上下左右，代价 1 */
const DIRS: ReadonlyArray<readonly [number, number]> = [
[1, 0], [-1, 0], [0, 1], [0, -1],
];
开放集用「数组 + 线性扫描取最小」实现。这在教学代码里完全够用，因为关卡网格通常只有几十乘几十；如果地图大到几百格，再换成二叉堆，接口不变。关闭集用 Set 记录已经确定最优的格子，防止重复扩展：
export function findPath(
grid: WalkGrid,
sx: number, sy: number,
gx: number, gy: number,
h: Heuristic,
): Array<{ x: number; y: number }> | null {
if (grid.blocked(sx, sy) || grid.blocked(gx, gy)) return null;
const open: SearchNode[] = [];
const closed = new Set<number>();
const start: SearchNode = { x: sx, y: sy, g: 0, f: h(sx, sy, gx, gy), parent: null };
open.push(start);
while (open.length > 0) {
// 取 f 最小的节点：线性扫描，教学实现足够
let bestIdx = 0;
for (let i = 1; i < open.length; i++) {
if (open[i].f < open[bestIdx].f) bestIdx = i;
}
const cur = open.splice(bestIdx, 1)[0];
closed.add(key(cur.x, cur.y));
if (cur.x === gx && cur.y === gy) return reconstruct(cur);
for (const [dx, dy] of DIRS) {
const nx = cur.x + dx;
const ny = cur.y + dy;
if (grid.blocked(nx, ny)) continue;
if (closed.has(key(nx, ny))) continue;
const ng = cur.g + 1;
const existing = open.find((n) => n.x === nx && n.y === ny);
if (existing && ng >= existing.g) continue;
const node: SearchNode = { x: nx, y: ny, g: ng, f: ng + h(nx, ny, gx, gy), parent: cur };
if (existing) {
existing.g = ng;
existing.f = node.f;
existing.parent = cur;
} else {
open.push(node);
}
}
}
return null;
}
function reconstruct(node: SearchNode): Array<{ x: number; y: number }> {
const path: Array<{ x: number; y: number }> = [];
let cur: SearchNode | null = node;
while (cur) {
path.push({ x: cur.x, y: cur.y });
cur = cur.parent;
}
return path.reverse();
}
三个细节值得停下来看。第一，closed 里的格子不再进入开放集——这正是「关闭集」的作用，没有它搜索会指数膨胀。第二，当发现一条更短的到达路径时（ng < existing.g），我们原地更新开放集里那个节点的 g 和父指针，而不是再塞一个进去，否则同一个格子会有多份副本。第三，reconstruct 从终点沿 parent 回溯再 reverse，得到的是起点到终点的顺序。
13.2.4 启发函数：三种距离与一个铁律
h 的选法直接决定搜索效率。三种常见距离：
/** 曼哈顿距离：四邻域移动的最优启发，可采纳 */
export const manhattan: Heuristic = (x, y, gx, gy) =>
Math.abs(x - gx) + Math.abs(y - gy);
/** 欧氏距离：更「直」，但对四邻域会高估 */
export const euclidean: Heuristic = (x, y, gx, gy) =>
Math.hypot(x - gx, y - gy);
/** 切比雪夫距离：允许八向移动时用 */
export const chebyshev: Heuristic = (x, y, gx, gy) =>
Math.max(Math.abs(x - gx), Math.abs(y - gy));
有一条铁律：h 绝不能高估真实剩余代价（否则称为不可采纳，admissible），否则 A* 可能返回次优路径。四邻域移动下，曼哈顿距离恰好等于真实代价，是最稳的选择；欧氏距离在斜向情形下会小于真实代价，因此也安全，但搜索的格子数更多（它「看起来」更近，A* 会更贪心地往终点扑）。切比雪夫只在允许八向移动时才与真实代价匹配。结论：四邻域用曼哈顿，八邻域用切比雪夫，不要随手抓一个。
13.2.5 路径平滑：从折线到视线
A* 在网格上走，输出的是「一格一格」的折线，敌人沿它走会像机器人一样走直角。平滑的做法叫视线拉直（string pulling）：从当前点出发，尽量往后找一个「还能直线看到」的最远点，把中间的拐点全丢掉：
/** 网格上的 Bresenham 视线：两点之间是否全可通行 */
export function lineOfSight(
grid: WalkGrid, x0: number, y0: number, x1: number, y1: number,
): boolean {
let dx = Math.abs(x1 - x0);
let dy = -Math.abs(y1 - y0);
const sx = x0 < x1 ? 1 : -1;
const sy = y0 < y1 ? 1 : -1;
let err = dx + dy;
let x = x0;
let y = y0;
for (;;) {
if (grid.blocked(x, y)) return false;
if (x === x1 && y === y1) return true;
const e2 = 2 * err;
if (e2 >= dy) { err += dy; x += sx; }
if (e2 <= dx) { err += dx; y += sy; }
}
}
export function smooth(
grid: WalkGrid, path: Array<{ x: number; y: number }>,
): Array<{ x: number; y: number }> {
if (path.length <= 2) return path;
const out = [path[0]];
let anchor = 0;
for (let i = 2; i < path.length; i++) {
if (!lineOfSight(grid, path[anchor].x, path[anchor].y, path[i].x, path[i].y)) {
out.push(path[i - 1]);
anchor = i - 1;
}
}
out.push(path[path.length - 1]);
return out;
}
lineOfSight 用的是 Bresenham 直线算法，逐格步进检查，只要中途撞到障碍就返回 false。smooth 维护一个 anchor（锚点），一旦锚点到当前点不再直线可达，就把上一个点收进结果并更新锚点。注意平滑只改变折线的形状，不改变可达性——所有保留的点仍在原路径上，所以不会穿墙。
13.2.6 导航网格：把格子合并成凸多边形
网格 A* 的缺点是路径贴格子，且格子越多内存与搜索越贵。业界更常用导航网格（navmesh）：把可通行区域预先合并成一堆凸多边形，在「多边形 + 邻接关系」这张图上搜索，再在走廊里做通道拉直。凸多边形有个好性质——多边形内任意两点连线都在内部，所以路径穿过多边形时可以直接拉直，天然得到平滑结果，不必再做 13.2.5 的视线检查。
mini2d 不做完整的多边形剖分，但有一个简化思路值得写出来：把连续的同类格子合并成矩形（greedy meshing），每个矩形当作一个导航节点，邻接关系由共享边决定：
export interface NavRect { x: number; y: number; w: number; h: number; }
/** 把可通行格贪心合并成矩形，作为 navmesh 的简化替身 */
export function mergeRects(grid: WalkGrid): NavRect[] {
const used = new Set<number>();
const rects: NavRect[] = [];
for (let y = 0; y < grid.height; y++) {
for (let x = 0; x < grid.width; x++) {
if (grid.blocked(x, y) || used.has(key(x, y))) continue;
let w = 1;
while (x + w < grid.width && !grid.blocked(x + w, y) && !used.has(key(x + w, y))) w++;
let h = 1;
outer: while (y + h < grid.height) {
for (let i = 0; i < w; i++) {
if (grid.blocked(x + i, y + h) || used.has(key(x + i, y + h))) break outer;
}
h++;
}
for (let j = 0; j < h; j++) {
for (let i = 0; i < w; i++) used.add(key(x + i, y + j));
}
rects.push({ x, y, w, h });
}
}
return rects;
}
这一步的收益是搜索节点数从格数降到矩形数，在一张空旷的地图上往往能少一个数量级。代价是合并本身要花时间，所以通常预计算一次并随关卡数据一起存盘，运行时只做矩形图上的 A*。完整的 navmesh 还会做多边形剖分与边缘优化，思路与此一致。
13.2.7 Cocos 对照：TiledMap 与 TiledLayer
Cocos Creator 3.8 提供了 Tiled 地图组件，可以把 Tiled 编辑器产出的 .tmx 直接渲染出来，并暴露出格子数据供寻路读取。cc.d.ts 里 TiledMap extends Component，对外方法包括 getMapSize(): math.Size、getTileSize(): math.Size、getLayers(): TiledLayer[]、getLayer(layerName: any): TiledLayer | null、getObjectGroup(groupName: string): TiledObjectGroup | null。拿到图层后，TiledLayer（export class TiledLayer extends UIRenderer）有 getTileGIDAt(x: number, y: number): number | null 与 getTiledTileAt(x, y, forceCreate?): TiledTile | null：
import { _decorator, Component, TiledMap, TiledLayer } from 'cc';
const { ccclass, property } = _decorator;
@ccclass('TiledWalkGrid')
export class TiledWalkGrid extends Component {
@property(TiledMap)
public map: TiledMap | null = null;
@property
public collisionLayerName = 'collision';
buildGrid(): WalkGrid | null {
if (!this.map) return null;
const size = this.map.getMapSize();
const layer: TiledLayer | null = this.map.getLayer(this.collisionLayerName);
if (!layer) return null;
return {
width: size.width,
height: size.height,
blocked: (x: number, y: number) => {
const gid = layer.getTileGIDAt(x, y);
// GID 为 0 表示空，非 0 即碰撞层上放了格子
return gid !== null && gid !== 0;
},
};
}
}
注意 Tiled 的坐标系 y 轴向下，而 Cocos 世界坐标 y 轴向上，TiledLayer.getPositionAt(pos: math.IVec2Like | number, y?: number): math.Vec2 | null 会把格子坐标转成节点坐标，直接用它可以省掉自己写翻转。math.Vec2 定义在 export namespace math 下（export class Vec2 extends ValueType），静态方法有 distance、squaredDistance、subtract、normalize 等——把 13.2 的向量工具换成 math.Vec2 的静态方法即可，语义完全一致。
一个关键差异：Cocos 没有内置寻路，导航网格与 A* 都要自己实现或引第三方库。所以本节写的 findPath 可以直接搬进 Cocos 工程，只是把 WalkGrid 的数据源从「字符串数组」换成「TiledLayer.getTileGIDAt」。另外，.tmx 地图文件需 Tiled 编辑器或 Cocos Creator 3.8 编辑器制作与导入，本节无法命令行复现——但读取它产出的格子数据这段逻辑，是可以脱离编辑器用纯 TS 单测覆盖的。下一节我们把「地图从哪来」这件事讲透：关卡数据与程序化生成。
阅读导航：上一节：13.1 有限状态机与行为树 · 下一节：13.3 关卡数据与程序化生成 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。