1. 为什么要在游戏里手写一个A*寻路先把结论摆在这儿A*寻路的核心逻辑其实非常短短到用Lua写出来只需要150行左右。很多人一听到“寻路算法”四个字脑子里立刻浮现出一大堆数学公式和复杂的图论概念觉得这东西必须依赖引擎自带组件或者第三方库才能跑起来。但实际情况是只要你的地图是标准的方格地图A*本身就是一个“带优先级的广度优先搜索”核心代码量远比想象中少。这篇文章适合三类人看第一类是做独立游戏或者小游戏开发地图规模不大不想引入重型寻路模块的开发者第二类是想真正搞懂A*内部运转机制而不是只会调API的进阶学习者第三类是在Lua环境下做原型验证需要快速把寻路跑通看效果的人。不管你之前有没有接触过寻路只要你会写基本的Lua循环和表操作这150行代码你就能吃透。我之所以选择用Lua来实现原因很直接。Lua在游戏脚本层的使用极其广泛语法轻、上手快、和宿主引擎的绑定成本低。很多游戏引擎的逻辑层都支持Lua你写完这套寻路之后可以直接嵌到项目里用不需要编译不需要额外依赖。而且Lua的table天然适合做开放列表和关闭列表的数据结构配合简单的排序就能实现优先队列的效果。注意这里说的150行指的是核心寻路逻辑不包含地图数据的加载和可视化渲染。如果你要把地图绘制、点击交互、路径动画全算进去代码量肯定会超过150行。但寻路算法本身确实可以压缩到这个量级。在展开具体实现之前我需要先说明一个前提这套方案针对的是方格地图也就是类似战棋、塔防、Roguelike里常见的那种格子地图。每个格子要么可走要么不可走移动代价默认相同。如果你的地图是导航网格或者路点图思路是一样的但邻居节点的定义方式需要调整这个后面会提到。2. A*算法的核心思路拆解2.1 从“盲目搜索”到“有方向地搜索”要理解A*得先理解它解决了什么问题。假设你在一张方格地图上从起点走到终点最笨的办法是广度优先搜索从起点开始一层一层往外扩直到碰到终点。这个办法一定能找到最短路径但问题是它“没有方向感”会往所有方向均匀扩散搜索范围非常大。A*的改进点在于它给每个待搜索的格子算了一个“分数”用这个分数来决定先搜哪个格子。这个分数由两部分组成G值从起点走到当前格子实际已经花掉的代价。H值从当前格子到终点预估还要花多少代价也叫启发值。两者相加就是F值也就是这个格子的综合评分。A*每次从开放列表里取出F值最小的格子来扩展这样搜索就会优先朝着终点方向推进而不是盲目地四面开花。用一个生活化的类比你要从家走到某个商场广度优先搜索相当于把周围所有街道都走一遍再决定方向A*相当于你手里有个指南针虽然你不知道具体路线但你知道商场大概在东北方向所以你会优先往东北方向的街道探索。这个“大概方向”就是启发函数H值的作用。2.2 启发函数怎么选直接影响效率启发函数的选择是A*实现里最关键的一个决策点。最常见的两种启发函数计算公式特点适用场景曼哈顿距离|dx| |dy|只允许上下左右移动时最准确四方向方格地图对角距离max(|dx|,|dy|) 或更精确的混合公式允许斜向移动时更贴近真实代价八方向方格地图欧几里得距离√(dx²dy²)理论最短但计算涉及开方任意方向移动选错启发函数会带来两个后果如果H值估得比实际代价大A*可能找不到最短路径如果H值估得比实际代价小很多搜索效率会下降退化成接近广度优先搜索。所以最稳妥的做法是让H值永远不超过实际移动代价在这个前提下H值越接近真实值搜索越快。对于四方向移动的方格地图曼哈顿距离是完美匹配的因为它和实际移动步数完全一致。对于八方向移动情况稍微复杂一点因为斜向移动的代价通常是直向的1.414倍左右这时候用简单的max(dx,dy)会高估代价需要用更精确的公式来修正。2.3 开放列表和关闭列表的职责划分A*运行过程中需要维护两个集合开放列表open list存放已经发现但还没处理的格子。每次从里面取F值最小的。关闭列表closed list存放已经处理过的格子避免重复处理。这两个列表的实现方式直接决定了算法的性能。在Lua里关闭列表可以用一个以格子坐标为key的table来实现查找复杂度是O(1)。开放列表稍微麻烦一点因为需要频繁取最小值如果每次都用遍历找最小在格子数量多的时候会明显变慢。实操心得在地图规模不超过几百个格子的情况下开放列表直接用数组加线性查找完全够用。不要一上来就想着上二叉堆那会把代码量拉上去而且在这个规模下性能差异你根本感知不到。先把逻辑跑通等真的遇到性能瓶颈再优化。3. 150行Lua代码的完整实现3.1 数据结构定义与地图表示先定义地图。最直观的方式是用二维数组0表示可走1表示障碍。但Lua里更推荐用一维表配合坐标转换或者直接用字符串数组来表示读起来更清晰。-- 地图定义0可走1障碍 local map { {0,0,0,0,0,0,0,0}, {0,1,1,1,0,1,0,0}, {0,0,0,1,0,0,0,0}, {0,1,0,0,0,1,1,0}, {0,0,0,1,0,0,0,0}, {0,1,0,0,0,1,0,0}, {0,0,0,0,0,0,0,0}, } local MAP_W #map[1] local MAP_H #map每个节点需要记录的信息包括坐标、G值、H值、F值、父节点。在Lua里用一个table表示local function createNode(x, y, g, h, parent) return { x x, y y, g g or 0, h h or 0, f (g or 0) (h or 0), parent parent } end这里有个细节F值我选择在创建时就计算好存下来而不是每次比较时现算。原因是开放列表里会反复比较F值存下来可以避免重复计算。虽然单次计算量很小但在搜索规模大的时候这个优化是有意义的。坐标转key的函数也很简单用字符串拼接或者数值编码都行local function posKey(x, y) return x * 1000 y end用数值编码比字符串拼接快因为避免了字符串创建的开销。这里乘以1000是假设地图宽度不超过1000实际项目中根据地图尺寸调整即可。3.2 启发函数与邻居节点生成启发函数用曼哈顿距离local function heuristic(x1, y1, x2, y2) return math.abs(x1 - x2) math.abs(y1 - y2) end邻居节点生成四方向版本local directions { {0, -1}, -- 上 {0, 1}, -- 下 {-1, 0}, -- 左 {1, 0}, -- 右 } local function getNeighbors(node) local neighbors {} for _, dir in ipairs(directions) do local nx node.x dir[1] local ny node.y dir[2] if nx 1 and nx MAP_W and ny 1 and ny MAP_H then if map[ny][nx] 0 then neighbors[#neighbors 1] {x nx, y ny} end end end return neighbors end这段代码做了两件事边界检查和障碍检查。注意Lua的数组下标从1开始所以坐标范围是1到MAP_W和1到MAP_H。这个细节如果搞错会出现越界访问或者漏掉边缘格子的问题。注意事项如果你的地图允许斜向移动邻居方向要加上四个对角方向同时移动代价要区分直向和斜向。直向代价设为1斜向代价设为1.414或者用10和14的整数近似。这时候启发函数也要相应调整否则会高估代价导致路径不是最优。3.3 主循环开放列表的取最小与扩展主循环是A*的核心逻辑如下local function findPath(startX, startY, endX, endY) local openList {} local closedList {} local startNode createNode(startX, startY, 0, heuristic(startX, startY, endX, endY), nil) openList[1] startNode while #openList 0 do -- 找F值最小的节点 local minIndex 1 for i 2, #openList do if openList[i].f openList[minIndex].f then minIndex i end end local current table.remove(openList, minIndex) -- 到达终点 if current.x endX and current.y endY then return reconstructPath(current) end -- 加入关闭列表 closedList[posKey(current.x, current.y)] true -- 扩展邻居 local neighbors getNeighbors(current) for _, n in ipairs(neighbors) do local key posKey(n.x, n.y) if not closedList[key] then local g current.g 1 local h heuristic(n.x, n.y, endX, endY) local newNode createNode(n.x, n.y, g, h, current) -- 检查是否已在开放列表中 local found false for i, node in ipairs(openList) do if node.x n.x and node.y n.y then found true if g node.g then openList[i] newNode end break end end if not found then openList[#openList 1] newNode end end end end return nil -- 无路径 end这段代码里有几个值得展开讲的点。第一取最小F值节点用的是线性查找。在开放列表长度不大的时候这比维护一个堆要简单得多而且不容易出bug。如果你确实需要优化可以把开放列表换成一个简单的二叉堆但代码量会增加三四十行。第二重复节点的处理。当一个邻居节点已经在开放列表里时如果新算出来的G值更小说明找到了一条更优的路径到达这个节点需要更新它的G值和父节点。这个判断是保证路径最优的关键漏掉的话可能得到次优路径。第三关闭列表的key用数值编码。前面定义的posKey函数在这里派上用场用数值做key比用字符串快而且不会产生额外的字符串对象。3.4 路径回溯与结果输出找到终点后需要从终点节点沿着parent指针一路回溯到起点local function reconstructPath(node) local path {} while node do table.insert(path, 1, {x node.x, y node.y}) node node.parent end return path end注意这里是从头部插入这样得到的路径就是从起点到终点的顺序。如果用table.insert(path, node)追加到尾部最后需要再反转一次。从头部插入在路径长度不大时没问题如果路径很长可以考虑先追加再反转效率更高。调用示例local path findPath(1, 1, 7, 7) if path then for _, p in ipairs(path) do print(string.format((%d, %d), p.x, p.y)) end else print(没有找到路径) end到这里核心代码加起来大概130到150行取决于你的注释密度和变量命名长度。这就是A*寻路的完整实现。4. 实际运行中会遇到的问题与排查4.1 路径不是最短的问题出在哪这是最常见的问题。A*找不到最短路径通常有三个原因原因一启发函数高估了实际代价。比如在四方向地图上用了欧几里得距离或者在对角移动地图上用了曼哈顿距离。启发函数高估会导致算法过早地认为某条路径是最优的从而错过真正的最短路径。解决办法是确保H值永远不超过从当前格子到终点的实际最小代价。原因二重复节点更新逻辑有误。前面提到当邻居节点已在开放列表中且新G值更小时需要更新。如果这个判断写反了或者忘记更新父节点就会导致路径回溯时走到错误的父节点上。原因三关闭列表加入时机不对。有些实现会在节点加入开放列表时就放入关闭列表这是错误的。关闭列表应该在节点被取出并处理时才加入否则会阻止更优路径的发现。排查方法很简单找一张小地图手动推演一遍A*的每一步把开放列表和关闭列表的变化打印出来对照你的代码输出很快就能定位到问题。4.2 搜索速度慢怎么优化当地图变大或者障碍物变复杂时搜索速度会明显下降。优化方向有几个优化手段具体做法效果代价开放列表改用二叉堆用数组实现最小堆取最小O(log n)显著提升增加约40行代码关闭列表用二维数组避免哈希计算小幅提升需要预分配内存启发函数加权H值乘以1.1~1.5搜索更快但可能次优路径质量下降跳点搜索JPS跳过大量对称路径大幅提升实现复杂度高实操心得在格子数量低于5000的场景下线性查找开放列表和哈希关闭列表的组合完全够用。我实测过一张60x60的地图障碍物密度30%从一角走到对角线性版本耗时在几毫秒级别玩家根本感知不到。不要过早优化。4.3 常见问题速查表现象可能原因解决方法返回nil但实际有路径邻居生成漏了方向或边界判断错误检查directions表和边界条件路径穿墙障碍判断条件写反确认map值为0才可走路径绕远路启发函数高估或重复节点未更新检查H值计算和G值比较逻辑死循环关闭列表未生效或节点重复加入确认关闭列表在取出时加入起点等于终点未做特判在函数开头判断起终点相同直接返回斜向移动穿墙角未检查对角方向的相邻格子斜向移动时额外检查两个直向邻居4.4 几个容易踩的坑坑一Lua的数组下标从1开始。如果你习惯其他语言从0开始在坐标转换和边界判断时很容易搞错。建议统一用1-based坐标地图数据也用1-based存储避免混用。坑二table.remove在循环中改变数组长度。在主循环里取出最小节点后开放列表长度会变化如果后面还有依赖原长度的操作需要重新获取#openList。我在代码里是先取出再扩展邻居顺序上没问题但如果你调整了代码结构要留意这个点。坑三浮点数比较。如果移动代价用了1.414这样的浮点数F值比较时可能出现精度问题。建议用整数代价直向10、斜向14最后除以10得到实际步数。这样既避免了浮点误差又保持了精度。坑四地图数据被意外修改。如果多个单位同时寻路而地图数据是共享的要确保寻路过程只读不写。关闭列表和开放列表必须是每次调用时新建的局部变量不能做成全局的。5. 从方格地图扩展到更复杂的场景5.1 八方向移动的代价调整四方向改八方向改动集中在三个地方directions表增加四个对角方向移动代价区分直向和斜向启发函数从曼哈顿距离换成对角距离。对角距离的精确公式是h (dx dy) (√2 - 2) * min(dx, dy)用整数近似就是h 10 * (dx dy) (14 - 20) * min(dx, dy) 10 * (dx dy) - 6 * min(dx, dy)这个公式保证H值不会超过实际代价同时比简单的max(dx,dy)更接近真实值搜索效率更高。5.2 不同地形代价的处理如果地图上有草地、沼泽、道路等不同地形移动代价不同A*同样能处理。只需要把getNeighbors里的固定代价1换成根据地形查表得到的代价local terrainCost { [0] 1, -- 普通地面 [2] 3, -- 沼泽代价高 [3] 0.5, -- 道路代价低 }注意启发函数仍然要用最小可能代价来估算否则会高估。如果最低代价是0.5启发函数算出来的值要乘以0.5保证不超过实际代价。5.3 性能优化的进阶方向当你的游戏地图达到几百乘几百的规模或者需要同时为几十个单位寻路时基础版A*可能会成为瓶颈。这时候可以考虑分层寻路把地图分成大区域先在区域级别寻路再在区域内部寻路。适合超大地图。路径缓存对频繁请求的起终点对缓存结果避免重复计算。异步寻路把寻路放到协程里分帧执行避免单帧卡顿。跳点搜索利用方格地图的对称性跳过大量不必要的节点扩展速度可以提升一个数量级。这些优化每一个都值得单独展开但核心的A*逻辑是不变的。先把基础版跑通、跑对再根据实际性能数据决定要不要上更复杂的方案。6. 我在实际项目中的几点体会这套150行的A*实现我在几个小规模项目里都用过最深的体会是算法的价值不在于代码多复杂而在于你是否真正理解它每一步在做什么。很多人调库调习惯了遇到寻路出问题就抓瞎因为不知道内部发生了什么。自己手写一遍之后路径为什么绕远、为什么卡住、为什么找不到你都能从开放列表和关闭列表的状态里看出端倪。另一个体会是关于代码量的控制。150行不是硬性指标而是一个信号它说明A*的核心逻辑本身并不庞大。如果你写出来超过300行大概率是引入了不必要的抽象或者过度设计。保持代码扁平、直接反而更容易调试和维护。最后分享一个小技巧在开发阶段把每次搜索的开放列表和关闭列表用不同颜色画在地图上直观地看到搜索的扩散过程。这个可视化调试手段比打印日志高效得多一眼就能看出启发函数是不是在正确引导搜索方向。等路径跑通之后再把调试绘制去掉换成最终的路径显示。如果你正在做格子地图的游戏不管是战棋、塔防还是Roguelike这套代码可以直接拿去用。改改地图数据格式接上你的渲染层就能跑起来。遇到问题的时候回到开放列表和关闭列表的状态去看答案通常就在那里。