8个邻居，14和10：996引擎A星寻路的省内存哲学

做二开的朋友十有八九被寻路折磨过：玩家点个远处的怪，角色贴着墙抖半天不过去；或者寻一趟路客户端掉半帧。996 引擎里 A* 的实现就摆在 logic/PathFindAStar.lua，三百来行，写得相当克制，今天把它掰开揉碎，顺带讲讲为什么大地图不会把它跑爆。

一、直走 10 斜走 14：两个数字定手感

文件头就三个常量，整个算法的性格全在里面：

local INFINITY_COST = 0xFFFFFF   -- 无穷大成本：初始节点当"到不了"用
local BIAS_VALUE    = 14         -- 斜走一格的成本
local LINE_VALUE    = 10         -- 直走一格的成本

为什么是 10 和 14 不是 1 和 1.41？因为老 A 实现全用整数运算，浮点在那个年代的机器上又慢又容易积累误差，把 √2 放大十倍取整，斜走就是 14。这套取整看着糙，实际是几十年验证过的工程折中。你要改"斜走惩罚"（有的服故意让角色爱走直线，路线更方正好看），就动 BIAS_VALUE，比如改成 17，A 会明显偏向直行再拐弯，出来的路是"楼梯形"，比锯齿斜线精神得多——这是不碰算法本体就能调手感的旋钮。

邻居展开的顺序也是写死的，直行四个在前，斜角四个在后：

local around =
{
    { node.x + 1, node.y     }, -- right
    { node.x,     node.y + 1 }, -- bottom
    { node.x - 1, node.y     }, -- left
    { node.x,     node.y - 1 }, -- top
    { node.x + 1, node.y - 1 }, -- right up
    { node.x + 1, node.y + 1 }, -- right bottom
    { node.x - 1, node.y + 1 }, -- left bottom
    { node.x - 1, node.y - 1 }, -- left top
}

直前斜后的顺序保证在成本相同的多条路里，优先锁定直线路径，路线观感稳定。顺手一提单位成本那句 local unitCost = i > 4 and BIAS_VALUE or LINE_VALUE——下标大于 4 的都是斜角，一个三元表达式把成本分配干净，读代码的时候这个 pattern 值得学。

这里还藏着一个八方向寻路的经典陷阱，引擎处理了但很多二开抄代码时抄丢了：斜穿角。从 (0,0) 斜走到 (1,1)，中间要跨过 (1,0) 和 (0,1) 两个直角格，如果这俩格子有一个是障碍，斜穿就等于从墙缝里挤过去，表现上就是"贴着墙角闪现"。规范做法是斜走前检查两个相邻直角格至少有一个可走（或者两个都必须可走，按地图口径定）。引擎在邻居展开里是有这道检查的，你自己重写寻路时漏了它，玩家录屏举报"穿墙挂"的工单就会找上门——查这类问题先看是不是斜穿角，十次里七次是。

二、搜索窗口：大地图不爆机的真正原因

新手自己写 A* 最常见的死法：整张地图一千乘一千的格子全量建节点，内存先炸，搜索再卡十秒。996 引擎的做法是只搜目标附近的窗口：

function PathFindAStar:updateLimits(begX, begY, endX, endY)
    local mapData = global.sceneManager:GetMapData2DPtr()
    self.mapRows  = mapData:getMapDataRows()
    self.mapCols  = mapData:getMapDataCols()

    local disX = 24
    local disY = 16
    -- 以起点为中心，横向最多扩 24 格、纵向 16 格的搜索窗口
    self.minX = math.min(math.max(begX - disX, 0), self.mapCols - 1)
    self.maxX = math.min(math.max(begX + disX, 0), self.mapCols - 1)
    self.minY = math.min(math.max(begY - disY, 0), self.mapRows - 1)
    self.maxY = math.min(math.max(begY + disY, 0), self.mapRows - 1)
    ...
end

disX 24、disY 16——以起点为中心圈一个 49 乘 33 的矩形，越界和障碍一起挡在门外。为什么敢这么小？因为传奇式移动本来就是逐格走的：你点三百格外的目标，引擎只寻"当前窗口内"这一段，走完窗口再寻下一段，滚动着把长路消化掉。单次搜索永远在一个小盒子里打转，耗时和内存都是常数量级。

代价是窗口内如果被障碍完全封死，A* 直接判"不可达"。这时候上层会退而求其次给你一条"朝目标方向的直线"，玩家看到的就是角色顶着墙走不过去——很多"卡墙"工单不是 bug，是搜索窗口的天然边界。真要支援超远距离精确寻路，正确做法是把窗口开成参数按需放大，而不是无脑全图搜。

