再强的算法也找不到来时的路 —— A Star寻路算法

不念不忘少年蓝@ 2023-10-16 09:39 10阅读 0赞

--------------------

### theme: channing-cyan ###

![cover (1).png][cover _1_.png]

## 一、前言 ##

> 再强的算法也找不到来时的路， A Star寻路算法，助我穿越迷雾。
> 
> 节点展开，扩展出路径的分支， 启发式评估，指引前行的方向。
> 
> 从起点出发，逐步向目标前进， 估计最优路径，绕过障碍遥遥蓝天。
> 
> 每一步决策，都基于代价和启发式， 在格子之间，我漫步寻找前程。
> 
> 路途崎岖，坎坷而又不平坦， 我依靠A Star，寻得最短的路径线。
> 
> 虽然不能回到最初的出发地， 但我已找到，通往目标的门径。
> 
> 在未知的领域，A Star指引方向， 虽不能穿越时空，却为我引来光亮。

效果图如下： ![在这里插入图片描述][watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfNjQ_g_se_x_0_y_0_t_100]

## 二、什么是A Start ##

A\*搜索算法是求出在一个二维平面中从起点到终点最低运算代价的算法，它可以算出**A点**到**B点**的最短距离，也就是最优路径。常见的应有主要是在游戏中，人物的自动寻路；机器人探路；交通路线导航等。

## 三、原理和流程 ##

### 2.1 前提 ###

在讲述A Star算法之前，需要声明下列这些属性：

**(1)从起点开始扩散的节点；**

**(2)最短距离计算公式：F = G + H；**

**(3)欧几里得距离计算公式：p = $\\sqrt (x*2 - x*1)^2+(y*2 - y*1)^2$(其实就是勾股定理)；**

**(4)OPENLIST 和 CLOSELIST；**

*上面的属性和公式不懂没关系，下面我会对他们一一进行详细介绍。非常简单！*

#### 2.1.1 从起点开始扩散的节点 ####

我们在HTML页面上使用横和 竖画出来的格子。所谓扩散就是以 起点 为基点向**上**、**下**、**左**、**右**四个放向进行扩散，这些扩展的节点就是可以走的“路”。如下图所示**黄色**的方格就是扩散的点： ![在这里插入图片描述][watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfODc_g_se_x_0_y_0_t_100]

A Star有**四个方向**和**八个方向**的扩散。扩展四个方向的节点就是目前我们所说的；八个方向是还包含了，上左、上右、下左、下右四个方向的节点。我们通篇使用的是四个方向的扩展。

#### 2.1.2 最短距离计算公式：F = G + H ####

如何在扩散的节点中找到最优也就是 `最短` 的一条路呢？就需要用到这个公式$：$ $$ F=G+H $$ 那么这个公式里面的属性都代表什么意识呢？下面我们就说明一下：

**(1)G:** 表示从**起点**到扩散的四个节点的距离，换句话说就是从起点到扩散的四个节点需要移动的格子。`G`的值可以使用欧几里得距离计算公式进行计算。 如下图： ![在这里插入图片描述][watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfODQ_g_se_x_0_y_0_t_100]

**(2)H:**

表示从**起点**开始，到**终点**需要移动的格子(注意：忽略障碍物，可以从障碍物中穿过去)，这个距离需要通过 **欧几里得距离计算公式** 公式算出来。当然你没必要一定要使用欧几里得距离计算公式，你还可以单纯的将**起点**到**终点**的x报坐标差值和y坐标差值进行相加即可。 如下图： ![在这里插入图片描述][watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfODQ_g_se_x_0_y_0_t_100 1] **(3)F:** $ F = G + H $

在扩散节点中F的值最小的就是我们需要走的节点。也就是最短的路径。

#### 2.1.3 欧几里得距离计算公式 ####

这个公式是用来计算`H`和`G`的。公式： $$ p = \\sqrt(x*2 - x*1)^2+(y*2 - y*1)^2 $$ 其实就是**终点**的x坐标减去**起点**的x坐标的平方 + **终点**的y坐标减去**起点**的y坐标的平方 开根号，这不就是勾股定理嘛。

#### 2.1.4 OPENLIST 和 CLOSELIST ####

`OPENLIST`和`CLOSELIST`代表两个“容器”(“容器”在代码中就是两个集合，使用List集合或者数组声明都可以)。这个两个“容器”存放的内容和作用如下：

**(1)OPENLIST** 用于存储扩散的节点。刚开始由**起点**开始向四个方向扩散的节点就需要放到OPENLIST集合中(如果扩散的节点是**障碍物**或者是在`CLOSELIST`中已经存在则不放入)。OPENLIST是主要遍历的集合，计算F值的节点都是来自这个集合。

