A*寻路算法详解

算法详解"/>

A*寻路算法详解

博主自制工具   翰华Box：

翰华Box - 开发日志：

在我们平时打小游戏的时候，有时候会遇到一些小怪兽，这些小怪兽会自动追击我们的玩家的角色，但是，通常我们玩家的路线并不是固定的，那么这些小怪兽要如何自动绕开障碍物，走什么样的路线，才能最快地进行追击呢，答案就是A*寻路算法。

A* 算法是一种启发式搜索算法。本质上来讲，可以算作是广度优先搜索算法的改进。我们知道，广度优先搜索总能找到路径最短的最优解，因为它每次新的一轮遍历永远是离起始点最近的位置，这样，当扫描到目标点时，可以保证目标点的距离是离起点距离最近的，也就是找到了寻路的最优解。

A*算法的原理是什么呢？

我们假设有一个6*6的地图。

首先我们需要引进三个东西：OpenList，CloseList，[F=G+H]。

OpenList和CloseList都是存储格子的集合，OpneList中存储的是可到达格子的集合，而CloseList中存储的是已到达的盒子。而F=G+H则是对格子价值的评估，其中G代表了从起点走到当前格子的成本，也就是走了多少步。而H代表了从当前格走到目标格子的距离。也就是不考虑障碍的情况下距离，距离目标还有多远。至于F，则是对G和H的综合评估。显然我们应该选择步数更少，距离目标更近的格子，所以F的值越小越好。

在上面的地图中，我们先把起点[1,3]放入OpenList，此时CloseList为空。

第二步，我们找出OpenList中F最小的方格，即唯一的方格[1,3]作为当前方格，并且把当且格子移除OpenList，放入CloseList表示这个格子已经到达并且检查过了。此时OpenList为空，而CloseLsist中存储着[1,3]。

第三步，我们要找出当前格上下左右可以到达的格子，看他们是否在OPenList中，如果不在，加入OpenList当中，计算出相应的G,H,F值，并把当前格子作为他们的父亲节点，

OpenList中的点：[1,2][2,3][1,4][0,3]

CloseList中的点:[1,3]

记录父亲节点有什么用呢？父亲节点记录了每一个点的来路，在我们最后确认最终路线的时候会使用到。

（以上的步骤就是我们的一次局部搜索，在后面的寻路中，我们会多次重复这个过程，直到找到终点为止。）

接下来，我们在OpenList中昭到F值最小的点（[2,3]）：

将[2,3]放入CloseList中，然后，我们继续找当前格子上下左右中所有可以到达的格子：

这次只增加了两个格子：[2,2][2,4],因为左边的[1,3]格子已经在CloseList中了，而右边的格子是不可以到达的墙壁。

接下来，我们要在OpenList找到当前父格子的子节点中F最小的点，因为两个点的F值相等，我们可以选择任意一个加入到CloseList中，此时

OpenList中的点：[1,2][2,3][1,4][0,3][2,2]

CloseList中的点:[1,3][2,4]

然后接下来，我们再找到当前格子上下左右所有可以到达的格子，看他们是否再OpenList中，如果不在，则加入到OpenList中计算出相应的GHF值，并把当前格子作为父亲节点：

OpenList中的点：[1,2][2,3][1,4][0,3][2,2][2,5]

CloseList中的点:[1,3][2,4]

这次只有一个点，所以我们将其放入CloseList中：

OpenList中的点：[1,2][2,3][1,4][0,3][2,2]

CloseList中的点:[1,3][2,4][2,5]

然后接下来重复刚才的步骤进行迭代，直到到达终点：

听起来不是很难，我们来看一下如何伪代码：

public Node aStarSearch(Node start, Node end) {openList.add(start);// 第一步：把起点加入 open listwhile (openList.size() > 0) { //循环，每一轮检查一个当前方格节点Node current = findMinNode();// 在OpenList中查找 F值最小的节点作为当前方格节点openList.remove(current);// 当前方格节点从open list中移除closeList.add(current);// 当前方格节点进入 close listList<Node> neighbors = findNeighbors(current);// 找到所有邻节点for (Node node : neighbors) {if (!openList.contains(node)) {//邻近节点不在OpenList中，标记父亲、G、H、F，并放入OpenListmarkAndInvolve(current, end, node);}}//如果终点在OpenList中，直接返回终点格子if (find(openList, end) != null) {return find(openList, end);}}//OpenList用尽，仍然找不到终点，说明终点不可到达，返回空return null;}