AStar-寻路原理

[unn]

本文转自 Unity Connect 官方博主 majorWu

起源

  由于一次面试被问起 AStar 算法原理，我当场面红耳赤，不知怎么开口，这个耳熟能详的寻路算法，我对它的原理却浑然不知，一直都有听大家说到这个算法，也有调用过相关接口，然自己却那么陌生，真想一头钻到地底。于是就有这边篇记录 AStar 算法原理的学习文章。

    AStar 算法是一种静态路网中求解最短路径最有效的直接搜索方法。在包含各种障碍物的地图中，为游戏角色的移动，寻找一条到目标地点最短路径。

简介

    AStar （又称 A*），它结合了 Dijkstra 算法的节点信息（倾向于距离起点较近的节点）和贪心算法的最好优先搜索算法信息（倾向于距离目标较近的节点）。可以像 Dijkstra 算法一样保证找到最短路径，同时也像贪心最好优先搜索算法一样使用启发值对算法进行引导。

    简单点说，AStar 的核心在于将游戏背景分为一个又一个格子，每个格子有自己的靠谱值，然后通过遍历起点的格子去找到周围靠谱的格子，接着继续遍历周围…… 最终找到终点。

AStar 算法原理

    在游戏的地图中，AStar 会被预先烘焙成相应的格子记录相关信息。

经典原图 上图 A 表示起点，B 表示终点，蓝色方块表示障碍物，我们需要找出一条路，从 A 点开始，绕过蓝色方块，到达 B 点。

首先说一下用到的名词：

开放列表：一个记录所有被考虑来寻找最短路径的网格集合

关闭列表：一个记录下不会被考虑的网格集合

G：表示从起点方格移动到网格上指定方格的移动耗费 (可沿斜方向移动).

H：表示从指定的方格移动到终点方格的预计耗费 (H 启发函数).

这就是 Astar 核心部分：路径代价

       权重值：F=G+H，G 和 H 前面我们有介绍过，我们将根据这个权重值引导每一步的走向，直至目标点

       那么 G 和 H 我们应该怎么计算，下面给出了三种基本的估价算法(也称估价公式)

分别为：曼哈顿估价法、几何估价法、对角线估价法

我们以曼哈顿估价法为例：起点 A(X1，Y1)，终点 B(X2，B2)，那么距离可根据上图第一幅图可得出：D=X2-X1+Y2-Y1

现在我们知道了估价法，接下来我们继续下一步方块的确定。

通过 F 值比较，我们找出 F 值最小的方块，也就是当前方块右侧的那块，标记为 C （ F 值为 40 ），我们把当前方块放入关闭列表，周围的方块放到开启列表中，然后同上反复操作，找到 C 周围相邻的方块（过滤掉蓝色方块的障碍区域及已被添加到关闭列表的），估价计算出相应的 F 值，上下 F 值一样，然后随机找到了 D，把当前 C 放入关闭列表，周围的方块放到开启列表中(已存在的跳过)

实现步骤:

1.把起始格添加到开启列表。

2.重复如下的工作：

  a) 寻找开启列表中估量代价 F 值最低的格子。我们称它为当前格。

  b) 把它切换到关闭列表。

  c) 对相邻的 8 格中的每一个进行如下操作

      * 如果它不可通过或者已经在关闭列表中，略过它。反之如下。

      * 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的 F,G,和 H 值。

      * 如果它已经在开启列表中，用 G 值为参考检查新的路径是否更好。更低的 G 值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的 G 和 F 值。如果你保持你的开启列表按 F 值排序，改变之后你可能需要重新对开启列表排序。

  d) 停止，当你

      * 把目标格添加进了关闭列表(注解)，这时候路径被找到，或者

      * 没有找到目标格，开启列表已经空了。这时候，路径不存在。

3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。

最后本文是按自己对 AStar 的理解，按照自己的思路写出来，作为总结和备忘。有不对或理解错误的地方，烦请指正。由于无法上传图片，详细内容请看原文。

原文链接： https://connect.unity.com/p/astar-xun-lu-yuan-li?app=true 欢迎大家戳上方链接，下载 Unity 官方 app，和博主一起探讨交流，在这里可以认识很多有趣的小伙伴，还有在线答疑，更多实用干货。