【游戏算法】 - 寻路算法-启发函数

讲解寻路算法前，需要了解几种启发函数

启发函数

曼哈顿距离（Manhattan Distance）

• 定义：在网格地图中，仅允许上下左右四个方向移动时，两点之间的路径长度为横向和纵向距离之和。
• 公式：
  
• 优点：
  • 计算简单，适合实时应用。
  • 保证可容性和一致性。
• 缺点：
  • 对自由空间（可任意方向移动）的估计误差较大。

对角线距离（Diagonal Distance）

• 定义：在允许斜向移动的网格地图中，结合曼哈顿距离和对角线移动的代价。
• 公式：
  
  • ：横向或纵向移动的代价（通常为 1）。
  • ：对角线移动的代价（通常为 ）。
• 优点：
  • 比曼哈顿距离更接近实际路径。
  • 适用于斜向移动的场景。
• 缺点：
  • 需要额外参数 和 ，灵活性较低。

欧几里得距离（Euclidean Distance）

• 定义：在自由空间中，两点之间的直线距离。
• 公式：
  
• 优点：
  • 估计值更接近实际最短路径。
  • 适合连续空间。
• 缺点：
  • 计算开销较高（平方根运算，实际使用时，可以不使用开方计算，降低计算开销）。
  • 在网格地图中可能低估代价（需结合移动方向调整）。

切比雪夫距离（Chebyshev Distance）

• 定义：在允许任意方向移动的网格地图中，两点的最大坐标差。
• 公式：
  
• 适用场景：
  • 单位移动范围不受方向限制的场景（如《星际争霸》中的飞行单位）。
• 优点：
  • 计算简单，适合大范围移动。
• 缺点：
  • 可能高估实际代价（需谨慎设计移动规则）。

octile距离

适用于允许斜向移动但受限于 45° 角转弯的场景。它的核心思想是通过调整直行和斜行的代价比例，更精确地估计两点之间的最短路径长度。
Octile 距离的计算公式如下：

• dx 和 dy：当前节点与目标节点在 x 和 y 方向上的坐标差（绝对值）。
• ：这是斜行代价与直行代价的比例系数。假设直行代价为 ，斜行代价为 ，则 是斜行代价与直行代价的差值比例。

对比表格

以下是 曼哈顿距离、欧氏距离、对角线距离、切比雪夫距离、Octile 距离 的对比表格，涵盖公式、特点及适用场景：

距离类型	允许移动方向	公式	特点	适用场景
曼哈顿距离	上下左右四方向		计算简单，适合网格地图	城市街区路径规划、四方向移动游戏
欧氏距离	自由方向		精度高，适合连续空间	自动驾驶、无人机导航、3D 空间路径规划
对角线距离	八方向（含斜向）		平衡直行和斜行代价	八方向移动的网格地图（如《魔兽争霸》）
切比雪夫距离	无方向限制		估计最大坐标差，计算简单	国际象棋国王移动、无方向限制的网格地图
Octile 距离	45° 斜向移动（受限）		平衡直行和斜行代价，避免平方根运算	45° 斜向移动的网格地图（如《塞尔达传说》）

---