**(2)CLOSELIST** 用于存储**起点**、**障碍物节点**、**走过的点**。在扩散节点的时候，需要到CLOSELIST集合中去检查，如果扩散的节点D已经在`CLOSELIST`集合中了(根据坐标进行判断)，或者是D节点是**障碍物**那么就跳过此节点。走过的点也需要放到`CLOSELIST`中去。 **走过的点**如下图所示： ![在这里插入图片描述][watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfNjM_g_se_x_0_y_0_t_100]

### 2.2 流程 ###

#### 2.2.1 第一步：扩散 ####

从起点开始向上下左右扩散四个节点。假如起点的坐标为`(x:3,y:2)`，那么四个节点为：上`(x:2,y:2)`、下`(x:4,y:2)`、左`(x:3,y:1)`、右`(x:3,y:3)`。

#### 2.2.2 第二步：检查节点 ####

**遍历CLOSELIST集合**，判断扩散的这四个节点是否存在于`CLOSELIST`或者`OPENLIST`中，如果不存在放到`OPENLIST`中，反之跳过该节点。如果该节点是**障碍物**也需要跳过。

#### 2.2.3 第三步：计算F的值 ####

**遍历OPENLIST集合**，并计算集合中节点的F的值，找出F值为最小的节点(距离最近)`minNode`，这个节点就是要走的节点。然后把除了`mindNode`之外的其它扩散的节点放入到`CLOSELIST`中。

#### 2.2.4 第四步：改变起点的位置 ####

通过第三步我们找到了F值最小的一个节点`minNode`，那么就把起点等于`minNode`。然后继续进行扩散重复上面的四个步骤，直至在**扩散的节点中包含终点**我们走过的节点就是最短路径。

## 3.A Star算法代码实现 ##

[jcode][]

`Java`代码我就不放出来了，如果想要的可以评论区留言。下面是用`JS`写的。写的不好的地方大家指出，我会即时更正！

HTML:

\`\`\`html

寻路02

随机生成障碍物 开始寻路 停止

JS：

\`\`\`javascript

\`\``上面代码有个**BUG**留给大家了，在随机生成障碍物时会出现`死路\`，就是在起点周围全部都是障碍物导致无法寻路到终点，那么怎么办呢？我上篇文章中写到 [洪水填充算法 —— 密恐][Link 1]可以解决，留给大家思考啦~

## 4. 结语 ##

`A Star`扩散四个方向的算法就这些。如果有时间可以把扩散八个方向的总结一下。写这篇文章我想向大家提供的是`A Star`算法的过程与实现的思路，但是如果想要真正运用还需要考虑很多东西，要贴合自己的场景。上面的代码还有问题。希望大家指出来，我会及时更正。还有什么不懂的可以在评论区讨论。

[cover _1_.png]: https://img-blog.csdnimg.cn/img_convert/578d25120cf32e239c0960a3882e81dc.png?x-oss-process=image/watermark,image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfMTQw,g_se,x_0,y_0,t_100
[watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfNjQ_g_se_x_0_y_0_t_100]: https://img-blog.csdnimg.cn/img_convert/6c91f61b3bb5841e067b741ecd98e035.gif?x-oss-process=image/watermark,image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfNjQ=,g_se,x_0,y_0,t_100
[watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfODc_g_se_x_0_y_0_t_100]: https://img-blog.csdnimg.cn/img_convert/3958fd259ca95d1974d091aecbd23a42.png?x-oss-process=image/watermark,image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfODc=,g_se,x_0,y_0,t_100
[watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfODQ_g_se_x_0_y_0_t_100]: https://img-blog.csdnimg.cn/img_convert/21469dbd195499c26114deeaf9bb7646.png?x-oss-process=image/watermark,image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfODQ=,g_se,x_0,y_0,t_100
[watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfODQ_g_se_x_0_y_0_t_100 1]: https://img-blog.csdnimg.cn/img_convert/e35548bb96700ee90751c440c2b3f8a7.png?x-oss-process=image/watermark,image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfODQ=,g_se,x_0,y_0,t_100
[watermark_image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfNjM_g_se_x_0_y_0_t_100]: https://img-blog.csdnimg.cn/img_convert/7f9341d85bf00cd5b623631769c66909.png?x-oss-process=image/watermark,image_bG9nby9jc2RuXzEucG5nP3gtb3NzLXByb2Nlc3M9aW1hZ2UvcmVzaXplLGhfNjM=,g_se,x_0,y_0,t_100
[jcode]: https://code.juejin.cn/pen/7265870490097909819
[Link 1]: https://juejin.cn/post/7264951443345850405