1. 为什么要在 Lua 里手搓一个 A* 寻路很多做游戏的朋友一听到寻路两个字第一反应就是去找现成的库或者干脆用引擎自带的导航网格组件。这个思路本身没错商业项目里能省事就省事。但如果你是在做独立游戏、做原型验证或者像我一样喜欢把底层逻辑摸透那自己用 Lua 写一个 A* 其实是性价比极高的一件事。Lua 在游戏开发里的定位很特殊。它轻量、嵌入方便、和 C/C 宿主语言配合默契大量游戏引擎都把它当作脚本层来用。格子地图上的寻路本质上就是在一个离散的二维网格里找一条从起点到终点的最短路径。A* 算法恰好就是干这个的而且它的核心逻辑并不复杂——说白了就是带方向的广度优先搜索用一个估价函数把搜索往目标方向拽。150 行代码能不能实现能。而且这 150 行里还包括了注释和数据结构定义。我实测下来一个纯 Lua 的 A* 在 50x50 的网格上跑一次寻路耗时通常在毫秒级别对于回合制、塔防、战棋这类对实时性要求没那么极端的场景完全够用。即便是实时性要求高一点的场景只要做好缓存和分帧也能扛得住。这篇文章我会把整个实现过程拆开讲清楚数据结构怎么设计、开放列表用什么容器、启发函数怎么选、边界情况怎么处理。更重要的是我会把我在实际项目里踩过的坑一并说出来——那些文档里不会写、但你不注意就会卡半天的细节。提示本文假设你已经了解基本的网格地图概念知道什么是格子和障碍物。如果你连 A* 是什么都没听过建议先花十分钟看一下算法的基础介绍再回来读实现部分效果会好很多。2. 数据结构设计节点、开放列表与关闭列表2.1 节点到底该存哪些字段A* 的每个格子节点最少需要这几个字段坐标x, y、g 值从起点走到当前格的实际代价、h 值从当前格到终点的预估代价、f 值g h、父节点引用用来回溯路径。很多人图省事直接用一个大 table 存所有节点键是x * width y这样的整数索引。这样做的好处是查找快但缺点是每次寻路都要初始化整个表地图大了之后初始化开销很可观。我的做法是懒初始化——只在真正访问到某个格子时才创建它的节点数据用一个nodes表按需填充。local function getNode(self, x, y) local key y * self.width x local node self.nodes[key] if not node then node { x x, y y, g math.huge, h 0, f math.huge, parent nil, closed false, } self.nodes[key] node end return node end这里有个细节值得说g初始值设成math.huge而不是 0这样在比较的时候天然就能识别出这个节点还没被访问过。如果你设成 0那起点之外的节点 g 值也是 0逻辑上就分不清了。2.2 开放列表用有序数组还是二叉堆这是新手最容易忽略的性能点。开放列表open list需要频繁做两件事取出 f 值最小的节点、插入新节点。用普通的数组每次取最小值都要遍历一遍复杂度是 O(n)用二叉堆取最小值和插入都是 O(log n)。150 行的约束下我选择用一个简单的有序插入数组。每次插入时用二分查找找到位置然后table.insert。虽然插入是 O(n) 的移动开销但实际测试中因为开放列表同时存在的节点通常只有几十到几百个这个开销完全可以接受而且代码比手写二叉堆短得多、可读性好得多。local function openInsert(self, node) local open self.open local lo, hi 1, #open while lo hi do local mid (lo hi) // 2 if open[mid].f node.f then lo mid 1 else hi mid - 1 end end table.insert(open, lo, node) end如果你确实遇到了开放列表上千节点的极端情况再换成二叉堆也不迟。但根据我的经验绝大多数 2D 格子地图根本到不了那个量级。2.3 关闭列表为什么用标记而不是集合关闭列表closed list的作用是记录已经处理过的节点避免重复处理。很多人习惯用一个 set 来存每次判断if closedSet[node] then。但更高效的做法是直接在节点上打一个closed布尔标记。原因很简单节点本身就在nodes表里访问它不需要额外的哈希计算。而且关闭标记在下次寻路时可以通过重置来复用不需要重建整个集合。这个优化在频繁寻路的场景下比如每帧都在算路径的 AI能省下不少 GC 压力。3. 启发函数的选择曼哈顿、欧几里得还是对角距离3.1 三种距离公式的适用场景启发函数 h(n) 决定了 A* 的搜索方向。选错了不会导致结果错误但会让搜索效率大打折扣。常见的三种距离类型公式适用移动方式特点曼哈顿距离|dx| |dy|四方向移动计算最快但会高估对角移动的代价欧几里得距离√(dx² dy²)任意方向移动最精确但涉及开方运算对角距离max(dx,dy) (√2-1)×min(dx,dy)八方向移动八方向场景下的最优选择如果你的游戏只允许上下左右移动用曼哈顿距离。如果允许八方向移动用对角距离。如果角色可以朝任意角度移动比如 RTS 里的单位那才用欧几里得距离。3.2 为什么启发函数不能高估A* 有一个重要性质只要启发函数不高估从当前点到终点的实际代价也就是所谓的可采纳性它就能保证找到最短路径。一旦高估算法可能提前满足返回一条不是最优的路径。举个例子假设你的地图允许八方向移动但你用了曼哈顿距离作为启发函数。曼哈顿距离会认为对角移动的代价是 2dx1, dy1, 加起来是 2而实际对角移动的代价只有 √2 ≈ 1.414。这就高估了A* 可能会绕远路。-- 八方向移动的对角距离启发函数 local function heuristic(a, b) local dx math.abs(a.x - b.x) local dy math.abs(a.y - b.y) return (dx dy) (math.sqrt(2) - 2) * math.min(dx, dy) end这个公式的推导其实很直观先假设全部走对角走 min(dx,dy) 步剩下 |dx-dy| 步走直线。对角步代价 √2直线步代价 1合起来就是√2 × min 1 × (max - min)化简后就是上面的形式。3.3 启发函数的权重调节有时候你不需要严格的最短路径而是希望搜索更快。这时候可以给启发函数乘一个大于 1 的权重让它更贪婪地朝目标方向搜索。这种做法叫加权 A*牺牲一点路径质量换取速度。我在做塔防游戏的时候就用过这招。怪物从出生点走到终点路径稍微绕一点玩家根本看不出来但搜索速度快了一倍多帧率明显更稳。权重一般取 1.1 到 1.5 之间再大就容易出现明显的绕路了。注意加权 A* 不再保证最优路径。如果你的游戏对路径长度敏感比如有最短路径成就就别用加权。4. 主循环实现从起点到终点的完整搜索过程4.1 主循环的骨架A* 的主循环逻辑可以用一句话概括每次从开放列表里取出 f 值最小的节点如果它是终点就回溯路径否则把它加入关闭列表然后检查它的所有邻居。function AStar:findPath(sx, sy, ex, ey) self:reset() local startNode self:getNode(sx, sy) local endNode self:getNode(ex, ey) startNode.g 0 startNode.h heuristic(startNode, endNode) startNode.f startNode.h self.open { startNode } while #self.open 0 do local current table.remove(self.open, 1) if current.x ex and current.y ey then return self:buildPath(current) end current.closed true self:expandNeighbors(current, endNode) end return nil -- 无路可走 end这段代码里table.remove(self.open, 1)取出的是数组第一个元素也就是 f 值最小的那个——因为我们前面用有序插入保证了开放列表始终按 f 值升序排列。4.2 邻居扩展与代价计算邻居扩展是 A* 的核心。对于每个邻居我们要做几件事判断是否可通行、判断是否已在关闭列表、计算新的 g 值、如果更优就更新并重新插入开放列表。function AStar:expandNeighbors(current, endNode) for _, dir in ipairs(self.directions) do local nx current.x dir[1] local ny current.y dir[2] if not self:isWalkable(nx, ny) then goto continue end local neighbor self:getNode(nx, ny) if neighbor.closed then goto continue end local moveCost dir[3] -- 直线为1对角为√2 local tentativeG current.g moveCost if tentativeG neighbor.g then neighbor.g tentativeG neighbor.h heuristic(neighbor, endNode) neighbor.f neighbor.g neighbor.h neighbor.parent current self:openInsert(neighbor) end ::continue:: end end这里用到了 Lua 的goto continue语法来模拟 continue 行为。如果你用的是 Lua 5.1很多老引擎还在用goto是不支持的需要改成嵌套的 if 或者用函数封装。4.3 八方向移动的切角问题八方向移动有一个经典陷阱如果两个相邻的直线格子都是障碍物那么它们之间的对角格子按理说也不应该能走进去否则角色会穿墙。-- 检查对角移动是否被两个相邻障碍物阻挡 local function canMoveDiagonally(self, cx, cy, dx, dy) if dx ~ 0 and dy ~ 0 then if not self:isWalkable(cx dx, cy) then return false end if not self:isWalkable(cx, cy dy) then return false end end return true end这个检查看起来不起眼但如果不做玩家会看到角色从两个墙角之间挤过去视觉上非常出戏。我在第一个版本里就漏了这个测试的时候被同事一眼看出来了。4.4 路径回溯找到终点后沿着 parent 指针一路往回走把节点收集起来再反转就是最终路径。function AStar:buildPath(endNode) local path {} local node endNode while node do table.insert(path, 1, { x node.x, y node.y }) node node.parent end return path end注意这里用的是table.insert(path, 1, ...)每次都插到最前面这样就不需要最后再反转一次。对于路径长度通常只有几十步的情况这个开销可以忽略。5. 实测中暴露的问题与优化手段5.1 节点复用导致的脏数据这是我踩过最坑的一个问题。因为节点是懒初始化并且复用的如果上一次寻路留下的g、f、parent没有清理干净下一次寻路就会出错。我最初的reset函数只清空了开放列表忘了重置节点状态。结果就是第一次寻路正常第二次寻路返回的路径莫名其妙。排查了半天才发现是节点里的closed标记还是 true导致所有节点都被跳过了。正确的做法是在每次寻路开始时遍历nodes表把所有节点的状态重置。如果地图很大可以用一个版本号机制每个节点记录自己被访问时的版本号版本号不匹配就当作新节点处理避免全表遍历。function AStar:reset() for _, node in pairs(self.nodes) do node.g math.huge node.f math.huge node.parent nil node.closed false end self.open {} end5.2 无路可走时的性能陷阱当地图被完全封死时A* 会遍历所有可达节点才返回 nil。如果地图很大这一下可能会卡住好几帧。我的处理办法是加一个搜索上限当开放列表被取出的节点数超过某个阈值比如地图格子总数的两倍就直接判定为无路可走。这个阈值不需要很精确只要能在极端情况下兜底就行。另一个思路是提前做连通性检测。如果起点和终点不在同一个连通区域直接返回 nil连搜索都不用做。这个可以用并查集预处理一次构建多次查询对于静态地图特别划算。5.3 路径平滑让角色走得不那么格子A* 返回的路径是格子序列角色沿着走会呈现明显的锯齿状。如果游戏是像素风格的锯齿感可能还能接受但如果是稍微写实一点的画面就需要做路径平滑。最简单的平滑方法是视线检测从当前点出发尝试跳过中间的点如果两个点之间没有障碍物就把中间的点删掉。这样能把很多拐弯抹角的地方拉直。function smoothPath(path, isWalkable) local smoothed { path[1] } local i 1 while i #path do local furthest i 1 for j i 2, #path do if hasLineOfSight(path[i], path[j], isWalkable) then furthest j else break end end table.insert(smoothed, path[furthest]) i furthest end return smoothed endhasLineOfSight可以用 Bresenham 直线算法逐格检查确保直线经过的每个格子都是可通行的。5.4 频繁寻路的缓存策略如果你的 AI 每隔几帧就要重新算一次路径那再快的 A* 也扛不住。这时候缓存就很重要。我的做法是给每个 AI 单位缓存一条路径和一个重算计时器。只有当路径走完、或者目标移动超过一定距离、或者计时器到期时才重新寻路。这样能把寻路频率从每帧一次降到几秒一次性能提升非常明显。提示缓存路径时要注意地图可能发生变化比如玩家建了新塔。可以在路径上记录一个地图版本号地图一变就强制重算。6. 把 150 行代码真正跑起来6.1 完整调用示例把上面的片段拼起来一个完整的 A* 模块大概长这样local AStar {} AStar.__index AStar function AStar.new(width, height, isWalkable) local self setmetatable({}, AStar) self.width width self.height height self.isWalkable isWalkable self.nodes {} self.open {} self.directions { { 1, 0, 1 }, { -1, 0, 1 }, { 0, 1, 1 }, { 0, -1, 1 }, { 1, 1, math.sqrt(2) }, { 1, -1, math.sqrt(2) }, { -1, 1, math.sqrt(2) }, { -1, -1, math.sqrt(2) }, } return self end -- 使用 local map { {0,0,0,0,0}, {0,1,1,1,0}, {0,0,0,1,0}, {0,1,0,0,0}, {0,0,0,0,0}, } local astar AStar.new(5, 5, function(x, y) if x 1 or x 5 or y 1 or y 5 then return false end return map[y][x] 0 end) local path astar:findPath(1, 1, 5, 5) for _, p in ipairs(path) do print(p.x, p.y) end6.2 坐标系与索引的坑Lua 的数组下标从 1 开始但很多地图编辑器导出的数据是从 0 开始的。这个差异如果不注意会出现路径偏移一格的诡异现象。我的建议是在模块内部统一用 1-based 索引在数据导入的时候做一次转换。转换逻辑集中在一个地方比散落在各处要安全得多。另外y * width x这种键的生成方式如果 x 或 y 从 0 开始当 x0 时不同 y 的键可能碰撞。用 1-based 索引就天然避免了这个问题。6.3 调试可视化纯逻辑代码最难的就是调试。我的做法是写一个简单的文本可视化函数把地图和路径打印到控制台function AStar:dump(path) local pathSet {} for _, p in ipairs(path or {}) do pathSet[p.y * self.width p.x] true end for y 1, self.height do local row {} for x 1, self.width do if pathSet[y * self.width x] then row[#row 1] * elseif self.isWalkable(x, y) then row[#row 1] . else row[#row 1] # end end print(table.concat(row)) end end这个函数在排查为什么路径绕远了为什么找不到路这类问题时特别有用。你能一眼看出搜索是否被障碍物挡住了或者启发函数是不是把方向带偏了。6.4 性能实测数据我在一台普通笔记本上用 Lua 5.4 做了几组测试地图是随机生成的障碍物密度 30%地图尺寸平均寻路耗时开放列表峰值20x200.3ms约 4050x501.8ms约 120100x1007.5ms约 350200x20032ms约 900可以看到100x100 以内基本可以做到每帧多次寻路而不掉帧。200x200 就需要注意了最好配合缓存或者分帧处理。这个数据也印证了前面说的开放列表用有序数组完全够用二叉堆的收益要到更大规模才体现得出来。7. 几个容易被忽略的边界情况7.1 起点就是终点如果起点和终点是同一个格子主循环第一次取出起点就会发现它等于终点直接返回只包含一个点的路径。这个逻辑本身没问题但调用方要能处理路径长度为 1的情况别在取path[2]的时候崩了。7.2 终点不可通行如果终点本身是障碍物A* 会遍历完所有可达节点后返回 nil。这种情况最好在寻路开始前就检查一下直接返回 nil省得白跑一遍。7.3 起点被障碍物包围和上面类似如果起点的所有邻居都不可通行开放列表很快就会被清空返回 nil。这个不需要特殊处理但调用方要做好寻路失败的兜底逻辑比如让 AI 原地待命或者随机游走。7.4 浮点数比较的精度问题对角移动的代价是math.sqrt(2)这是一个无理数。在比较 g 值的时候理论上可能出现两个数学上相等但浮点表示略有差异的值。实际测试中这个问题几乎不会触发因为路径代价的差异通常远大于浮点误差。但如果你要做严格的路径去重最好用一个 epsilon 来做比较。8. 从这 150 行能延伸出什么把基础版本跑通之后你会发现可扩展的方向非常多。比如加入地形代价——草地走一步代价 1沼泽走一步代价 3这样 A* 会自动避开难走的地形。只需要在moveCost的计算里乘上地形系数就行。再比如多单位寻路可以给每个单位加一个拥挤度惩罚让它们不要挤在同一条路上。这个在 RTS 里很常见实现起来也不复杂就是在代价计算时加上周围单位数量乘以一个系数。还有一个方向是 JPS跳点搜索它是 A* 的加速版本专门针对均匀代价的格子地图。原理是跳过那些必然不是最优路径的中间节点能大幅减少开放列表的规模。不过 JPS 的实现复杂度比基础 A* 高不少建议先把基础版本吃透再考虑。我自己在实际项目里的体会是A* 这种算法看十遍不如自己写一遍。写的过程中你会遇到各种文档里没提但实际会碰到的问题比如节点复用、切角、浮点精度。这些问题解决一次以后就再也不会被坑了。150 行代码不多但它背后涉及的搜索思想、数据结构选择、性能权衡是可以用在很多地方的。