漫画：什么是A*寻路算法？

怼烎@ 2023-05-28 14:18 12阅读 0赞

![format_png][]

![format_png 1][]

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

比如像这样子：

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

![format_png 17][]

![format_png 18][]

![format_png 19][]

![format_png 20][]

![format_png 21][]

![format_png 22][]

**第一步：把起点放入OpenList**

![format_png 23][]

**第二步：找出OpenList中F值最小的方格，即唯一的方格Node(1,2)作为当前方格，并把当前格移出OpenList，放入CloseList。代表这个格子已到达并检查过了。**

![format_png 24][]

**第三步：找出当前格上下左右所有可到达的格子，看它们是否在OpenList当中。如果不在，加入OpenList，计算出相应的G、H、F值，并把当前格子作为它们的“父亲节点”。**

![format_png 25][]

**图中，每个格子的左下方数字是G，右下方是H，左上方是F。**

![format_png 26][]

![format_png 27][]

![format_png 28][]

**Round2 ~ 第一步：找出OpenList中F值最小的方格，即方格Node(2,2)作为当前方格，并把当前格移出OpenList，放入CloseList。代表这个格子已到达并检查过了。**

![format_png 29][]

**Round2 ~ 第二步：找出当前格上下左右所有可到达的格子，看它们是否在OpenList当中。如果不在，加入OpenList，计算出相应的G、H、F值，并把当前格子作为它们的“父亲节点”。**

![format_png 30][]

**为什么这一次OpenList只增加了两个新格子呢？因为Node(3,2)是墙壁，自然不用考虑，而Node(1,2)在CloseList当中，说明已经检查过了，也不用考虑。**

**Round3 ~ 第一步：找出OpenList中F值最小的方格。由于这时候多个方格的F值相等，任意选择一个即可，比如Node(2,3)作为当前方格，并把当前格移出OpenList，放入CloseList。代表这个格子已到达并检查过了。**

![format_png 31][]

**Round3 ~ 第二步：找出当前格上下左右所有可到达的格子，看它们是否在OpenList当中。如果不在，加入OpenList，计算出相应的G、H、F值，并把当前格子作为它们的“父亲节点”。**

![format_png 32][]

**剩下的就是以前面的方式继续迭代，直到OpenList中出现终点方格为止。这里就仅用图片简单描述了，方格中数字表示F值：**

![format_png 33][]

![format_png 34][]

![format_png 35][]

![format_png 36][]

![format_png 37][]

![format_png 38][]

![format_png 39][]

![format_png 40][]

![format_png 41][]

![format_png 42][]

![format_png 43][]

![format_png 44][]

![format_png 45][]

![format_png 46][]

![format_png 47][]

![format_png 48][]

public Node aStarSearch(Node start, Node end) {
        // 把起点加入 open list  
        openList.add(start);
        //主循环，每一轮检查一个当前方格节点
        while (openList.size() > 0) {
            // 在OpenList中查找 F值最小的节点作为当前方格节点
            Node current = findMinNode();
            // 当前方格节点从open list中移除
            openList.remove(current);
            // 当前方格节点进入 close list
            closeList.add(current);
            // 找到所有邻近节点
            List<Node> neighbors = findNeighbors(current);
            for (Node node : neighbors) {
                if (!openList.contains(node)) {
                    //邻近节点不在OpenList中，标记父亲、G、H、F，并放入OpenList
                    markAndInvolve(current, end, node);
                }
            }
            //如果终点在OpenList中，直接返回终点格子
            if (find(openList, end) != null) {
                return find(openList, end);
            }
        }
        //OpenList用尽，仍然找不到终点，说明终点不可到达，返回空
        return null;
    }

![format_png 49][]

**几点说明：**

1.这里对于A\*寻路的描述做了很大的简化。实际场景中可能会遇到斜向移动、特殊地形等等因素，有些时候需要对OpenList中的方格进行重新标记。

2.截图中的小游戏可不是小灰开发的，而是一款经典的老游戏，有哪位小伙伴玩过吗？

