据我个人所知,目前流行的寻径方法大体有两种,即A* 和Dijkstra(SP算法)
Dijkstra算法: 由Edsger Wybe Dijkstra先生发明(已故)
Dijkstra算法是典型的最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。Dijkstra算法是一种逐步搜索算法,通过为每个顶点n保留目前为止所找到的从m到n的最短路径来工作的。
搜索过程:
假如在第m步搜索到一个最短路径,而该路径上有n个距离源节点最近的节点,则将他们认为是一个节点集合N;在第m+1步,搜索不属于N的距离源节点最近的节点,并搜索到的节点加入到N中;继续搜索,直至到达目的节点,N中的节点集合便是从源节点到目的节点的最短路径。
算法描述:
Dijkstra算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,源点s的路径长度值被赋为0(d[s]=0), 同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点v除s外d[v]= ∞)。当算法结束时,d[v]中储存的便是从s到v的最短路径,或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点,而集合Q则保留其他所有顶点。集合S 初始状态为空,而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中,算法对每条外接边(u,v)进行拓展。
A*(A Star)算法:
A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为:f(n)=g(n)+h(n), 其中f(n) 是节点n从初始点到目标点的估价函数,g(n) 是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。
搜索过程:
创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。遍历当前节点的各个节点,将n节点放入CLOSE中,取n节点的子节点X,->算X的估价值.
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小,从最小路径的节点向下进行。
}
就实际应用而言,A*算法和Dijistra算法的最大区别就在于有无估价值,本质上Dijistra算法相当于A*算法中估价值为0的情况。所以此次我选取A*算法进行Java实现。
抛开理论性的数学概念,通常的A*算法,其实只有两个步骤,一是路径评估,以保证移动的下一个位置离目标最近,评估的结果越精确则寻径的效率也将越高。二是路径查询,也即将评估结果进行反应,而后从新位置再次进行评估指导无路可走为止,以此遍历出可行的路径。
在A*算法的程序实现中,本质上我们只需要关心三点,即起点、终点和地图信息,有了这三项基本数据,我们就可以构建任何情况下的A*实现。
下面我现在提供的是一个A*的Java静态寻径算法实现,逻辑见代码注释。
运行效果如下图(1,1 to 10,13):
(1,1 to 7,9 小房子门口中间)
(1,1 to 6,7 小房子内部)
Node.java
packageorg.test.astar;
importjava.awt.Point;
importjava.util.LinkedList;
/***//**
*<p>
*Title:LoonFramework
*</p>
*<p>
*Description:描述路径节点用类
*</p>
*<p>
*Copyright:Copyright(c)2008
*</p>
*<p>
*Company:LoonFramework
*</p>
*<p>
*License:http://www.apache.org/licenses/LICENSE-2.0
*</p>
*
*@authorchenpeng
*@email:ceponline@yahoo.com.cn
*@version0.1
*/
publicclassNodeimplementsComparable...{
//坐标
publicPoint_pos;
//开始地点数值
publicint_costFromStart;
//目标地点数值
publicint_costToObject;
//父节点
publicNode_parentNode;
privateNode()...{
}
/***//**
*以注入坐标点方式初始化Node
*
*@param_pos
*/
publicNode(Point_pos)...{
this._pos=_pos;
}
/***//**
*返回路径成本
*
*@paramnode
*@return
*/
publicintgetCost(Nodenode)...{
//获得坐标点间差值公式:(x1,y1)-(x2,y2)
intm=node._pos.x-_pos.x;
intn=node._pos.y-_pos.y;
//取两节点间欧几理德距离(直线距离)做为估价值,用以获得成本
return(int)Math.sqrt(m*m+n*n);
}
/***//**
*检查node对象是否和验证对象一致
*/
publicbooleanequals(Objectnode)...{
//验证坐标为判断依据
if(_pos.x==((Node)node)._pos.x&&_pos.y==((Node)node)._pos.y)...{
returntrue;
}
returnfalse;
}
/***//**
*比较两点以获得最小成本对象
*/
publicintcompareTo(Objectnode)...{
inta1=_costFromStart+_costToObject;
inta2=((Node)node)._costFromStart+((Node)node)._costToObject;
if(a1<a2)...{
return-1;
}elseif(a1==a2)...{
return0;
}else...{
return1;
}
}
/***//**
*获得上下左右各点间移动限制区域
*
*@return
*/
publicLinkedListgetLimit()...{
LinkedListlimit=newLinkedList();
intx=_pos.x;
inty=_pos.y;
//上下左右各点间移动区域(对于斜视地图,可以开启注释的偏移部分,此时将评估8个方位)
//上
limit.add(newNode(newPoint(x,y-1)));
//右上
//limit.add(newNode(newPoint(x+1,y-1)));
//右
limit.add(newNode(newPoint(x+1,y)));
//右下
//limit.add(newNode(newPoint(x+1,y+1)));
//下
limit.add(newNode(newPoint(x,y+1)));
//左下
//limit.add(newNode(newPoint(x-1,y+1)));
//左
limit.add(newNode(newPoint(x-1,y)));
//左上
//limit.add(newNode(newPoint(x-1,y-1)));
returnlimit;
}
}
PathFinder.java
packageorg.test.astar;
importjava.awt.Point;
importjava.util.LinkedList;
importjava.util.List;
/***//**
*<p>
*Title:LoonFramework
*</p>
*<p>
*Description:A*寻径处理用类(此类为演示用,并不意味着算法是最佳实现)
*</p>
*<p>
*Copyright:Copyright(c)2008
*</p>
*<p>
*Company:LoonFramework
*</p>
*<p>
*License:http://www.apache.org/licenses/LICENSE-2.0
*</p>
*
*@authorchenpeng
*@email:ceponline@yahoo.com.cn
*@version0.1
*/
publicclassPathFinder...{
//路径优先等级list(此示例中为内部方法)
privateLevelList_levelList;
//已完成路径的list
privateLinkedList_closedList;
//地图描述
privateint[][]_map;
//行走区域限制
privateint[]_limit;
/***//**
*以注入地图的2维数组及限制点描述初始化此类
*
*@param_map
*/
publicPathFinder(int[][]map,int[]limit)...{
_map=map;
_limit=limit;
_levelList=newLevelList();
_closedList=newLinkedList();
}
/***//**
*A*方式寻径,注入开始坐标及目标坐标后运算,返回可行路径的List
*
*@paramstartPos
*@paramobjectPos
*@return
*/
publicListsearchPath(PointstartPos,PointobjectPos)...{
//初始化起始节点与目标节点
NodestartNode=newNode(startPos);
NodeobjectNode=newNode(objectPos);
//设定起始节点参数
startNode._costFromStart=0;
startNode._costToObject=startNode.getCost(objectNode);
startNode._parentNode=null;
//加入运算等级序列
_levelList.add(startNode);
//当运算等级序列中存在数据时,循环处理寻径,直到levelList为空
while(!_levelList.isEmpty())...{
//取出并删除最初的元素
NodefirstNode=(Node)_levelList.removeFirst();
//判定是否和目标node坐标相等
if(firstNode.equals(objectNode))...{
//是的话即可构建出整个行走路线图,运算完毕
returnmakePath(firstNode);
}else...{
//否则
//加入已验证List
_closedList.add(firstNode);
//获得firstNode的移动区域
LinkedList_limit=firstNode.getLimit();
//遍历
for(inti=0;i<_limit.size();i++)...{
//获得相邻节点
NodeneighborNode=(Node)_limit.get(i);
//获得是否满足等级条件
booleanisOpen=_levelList.contains(neighborNode);
//获得是否已行走
booleanisClosed=_closedList.contains(neighborNode);
//判断是否无法通行
booleanisHit=isHit(neighborNode._pos.x,
neighborNode._pos.y);
//当三则判定皆非时
if(!isOpen&&!isClosed&&!isHit)...{
//设定costFromStart
neighborNode._costFromStart=firstNode._costFromStart+1;
//设定costToObject
neighborNode._costToObject=neighborNode
.getCost(objectNode);
//改变neighborNode父节点
neighborNode._parentNode=firstNode;
//加入level
_levelList.add(neighborNode);
}
}
}
}
//清空数据
_levelList.clear();
_closedList.clear();
//当while无法运行时,将返回null
returnnull;
}
/***//**
*判定是否为可通行区域
*
*@paramx
*@paramy
*@return
*/
privatebooleanisHit(intx,inty)...{
for(inti=0;i<_limit.length;i++)...{
if(_map[y][x]==_limit[i])...{
returntrue;
}
}
returnfalse;
}
/***//**
*通过Node制造行走路径
*
*@paramnode
*@return
*/
privateLinkedListmakePath(Nodenode)...{
LinkedListpath=newLinkedList();
//当上级节点存在时
while(node._parentNode!=null)...{
//在第一个元素处添加
path.addFirst(node);
//将node赋值为parentnode
node=node._parentNode;
}
//在第一个元素处添加
path.addFirst(node);
returnpath;
}
privateclassLevelListextendsLinkedList...{
/***//**
*
*/
privatestaticfinallongserialVersionUID=1L;
/***//**
*增加一个node
*
*@paramnode
*/
publicvoidadd(Nodenode)...{
for(inti=0;i<size();i++)...{
if(node.compareTo(get(i))<=0)...{
add(i,node);
return;
}
}
addLast(node);
}
}
}
TestMap.java
packageorg.test.astar;
importjava.awt.Graphics;
importjava.awt.Image;
importorg.loon.framework.game.image.Bitmap;
/***//**
*<p>
*Title:LoonFramework
*</p>
*<p>
*Description:一个简单的地图实现
*</p>
*<p>
*Copyright:Copyright(c)2008
*</p>
*<p>
*Company:LoonFramework
*</p>
*<p>
*License:http://www.apache.org/licenses/LICENSE-2.0
*</p>
*
*@authorchenpeng
*@email:ceponline@yahoo.com.cn
*@version0.1
*/
publicclassTestMap...{
finalstaticprivateintCS=32;
//地图描述
finalstaticpublicint[][]MAP=...{
...{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
...{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
...{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
...{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
...{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
...{1,0,0,0,0,1,1,1,1,1,0,0,0,0,1},
...{1,0,0,0,0,1,0,0,0,1,0,0,0,0,1},
...{1,0,0,0,0,1,0,0,0,1,0,0,0,0,1},
...{1,0,0,0,0,1,0,0,0,1,0,0,0,0,1},
...{1,0,0,0,0,1,1,0,1,1,0,0,0,0,1},
...{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
...{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
...{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
...{1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
...{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
//无法移动区域
finalstaticpublicint[]HIT=...{1};
//设定背景方格默认行数
finalstaticprivateintROW=15;
//设定背景方格默认列数
finalstaticprivateintCOL=15;
privateImagefloorImage;
privateImagewallImage;
publicTestMap()...{
floorImage=newBitmap("./astart/floor.gif").getImage();
wallImage=newBitmap("./astart/wall.gif").getImage();
}
publicvoiddraw(Graphicsg)...{
for(inti=0;i<ROW;i++)...{
for(intj=0;j<COL;j++)...{
switch(MAP[i][j])...{
case0:
g.drawImage(floorImage,j*CS,i*CS,null);
break;
case1:
g.drawImage(wallImage,j*CS,i*CS,null);
break;
}
}
}
}
}
Main.java
packageorg.test.astar;
importjava.awt.Color;
importjava.awt.Frame;
importjava.awt.Graphics;
importjava.awt.Image;
importjava.awt.Panel;
importjava.awt.Point;
importjava.awt.event.WindowAdapter;
importjava.awt.event.WindowEvent;
importjava.util.List;
importorg.loon.framework.game.image.Bitmap;
/***//**
*<p>
*Title:LoonFramework
*</p>
*<p>
*Description:Java的A*寻径实现
*</p>
*<p>
*Copyright:Copyright(c)2008
*</p>
*<p>
*Company:LoonFramework
*</p>
*<p>
*License:http://www.apache.org/licenses/LICENSE-2.0
*</p>
*
*@authorchenpeng
*@email:ceponline@yahoo.com.cn
*@version0.1
*/
publicclassMainextendsPanel...{
/***//**
*
*/
finalstaticprivatelongserialVersionUID=1L;
finalstaticprivateintWIDTH=480;
finalstaticprivateintHEIGHT=480;
finalstaticprivateintCS=32;
privateTestMapmap;
privatePathFinderastar;
//起始坐标1,1
privatestaticPointSTART_POS=newPoint(1,1);
//目的坐标10,13
privatestaticPointOBJECT_POS=newPoint(10,13);
privateImagescreen;
privateGraphicsgraphics;
privateListpath;
publicMain()...{
setSize(WIDTH,HEIGHT);
setFocusable(true);
screen=newBitmap(WIDTH,HEIGHT).getImage();
graphics=screen.getGraphics();
map=newTestMap();
//注入地图描述及障碍物描述
astar=newPathFinder(TestMap.MAP,TestMap.HIT);
//searchPath将获得两点间移动路径坐标的List集合
//在实际应用中,利用Thread分步处理List中坐标即可实现自动行走
path=astar.searchPath(START_POS,OBJECT_POS);
}
publicvoidupdate(Graphicsg)...{
paint(g);
}
publicvoidpaint(Graphicsg)...{
//绘制地图
map.draw(graphics);
graphics.setColor(Color.RED);
graphics.fillRect(START_POS.x*CS,START_POS.y*CS,CS,CS);
graphics.setColor(Color.BLUE);
graphics.fillRect(OBJECT_POS.x*CS,OBJECT_POS.y*CS,CS,CS);
//绘制路径
if(path!=null)...{
graphics.setColor(Color.YELLOW);
//遍历坐标,并一一描绘
for(inti=0;i<path.size();i++)...{
Nodenode=(Node)path.get(i);
Pointpos=node._pos;
//描绘边框
graphics.fillRect(pos.x*CS+7,pos.y*CS+7,CS-14,
CS-14);
}
}
g.drawImage(screen,0,0,this);
}
publicstaticvoidmain(String[]args)...{
Frameframe=newFrame();
frame.setTitle("Java的A*寻径实现");
frame.setSize(WIDTH,HEIGHT+20);
frame.setResizable(false);
frame.setLocationRelativeTo(null);
frame.add(newMain());
frame.setVisible(true);
frame.addWindowListener(newWindowAdapter()...{
publicvoidwindowClosing(WindowEvente)...{
System.exit(0);
}
});
}
}
分享到:
相关推荐
利用JAVA语言编程实现的经典A*算法,复制到eclipse即可运行
A*算法 A star 算法(matlab)版本,可以直接使用,包含路径优化。直接下载即可运行。A*算法 A star 算法(matlab)版本,可以直接使用,包含路径优化。直接下载即可运行。
Unity 算法 之 A星(A Star/A*)寻路算法实现和封装,并带动态演示Demo Demo 使用操作说明 1、按空格可以刷线地图,更新地图的障碍物位置(动态随机设置) 2、鼠标左键设置开始点位置 3、鼠标右键设置目标点位置...
A star PathfindingProject_4.2.8自动寻径
A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快。 本实例主要针对自动驾驶技术当中A*算法的应用现象,...
a* (A star ) 算法 VB 版(源文件) 有关详情到我的博客看吧. http://fdlove.139.com
利用启发式搜索中的A*算法解决八数码问题,比传统的宽度优先等搜索算法具有更高的效率
非常好的A*算法自己写的,里面基本每条代码都有注释,方便基础差的同学观看,另外附带了调试好的exe程序,下载就可执行!!你值得拥有,学了他,等同于一起学了特斯拉算法。请尊重版权!!1
“A*(A-Star)算法,一种静态路网中求解最短路径最有效的直接搜索方法。Matlab的实现
这是用D*算法实现机器人路径规划的JAVA程序,适用于动态路径环境下,可以在未知环境中快速的找到可行路线
A*算法,A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快。该资源是用WinForm实现的,可以更直接明了的...
基于SpringBoot框架,对外接口需要POST二位矩阵的横纵坐标数量、起始点坐标、障碍点坐标。
参数A * A *(A Star)的JVM(Scala / Java)实现,在可能的状态和转换中是参数化的。 标准实现是在2D地图上使用一组固定的导航命令定义的。 相反,此实现是所使用的“映射”结构和“命令”的完全参数化(不知道)。...
机器人全局路径规划,用于移动机器人导航,设定目标点到起始点的最优路径规划
用c语言实现 较为简单的a* (a star/a 星) 算法
A*算法,A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快。代码使用c#语言实现,欢迎下载
A star.docx A*算法
A-Star-Pathfinding-for-Platformers, 如何适应基于 2D 网格的A*定位算法 ###Tuts+ 教程:如何将A*查找调整为基于 2D 个网格的Platformer ####Instructor: Daniel Branicki本系列教程将解释如何通过考虑重力限制垂直...
Unity u3d A* A Star Pathfinding Project Pro, Unity A星寻路插件
附件中A_star.py为算法实现,有两个txt文件作为测试样例,mediumMaze是一个封闭的迷宫,openmaze是一个开放的迷宫