游戏 AI / 系统课时

启发式函数怎么选才不绕路

启发式函数怎么选才不绕路

A* 是否“聪明”,很大程度取决于启发式函数 h(n)h(n) 怎样估计当前位置到目标的剩余代价。选得太弱,搜索会扩散很多无关节点;选得与移动规则不匹配,又可能失去最优性。本节用网格寻路中最常见的三种启发式,建立一套可直接套用的选择方法。

学习目标

  • 理解曼哈顿、欧几里得和对角距离分别对应什么移动规则
  • 判断启发式是否会高估真实剩余代价
  • 能根据四方向、八方向和任意角度移动选择合适的 h(n)h(n)

先看启发式到底在控制什么

A* 通常用 f(n)=g(n)+h(n)f(n)=g(n)+h(n) 给候选节点排序。g(n)g(n) 是从起点走到当前节点已经付出的真实代价,h(n)h(n) 是从当前节点到目标的估计代价。搜索每次优先展开 ff 较小的节点,因此 hh 越接近真实剩余代价,搜索方向通常越集中。

但启发式不是越大越好。如果希望标准 A* 保证找到最小代价路径,常用要求是启发式不能高估真实最短剩余代价,也就是对任意节点都满足 h(n)≤h∗(n)h(n)≤h^*(n),其中 h∗(n)h^*(n) 表示真实最短剩余代价。

三种距离为什么不能混着用

设当前节点与目标的横向差值为 dx=∣x1−x2∣dx=|x_1-x_2|,纵向差值为 dy=∣y1−y2∣dy=|y_1-y_2|。常见启发式的核心区别,不是公式长什么样,而是它们对“允许怎样移动”做了不同假设。

移动规则 推荐启发式 直觉
只能上、下、左、右 曼哈顿距离 dx+dydx+dy 横向和纵向必须分别走完
可八方向移动,直走代价 1、斜走代价约 1.414 对角距离 能重叠完成的横纵位移优先走斜线
连续空间或允许任意方向直线移动 欧几里得距离 直接估算两点直线距离

三种启发式与移动规则的匹配关系

如果四方向网格里横向差 4 格、纵向差 3 格,那么最短路径至少需要 7 次直移,曼哈顿距离恰好给出 7。此时欧几里得距离为 5,只是更保守的下界,也能使用,但会让 A* 更接近 Dijkstra,展开更多节点。

八方向移动要把斜走代价算进去

八方向移动时,简单使用 dx+dydx+dy 会把横纵位移完全分开计算。例如 dx=3dx=3、dy=3dy=3,如果允许以约 1.414 的代价斜走,那么真实最短代价约为 3×1.414=4.2423×1.414=4.242,而曼哈顿距离给出 6,已经高估。

更合适的做法是先走 min(dx,dy)min(dx,dy) 次对角线,再走剩余的直线。若直移代价为 DD、斜移代价为 D2D2,可写成:

h=D×(dx+dy)+(D2−2D)×min(dx,dy)h=D×(dx+dy)+(D2-2D)×min(dx,dy)

当 D=1D=1、D2=1.414D2=1.414 时,这个估计与八方向网格的实际移动模型一致。若游戏把斜移也设成 1,则应改用切比雪夫距离 max(dx,dy)max(dx,dy),不能继续沿用 1.414 的版本。

障碍物不会改变启发式的基本选择

启发式通常不需要提前知道墙在哪里。它估计的是“忽略障碍后的最低可能代价”,而真实路径因为绕障碍只会更长。因此,在四方向网格里,即使中间有一堵墙,曼哈顿距离仍然可以作为安全的下界。

真正需要同步调整的是移动规则和边权。如果泥地每步代价变成 3,而普通地面每步代价为 1,那么启发式最好仍按全地图可能出现的最小单步代价估算。否则用更高代价直接乘距离,可能对经过普通地面的最优路径产生高估。

用一套判断顺序完成选择

实际项目里可以按下面的顺序判断:

  1. 先确定邻接规则:四方向、八方向,还是连续空间任意角度移动。
  2. 再确定每种移动的真实代价,尤其是斜向代价是否等于直移。
  3. 选择不会超过真实最短剩余代价的距离模型。
  4. 用无障碍小地图验证:启发式值应与理想情况下的最短代价一致或更小。
  5. 再加入墙体、泥地等复杂因素,确认路径最优性没有被破坏。

如果目标是标准、可证明最优的 A*,优先选择与移动规则严格匹配的启发式:四方向用曼哈顿,八方向按直移和斜移成本使用对角距离,连续空间再考虑欧几里得。真正决定“会不会绕路”的,不是某个公式名字,而是启发式是否忠实反映了你的移动模型。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

启发式函数怎么选才不绕路

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通