[format_png]: /images/20230528/9a32c085fd964a619fa523f24c46db03.png
[format_png 1]: /images/20230528/4f6960f512c24ff2a1d730d07762af92.png
[format_png 2]: /images/20230528/539e2f8343c449848dc3155a8e727a8a.png
[format_png 3]: /images/20230528/b597871cfe804e5da4dbd4ecc6db9522.png
[format_png 4]: /images/20230528/4466fd0ec26b4bd89c73aa64cebb11b8.png
[format_png 5]: /images/20230528/2394127ace04421cbc994de6b88b4dc6.png
[format_png 6]: /images/20230528/8a67d9e5f3834f8ab743216b83b70f68.png
[format_png 7]: /images/20230528/604becb260a7405cba184ada357592fb.png
[format_png 8]: /images/20230528/a1e39a39b59d484e9d410910be5fccf1.png
[format_png 9]: /images/20230528/d929319a72b04d5faea7414549f559bd.png
[format_png 10]: /images/20230528/fa36f23c890f43828b8879da1633181a.png
[format_png 11]: /images/20230528/727546f1b5ef45d8b8aba21d4a330a16.png
[format_png 12]: /images/20230528/fa6bbec2e12743bd9eb24d5fa9bce210.png
[format_png 13]: /images/20230528/2cbbaaef225a42bfa5146973d7300723.png
[format_png 14]: /images/20230528/1e00b4ef7fc34d318d1e0cff96e03114.png
[format_png 15]: /images/20230528/3ecb4f44b19a405f877f62e091d9ef17.png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UjlIRE5zNEt5MEJnaWJiSURHZ1FMVXI0WU9HSWljbzlvdVMxN2RpYVkwaWM3dUZBUzNVTFoyZEdFTEEvNjQw?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UnhmNFFzTWRxSHJ2RVVZWVpaUk5SOEptTjJVazFZNEk1dWQza2x3OUpZSG9ZWUpBR0VPMHNNQS82NDA?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UjNhMGhWNkJFVUdpYk1XMUI0bmpiNE9QSUc0MXNWaWM3WXlVSHF2OE5melJ5ajVHVnZLaWFxb2NJUS82NDA?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UjByM0JMTmpabG83Q2NMZmlha09xNWJsTjQzbHc2Sk9WYzdLQXBabkhvTWRwVmpKcHFmZ3d5ZFEvNjQw?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UkNaclZlQWF5OVlUbXppY3BWck44TGFwOWNIQTMyUnRLSlRXNUc0dGNyYkxsaFp4WFNSMEJKTEEvNjQw?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UnpXRDVRVGVNNktKV3BFTUpVY1M4aWNXYUFDd1ZleGlieWljaFF2cW5ZaDlTcmY5SjlOWjdkQjVMdy82NDA?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UnJKZlZCSFlvek1saWJNVVNBVmhKSDFxR00zWDRvMXlZOE93RGlhNVE1c2xDRFUycVI4aWIzQjE4US82NDA?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1Uk02VmlhYUdjRER4cjV0QjVMTm91Y2NiNk5taWNvNURLdG9xbzhGcm9rdVo4ZWozWXBZcXpxcWx3LzY0MA?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UlpGVzBVbFlQWFRMemxpYnRLcGZheTRCRXc5TTd4ZTZkS0RpYWJQT0lGTWljTWZ6bHI2STZhZFNkQS82NDA?x-oss-process=image/format,png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UkM4aWNIbjBhaFNQdnY3dG11QVF3U3hybGNpYUtKSE56M2ljSUFnRk9CTGx5RTgyaWJwcHFSNFFhb2cvNjQw?x-oss-process=image/format,png
[format_png 26]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UmljQXB3RGFENFBER1NXU2dSQUxMZ3FPaDNGREVKSWJYYnNBOGljaWJQWlQ1cUZSU1pVdUN6ekNaQS82NDA?x-oss-process=image/format,png
[format_png 27]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR293eHc5ZGF5QWZpYU9uemliNHBySVF1UjRYbXJpY2xWdm1hMHNUZGFpY0ViVW1ZY3RpYkU5aWFsUldUdmpTdncxVlA3a1pnb2liTkhHZVh4cnBBLzY0MA?x-oss-process=image/format,png
[format_png 28]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMk9ERUpwNnlRWmIxald1MUxSVFNhTVNwN0hoamliUXBoMmljcDd4bm1CZ1o2c1JjNThUdEUwSmRRLzY0MA?x-oss-process=image/format,png
[format_png 29]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMmNLb2ljdHM4RUFnTHBlZGJzdVozSGtQejI4VkhYSElpYnZpYW1tQ2liRjE0cWU3SXdCdGI1R2Rlb3cvNjQw?x-oss-process=image/format,png
[format_png 30]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMnF4TkxVdFk2UW1wcmljM09Tc1I0d3Q5STdDbVJhNEppYjF4aHh1ZDA2TzdZeUJ2M2NWWFNqRWlidy82NDA?x-oss-process=image/format,png
[format_png 31]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMjkyakdBU2ZSc29aNk14T3BZQndTNlYxSktXVHlOT3NlclBPa0hRRFpEOHczMVNoMkg1S2ljaWFBLzY0MA?x-oss-process=image/format,png
[format_png 32]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMmljQ2hhUXRCR0FRZlZhWTJXdGw2TTQ5RE9OR3VqNmFlb1Q4bUVna285VTJsVmliaWNLak5kSjZOdy82NDA?x-oss-process=image/format,png
[format_png 33]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMmlic3hzQVUxSTlwOHlYa2lhRU03NlFlZjAwaHJCWkJUMjBNWDlZR1BkTVd2b2liWk1pYnc0SDFlR2cvNjQw?x-oss-process=image/format,png
[format_png 34]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMjAzZDJsdG9ncU85WXlpYnhhdzlsd1BqY29ibEljZEJ6VGlhR0FMZk9YdEFMT1FwMzRaU3VDdmljdy82NDA?x-oss-process=image/format,png
[format_png 35]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMjRLeFdtd1hORHd2WDJ1SHRsUnRYSm9pYW1Yb2Y2M2w2azBXOW5FN0E3QUpOdXE0TU9obW5VT3cvNjQw?x-oss-process=image/format,png
[format_png 36]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMmljU2lhY2liVWJiMWRFZm9IVXN0cmVGU2d1c1pZQnVNMm4wdDZVbGxldENpY2hrQURRMGlhRGljVFlnZy82NDA?x-oss-process=image/format,png
[format_png 37]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMmhaR1YzV1A1WWpqYlpOOHFHTnU0ZFJQZDhwT1RQYlBQOFZOQmtUM3NlaGtXa3o0OFNLd1JCZy82NDA?x-oss-process=image/format,png
[format_png 38]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMkppYjcybnFYMGliMjI1VW81RE5ZYWlibnJWU2p1WlE5MmNpY0VBVEtGZFJLalhMZFlyS2liejUwQnRBLzY0MA?x-oss-process=image/format,png
[format_png 39]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMkJ5alJJVnZCa0FXZjVNa0FvWmtGaEhwdWVFcUszMU5NNE1vTUlpY3Q1dktUMFZaSWNqZG9DT1EvNjQw?x-oss-process=image/format,png
[format_png 40]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMllPa3pqbFpqQVptNFNONXU0bEdnaFBhb2liSmtqRmlhd0ZqclRtVzRkeWFucDR0QVppY0JnUGM2US82NDA?x-oss-process=image/format,png
[format_png 41]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMjVTcW9uS25nRzAyV05vU3o1M2ljQ1E4QXFzZHFJT05zTHNOc25pY2NTNmFERFZ3bUV3Z0M2c3VRLzY0MA?x-oss-process=image/format,png
[format_png 42]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMkE2NjNDMDFQd2RKWWNpYk50NUdDSmxMT0FNZUQ0cnJWWHZyUmV5QjlUQmxJU21PYXBWaWJqNlZRLzY0MA?x-oss-process=image/format,png
[format_png 43]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMjgyRFF3MGlhTWVpYkEyanhzVFBwRnpPakxaanV3MU1NcXBJQ1NXVW5XQUhYcDUyZUVXeWliY0hOdy82NDA?x-oss-process=image/format,png
[format_png 44]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR283VEpXZzcyZ3NnZmh0eDYzZXBlb0F3OUZmbU9ucXFQTEFYdGdpYmhvbGc4Sjd4WEN2SEx1SnBScTNPYnlONFZFRkREYmdYa1lNNUFnLzY0MA?x-oss-process=image/format,png
[format_png 45]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMmN5TDY5RVZzM3BJdVdyUmliYW5PUWI3azhqRFkyNVp3WVc0QTBkTG5PbDBrZmJWOTNmem9EWWcvNjQw?x-oss-process=image/format,png
[format_png 46]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMnZNSFJHWlpkM0tyYWNyTE5pY2t0M1lWYWN0aWNoaWNqaFVvT2IzdXFoVlJtaExhSEtLMHdmckhwdy82NDA?x-oss-process=image/format,png
[format_png 47]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMmlhWjdKclE4aEg1N09QVVF2ZVZTMUpWNkFYanloYkJoaWNUWjB2YzQ4WDgyRkdOS2ljeWpWNFJpYlEvNjQw?x-oss-process=image/format,png
[format_png 48]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMm5iNWRQTjg0WTU1THhPUE1EY3duamUzZkVVMkppYTBLbHFXUG91dW53UENZRGljQ0UzaWFzR2xPQS82NDA?x-oss-process=image/format,png
[format_png 49]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JuU2lhU3NDaDlSd2lhT211NXN0dktMMjdENlQyU1FmbmRyUHRrelFBVUhab0tmNDZPbTdpYU5VN0pDanVXUUpmSkhjaklvY1BpYTB6M1NRLzY0MA?x-oss-process=image/format,png