什么是A*寻路算法？
妈妈再也不用担心我会迷路了。...
来自：梦见（微信号：dreamsee321）
比如像这样子：
第一步：把起点放入OpenList
图中，每个格子的左下方数字是G，右下方是H，左上方是F。
为什么这一次OpenList只增加了两个新格子呢？因为Node(3,2)是墙壁，自然不用考虑，而Node(1,2)在CloseList当中，说明已经检查过了，也不用考虑。
Round3 ~ 第一步：找出OpenList中F值最小的方格。由于这时候多个方格的F值相等，任意选择一个即可，比如Node(2,3)作为当前方格，并把当前格移出OpenList，放入CloseList。代表这个格子已到达并检查过了。
剩下的就是以前面的方式继续迭代，直到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 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—————
系列文章：
《漫画：什么是一致性哈希？》
《漫画：什么是B+树？》
《漫画：什么是B-树？》
《漫画：什么是跳跃表？》
《漫画：什么是动态规划？》
《漫画：当程序猿遇上智力测试题》
《漫画：判断 2 的乘方》
《漫画算法：最小栈的实现》
《漫画：什么是大数据？》
《漫画算法：无序数组排序后的最大相邻差值》
《漫画：什么是Bitmap算法？》
《漫画：Bitmap算法 进阶篇》
《漫画：什么是布隆算法？》
●本文编号463，以后想阅读这篇文章直接输入463即可
●输入m获取到文章目录
推荐↓↓↓
大数据技术
更多推荐《18个技术类公众微信》
涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。
关注 算法与数据结构
微信扫一扫关注公众号
