AStar寻路原理

本文转自Unity Connect博主 majorWu

起源

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

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

简介

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

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

AStar算法原理

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

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

首先说一下用到的名词&＃xff1a;

• 开放列表&＃xff1a;一个记录所有被考虑来寻找最短路径的网格集合
• 关闭列表&＃xff1a;一个记录下不会被考虑的网格集合
• G &＃xff1a;表示从起点方格移动到网格上指定方格的移动耗费 (可沿斜方向移动).
• H &＃xff1a;表示从指定的方格移动到终点方格的预计耗费 (H启发函数).

核心部分

下图所示的中心方块为当前块&＃xff0c;已被放入关闭列表&＃xff0c;那接下来怎么确定下一步要走的方格&＃xff1f;

这就是Astar核心部分&＃xff1a;路径代价

权重值&＃xff1a;F&＃61;G&＃43;H&＃xff0c;G和H前面我们有介绍过&＃xff0c;我们将根据这个权重值引导每一步的走向&＃xff0c;直至目标点

那么G和H我们应该怎么计算&＃xff0c;下面给出了三种基本的估价算法(也称估价公式)&＃xff0c;其算法示意图如下&＃xff1a;

分别为&＃xff1a;曼哈顿估价法、几何估价法、对角线估价法

我们以曼哈顿估价法为例&＃xff1a;起点A(X1&＃xff0c;Y1)&＃xff0c;终点B(X2&＃xff0c;B2)&＃xff0c;那么距离可根据上图第一幅图可得出&＃xff1a;D&＃61;X2-X1&＃43;Y2-Y1

现在我们知道了估价法&＃xff0c;接下来我们继续下一步方块的确定。下图是我们对前相邻的每个方块的估价&＃xff0c;左上角表示F值&＃xff0c;左下角表示G值&＃xff0c;右下角表示H值。

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

实现步骤:

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

2.重复如下的工作&＃xff1a;

a) 寻找开启列表中估量代价F值最低的格子。我们称它为当前格。b) 把它切换到关闭列表。c) 对相邻的8格中的每一个进行如下操作* 如果它不可通过或者已经在关闭列表中&＃xff0c;略过它。反之如下。* 如果它不在开启列表中&＃xff0c;把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。* 如果它已经在开启列表中&＃xff0c;用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样&＃xff0c;就把这一格的父节点改成当前格&＃xff0c;并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序&＃xff0c;改变之后你可能需要重新对开启列表排序。d) 停止&＃xff0c;当你* 把目标格添加进了关闭列表(注解)&＃xff0c;这时候路径被找到&＃xff0c;或者* 没有找到目标格&＃xff0c;开启列表已经空了。这时候&＃xff0c;路径不存在。


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

最后本文是按自己对AStar的理解&＃xff0c;按照自己的思路写出来&＃xff0c;作为总结和备忘。有不对或理解错误的地方&＃xff0c;烦请指正。

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