A星算法

本是古典何须时尚 2022-12-06 12:59 222阅读 0赞

> A星算法就是试图在地图中找到一条最短路径，但不保证一定存在。

# 搜索区域(The Search Area) #

我们假设某人要从A点移动到B点，但是这两点之间被一堵墙隔开。如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

你应该注意到了，我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域。这样我们把我们的搜索区域简化为了二维数组。数组的每一项代表一个格子，它的状态就是可走和不可走。通过计算出从A到B需要走过哪些方格，就找到了路径。一旦路径找到了，任务就从一个方格的中心移动到了另一个方格的中心，直到到达目的地。

方格的中心点我们称为“节点(nodes)”。如果你读过其他关于A\*寻路算法的文章，你就会发现人们常常都在讨论节点。为什么不直接描述为方格呢？因为我们有可能把搜索区域划分为其他多边形而不是正方形，比如搜索区域可以是矩形、六角形等等。而节点可以放在任意多边形里面，可以放在多边形的中心，也可以多边形的的边上。我们使用这个系统，因为它最简单。

# 开始搜索(Starting the Search) #

一旦我们把搜索区域简化为一组可以量化的节点之后，就像上面做的一样，我们下一步要做的就是查找最短路径。在A\*中，我们从起点开始，检查其相邻的方格，然后向四周扩展，直到找到目标。

我们这样开始我们的寻路旅途：

1.  从起点A开始，并把它加入到一个由方格组成的open list（开放类表中）

[曼哈顿距离][Link 1]  
[3D][]  
[A星寻路算法—超详细的例子][A]  
[可视化demo][demo]  
[来源][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/94e4589d1df042ef9463d1bfb3b3faec.png
[Link 1]: https://baike.baidu.com/item/%E6%9B%BC%E5%93%88%E9%A1%BF%E8%B7%9D%E7%A6%BB/743092?fr=aladdin
[3D]: https://www.hightopo.com/demo/astar/astar.html
[A]: https://www.jianshu.com/p/65282bd32391
[demo]: https://anseyuyin.github.io/AStar-Process/demo/
[Link 2]: https://www.bilibili.com/video/BV1T7411o7V2?from=search&seid=482150629976654748