一个高效的a *寻路算法(八方向)

谁践踏了优雅 2022-06-17 01:53 316阅读 0赞

http://blog.csdn.net/onafioo/article/details/41089579

**这种写法比较垃圾,表现在每次搜索一个点要遍历整个地图那么大的数组,如果地图为256 \* 256,每次搜索都要执行65535次,如果遍历多个点就是n \* 65535,速度上实在是太垃圾了**

**简单说下思路,以后补充[算法][Link 1]**

优化重点在表在开放和关闭表的遍历上,这两个地方优化后,斯达会大量提速

亲密只用来查询所以可以用哈希这样就避免了遍历

打开首先用来查询是否有相同的点如果有会比较替换F值,其次用来遍历查询最小点,如果用优先级队列加哈希可以减少2次遍历,但是相同点替换F值和父节点就没办法了,只能遍历一次(但一般找到该找的点就可以休息,不需要完整遍历)

如果用[Java][]c\#,由于有垃圾回收机制,为了避免产生过多垃圾降低垃圾回收压力,可以用空闲对象池来避免频繁创建节点,控制内存泄露

原作者是[http://www.codefans.net][http_www.codefans.net]的贾罗德

之所以说这个a \*算法高效,是因为它的开放列表和close-list使用的完全是静态数组,这样就极大地降低了入栈出栈的负担。这个代码非常值得推荐。

用法很简单:

结果route\_pt\[\]=零;

/ / result\_pt是一个简单类,它只有两个成员变量:int x和int y。

/ /参数说明:地图是一个二维数组,具体见程序注释

AStarRoute2 asr = new AStarRoute2(地图,start\_x,start\_y、end\_x end\_y);

尝试\{

结果= asr.getResult();

\}捕捉(例外的前女友)\{

如果结果! =零那么寻路就成功了。

注意:最后获得的路径,是从终点指向起点的。您可以把两组参数倒过来传,以获得正常方向的返回值。

本人对贾罗德的代码略作修改,主要是用循环取代了递归,避免栈溢出。

这是本人修改后的八方向寻路算法。如下:

进口java.util.ArrayList;

公开课AStarRoute2 \{

私人int\[\]\[\]地图;/ /地图矩阵,0表示能通过,1表示不能通过

私人int map\_w;  / /地图宽度

私人int map\_h;  / /地图高度

私人int start\_x;/ /起点坐标X

私人int start\_y;/ /起点坐标Y

私人int goal\_x;/ /终点坐标X

私人int goal\_y;/ /终点坐标Y

私人布尔closeList\[\]\[\];          / /关闭列表

公共int openList\[\]\[\]\[\];            / /打开列表

私人int openListLength;

私有静态最终int存在= 1;

私有静态最终int NOT\_EXIST = 0;

私有静态最终int ISEXIST = 0;

私有静态最终int费用= 1;  / /自身的代价

私有静态最终int距离= 2;  / /距离的代价

私有静态最终int成本= 3;      / /消耗的总代价

私有静态最终int FATHER\_DIR = 4;/ /父节点的方向

公共静态最终int DIR\_NULL = 0;

公共静态最终int DIR\_DOWN = 1;  / /方向:下

公共静态最终int DIR\_UP = 2;    / /方向:上

公共静态最终int DIR\_LEFT = 3;  / /方向:左

公共静态最终int DIR\_RIGHT = 4;  / /方向右

公共静态最终int DIR\_UP\_LEFT = 5;

公共静态最终int DIR\_UP\_RIGHT = 6;

公共静态最终int DIR\_DOWN\_LEFT = 7;

公共静态最终int DIR\_DOWN\_RIGHT = 8;

私人int astar\_counter;              / /算法嵌套深度

私人布尔isFound;                / /是否找到路径

公共AStarRoute2(int\[\]\[\]mx,int sx,int sy,int gx,int gy)\{

start\_x = sx;

start\_y = sy;

goal\_x= gx;

goal\_y= gy;

地图  = mx;

map\_w= mx.length;

map\_h= mx\[0\]. length;

astar\_counter = 5000;

initCloseList();

initOpenList(goal\_x goal\_y);

/ /得到地图上这一点的消耗值

私人int getMapExpense(int x,int y,int dir)

如果(dir < 5)\{

返回10;

其他\} \{

返回14;

/ /得到距离的消耗值

私人int getDistance(int x,int y,int,int)等等)

返回10 \*(数学。 abs(x - ex)+数学。 abs(y -迪士尼));

/ /得到给定坐标格子此时的总消耗值

私人int getCost(int x,int y)

返回openList\[x\]\[y\]\[费用\];

/ /开始寻路

公共空间searchPath()

addOpenList(start\_x start\_y);

斯达(start\_x start\_y);

/ /寻路

私人空间斯达(int x,int y)

/ /控制算法深度

(int t = 0;t < astar\_counter;t + +)\{

如果(((x = = goal\_x)& &(y = = goal\_y)))\{

isFound = true;

返回;

else if((openListLength = = 0))\{

isFound = false;

返回;

removeOpenList(x,y);

addCloseList(x,y);

/ /该点周围能够行走的点

addNewOpenList(x,y,x,y + 1,DIR\_UP);

addNewOpenList(x,y,x,y - 1,DIR\_DOWN);

addNewOpenList(x,y,x - 1,y,DIR\_RIGHT);

addNewOpenList(x,y,x + 1,y,DIR\_LEFT);

addNewOpenList(x,y,x + 1,y + 1,DIR\_UP\_LEFT);

addNewOpenList(x,y,x - 1,y + 1,DIR\_UP\_RIGHT);

addNewOpenList(x,y,x + 1,y - 1,DIR\_DOWN\_LEFT);

addNewOpenList(x,y,x - 1,y - 1,DIR\_DOWN\_RIGHT);

/ /找到估值最小的点,进行下一轮算法

int成本= 0 x7fffffff;

for(int i = 0;我< map\_w;+ +)\{

for(int j = 0;< map\_h;j + +)\{

如果(openList\[我\]\[j\]\[ISEXIST\]= =存在)\{

如果(成本> getCost(i,j))\{

成本= getCost(i,j);

x =我;

y = j;

/ /算法超深

isFound = false;

返回;

/ /添加一个新的节点

私人空间addNewOpenList(int x,int y,int newX,int newY,int dir)

如果(isCanPass(newX newY))\{

如果(openList\[newX\]\[newY\]\[ISEXIST\]= =存在)\{

如果(openList\[x\]\[y\]\[费用\]+ getMapExpense(newX、newY dir)<

openList\[newX\]\[newY\]\[费用\])\{

setFatherDir(newX newY dir);

setCost(newX newY,x,y,dir);

其他\} \{

addOpenList(newX newY);

setFatherDir(newX newY dir);

setCost(newX newY,x,y,dir);

/ /设置消耗值

私人空间setCost(int x,int y,int,int,int dir)

openList\[x\]\[y\]\[费用\]= openList\[例\]\[是\]\[费用\]  \+ getMapExpense(x,y,dir);

openList\[x\]\[y\]\[距离\]= getDistance(x,y,交货哦,是吧);

openList\[x\]\[y\]\[费用\]= openList\[x\]\[y\]\[费用\]  \+ openList\[x\]\[y\](距离);

/ /设置父节点方向

私人空间setFatherDir(int x,int y,int dir)

openList\[x\]\[y\]\[FATHER\_DIR\]= dir;

/ /判断一个点是否可以通过

私人布尔isCanPass(int x,int y)

/ /超出边界

如果(x < 0 | | x > = map\_w | | y < 0 | | y > = map\_h)\{

返回错误;

/ /地图不通

如果(map\[x\]\[y\]! = 0)\{

返回错误;

/ /在关闭列表中

如果(isInCloseList(x,y))\{

返回错误;

返回true;

/ /移除打开列表的一个元素

私人空间removeOpenList(int x,int y)

如果(openList\[x\]\[y\]\[ISEXIST\]= =存在)\{

openList\[x\]\[y\]\[ISEXIST\]= NOT\_EXIST;

openListLength——;

/ /判断一点是否在关闭列表中

私人布尔isInCloseList(int x,int y)

返回closeList\[x\]\[y\];

/ /添加关闭列表

私人空间addCloseList(int x,int y)

closeList\[x\]\[y\]= true;

/ /添加打开列表

私人空间addOpenList(int x,int y)

如果(openList\[x\]\[y\]\[ISEXIST\]= = NOT\_EXIST)\{

openList\[x\]\[y\]\[ISEXIST\]=存在;

openListLength + +;

/ /初始化关闭列表

私人空间initCloseList()

closeList = new布尔\[map\_w\]\[map\_h\];

for(int i = 0;我< map\_w;+ +)\{

for(int j = 0;< map\_h;j + +)\{

closeList\[我\]\[j\]= false;

/ /初始化打开列表

私人空间initOpenList(int,int)等等)

openList= new int\[map\_w\]\[map\_h\]\[5\];

for(int i = 0;我< map\_w;+ +)\{

for(int j = 0;< map\_h;j + +)\{

openList\[我\]\[j\]\[ISEXIST\]= NOT\_EXIST;

openList\[我\]\[j\]\[费用\]= getMapExpense(i,j,DIR\_NULL);

openList\[我\]\[j\]\[距离\]= getDistance(i,j,交货哦,是吧);

openList\[我\]\[j\]\[费用\]= openList\[我\]\[j\]\[费用\]  \+ openList\[我\]\[j\](距离);

openList\[我\]\[j\]\[FATHER\_DIR\]= DIR\_NULL;

openListLength = 0;

/ /获得寻路结果

公共route\_pt\[\]getResult()\{

route\_pt\[\]的结果;

ArrayList < route\_pt >路线;

searchPath();

如果(! isFound)\{

返回null;

路线= new ArrayList < route\_pt >();

/ / openList是从目标点向起始点倒推的。

int第九= goal\_x;

int iY = goal\_y;

而(第九! = start\_x | | iY ! = start\_y))\{

路线。 添加(新route\_pt(第九,iY));

开关(openList\[iX\]\[iY\]\[FATHER\_DIR\])\{

案例DIR\_DOWN:        iY + +;          打破;

案例DIR\_UP:          iY——;          打破;

案例DIR\_LEFT:        第九,;          打破;

案例DIR\_RIGHT:      第九+ +;          打破;

案例DIR\_UP\_LEFT:    第九,;iY——;  打破;

案例DIR\_UP\_RIGHT:    第九+ +;iY——;  打破;

案例DIR\_DOWN\_LEFT:  第九,;iY + +;  打破;

案例DIR\_DOWN\_RIGHT:  第九+ +;iY + +;  打破;

int大小= route.size();

结果= new route\_pt(大小);

for(int i = 0;我+ +)\{ <大小;

结果新route\_pt\[我\]=((route\_pt)route.get(我));

返回结果;

[Link 1]: http://lib.csdn.net/base/datastructure
[Java]: http://lib.csdn.net/base/javase
[http_www.codefans.net]: http://www.codefans.net/

一个高效的a *寻路算法(八方向)

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 A*寻路算法详细解读

相关 A*寻路算法(带动画)

相关 A*寻路算法入门(五)

相关 A*寻路算法浅析

相关一个高效的a *寻路算法(八方向)

相关一种高效的寻路算法 - B*寻路算法

相关记录一个下午撸的A星寻路算法

相关一个高效的A-star寻路算法（四方向）

相关一个高效的A-star寻路算法（八方向）

相关 A*寻路算法-C#版