游戏a算法算法

‘壹’ A星算法详解(个人认为最详细,最通俗易懂的一个版本)

在探索领域中，寻找最短路径的问题经常需要使用到A*算法。A*算法是一种广泛应用于路径规划和游戏开发中的启发式搜索算法。本文将通过详细的步骤，深入解读A*算法的运作原理和实现细节。首先，我们假设目标是从A点移动到B点，其中两点之间被一堵墙隔开。图1展示了这个示例，其中绿色代表A点，红色代表B点，蓝色代表墙。

图1展示了简化后的搜索区域，我们将其划分为正方形的格子。这一简化方法将搜索区域转化为二维数组，数组的每一项代表一个格子，其状态为可走或不可走。通过计算从A点到B点需要经过哪些格子，我们可以找到一条路径。当路径确定后，角色将从一个格子的中心移动到另一个格子的中心，直至到达目的地。

在A*算法中，搜索区域的简化为节点（nodes）的引入提供了基础。节点可以被放置在任意多边形内，可以位于多边形的中心，也可以位于边线上。使用这种方法最简单的原因在于其通用性，适用于不同形状的搜索区域。

算法开始于定义起点A，并将其加入到一个名为开放列表（open list）的集合中。开放列表是一个待检查的格子列表，其中的格子可能是路径的一部分，也可能是路径的候选。随后，我们检查起点A的相邻格子，并将其中可走的或可到达的格子加入开放列表中，同时将起点A作为这些格子的父节点。在追踪路径时，父节点的信息至关重要。

下一步是从开放列表中选择一个与起点A相邻的格子，重复上述过程。但选择哪一格子则基于其F值最小的原则。F值是由G值（从起点A到特定格子的移动代价）和H值（从该格子到终点B的估算成本）相加得到的。

路径排序涉及计算路径中每个格子的F、G和H值。G值代表从起点A到指定格子的移动代价，横向和纵向移动的代价为10，对角线移动的代价为14。这些数值简化了计算过程，同时提高了算法的执行效率。H值通过估计起点到终点的曼哈顿距离计算得出，即横向和纵向距离的总和，忽略对角移动。

计算出G和H值后，我们得到F值，用于后续选择操作。在选择过程开始时，我们会遍历开放列表，选择F值最小的格子。这一过程不断重复，直到将终点加入开放列表，路径被找到。在每一步中，选择的格子从开放列表移除，加入到关闭列表（closed list）中，表示不再需要关注的格子。

在搜索过程中，我们需要对选定的格子执行一系列操作。首先，将该格子从开放列表中移除并加入到关闭列表中。接着，检查与该格子相邻的格子，忽略那些已位于关闭列表中或不可走的格子。对于不在开放列表中的相邻格子，将其加入开放列表中，并将选定的格子作为其父节点。若相邻格子已在开放列表中，会检查新路径是否更优。如果新路径更优，则更新该格子的父节点，并重新计算其F、G和H值。

在搜索过程中，我们不断重复上述步骤，直到找到终点或确定无法找到路径。当终点被加入开放列表后，搜索过程完成。此时，我们可以通过追踪父节点从终点回溯到起点，找到最短路径。

在实现A*算法时，关键在于如何高效地维护开放列表和关闭列表，以及计算路径代价（G、H和F值）。为了优化性能，可以采用排序数据结构（如二叉堆）来管理开放列表，以便快速找到具有最小F值的格子。在考虑其他单位、优化速度、地形损耗、维护未探测区域、平滑路径以及处理非方形搜索区域时，A*算法的实现细节变得更为丰富和复杂。通过阅读相关的高级主题和参考资料，如Amit的A*页面、Smart Moves: Intelligent Path Finding和Terrain Analysis等文章，可以进一步深入理解A*算法的高级应用和优化策略。