四大A*启发函数场景选型全解
这四个是2D路径规划中最核心的A启发函数，核心差异在于适配的移动规则、代价模型、可采纳性，直接决定A能否找到最优解、搜索效率高低。
1. 曼哈顿距离（Manhattan Distance，L1范数）
核心公式
二维栅格中，当前节点 n(x1,y1) 、目标节点 t(x2,y2) ，单步横竖移动基础代价 D （通常取1）：
h(n) = D × (|x1 - x2| + |y1 - y2|)
核心特点
- 四方向移动专属，是该场景下真实最短路径的严格下界，100%满足可采纳性，A*必出全局最优解；
- 纯整数加减运算，无浮点开销，计算成本几乎为0；
- 启发力度远强于零启发（Dijkstra），可大幅缩小搜索范围；
- 无高估风险，非适配场景仅会出现性能劣势，不会破坏A*最优性。
✅ 什么时候用
1. 移动规则仅允许上下左右四方向，无对角线移动权限的栅格场景；
2. 对路径最优性有严格要求，且需要极致轻量化计算的嵌入式/低算力设备场景；
3. 八数码、十五数码等滑块拼图问题的基础启发。
❌ 什么时候不用
- 【不推荐】允许对角线/八方向移动的栅格场景：启发力度远弱于切比雪夫/Octile距离，搜索范围大、效率极低；
- 【不推荐】允许任意角度连续移动的场景：启发力度远不如欧几里得距离，搜索效率差；
- 【无绝对禁用场景】：仅存在性能劣势，极端情况下可作为保底方案。
真实使用例子
智能仓储AGV机器人导航：仓储货架按横竖网格排布，AGV仅能沿着货架之间的横竖通道行驶，无法斜穿货架（无对角线移动权限），单格移动代价固定为1。此时A*采用曼哈顿距离作为启发函数，既能100%保证找到最短行驶路径，又能以极低的算力开销完成路径规划，完美适配AGV的嵌入式低算力控制器。
2. 切比雪夫距离（Chebyshev Distance，L∞范数）
核心公式
二维栅格中，单步横竖/对角线移动统一代价 D （通常取1）：
h(n) = D × max(|x1 - x2|, |y1 - y2|)
核心特点
- 八方向等代价移动专属，是该场景下真实最短路径的严格下界，满足可采纳性，A*可找到全局最优解；
- 纯整数运算，无浮点开销，计算成本极低；
- 启发力度极强，是等代价八方向场景下效率最高的基础启发函数；
- 边界极严，超出适配场景会直接高估代价，破坏可采纳性，导致A*失效。
✅ 什么时候用（必用/推荐场景）
1. 移动规则允许八方向移动，且对角线单步代价=横竖单步代价的栅格场景；
2. 回合制网格战棋、棋盘类场景，斜向与横向移动消耗完全相同的场景。
❌ 什么时候不用（禁用/不推荐场景）
- 【绝对禁用】仅允许四方向移动的栅格场景：会严重高估路径代价，破坏可采纳性，A*无法保证找到最优解，是新手最常见的致命错误；
- 【绝对禁用】八方向移动但对角线代价≠横竖代价的场景：会高估/低估代价，要么破坏最优性，要么启发力度不足；
- 【不推荐】任意角度连续移动场景：启发力度远不如欧几里得距离，效率极低。
真实使用例子
回合制战棋游戏《火焰纹章》的单位路径规划：游戏地图为网格制，单位每回合拥有固定移动力，横竖移动1格、斜向移动1格均消耗1点移动力（对角线与横竖代价完全相等）。此时A*采用切比雪夫距离作为启发函数，既能保证找到消耗移动力最少的最优路径，又能以极低的算力完成多单位的实时路径计算，适配游戏的回合制实时交互需求。
3. 欧几里得距离（Euclidean Distance，L2范数）
核心公式
二维空间中，单步基础代价 D ：
h(n) = D × √[(x1 - x2)² + (y1 - y2)²]
核心特点
- 全场景通用下界：基于「两点之间直线最短」公理，所有移动场景下都是真实最短路径的严格下界，永远满足可采纳性，A*必出全局最优解；
- 适配性极强，支持任意角度的连续空间移动，无栅格方向限制；
- 缺点：带平方根的浮点运算，计算开销高于整数型启发函数；
- 栅格场景下启发力度弱于专属函数，搜索效率偏低。
✅ 什么时候用（必用/推荐场景）
1. 允许任意角度连续移动、无栅格方向限制的连续空间场景；
2. 无固定移动规则、需要通用可采纳启发函数的通用路径规划场景；
3. 3D及以上多维空间的路径规划场景，适配性远超其他三个函数。
❌ 什么时候不用（禁用/不推荐场景）
- 【不推荐】四方向/八方向栅格最优路径规划场景：浮点运算有额外算力开销，且启发力度远弱于对应场景的专属函数，搜索效率低；
- 【不推荐】低算力嵌入式设备的栅格场景：平方根运算会占用大量算力，甚至无法实时运行；
- 【无绝对禁用场景】：仅存在性能劣势，永远不会破坏A*最优性，可作为全场景保底方案。
真实使用例子
园区巡检无人机的全局路径规划：无人机可在园区空域内任意角度直线飞行，无固定栅格通道限制，仅需避开建筑物、树木等障碍物。此时A*采用欧几里得距离作为启发函数，既能保证找到飞行距离最短的全局最优路径，又能完美适配无人机全方向自由飞行的移动规则，同时满足空域3D空间的路径规划需求。
4. Octile距离（八角距离/对角线距离）
核心公式
二维栅格中， dx=|x1-x2| 、 dy=|y1-y2| ，横竖单步代价 D （通常取1），对角线单步代价 D_diag （通常取 √2×D≈1.414 ，对应斜向移动的真实欧氏距离）：
h(n) = D × max(dx, dy) + (D_diag - D) × min(dx, dy)
核心特点
- 八方向非等代价移动专属，是该场景下真实最短路径的严格下界，100%满足可采纳性，A*必出全局最优解；
- 启发力度是八方向非等代价场景下最强的，搜索效率远超切比雪夫、欧几里得距离；
- 兼容性极强： D_diag=D 时退化为切比雪夫距离， D_diag→∞ 时退化为曼哈顿距离；
- 仅需基础加减乘运算，可预计算常数项，算力开销极低，远低于欧几里得距离。
✅ 什么时候用（必用/推荐场景）
1. 移动规则允许八方向移动，且对角线单步代价≠横竖代价（通常对角线代价更高）的栅格场景；
2. 2D像素/栅格游戏的角色移动、机器人栅格导航，需要计算真实物理距离最短路径的场景；
3. 工业级栅格路径规划的首选，兼顾最优性与极致搜索效率。
❌ 什么时候不用（禁用/不推荐场景）
- 【绝对禁用】八方向移动但对角线代价<横竖代价的场景：会高估路径代价，破坏可采纳性，A*无法保证最优解；
- 【绝对禁用】仅允许四方向移动的栅格场景：启发力度不足，搜索效率远低于曼哈顿距离，无任何优势；
- 【不推荐】八方向等代价移动场景：会退化为切比雪夫距离，额外增加不必要的计算量；
- 【不推荐】任意角度连续移动场景：适配性远不如欧几里得距离，启发力度不足。
真实使用例子
2D开放世界游戏《星露谷物语》的玩家角色路径规划：游戏地图为像素栅格，玩家可横竖、斜向自由移动，斜向移动1格的真实像素距离为√2（约1.414），是横竖移动1格距离的1.414倍（对角线代价高于横竖代价）。此时A*采用Octile距离作为启发函数，既能保证找到玩家移动的真实最短路径，又能以极低的算力开销完成实时路径规划，完美适配玩家自由移动的操作需求，避免出现角色绕路的问题。
致命踩坑提醒
1. 四方向栅格绝对不能用切比雪夫距离：会直接高估代价，破坏A*可采纳性，导致找不到最优解，是新手最常见的错误；
2. 八方向非等代价栅格不要用切比雪夫：要么丢最优性，要么丢效率，必须用Octile距离；
3. 栅格场景优先用整数型启发函数：非必要不要用欧几里得距离，避免浮点运算额外开销；
4. 所有场景优先选专属适配函数：通用型函数虽不会出错，但效率远不如专属函数。