游戏 AI / 系统课时
A*为什么需要地图抽象
A*为什么需要地图抽象
寻路算法不能直接理解“地面、墙体、斜坡和房间”这些场景对象。它需要的是一组可枚举的位置,以及位置之间能否到达、移动代价多少。地图抽象的目标,就是把连续世界转成算法可以搜索的离散空间。
学习目标
- 理解直线移动和随机探索为什么无法解决一般寻路问题
- 说清地图抽象至少要提供哪些搜索信息
- 能判断网格、路点和导航网格分别适合什么场景
为什么直接朝目标移动不够
最简单的 NPC 移动方式,是每帧朝目标位置前进。空旷场地里它看起来有效,但一旦中间出现墙体、河流或不可跨越高差,NPC 只能撞在障碍上。它知道“目标在哪”,却不知道“从哪里绕过去”。
随机探索虽然能偶尔绕开障碍,却没有方向性,也无法保证在有限时间内找到路线。更关键的是,算法没有一个明确的“下一步候选集合”,就无法系统地比较不同路线。
因此,寻路真正需要解决的不是“往哪个方向走”,而是把问题改写成:当前位置可以到哪些位置,这些位置离目标还有多远,经过它们要付出多少代价。
地图抽象到底提供什么
A* 搜索通常把地图看成一个图。图中的节点代表可停留或可经过的位置,边代表两个位置之间允许移动,边权代表移动代价。算法只在这张图上工作,并不直接处理场景里的模型、贴图或碰撞体。

一个可用的搜索空间至少要回答三类问题:
- 节点是什么:例如格子中心、人工路点或导航多边形。
- 邻居是谁:例如四方向、八方向,或同一导航区域中可直接通行的位置。
- 代价是多少:例如直走代价、斜走代价、泥地额外代价,甚至危险区域惩罚。
A* 后续使用的启发式距离,也依赖这个抽象。只有先把“位置”和“连接关系”定义清楚,算法才知道该从哪些候选节点中继续扩展。
抽象粒度会直接改变寻路结果
地图抽象不是越精细越好。节点越多,路线通常越贴近真实地形,但搜索需要处理的状态也越多;节点太少,搜索更快,却可能错过窄路、拐角或局部障碍。
常见做法有三类:
| 抽象方式 | 节点含义 | 优点 | 典型代价 |
|---|---|---|---|
| 网格 Grid | 一个离散格子 | 规则、易实现、易调试 | 大地图节点数量多 |
| 路点 Waypoint | 人工或自动生成的关键位置 | 节点少、路线清晰 | 需要维护连接关系 |
| 导航网格 NavMesh | 可行走区域多边形 | 适合连续 3D 场景 | 构建与动态更新更复杂 |
二维方格地图通常从网格开始最合适;开放 3D 场景更常使用导航网格;固定道路网络或飞行航线则可能更适合路点图。
什么时候说明抽象有问题
如果 A* 的搜索逻辑没有错误,却仍然出现“明明有路却找不到”“穿墙”“无法通过看起来很宽的通道”,首先应检查搜索空间,而不是立刻修改启发式函数。
常见根因是可通行状态标错、邻接关系漏连、角色尺寸没有计入、世界坐标映射到错误节点,或者抽象粒度过粗。A* 只能在你提供的空间里寻找最优路线;如果正确路线根本没有被表示出来,算法再准确也不可能找到它。