0°

什么是A*寻路算法?

内容预览:
  • 这里就仅用图片简单描述了,方格中数字表示F值: public Node aStarSear...~
  • 2.截图中的小游戏可不是小灰开发的,而是一款经典的老游戏,有哪位小伙...~
  • 原文始发于微信公众号(程序员数学之美):什么是A*寻路算法? 来自:程...~

原文始发于微信公众号(程序员数学之美):什么是A*寻路算法?

来自:程序员小灰(微信号:chengxuyuanxiaohui)

作者:玻璃猫


什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



比如像这样子:



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



第一步:把起点放入OpenList


什么是A*寻路算法?



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


什么是A*寻路算法?



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


什么是A*寻路算法?


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



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



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


什么是A*寻路算法?



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


什么是A*寻路算法?


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



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


什么是A*寻路算法?



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


什么是A*寻路算法?



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


什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?



什么是A*寻路算法?

什么是A*寻路算法?

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

什么是A*寻路算法?



几点说明:


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


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


—————END—————



●本文编号251,以后想阅读这篇文章直接输入251即可

●输入m获取到文章目录

推荐↓↓↓

 

什么是A*寻路算法?

算法与数据结构

更多推荐18个技术类微信公众号

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

和大佬一起学习网络安全知识

以上就是:什么是A*寻路算法? 的全部内容

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢^^
Email:[email protected]


编程语言
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论