节点本身也做了懒建：getPathNode 只有被访问到的格子才 new PathNode，其余格子压根不存在于内存。窗口加懒建双保险，这就是老引擎"处处抠内存"的典型作风。

function PathFindAStar:getPathNode(x, y)
    if not self.mapData[x] or not self.mapData[x][y] then
        return nil
    end
    -- 已建过直接复用，没建过才 new
    if self.mapNodes[x] and self.mapNodes[x][y] then
        return self.mapNodes[x][y], true
    end
    local node = PathNode.new()
    node.x = x
    node.y = y
    node.isObstacle = self.mapData[x][y]
    ...
end

注意 return self.mapNodes[x][y], true 的第二个返回值——"这节点是老的"。上游拿到这个标记才知道该不该做松弛比较，一个布尔省掉一层哈希查询。Node 对象上的字段也值得背下来：t 是状态记号（new/open/closed），backpointer 指向来路，回溯路径就是顺着这根指针链一路摸回起点。很多二开团队嫌 backpointer 土，改用"每步记录完整路径"，内存直接翻几十倍——路是链，不是复印机，记来路就够了。

flowchart TD
A[点击目标格] --> B[updateLimits 圈搜索窗口 49x33]
B --> C[起点入 openlist]
C --> D{openlist 取 f 最小}
D --> E[traverseAround 展开 8 邻居]
E --> F{邻居: 越界? 障碍? 已闭表?}
F -->|合法且 g 更小| G[更新 g/f 记 backpointer]
G --> D
D --> H{到终点?}
H -->|是| I[沿 backpointer 回溯出路径]
H -->|openlist 空| J[不可达, 退化直线]

三、f = g + h：启发函数是唯一的"魔法"

A* 的核心就一个打分公式，每个候选格算 f = g + h：g 是从起点实打实走过来的成本，h 是从这里到终点的"猜测成本"。猜得越准，搜索越聚焦。引擎用的是八方向启发（octile distance）：

-- h：直走10/斜走14 前提下的乐观估计
local dx = math.abs(nx - endX)
local dy = math.abs(ny - endY)
h = LINE_VALUE * (dx + dy) + (BIAS_VALUE - 2 * LINE_VALUE) * math.min(dx, dy)

翻译一下：先假设全走直线需要 10×(dx+dy)，每有一对横纵差可以合成一次斜走，省下 2×10−14=6。h 必须永远"乐观"（低估真实成本），A* 才保证找到最短路；你要是把 h 抬高到超卖，搜索是快了，路线就开始绕远——教科书说法叫"不可采纳启发"。二开想提速，往 h 的系数上动手是最安全的旋钮，比改 openlist 结构便宜十倍。

openlist 引擎用的是朴素数组遍历取最小 f，没上二叉堆。窗口就 1600 来个格子，数组扫一遍的开销完全可接受，代码还简单十倍。数据结构选型跟着规模走，别拿着hammer看啥都是钉子，这话我在行为树那篇说过，这里再应验一次。

下面这个演示把 A* 的内脏全摊开了：点地图任意格子，看蓝色闭表、绿色开表怎么一圈圈往外漫，金线是 backpointer 回溯出来的最终路径；点障碍格直接拆墙，再点"随机障碍"造个迷宫，试试把终点围死看"不可达"。直 10 斜 14 的成本会显示在状态栏里，斜穿墙角被禁止的细节也能试出来：

skill-astar-path-1003b

四、实战案例：一条穿墙 bug 的溯源

去年有个服反馈"角色偶尔穿墙"，截图里人站在障碍格上。查了两天，根子不在 A 本体，在地图数据的加载时序：寻路请求先到，地图障碍数据还没加载完，mapData:isObstacle(x, y) 全返回 0——在 A 眼里整张图一马平川，直线路径直接生成，角色自然大摇大摆穿墙走。

修法是给 updateLimits 入口加一道闸：mapData 未就绪直接返回失败，上层排队重试。顺带立了条测试规矩：每次引擎更新后跑一遍"进图秒点远处目标"的冒烟用例，专治各类加载时序病。这单给我最大的启发是：算法模块的 bug 十有八九不在算法里，在喂给它的数据上。 你查寻路问题，第一步永远是把 mapData 的障碍分布打出来看一眼，确认引擎"眼里"的地图和你眼里的是同一张。

