在上一篇博客中,我们一起学习了随机迷宫算法,在本篇博客中,我们将一起了解一下寻路算法中常用的A*算法。
通常情况下,迷宫寻路算法可以使用深度优先或者广度优先算法,但是由于效率的原因,不会直接使用这些算法,在路径搜索算法中最常见的就是A*寻路算法。使用A*算法的魅力之处在于它不仅能找到地图中从A到B的一条路径,还能保证找到的是一条最短路径,它是一种常见的启发式搜索算法,类似于Dijkstra算法一样的最短路径查找算法,很多游戏应用中的路径搜索基本都是采用这种算法或者是A*算法的变种。
下面我们来了解一下A*算法相关的理论知识:
如图,我们需要在迷宫中找到A点到B点的一条最短的可以通过的路径,A和B直接被一面墙堵住了。在上一篇博客中我们说到了,地图是有二维数组组成的,墙表示不能通过的地方,用1表示,A*算法所要做的就是从A找到一条最短的通向B的路径。当然,不能从墙上飞过去,也不能瞬移到B。只能每次移动一个格子,一步一步地移动到B目标位置。问题在于,每次移动一格的时候,有上下左右四个方向,这里我们限制物体斜向移动,如何选择下一个移动方向呢?按照我们的想法,不就是找一条离目标最近的路吗?那我们可以在这四个方向中,找一个最接近目标点的位置,当然,还要考虑障碍因素,基于这个思想,A*算法采用了以下的搜索步骤来实现:
1.首先把起始位置点加入到一个称为“open List”的列表,在寻路的过程中,目前,我们可以认为open List这个列表会存放许多待测试的点,这些点是通往目标点的关键,以后会逐渐往里面添加更多的测试点,同时,为了效率考虑,通常这个列表是个已经排序的列表。
2.如果open List列表不为空,则重复以下工作:
(1)找出open List中通往目标点代价最小的点作为当前点;
(2)把当前点放入一个称为close List的列表;
(3)对当前点周围的4个点每个进行处理(这里是限制了斜向的移动),如果该点是可以通过并且该点不在close List列表中,则处理如下;
(4)如果该点正好是目标点,则把当前点作为该点的父节点,并退出循环,设置已经找到路径标记;
(5)如果该点也不在open List中,则计算该节点到目标节点的代价,把当前点作为该点的父节点,并把该节点添加到open List中;
(6)如果该点已经在open List中了,则比较该点和当前点通往目标点的代价,如果当前点的代价更小,则把当前点作为该点的父节点,同时,重新计算该点通往目标点的代价,并把open List重新排序;
3.完成以上循环后,如果已经找到路径,则从目标点开始,依次查找每个节点的父节点,直到找到开始点,这样就形成了一条路径。
以上,就是A*算法的全部步骤,按照这个步骤,就可以得到一条正确的路径。这里有一个关键的地方,就是如何计算每个点通往目标点的代价,之所以称为A*算法为启发式搜索,就是因为通过评估这个代价值来搜索最近的路径,对于任意一个点的代价值,在A*算法中通常使用下列的公式计算:
代价F=G+H
在这里,F表示通往目标点的代价,G表示从起始点移动到该点的距离,H则表示从该点到目标点的距离,比如图中,可以看到小狗的附近格子的代价值,其中左上角的数字代表F值,左下角的数字代表G值,右下角的数字代表H值。拿小狗上方的格子来举例,G=1,表示从小狗的位置到该点的距离为1个格子,H=6,表示从小狗到骨头的距离是6个格子,则F=G+H=7。在此处,距离的算法是采用曼哈顿距离,它计算从当前格子到目的格子之间水平和垂直的方格的数量总和,例如在平面上,坐标(x1,y1)的点和坐标(x2,y2)的点的曼哈顿距离为:
|x1-x2|+|y1-y2|
当然,距离的算法也可以采用其他的方法,实际在游戏中,这个移动的代价除了要考虑距离因素外,还要考虑当前格子的游戏属性。比如有的格子表示水路、草地、陆地,这些有可能影响人物移动的速度,实际计算的时候还要把这些考虑在内。
另一个需要注意的就是,在计算这个距离的时候是毋须考虑障碍因素的,因为在以上A*算法步骤中会剔除掉障碍。
这样,按照前面所说的A*算法的步骤,第一次循环open List的时候,把A点作为当前点,同时把A周围的四个点放入到open List中。第二次循环的时候把A右边的点作为当前点,该点的父节点就是A,这是处理当前点的时候,只需要把当前点的上下两个点放入open List中,因为左边的A已经在close List中,而右边的是墙,所以直接被忽略。
A*的算法具体代码如下:
1 //地图工具
2 var _MapUtil = win.MapUtil =
3 {
4 //定义点对象
5 Point:function(x,y)
6 {
7 this.x = x;
8 this.y = y;
9 this.parent = null;
10 this.f = 0;
11 this.g = 0;
12 this.h=0;
13 //当前点状态,0:表示在openlist 1:表示closelist,-1表示还没处理
14 this.state=-1;
15 //flag表明该点是否可通过
16 this.flag = 0;
17 },
18 //产生随机迷宫
19 primMaze:function(r,c)
20 {
21 //初始化数组
22 function init(r,c)
23 {
24 var a = new Array(2*r+1);
25 //全部置1
26 for(var i=0,len=a.length;i<len;i++)
27 {
28 var cols = 2*c+1;
29 a[i]= new Array(cols);
30 ArrayUtil.fillWith(a[i],1);
31 }
32 //中间格子为0
33 for(var i=0;i<r;i++)
34 for(var j=0;j<c;j++)
35 {
36 a[2*i+1][2*j+1] = 0;
37 }
38 return a;
39 }
40 //处理数组,产生最终的数组
41 function process(arr)
42 {
43 //acc存放已访问队列,noacc存放没有访问队列
44 var acc = [],noacc = [];
45 var r = arr.length>>1,c=arr[0].length>>1;
46 var count = r*c;
47 for(var i=0;i<count;i++){noacc[i]=0;}
48 //定义空单元上下左右偏移
49 var offs=[-c,c,-1,1],offR=[-1,1,0,0],offC=[0,0,-1,1];
50 //随机从noacc取出一个位置
51 var pos = MathUtil.randInt(count);
52 noacc[pos]=1;
53 acc.push(pos);
54 while(acc.length<count)
55 {
56 var ls = -1,offPos = -1;
57 offPos = -1;
58 //找出pos位置在二维数组中的坐标
59 var pr = pos/c|0,pc=pos%c,co=0,o=0;
60 //随机取上下左右四个单元
61 while(++co<5)
62 {
63 o = MathUtil.randInt(0,5);
64 ls =offs[o]+pos;
65 var tpr = pr+offR[o];
66 var tpc = pc+offC[o];
67 if(tpr>=0&&tpc>=0&&tpr<=r-1&&tpc<=c-1&&noacc[ls]==0){ offPos = o;break;}
68 }
69 if(offPos<0)
70 {
71
72 pos = acc[MathUtil.randInt(acc.length)];
73 }
74 else
75 {
76 pr = 2*pr+1;
77 pc = 2*pc+1;
78 //相邻空单元中间的位置置0
79 arr[pr+offR[offPos]][pc+offC[offPos]]=0;
80 pos = ls;
81 noacc[pos] = 1;
82 acc.push(pos);
83 }
84 }
85 }
86 var a = init(r,c);
87 process(a);
88 return a;
89 },
90 //把普通二维数组(全部由1,0表示)的转换成a*所需要的点数组
91 convertArrToAS:function(arr)
92 {
93 var r = arr.length,c=arr[0].length;
94 var a = new Array(r);
95 for(var i=0;i<r;i++)
96 {
97 a[i] = new Array(c);
98 for(var j=0;j<c;j++)
99 {
100 var pos = new MapUtil.Point(i,j);
101 pos.flag = arr[i][j];
102 a[i][j]=pos;
103 }
104 }
105 return a;
106 },
107 //A*算法,pathArr表示最后返回的路径
108 findPathA:function(pathArr,start,end,row,col)
109 {
110 //添加数据到排序数组中
111 function addArrSort(descSortedArr,element,compare)
112 {
113 var left = 0;
114 var right = descSortedArr.length-1;
115 var idx = -1;
116 var mid = (left+right)>>1;
117 while(left<=right)
118 {
119 var mid = (left+right)>>1;
120 if(compare(descSortedArr[mid],element)==1)
121 {
122 left = mid+1;
123 }
124 else if(compare(descSortedArr[mid],element)==-1)
125 {
126 right = mid-1;
127 }
128 else
129 {
130 break;
131 }
132 }
133 for(var i = descSortedArr.length-1;i>=left;i--)
134 {
135 descSortedArr[i+1] = descSortedArr[i];
136 }
137 descSortedArr[left] = element;
138 return idx;
139 }
140 //判断两个点是否相同
141 function pEqual(p1,p2)
142 {
143 return p1.x==p2.x&&p1.y==p2.y;
144 }
145 //获取两个点距离,采用曼哈顿方法
146 function posDist(pos,pos1)
147 {
148 return (Math.abs(pos1.x-pos.x)+Math.abs(pos1.y-pos.y));
149 }
150 function between(val,min,max)
151 {
152 return (val>=min&&val<=max)
153 }
154 //比较两个点f值大小
155 function compPointF(pt1,pt2)
156 {
157 return pt1.f-pt2.f;
158 }
159 //处理当前节点
160 function processCurrpoint(arr,openList,row,col,currPoint,destPoint)
161 {
162 //get up,down,left,right direct
163 var ltx = currPoint.x-1;
164 var lty = currPoint.y-1;
165 for(var i=0;i<3;i++)
166 for(var j=0;j<3;j++)
167 {
168 var cx = ltx+i;
169 var cy = lty+j;
170 if((cx==currPoint.x||cy==currPoint.y)&&between(ltx,0,row-1)&&between(lty,0,col-1))
171 {
172 var tp = arr[cx][cy];
173 if(tp.flag == 0 && tp.state!=1)
174 {
175 if(pEqual(tp,destPoint))
176 {
177 tp.parent = currPoint;
178 return true;
179 }
180 if(tp.state == -1)
181 {
182 tp.parent = currPoint;
183 tp.g= 1+currPoint.g;
184 tp.h= posDist(tp,destPoint);
185 tp.f = tp.h+tp.f;
186 tp.state = 0
187 addArrSort(openList,tp,compPointF);
188 }
189 else
190 {
191 var g = 1+currPoint.g
192 if(g<tp.g)
193 {
194 tp.parent = currPoint;
195 tp.g = g;
196 tp.f = tp.g+tp.h;
197 openList.quickSort(compPointF);
198 }
199 }
200 }
201 }
202 }
203 return false;
204 }
205 //定义openList
206 var openList = [];
207 //定义closeList
208 var closeList = [];
209 start = pathArr[start[0]][start[1]];
210 end = pathArr[end[0]][end[1]];
211 //添加开始节点到openList;
212 addArrSort(openList,start,compPointF);
213 var finded = false;
214 var tcount = 0;
215 while((openList.length>0))
216 {
217 var currPoint = openList.pop();
218 currPoint.state = 1;
219 closeList.push(currPoint);
220 finded = processCurrpoint(pathArr,openList,row,col,currPoint,end);
221 if(finded)
222 {
223 break;
224 }
225 }
226 if(finded)
227 {
228 var farr = [];
229 var tp = end.parent;
230 farr.push(end);
231 while(tp!=null)
232 {
233 farr.push(tp);
234 tp = tp.parent;
235 }
236 return farr;
237 }
238 else
239 {
240 return null;
241 }
242 }
243 }
运用上面的代码,我们可以实现一个简单的迷宫寻路DEMO,用户在迷宫中点击任意的地点,蓝色的球体就会自动寻路移动到该点,如图:
此DEMO的源码地址
A*算法不仅可以应用在游戏当中,同样也可以应用到其他领域,比如车辆定位和行车自动导航,当然,这得需要另外的地理信息数据支持。
作者:马三小伙儿 出处:http://www.cnblogs.com/msxh/p/5674417.html 请尊重别人的劳动成果,让分享成为一种美德,欢迎转载。另外,文章在表述和代码方面如有不妥之处,欢迎批评指正。留下你的脚印,欢迎评论!