A*算法-自动寻路

A* 算法属于一种启发式搜索算法(Heuristically Search Algorithm)

算法解析

人物的起点就是他当下所在的位置,终点就是鼠标点击的位置。我们需要在地图中,找一条从起点到终点的路径。这条路径要绕过地图中所有障碍物,并且看起来要是一种非常聪明的走法。所谓“聪明”,笼统地解释就是,走的路不能太绕。理论上讲,最短路径显然是最聪明的走法,是这个问题的最优解。不过,如果图非常大,那 Dijkstra 最短路径算法的执行耗时会很多。

实际上,像出行路线规划、游戏寻路,这些真实软件开发中的问题,一般情况下,我们都不需要非得求最优解(也就是最短路径)。在权衡路线规划质量和执行效率的情况下,我们只需要寻求一个次优解就足够了。

A* 算法是对 Dijkstra 算法的优化和改造,下面这个图对应一个真实的地图,每个顶点在地图中的位置,我们用一个二维坐标(x,y)来表示,其中,x 表示横坐标,y 表示纵坐标


假设我们要从S 到 t,如果利用Dijkstra 算法,那么像0-1-2-3这条路径也会被考虑进去

算法步骤

1.选取0周围的4个顶点,分别计算0到各个顶点的距离记作g(i),再分别计算各个顶点到终点t的曼哈顿距离(Manhattan distance)(欧几里得距离需要平方根,比较耗时)记作h(i),专业的叫法是启发函数(heuristic function)

取g(i)+h(i) 的值最小的那个顶点作为步入的下一个顶点

2.重复上述步骤,知道到达终点t

在实际应用中,可以有很多变种,比如将整个地图分割成一个一个的小方块。在某一个方块上的人物,只能往上下左右四个方向的方块上移动。我们可以把每个方块看作一个顶点。两个方块相邻,我们就在它们之间,连两条有向边,并且边的权值都是 1。所以,这个问题就转化成了,在一个有向有权图中,找某个顶点到另一个顶点的路径问题。将地图抽象成边权值为 1 的有向图之后,我们就可以套用 A* 算法,来实现游戏中人物的自动寻路功能了


摘录自 极客时间-数据结构与算法之美

上一篇: 迪杰斯特拉最短路径
下一篇: 分治法
作者邮箱: 203328517@qq.com