自动寻路算法全解析：从A*到导航网格的实战指南-北京尧图网络

自动寻路这件事我在刚接触游戏开发的时候踩过不少坑。最早做一个小场景敌人追玩家我直接写了个“朝玩家方向直线移动”结果敌人一头撞在墙上原地抽搐那画面现在想起来还挺好笑。后来才知道让角色“聪明地绕开障碍走到目标点”这件事背后是一整套成熟的算法体系而游戏引擎里最常被拿来用的就是基于图搜索的那一套东西。这篇内容我想把自动寻路从原理到落地讲透重点拆解几种主流算法各自解决什么问题、为什么这么选、参数怎么调以及实际项目里那些文档不会写的坑。适合刚入门想搞懂寻路底层逻辑的新手也适合已经会用但想弄明白“为什么这么配”的进阶开发者。核心关键词会围绕自动寻路、寻路算法、网格寻路、导航网格、路径规划这些展开读完之后你至少能判断什么场景该用哪种算法参数为什么这么设出了问题往哪儿查。1. 自动寻路的整体设计与算法选型思路1.1 寻路到底在解决一个什么问题先把问题说清楚。自动寻路的本质是在一张“可通行性地图”上找到从起点到终点的一条代价尽可能低、且不穿越障碍的路径。注意这里有两个关键词代价和不穿越障碍。代价可以是距离最短也可以是时间最少、消耗最低、最安全甚至可以是“尽量走大路不走草丛”这种游戏性偏好。所以寻路从来不是单纯找“最短”而是找“最合适”。把现实场景类比一下就很好理解。你从家去公司导航给你的路线未必是直线距离最短的那条它可能绕开拥堵、避开施工路段最后选了一条综合代价最低的。游戏里的寻路一模一样地图被抽象成一张图Graph图的节点是可走的位置边是位置之间的连通关系边上有权重代价寻路算法就是在这张图上做搜索。这里有个容易被忽略的点地图抽象方式决定了算法的上限。你把地图切成方格那路径就是格子到格子的跳跃你用导航网格路径就是多边形之间的连线你用路径点那就是预设点之间的连接。抽象方式选错了后面算法再优化也救不回来。我见过有人在小房间里用几万个格子做寻路帧率掉得厉害其实换成导航网格几十个多边形就搞定了。1.2 为什么主流方案都绕不开图搜索游戏里的寻路算法五花八门但真正在项目里大规模用的基本都归属于图搜索这个大家族。原因很实在图搜索有完备的理论保证只要图是连通的就一定能找到路径如果存在的话而且代价可控、可预测。相比之下一些启发式的、基于势场的方法虽然实现简单但容易陷入局部最优角色会在障碍物前面来回震荡体验很差。图搜索里最经典的就是 Dijkstra 和 A*。Dijkstra 的思路是“从起点开始一圈一圈往外扩每次扩展当前代价最小的节点”它能保证找到全局最优路径但问题是它不分方向往终点反方向也会傻乎乎地扩节点多了就慢。A* 在 Dijkstra 基础上加了一个启发函数Heuristic相当于给搜索装了个“指南针”优先往终点方向探索效率高很多这也是游戏里用得最多的。再往细分还有几种针对特定场景的变体。比如双向搜索从起点和终点同时往中间搜理论上能把搜索范围砍掉一半Jump Point SearchJPS专门针对均匀网格能跳过大量对称的冗余节点在开阔地图上比 A* 快一个数量级D系列*D*、D* Lite则是为动态环境设计的地图变了不用从头算增量更新路径适合那种障碍物会移动或者地图会变化的场景。选型的核心逻辑其实就一句话看你的地图是静态还是动态、是均匀网格还是不规则多边形、对路径质量要求高不高、对性能预算有多少。静态均匀网格、追求实现简单A* 足够开阔大地图、格子多上 JPS障碍频繁变化考虑 D* Lite需要多单位同时寻路还得考虑分层寻路Hierarchical Pathfinding先在大区域间规划再在区域内细化。1.3 一张表看清几种算法的取舍我把几种常见算法拉出来对比一下方便你快速判断。这张表是我自己项目里总结的参数和表现基于常见实现具体数值会因地图和实现差异浮动。算法最优性适用地图性能表现动态适应实现复杂度Dijkstra保证最优任意带权图较慢无方向性差低A*保证最优启发可采纳时任意带权图快方向性强差中JPS保证最优均匀网格开阔地图极快差中高双向 A*保证最优任意带权图约为单向一半搜索量差中D* Lite保证最优动态带权图增量更新快好高分层寻路近似最优大型地图大幅降低单次搜索量中高这张表里“最优性”指的是能否保证找到代价最低的路径。要注意 A* 的“保证最优”是有前提的启发函数必须可采纳admissible也就是它估计的代价不能超过真实代价否则可能找到次优路径。这个细节后面会展开讲。2. 核心算法细节拆解与实操要点2.1 A* 的灵魂启发函数怎么选、怎么算A* 的评估公式是f(n) g(n) h(n)。g(n)是从起点到当前节点的实际代价h(n)是从当前节点到终点的估计代价也就是启发函数。整个算法的优先级队列就是按f值排序每次取f最小的节点扩展。启发函数的选择直接决定效率和正确性。最常见的有三种距离度量曼哈顿距离h |dx| |dy|适合只能上下左右四方向移动的网格。欧几里得距离h sqrt(dx² dy²)适合可以任意方向移动的场景。对角距离Octileh max(dx, dy) (sqrt(2) - 1) * min(dx, dy)适合八方向移动的网格。为什么这么选因为启发函数必须“不高估”真实代价。四方向移动时两点间真实最少步数就是曼哈顿距离用欧几里得距离会低估低估是安全的只是效率低一点但如果你用了一个高估的函数比如把曼哈顿距离乘个 1.5那就可能错过最优路径。我早期就犯过这个错为了让搜索更快把启发权重调大结果角色偶尔走出一条明显绕远的路线排查了半天才发现是启发函数不可采纳导致的。这里有个实操技巧加权 A*。把公式改成f g w * hw大于 1 时搜索更快但可能次优w等于 1 是标准 A*。很多游戏其实不要求严格最优稍微绕一点无所谓这时候用w 1.2到1.5能明显提速。这个取舍要看你游戏类型竞速类对路径质量敏感就别加权休闲类可以放心加。代码层面A* 的核心就是一个开放列表Open List通常用优先队列/二叉堆和一个关闭列表Closed List记录已扩展节点。下面是一个简化但可运行的 Python 版本帮助理解流程import heapq def heuristic(a, b): # 八方向网格用对角距离 dx abs(a[0] - b[0]) dy abs(a[1] - b[1]) return max(dx, dy) (1.414 - 1) * min(dx, dy) def a_star(grid, start, goal): open_heap [(0, start)] came_from {} g_score {start: 0} closed set() while open_heap: _, current heapq.heappop(open_heap) if current goal: # 回溯路径 path [current] while current in came_from: current came_from[current] path.append(current) return path[::-1] if current in closed: continue closed.add(current) for dx, dy in [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]: neighbor (current[0] dx, current[1] dy) if not (0 neighbor[0] len(grid) and 0 neighbor[1] len(grid[0])): continue if grid[neighbor[0]][neighbor[1]] 1: # 1 表示障碍 continue step 1.414 if dx ! 0 and dy ! 0 else 1.0 tentative_g g_score[current] step if tentative_g g_score.get(neighbor, float(inf)): came_from[neighbor] current g_score[neighbor] tentative_g f tentative_g heuristic(neighbor, goal) heapq.heappush(open_heap, (f, neighbor)) return None # 无路径这段代码里有个细节值得说if current in closed: continue这一句。因为同一个节点可能被多次压入堆每次找到更优的 g 值就压一次弹出时如果已经处理过就跳过。这是 A* 实现里非常常见的写法能避免重复扩展。2.2 网格寻路的代价设置别只盯着距离很多人做网格寻路代价就设成“走一格 1”斜着走 1.414。这没错但太朴素了。真实项目里代价应该反映游戏性。比如草地走一格代价 1沼泽走一格代价 3角色自然就绕开沼泽。靠近敌人火力范围的格子加额外代价AI 就会倾向于走掩体路线。上坡比平地贵下坡便宜地形就有意义了。这种“带权网格”是让寻路结果看起来“聪明”的关键。我做过一个塔防类的小 Demo一开始敌人傻乎乎地走最短直线穿过一片减速区域结果全被拖死。后来给减速区域加了高代价敌人自动绕行玩家就得重新布置防线游戏性一下就上来了。代价设置有个原则代价差异要足够大才能压过距离差异。如果你把沼泽代价设成 1.1那角色为了绕开一小片沼泽多走两步总代价反而更高它还是会穿过去。一般建议危险/减速区域的代价至少是普通区域的 2 到 3 倍才能形成明显的绕行倾向。2.3 导航网格不规则地图的正确打开方式网格寻路简单直观但有个硬伤格子是均匀的地图大了格子数量爆炸而且路径是锯齿状的角色走起来一顿一顿。导航网格NavMesh就是来解决这个问题的。它把可行走区域划分成若干个凸多边形寻路时在多边形之间搜索路径是平滑的折线。为什么用凸多边形因为凸多边形有个好性质多边形内任意两点之间的直线段都在多边形内部不会穿出去。这样角色在多边形内部移动时不需要再做碰撞检测路径点只需要放在多边形的边上门户Portal移动就是“走到门户再走向下一个门户”非常高效。导航网格的生成一般分几步先对场景做体素化Voxelization标记出可行走区域然后提取轮廓、简化轮廓再做凸多边形划分最后建立多边形之间的邻接关系。这套流程在引擎里通常是自动的但参数得调。比如体素大小Cell Size决定了精度太小生成慢、内存高太大细节丢失角色可能卡在窄缝里。我一般按角色半径来定体素边长取角色半径的 1/3 到 1/2 比较稳妥。导航网格寻路的搜索过程本质是在“多边形邻接图”上跑 A*只不过节点是多边形边的代价是两个多边形门户之间的距离。找到多边形序列后再用漏斗算法Funnel Algorithm把门户点串成一条平滑路径。漏斗算法这块稍微绕核心思想是维护一个“可视锥”不断收窄遇到拐点就输出路径点。实际用引擎的话这部分是封装好的但理解它对排查“路径贴墙”“拐角卡住”这类问题很有帮助。2.4 动态障碍与局部避障全局和局部分开处理全局寻路A*、NavMesh解决的是“从 A 到 B 大致怎么走”但它假设地图是静态的。一旦有会移动的障碍比如其他角色、可破坏的箱子全局路径就可能失效。这时候需要局部避障来兜底。常见的局部避障方案有几种。转向行为Steering Behaviors是最轻量的给角色加“避让”“分离”“对齐”等力让它在移动中微调方向但容易陷入局部最优比如被一群单位围住就出不来。速度障碍法Velocity Obstacle更严谨一些通过计算相对速度判断是否会碰撞提前调整适合单位密集的场景。还有ORCAOptimal Reciprocal Collision Avoidance多个单位各自承担一半避让责任群体移动很自然很多 RTS 和模拟经营游戏用它。我的经验是全局路径负责“大方向”局部避障负责“小调整”两者分层。全局路径每隔一段时间比如 0.5 秒重算一次局部避障每帧跑。如果局部避障发现前方被堵死就触发一次全局重算。这样既保证了响应性又不会每帧都跑昂贵的全局搜索。这里有个坑局部避障和全局路径可能“打架”。比如全局路径让角色贴着墙走局部避障又把它往墙里推结果角色在墙边抖动。解决办法是给局部避障加约束比如限制横向偏移量或者让全局路径生成时就和障碍保持一定安全距离给导航网格加“代理半径”偏移。3. 实操过程与核心环节实现3.1 从零搭一个可跑的网格寻路 Demo光看原理不够我带你走一遍完整流程。假设做一个 2D 俯视角的小场景地图是 20x20 的网格有静态障碍角色从左上走到右下。第一步地图数据表示。用一个二维数组0 表示可走1 表示障碍。实际项目里这个数组可能来自关卡编辑器导出或者从图片像素读取黑色是墙白色是路。grid [ [0,0,0,0,1,0,0,0,0,0, ...], [0,1,1,0,1,0,1,1,0,0, ...], # ... 共 20 行每行 20 列 ]第二步确定移动规则。四方向还是八方向八方向路径更自然但要注意“斜穿墙角”的问题如果两个相邻的直角格子都是障碍斜着穿过去就相当于穿墙了。解决办法是斜向移动时检查两个正交邻居是否都可走有一个是障碍就禁止斜穿。这个细节很多教程不讲但实际做出来不处理角色就会卡墙角或者穿模。第三步跑 A得到路径*。用上面那段代码传入起点终点拿回一个坐标列表。这时候路径是格子中心的连线锯齿感明显。第四步路径平滑。最常用的方法是“视线检测拉直”从当前点出发尝试连接路径上更远的点如果两点之间没有障碍用射线检测或 Bresenham 直线算法判断就跳过中间点。这样能把锯齿路径拉成尽量少的直线段。平滑之后角色移动就顺滑多了。第五步路径跟随。角色不是瞬移得沿着路径点一个个走。这里要注意“到达判定”的阈值不能要求精确到点否则角色会在路径点附近打转。一般设一个“到达半径”进入半径就算到达切下一个点。转向也要平滑用插值或者转向速度限制别让角色瞬间掉头。这套流程跑通一个基础的自动寻路就有了。我建议新手一定自己手写一遍 A*别一上来就用引擎封装好的因为手写一遍你才会真正理解开放列表、关闭列表、g 值更新这些概念后面调参和排查问题才有底气。3.2 参数计算启发权重和搜索上限怎么定实际项目里A* 不能无限搜下去得有保护。两个关键参数启发权重和最大搜索节点数。启发权重前面说了标准 A* 是 1加权可以到 1.2 到 1.5。怎么定我的做法是做个对比测试同一张地图跑 100 次随机起终点的寻路记录平均耗时和平均路径长度。权重从 1.0 开始往上加观察路径长度增长曲线。一般到 1.3 左右路径长度只增加 2% 到 5%但耗时能降 30% 以上这个点就很划算。超过 1.5 之后路径质量下降明显就不建议了。最大搜索节点数是为了防止极端情况比如终点被完全围死导致搜索爆炸。设多少可以按地图规模估网格总数乘以一个系数比如 0.5 到 1。意思是最多搜一半到全部节点搜完还没有路径就判定不可达。这个值设太小会误判“有路却找不到”设太大又失去保护意义。我一般先设成总节点数跑测试看实际最大搜索量再留 20% 余量收紧。还有一个容易被忽略的参数重寻路频率。动态场景里路径不能一直用旧的但也不能每帧重算。我的经验值是 0.3 到 0.5 秒重算一次或者当目标移动超过一定距离比如 2 个格子时触发重算。这个要结合角色移动速度调走得快的角色重算要更频繁。3.3 多单位寻路的性能优化实录单个角色寻路A* 随便跑。但几十上百个单位同时寻路问题就来了。我做过一个模拟经营的小 Demo50 个工人同时找路一开始每帧卡顿后来做了几层优化才顺。第一层请求排队与分摊。不要让所有单位在同一帧发起寻路用一个队列每帧只处理固定数量比如 5 个的寻路请求其余的等下一帧。这样把计算压力摊平帧率就稳了。玩家几乎感知不到那几十毫秒的延迟。第二层路径缓存与复用。很多单位起点终点相近算出来的路径高度相似。可以做一个缓存键是“起点区域终点区域”同一对区域直接复用路径再做局部微调。区域怎么划分把地图切成大块比如 5x5 格子一个区域精度够用。第三层分层寻路。大地图上先在大区域之间算一条粗路径区域级 A*再在每个区域内算细路径。区域数量远小于格子数量粗路径算得飞快细路径只在少数几个区域内算总量大幅下降。这就是前面表格里提到的分层寻路大型地图必备。第四层流场Flow Field。如果大量单位追同一个目标比如塔防里所有敌人冲向基地可以反过来算从目标点出发做一次 Dijkstra生成一张“每个格子指向下一步”的方向场所有单位查表移动。一次计算全体受益这是群体寻路的终极优化。缺点是目标一变就得重算整张场适合目标固定的场景。这几层优化不是非此即彼实际项目里常常组合用。我的建议是先用请求排队把帧率稳住再看是否需要缓存和分层流场留给特定场景。4. 常见问题与排查技巧实录4.1 角色卡墙、抖动、绕远路怎么查寻路出问题症状就那么几类但原因可能五花八门。我整理了一张速查表按症状倒推原因实际排查时对着看能省不少时间。症状可能原因排查方法解决方向角色贴墙抖动局部避障与全局路径冲突打印每帧期望方向和实际方向给避障加横向约束路径留安全距离角色卡在墙角斜向移动穿墙角未检测检查斜向邻居的两个正交格禁止斜穿或加碰撞体路径明显绕远启发函数不可采纳/权重过大对比标准 A* 路径长度降低启发权重检查代价设置找不到路径但明明有路网格精度不足/障碍膨胀过度可视化可走区域调小体素减小代理半径群体移动互相推挤局部避障参数过激观察分离力大小调低分离权重用 ORCA帧率骤降同帧寻路请求过多统计每帧寻路次数请求排队分摊到多帧拿“角色贴墙抖动”来说这是最常见的。根因通常是全局路径贴着障碍边缘走局部避障又觉得离墙太近想推开两个力方向相反角色就在原地小幅震荡。我的处理办法是双管齐下全局路径生成时给障碍加“膨胀”把障碍格子往外扩一圈或者导航网格加代理半径让路径天然离墙远一点局部避障的横向推力设个上限别让它太激进。“绕远路”这个坑我印象很深。有次测试发现角色明明可以直走非要绕一个大圈。查了半天发现是代价设置里给某类地形加了过高权重导致算法宁可绕远也不走那片区域。教训是代价设置要符合直觉加完权重要实际跑一遍看路径是否合理别拍脑袋设个 10 倍就完事。4.2 动态地图下的路径失效处理地图会变门开了、桥断了、箱子被推走了静态路径就失效了。处理思路分两种全量重算和增量更新。全量重算简单粗暴地图一变就把所有相关单位的路径标记为脏下次寻路时重算。适合变化不频繁的场景。增量更新就是 D* Lite 那套只更新受影响的部分适合变化频繁的大地图。但 D* Lite 实现复杂我一般建议中小项目直接全量重算请求排队够用了只有地图频繁变化且单位很多时才值得上增量算法。有个实用技巧路径有效性校验。角色沿路径移动时每走一段就检查前方路径点是否还可走比如射线检测发现被堵就立即触发重算。这比定时重算更及时也比每帧重算更省。校验频率可以按角色速度调走得快就查得勤。4.3 几个文档里不会写的实操心得第一个心得可视化调试是寻路开发的生命线。把开放列表、关闭列表、最终路径、代价热力图都画出来问题一目了然。我早期不看可视化靠打印日志排查效率极低。后来写了个简单的调试绘制把搜索过的节点染成不同颜色一眼就能看出启发函数是不是在“乱搜”。第二个心得先保证正确再谈优化。很多人一上来就追求 JPS、分层、流场结果基础 A* 都没跑对路径偶尔穿墙都发现不了。我的建议是先用最朴素的 A* 跑通路径正确、角色能走再逐步加优化每加一层都做回归测试确保没引入新 bug。第三个心得边界情况要专门造测试。起点在障碍里、终点不可达、起点终点重合、地图全空、地图全堵这些边界不测上线必出问题。我习惯写一组固定的测试用例每次改寻路代码都跑一遍省心。第四个心得别迷信“最优路径”。玩家要的是“看起来合理”不是数学最优。有时候稍微绕一点、走得更顺滑的路径体验反而更好。所以路径平滑、转向插值这些“体验层”的优化优先级不比算法本身低。最后分享一个我常用的排查小技巧当路径诡异时先把启发函数临时改成返回 0退化成 Dijkstra看路径是否正常。如果正常了说明问题出在启发函数如果还是诡异那就是代价设置或地图数据的问题。这个二分法能快速定位问题域比盲目读代码高效得多。

自动寻路算法全解析：从A*到导航网格的实战指南

相关推荐

整数唯一分解定理在算法竞赛中的应用与实践

lft.php：单文件 PHP 实现 SIP 图片消息中转与游标队列

用披萨店实战简单工厂模式：从设计到扩展的完整指南

更多资讯

Lua脚本在游戏动态道具系统中的设计与优化

高校心理咨询系统开发：SpringBoot+小程序技术解析

校园点餐管理系统源代码：从课设到高并发实战的避坑指南

Python文件读写与CSV操作在游戏测试中的高效应用

text-to-CAD技术解析：从工程语义理解到STEP/URDF/DXF多格式交付

impeccable用法深度解析：从词源到搭配，彻底告别与perfect、flawless的混用

今日更新

Agent-Reach：打通大模型触达外部系统的最后一公里

深度学习图像隐写分析实战：从CNN原理到毕设源码全解析

AI赋能知识产权供需匹配：专利评估、需求挖掘与多路召回工程实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？