游戏 AI / 系统课时
启发式函数怎么选才不绕路
启发式函数怎么选才不绕路
A* 是否“聪明”,很大程度取决于启发式函数 怎样估计当前位置到目标的剩余代价。选得太弱,搜索会扩散很多无关节点;选得与移动规则不匹配,又可能失去最优性。本节用网格寻路中最常见的三种启发式,建立一套可直接套用的选择方法。
学习目标
- 理解曼哈顿、欧几里得和对角距离分别对应什么移动规则
- 判断启发式是否会高估真实剩余代价
- 能根据四方向、八方向和任意角度移动选择合适的
先看启发式到底在控制什么
A* 通常用 给候选节点排序。 是从起点走到当前节点已经付出的真实代价, 是从当前节点到目标的估计代价。搜索每次优先展开 较小的节点,因此 越接近真实剩余代价,搜索方向通常越集中。
但启发式不是越大越好。如果希望标准 A* 保证找到最小代价路径,常用要求是启发式不能高估真实最短剩余代价,也就是对任意节点都满足 ,其中 表示真实最短剩余代价。
三种距离为什么不能混着用
设当前节点与目标的横向差值为 ,纵向差值为 。常见启发式的核心区别,不是公式长什么样,而是它们对“允许怎样移动”做了不同假设。
| 移动规则 | 推荐启发式 | 直觉 |
|---|---|---|
| 只能上、下、左、右 | 曼哈顿距离 | 横向和纵向必须分别走完 |
| 可八方向移动,直走代价 1、斜走代价约 1.414 | 对角距离 | 能重叠完成的横纵位移优先走斜线 |
| 连续空间或允许任意方向直线移动 | 欧几里得距离 | 直接估算两点直线距离 |

如果四方向网格里横向差 4 格、纵向差 3 格,那么最短路径至少需要 7 次直移,曼哈顿距离恰好给出 7。此时欧几里得距离为 5,只是更保守的下界,也能使用,但会让 A* 更接近 Dijkstra,展开更多节点。
八方向移动要把斜走代价算进去
八方向移动时,简单使用 会把横纵位移完全分开计算。例如 、,如果允许以约 1.414 的代价斜走,那么真实最短代价约为 ,而曼哈顿距离给出 6,已经高估。
更合适的做法是先走 次对角线,再走剩余的直线。若直移代价为 、斜移代价为 ,可写成:
当 、 时,这个估计与八方向网格的实际移动模型一致。若游戏把斜移也设成 1,则应改用切比雪夫距离 ,不能继续沿用 1.414 的版本。
障碍物不会改变启发式的基本选择
启发式通常不需要提前知道墙在哪里。它估计的是“忽略障碍后的最低可能代价”,而真实路径因为绕障碍只会更长。因此,在四方向网格里,即使中间有一堵墙,曼哈顿距离仍然可以作为安全的下界。
真正需要同步调整的是移动规则和边权。如果泥地每步代价变成 3,而普通地面每步代价为 1,那么启发式最好仍按全地图可能出现的最小单步代价估算。否则用更高代价直接乘距离,可能对经过普通地面的最优路径产生高估。
用一套判断顺序完成选择
实际项目里可以按下面的顺序判断:
- 先确定邻接规则:四方向、八方向,还是连续空间任意角度移动。
- 再确定每种移动的真实代价,尤其是斜向代价是否等于直移。
- 选择不会超过真实最短剩余代价的距离模型。
- 用无障碍小地图验证:启发式值应与理想情况下的最短代价一致或更小。
- 再加入墙体、泥地等复杂因素,确认路径最优性没有被破坏。
如果目标是标准、可证明最优的 A*,优先选择与移动规则严格匹配的启发式:四方向用曼哈顿,八方向按直移和斜移成本使用对角距离,连续空间再考虑欧几里得。真正决定“会不会绕路”的,不是某个公式名字,而是启发式是否忠实反映了你的移动模型。