游戏算法-A*搜索算法知识梳理和通用框架

type

status

date

slug

summary

A*搜索算法知识梳理

1. A*算法的基本概念

A*算法是一种启发式搜索算法，它通过评估函数来决定搜索的顺序。其中：

是从起点到节点的实际代价。

是从节点到目标节点的估计代价（启发式函数）。

A*算法的目标是找到从起点到目标节点的最优路径，即代价最小的路径。

2. 可采纳性（Admissibility）

启发式函数必须满足可采纳性，即不能高估从节点到目标节点的实际代价；即必须小于或等于从到目标节点的真实代价，即。

🐈

结论：

只要启发式函数满足可采纳性（即），A*算法就能保证找到最优路径。

反证法：

假设A*算法返回了一条非最优路径，其代价。

在非最优路径上，存在一个节点，使得：。

特别地，目标节点满足：

在最优路径上，一定存在一个不同于的节点，使得：。

而A*算法按照的值从小到大扩展节点（每次从小根堆中弹出元素加入closeList）；这意味着会先于被扩展。

如果被扩展，A*算法会继续从向目标节点搜索，找到最优路径；与假设矛盾。

3. 一致性（Consistency）

一致性是比可采纳性更强的条件。它要求对于任意节点和它的后继节点，启发式函数满足以下不等式：；其中是从节点到节点的实际代价。

一致性确保了启发式函数在搜索过程中不会与过去的预测相矛盾:

最优性保证：一致性是可采纳性的一个更强条件。如果满足一致性，那么它必然满足可采纳性。

路径代价的一致性：在搜索过程中，算法不会发现一条路径的代价比之前估计的更低；避免了算法在搜索过程中反复调整路径。

🐈

一致性与可采纳性的区别：

一致性不仅要求可采纳性，还要求启发式函数满足三角不等式：；保证了启发式函数在节点扩展时是“平滑”的，避免了重复更新节点代价的情况。

如果启发式函数仅满足可采纳性，A*算法仍然能找到最优路径，但可能会多次重新开放和更新某些节点的代价，导致效率降低。

4.启发式函数变体（Variable）

在网格地图中，通常使用曼哈顿距离、欧式距离等作为启发式函数的计算，但在中继点地图（Waypoint Graph）或GOAP（目标导向行动规划）中，的设计需要适应新的问题。

在GOAP中，的设计不再是简单的几何距离，而是需要估计当前状态与目标状态的“接近程度”；例如：

如果目标是“找到武器”，为当前状态与“拥有武器”状态之间的差异。

如果目标是“击败敌人”，为当前状态与“敌人被击败”状态之间的差异。

5.算法退化（Degradation）

当启发式函数始终返回0时，A*算法会退化为Dijkstra算法。因为；算法在选择下一个扩展节点时，只考虑从起点到当前节点的实际代价（Dijkstra算法就是每次选择当前已知代价最小的节点进行扩展，总代价函数实际上就是），从而A*算法失去了启发式引导的作用。

A*搜索算法通用框架

节点接口

任意类通过继承此接口，成为A*算法中的可搜索节点。

属性

属性	作用
`Parent`	父节点，用于回溯生成完整路径
`SelfCost`	移动到该节点的单步代价（如地形消耗）
`GCost`	从起点到该节点的累计实际代价
`HCost`	到终点的启发式估计代价（如直线距离）
`FCost`	总代价 = `GCost + HCost`（只读）

关键方法

GetDistance(T otherNode

用途：计算到目标节点的启发式估计值（如曼哈顿距离）。

参数：otherNode - 目标节点。

GetSuccessors(object nodeMap)

用途：获取所有可达的邻居节点列表。

参数：nodeMap - 搜索空间（如地图数据）。

注意：需在此方法中设置邻居节点的 SelfCost（自身移动到邻居节点的代价）。

IAstarNode<T>接口

搜索器

实现A*搜索算法，用于在给定的搜索空间（地图）中寻找起点到终点的最优路径

泛型约束

泛型参数	约束条件	作用
`T_Map`	无	表示搜索空间（如地图）。
`T_Node`	`IAStarNode<T_Node>`, `IComparable<T_Node>`, `IEquatable<T_Node>`	表示搜索节点，需实现节点接口和比较接口。

核心成员

成员	类型	作用
`closeList`	`HashSet<T_Node>`	探索集，存储已探索的节点（哈希集合）。
`openList`	`MyHeap<T_Node>`	边缘集，存储待探索的节点（优先队列）。
`nodeMap`	`T_Map`	搜索空间（地图）。