最近读到一篇关于《HTML5实现炮塔防守》的文章,对其中的路径搜索算法有点兴趣,稍微探索了一下。
基于搜索下载的Micheal Hong的Java版本的AStar算法,并做了一些调整。核心代码如下:
while (open.isEmpty() == false) {
close.add(open.remove(0));
getNeighbour(node, neighbour);
for (int i = 0; i < neighbour.length; i++) {
if ((index = contain(open, neighbour[i].x, neighbour[i].y)) != -1) {
if (open.get(index).gn > neighbour[i].gn)
// 以前掠过这个节点的时候(getNeighbour的形式)的代价比现在掠过这里的代价大,说明现在的掠过更好
// 所以用现在的掠过代替?也就是说要把原来的那个替换掉,
open.set(index, neighbour[i]);
// 反之,就不考虑这个新的掠过
} else
open.add(neighbour[i]); // 没有曾经掠过,就作为候选节点加入
}
/* 判断是否到达目标 */
if ((index = contain(open, end.x, end.y)) != -1) {
int count = 1;
Node d = open.get(index);
while (d.father != null) {
d = d.father;
count++;
}
d = open.get(index);
int[][] path = new int[count][];
for (int i = count - 1; i >= 0; i--) {
path[i] = new int[2];
path[i][0] = d.x;
path[i][1] = d.y;
d = d.father;
}
return path;
}
/* 对open表进行排序(按fn由小到大) */
// 我认为可以不用sort,只是取一个值而已,
// 也可以在加入open队列的时候就已经形成了大值排序
Collections.sort((open));
}
我认为AStar算法的思想不错。
对于遍历,我们想到的可能就是深度优先遍历和广度优先遍历,但是那种教科书式的遍历方法的搜索空间太大了。
于是人们想到了缩小范围的方法,技术总是在不断改进的驱动下进步的。
AStar就是这个思想驱动下诞生的,首先基于原有广度优先遍历会随着层级的递增可选的next step会越来越多,我们不难想到如何在可选的next step集合中找到一个最优的next step,所以关键点就在于如何定义这个最优评估的方法的问题了。
AStar的评估方法就是F=H+G,也就是说评估值等于已经走过的路径总长度加上未来可能还需要走的路径总长度。全局排序后选最优的,也就是最短的。
已经走过的路径很容易,只要我们把它记录累加就能得到,所以关键点又落到了如何预估未来需要走的路径总长度。
那未来需要走的路径总长度又怎么评估呢?就像一个人进入一个沙漠,完全不知道剩下的路到底还有多长,只知道自己已经走了三天三夜,呵呵。
AStar给出了一个方案,那就是当前坐标和目的地坐标的X,Y的差值和,外国人叫曼哈顿距离。具体见百度百科
这样通过比较F值也就是说总路程最短的优先作为next step(虽然只是预估出来的)。
这就像迷茫的寻路过程有了一盏灯指引着你走向终点。而这盏灯其实关键点就是那个曼哈顿距离,所以AStar算法是一种启发式的路径搜索算法。
膜拜了一下这个曼哈顿距离,不经让我发问:为什么就曼哈顿距离而不是其他距离?(TB continue..)
分享到:
相关推荐
根据最优路径算法Astar算法编写的C++求解迷宫问题
使用AStar算法实现了一个简单的demo,亲测可用,代码不多流程简单,一看就会
2.内容:基于Astar算法的栅格地图避障路线规划matlab仿真+代码仿真操作视频 3.用处:用于Astar算法编程学习 4.指向人群:本硕博等教研学习使用 5.运行注意事项: 使用matlab2021a或者更高版本测试,运行里面的...
AStar算法 C#写的但不是我写的 自己稍加修改了一下
Astar算法在ROS上的简单移植,含有参考的地址,算是基础的东西
人工智能 AStar 算法 Java窗体实现
Python基于DWA算法和Astar算法的轮式机器人路径规划源码+项目部署说明.zip 实现Astar算法和DWA算法的结合 1. main.py: 文件可以通过Astar算法实现两点间的路径规划 2. dwa.py: 文件在main.py文件的基础上增加了dwa...
AStar算法详解PPT教学课件.pptx
AStar算法的具体C实现,含有界面、论文等等,论文中有所用到的流程图、数据结构、OPEN表、CLOSED表以及状态空间图 还有CLOSED表、OPEN表的搜索过程
Astar算法机器人路径规划 Ubuntu,在playerstage仿真。
人工智能,用ASTAR算法实现8数码和15数码问题
包含A星算法 ....... .xxx... ...x.x. ...x.x. .....x. .....x. .....x.
将Astar算法应用在四足机器人上面,实现利用Astar算法进行机器人自由步态规划,并可以实现越障等功能
一种利用Astar算法实现最短路径查找,本程序利用5*5方格进行路径模拟
基于DWA算法和Astar算法的轮式机器人路径规划python源码+项目说明.zip 基于DWA算法和Astar算法的轮式机器人路径规划python源码+项目说明.zip 基于DWA算法和Astar算法的轮式机器人路径规划python源码+项目说明.zip ...
Python基于DWA算法和Astar算法的轮式机器人路径规划源码+使用说明.zip本资源中的源码都是经过本地编译过可运行的,评审分达到95分以上。资源项目的难度比较适中,内容都是经过助教老师审定过的能够满足学习、使用...
人工智能Astar算法C语言实现八数码问题
路径规划中的Astar算法,开源项目网站Handsfree(https://github.com/HANDS-FREE/OpenRE); 项目网站和教程: http://wiki.hfreetech.org/ 开源代码 : https://github.com/hands-free
路径规划A*算法的python实现,带有详尽注释
A*算法matlab代码(适合初学者)