Astar经典算法Word文件下载.docx
- 文档编号:7177363
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:13
- 大小:43.76KB
Astar经典算法Word文件下载.docx
《Astar经典算法Word文件下载.docx》由会员分享,可在线阅读,更多相关《Astar经典算法Word文件下载.docx(13页珍藏版)》请在冰点文库上搜索。
∙首先派出编号为0的“预备士兵”侦查起点,然后升其为“开启士兵”,列入“开启士兵名录”。
∙检查“开启士兵名录”,找出F值最低的“开启士兵”(只有一名人员,当然是0号),发出“行动令牌”派其执行探索任务。
∙0号“开启士兵”接到“行动令牌”,晋为“预备将军”,探索周围格子。
∙向周围8个格子分别派出编号为1到8的“预备士兵”,成为这八名“预备士兵”的“父将”。
∙八名“预备士兵”到达方格后计算G值和F值,报告0号“父将”,晋为“开启士兵”。
∙0号“预备将军”收到八名“开启士兵”的报告,归还“行动令牌”,晋为“关闭将军”。
∙元帅收回“行动令牌”,将0号加入“关闭将军名录”,1到8号加入“开启士兵名录”。
此过程结果如下(方格右上角数字是人员编号,左下角是G,右下角是H,左上角是F):
第一轮探索任务完成,元帅开始检查“开启士兵名录”。
此时名录中有8名人员,其中1号F值最低为40(起点右移一格,G值为10,到终点平移3格,H值为30,F=G+H=40),向其发出“行动令牌”。
∙1号“开启士兵”接到“行动令牌”,晋为“预备将军”,探索周围格子。
∙周围8个格子中有3格障碍,跳过。
一格是“关闭将军”,跳过。
其余四格是“开启士兵”,检查如果从该位置过去G值是否更低。
以2号为例,如果从1号过去G值为10+14=24(1号的G值加上1号到2号的步数),而2号原来的G值是10,不做处理(如果此时发现新的G值更低,则更新2号的G值,并改2号的“父将”为1号)。
其他类推。
∙1号检测完周围的方格,不需做任何处理,归还“行动令牌”,晋为“关闭将军”。
∙元帅收回“行动令牌”,将1号加入“关闭将军名录”。
此过程结果如下:
第二轮结束,元帅再次检查“开启士兵名录”。
此时还有7名“开启士兵”,5号和8号的F值都为最低的54,选择不同寻路的结果也将不同。
元帅选择了最后加入的8号“开启士兵”发出“行动令牌”,过程同上,不赘述,结果如下:
重复这个过程直到某位“关闭将军”站到了终点上(或者“开启士兵”探测到了终点,这样更快捷,但某些情况找到的路径不够短),亦即找到了路径;
或是“开启士兵名录”已空,无法到达终点。
下面整理一下全过程并翻译成“标准语言”,首先是各名词:
∙“开启士兵名录”-开启列表-openlist
∙“关闭将军名录”-关闭列表-closedlist
∙“父将”-父节点-parentsquare
∙F-路径评分
∙G-起点到该点移动损耗
∙H-该点到终点(启发式)预计移动损耗
寻路过程:
∙1,将起点放入开启列表
∙2,寻找开放列表中F值最低的节点作为当前节点
∙3,将当前节节点切换到关闭列表
∙4,如果当前节点是终点则路径被找到,寻路结束
∙5,对于其周围8个节点:
o如果不可通过或已在关闭列表,跳过,否则:
o如果已在开放列表中,检查新路径是否更好。
如果新G值更低则更新其G值并改当前节点为其父节点,否则跳过
o如果是可通过区域则放入开启列表,计算这一点的F、G、H值,并记当前节点为其父节点
∙6,如果开启列表空了,则无法到达目标,路径不存在。
否则回到2
再翻译成“编程语言”?
请看第三部分,锋芒毕露-AS3代码和示例。
如虎添翼-使用二叉堆优化
如何让A*寻路更快?
元帅三顾茅庐,请来南阳二叉堆先生帮忙优化寻找“开启士兵名录”中最低F值的过程,将寻路速度提高了2到3倍,而且越大的地图效果越明显。
下面隆重介绍二叉堆先生:
下图是一个二叉堆的例子,形式上看,它从顶点开始,每个节点有两个子节点,每个子节点又各自有自己的两个子节点;
数值上看,每个节点的两个子节点都比它大或和它相等。
在二叉堆里我们要求:
∙最小的元素在顶端
∙每个元素都比它的父节点大,或者和父节点相等。
只要满足这两个条件,其他的元素怎么排都行。
如上面的例子,最小的元素10在最顶端,第二小的元素20在10的下面,但是第三小的元素24在20的下面,也就是第三层,更大的30反而在第二层。
这样一“堆”东西我们在程序中怎么用呢?
幸运的是,二叉堆可以用一个简单的一维数组来存储,如下图所示。
假设一个元素的位置是n(第一个元素的位置为1,而不是通常数组的第一个索引0),那么它两个子节点分别是n×
2和n×
2+1,父节点是n除以2取整。
比如第3个元素(例中是20)的两个子节点位置是6和7,父节点位置是1。
对于二叉堆我们通常有三种操作:
添加、删除和修改元素:
∙添加元素
首先把要添加的元素加到数组的末尾,然后和它的父节点(位置为当前位置除以2取整,比如第4个元素的父节点位置是2,第7个元素的父节点位置是3)比较,如果新元素比父节点元素小则交换这两个元素,然后再和新位置的父节点比较,直到它的父节点不再比它大,或者已经到达顶端,及第1的位置。
∙删除元素
删除元素的过程类似,只不过添加元素是“向上冒”,而删除元素是“向下沉”:
删除位置1的元素,把最后一个元素移到最前面,然后和它的两个子节点比较,如果较小的子节点比它小就将它们交换,直到两个子节点都比它大。
∙修改元素
和添加元素完全一样的“向上冒”过程,只是要注意被修改的元素在二叉堆中的位置。
可以看出,使用二叉堆只需很少的几步就可以完成排序,很大程度上提高了寻路速度。
关于二叉堆先生需要了解的就是这么多了,下面来看看他怎么帮助元帅工作:
∙每次派出的“预备士兵”都会获得一个唯一的编号(ID),一直到寻路结束,它所有的数据包括位置、F值、G值、“父将”编号都将按这个ID存储。
∙每次有新的“开启士兵”加入,二叉堆先生将它的编号加入“开启士兵名录”并重新排序,使F值最低的ID始终排在最前面
∙当有“开启士兵”晋为“关闭将军”,删除“开启士兵名录”的第一个元素并重新排序
∙当某个“开启士兵”的F值被修改,更新其数据并重新排序
注意,“开启士兵名录”里存的只是人员的编号,数据全都另外存储。
不太明白?
没关系,元帅将在第三部分来次真刀实枪的大演兵。
锋芒毕露-AS3代码和示例
地形数据不属于A*寻路的范围,这里定义一个IMapTileModel接口,由其它(模型)类来实现地图通路的判断。
其它比如寻路超时的判断这里也不介绍,具体参考AStar类及其测试代码。
这里只介绍三部分主要内容:
∙数据存储
∙寻路过程
∙列表排序
数据存储
首先看看三个关键变量:
privatevarm_openList:
Array;
//开放列表,存放节点ID
privatevarm_openCount:
int;
//当前开放列表中节点数量
privatevarm_openId:
//节点加入开放列表时分配的唯一ID(从0开始)
开放列表m_openList是个二叉堆(一维数组),F值最小的节点始终排在最前。
为加快排序,开放列表中只存放节点ID,其它数据放在各自的一维数组中:
privatevarm_xList:
//节点x坐标
privatevarm_yList:
//节点y坐标
privatevarm_pathScoreList:
//节点路径评分F值
privatevarm_movementCostList:
//(从起点移动到)节点的移动耗费G值
privatevarm_fatherList:
//节点的父节点(ID)
这些数据列表都以节点ID为索引顺序存储。
看看代码如何工作:
//每次取出开放列表最前面的ID
currId=this.m_openList[0];
//读取当前节点坐标
currNoteX=this.m_xList[currId];
currNoteY=this.m_yList[currId];
还有一个很关键的变量:
privatevarm_noteMap:
//节点(数组)地图,根据节点坐标记录节点开启关闭状态和ID
使用m_noteMap可以方便的存取任何位置节点的开启关闭状态,并可取其ID进而存取其它数据。
m_noteMap是个三维数组,第一维y坐标(第几行),第二维x坐标(第几列),第三维节点状态和ID。
判断点(p_x,p_y)是否在开启列表中:
returnthis.m_noteMap[p_y][p_x][NOTE_OPEN];
寻路过程
AStar类寻路的方法是find():
/**
*开始寻路
*@paramp_startX
起点X坐标
*@paramp_startY
起点Y坐标
*@paramp_endX
终点X坐标
*@paramp_endY
终点Y坐标
*@return
找到的路径(二维数组:
[p_startX,p_startY],...,[p_endX,p_endY])
*/
publicfunctionfind(p_startX:
int,p_startY:
int,p_endX:
int,p_endY:
int):
Array{/*寻路*/}
注意这里返回数据的形式:
从起点到终点的节点数组,其中每个节点为一维数组[x,y]的形式。
为了加快速度,类里没有使用Object或是Point,节点坐标全部以数组形式存储。
如节点note的x坐标为note[0],y坐标为note[1]。
下面开始寻路,第一步将起点添加到开启列表:
this.openNote(p_startX,p_startY,0,0,0);
openNote()方法将节点加入开放列表的同时分配一个唯一的ID、按此ID存储数据、对开启列表排序。
接下来是寻路过程:
while(this.m_openCount>
0)
{
//将编码为此ID的元素列入关闭列表
this.closeNote(currId);
//如果终点被放入关闭列表寻路结束,返回路径
if(currNoteX==p_endX&
&
currNoteY==p_endY)
returnthis.getPath(p_startX,p_startY,currId);
//...每轮寻路过程
}
//开放列表已空,找不到路径
returnnull;
每轮的寻路:
//获取周围节点,排除不可通过和已在关闭列表中的
aroundNotes=this.getArounds(currNoteX,currNoteY);
//对于周围每个节点
foreach(varnote:
ArrayinaroundNotes)
//计算F和G值
cost=this.m_movementCostList[currId]+((note[0]==currNoteX||note[1]==currNoteY)?
COST_STRAIGHT:
COST_DIAGONAL);
score=cost+(Math.abs(p_endX-note[0])+Math.abs(p_endY-note[1]))*COST_STRAIGHT;
if(this.isOpen(note[0],note[1]))//如果节点已在开启列表中
//测试节点的ID
checkingId=this.m_noteMap[note[1]][note[0]][NOTE_ID];
//如果新的G值比节点原来的G值小,修改F,G值,换父节点
if(cost<
this.m_movementCostList[checkingId])
this.m_movementCostList[checkingId]=cost;
this.m_pathScoreList[checkingId]=score;
this.m_fatherList[checkingId]=currId;
//对开启列表重新排序
this.aheadNote(this.getIndex(checkingId));
}else//如果节点不在开放列表中
//将节点放入开放列表
this.openNote(note[0],note[1],score,cost,currId);
从终点开始依次沿父节点回到到起点,返回找到的路径:
*获取路径
起始点X坐标
起始点Y坐标
*@paramp_id
终点的ID
路径坐标数组
privatefunctiongetPath(p_startX:
int,p_id:
Array
vararr:
Array=[];
varnoteX:
int=this.m_xList[p_id];
varnoteY:
int=this.m_yList[p_id];
while(noteX!
=p_startX||noteY!
=p_startY)
arr.unshift([noteX,noteY]);
p_id=this.m_fatherList[p_id];
noteX=this.m_xList[p_id];
noteY=this.m_yList[p_id];
arr.unshift([p_startX,p_startY]);
this.destroyLists();
returnarr;
列表排序
这部分看代码和注释就可以了,不多说:
/**将(新加入开放别表或修改了路径评分的)节点向前移动*/
privatefunctionaheadNote(p_index:
void
varfather:
varchange:
//如果节点不在列表最前
while(p_index>
1)
//父节点的位置
father=Math.floor(p_index/2);
//如果该节点的F值小于父节点的F值则和父节点交换
if(this.getScore(p_index)<
this.getScore(father))
change=this.m_openList[p_index-1];
this.m_openList[p_index-1]=this.m_openList[father-1];
this.m_openList[father-1]=change;
p_index=father;
}else
break;
/**将(取出开启列表中路径评分最低的节点后从队尾移到最前的)节点向后移动*/
privatefunctionbackNote():
//尾部的节点被移到最前面
varcheckIndex:
int=1;
vartmp:
while(true)
tmp=checkIndex;
//如果有子节点
if(2*tmp<
=this.m_openCount)
//如果子节点的F值更小
if(this.getScore(checkIndex)>
this.getScore(2*tmp))
//记节点的新位置为子节点位置
checkIndex=2*tmp;
//如果有两个子节点
if(2*tmp+1<
//如果第二个子节点F值更小
this.getScore(2*tmp+1))
//更新节点新位置为第二个子节点位置
checkIndex=2*tmp+1;
//如果节点位置没有更新结束排序
if(tmp==checkIndex)
}
//反之和新位置交换,继续和新位置的子节点比较F值
else
change=this.m_openList[tmp-1];
this.m_openList[tmp-1]=this.m_openList[checkIndex-1];
this.m_openList[checkIndex-1]=change;
其中getScore()方法:
*获取某节点的路径评分F值
*@paramp_index
节点在开启列表中的索引(从1开始)
privatefunctiongetScore(p_index:
int
//开启列表索引从1开始,ID从0开始,数组索引从0开始
returnthis.m_pathScoreList[this.m_openList[p_index-1]];
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Astar 经典 算法