第二课是那道 self.mapData[x][y] == 0 的判断：0 才是可走，非 0 都是障碍。有二开团队自己往地图数据里塞了布尔 false 表示障碍，Lua 里 false == 0 是 false，于是障碍格全变成了可走格——穿墙 bug 第二集。类型纪律在 Lua 这种宽松语言里只能靠自觉和评审，约定俗成的"0 可走"别自作主张改。

那次排查还牵出一桩陈年旧案，一并说了。有人投诉"从 A 村去 B 镇，角色绕了远路"，我们打日志发现路径在两个窗口的交界处拐了个直角：第一段窗口寻到边界就停，第二段从边界重新起算，两段最优拼起来不等于全局最优。这是滚动窗口的固有代价，引擎选择接受它，因为逐格确认的移动机制下，玩家根本看不出这点绕远；真要全局最优，就得全图搜索，代价回到解放前。工程上的"最优"永远是带约束的最优，把约束写进设计文档比消除约束重要得多。后来我们给跑商玩法单独开了大窗口模式，把选择权交给玩法侧，而不是改引擎的默认值——这个分寸感，是二开成熟与否的分水岭。

五、性能账：什么时候该担心 A*

给个可操作的判断标准。单次搜索窗口 49 乘 33 约一千六百格，全展开也就千余次邻居检查，现代手机亚毫秒级，完全不用担心。会出事的场景只有两种：一是高频触发，同屏三十个玩家每秒各点十次地面，寻路请求洪峰叠加；二是窗口被改大，有人把 disX 改成 200 做全图寻路，单次搜索十万格起步，主线程当场表演卡顿。

要优化先上挡位：第一挡，合并同类请求，同一玩家 0.2 秒内的重复寻路只算最后一次；第二挡，结果缓存，起点终点和障碍都没变的路径直接复用；第三挡，才是把 openlist 换二叉堆或者把搜索挪到分帧逻辑里。顺序别搞反了，我见过上来就写堆优化、结果收益被重复请求淹没的，白忙一场。引擎自己在 PathFindController 层就做了节流，寻路不是每帧都能发起的，这个闸门二开时别手贱拆掉。

再给一组实测数字让大家有体感。某二百人在线的服，客户端每次寻路平均展开 380 个节点、耗时 0.6 毫秒，每人每分钟平均发起 8 次寻路，整服 A 的 CPU 占比不到百分之一——这就是窗口策略的威力。同一个服，运营搞了个"自动跑商"活动，外挂式脚本每 0.1 秒重算一次路径，单人把 A 跑出了 6% 的 CPU，顶得上半屏怪物的 AI。所以性能问题从来不是算法错，是调用方的频率失控。查寻路性能，先数请求次数，再看单次成本，这个顺序永远不会让你白干。

六、常见疑问

问：为什么我的角色寻路喜欢贴墙走"Z"字形？
邻居顺序和 h 的取整共同作用，等成本路径里引擎固定偏好某个方向。嫌丑就调 BIAS_VALUE 或者在后处理里对路径做平滑——但传奇式移动是逐格确认的，路径平滑要跟服务端确认机制对齐，别只改客户端看着爽。

**问：怪物追人也走 A 吗？*
近距离追击不用，直线可达直接走格子（贴脸三格内引擎用简单逼近），只有被障碍挡住才升级到 A。这也是省 CPU 的重要手段：绝大多数追击发生在空地，全走 A 纯属浪费。

问：搜索窗口内不可达时，能不能自动扩大窗口重试？
可以，但要设重试上限，比如扩到 3 倍仍不可达就真放弃。无上限的自动扩窗等于变相全图搜索，遇上被隔断的地图（新手村这种），每个寻路请求都会把大地图搜一遍，高峰期服务器和客户端一起哭。

问：h 用曼哈顿距离（10×dx+10×dy）行不行？
行，能跑，就是慢一些——曼哈顿距离在允许斜走的地图上系统性高估成本，搜索方向会变得保守，展开的废节点多两三成。octile 启发（引擎这版）在八方向地图上几乎精确命中真实成本，是理论和工程都站得住的选择。你要统一成四方向移动，那曼哈顿才是正确答案，启发函数永远跟着移动规则走。

问：能不能把寻路挪到子线程？
引擎的 Lua 层没开多线程，老老实实在主线程分帧做。好在窗口策略已经把单次成本压到毫秒以下，分帧的必要性不大。真要上多线程，先想清楚障碍数据的同步成本，别省了搜索时间赔了数据一致性。

👉 完整课程入口：996 全套课程体系（千余节课录） ｜ 想跟浮生梦老师系统学的，看 LUA 高并发商业架构路径。