漫画说算法|什么是A*寻路算法?

为了让小伙伴更加容易理解经典算法,留下深刻印象,小白决定创办「漫画说算法」,分享讲解算法的漫画文章,在阅读漫画的过程中学习。如果小伙伴有收藏的优秀文章,欢迎后台留言与小伙伴们一起分享。

本文转载自公众号:程序员小灰

比如像这样子:

第一步:把起点放入OpenList

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

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

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

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

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

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

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

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

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

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;
}

几点说明:

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

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

—————END—————

更多漫画算法文章,请关注“小白学视觉”

往期文章一览

1、5G时代下,如何利用碎片化时间学习

2、【OpennCV入门之十四】揭开mask

3、【OpenCV入门之十三】如何在ROI中添加Logo

4、如何让黑白相片恢复生机

5、我竟然用OpenCV实现了卡尔曼滤波

6、【走进OpenCV】滤波代码原来这么写

7、【走进OpenCV】这样腐蚀下来让我膨胀

8、小心!你看到的图像可能隐藏了重大机密

原文发布于微信公众号 - 小白学视觉(NoobCV)

原文发表时间:2019-04-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券