寻路算法－广度搜索寻找最短路径

作者佚名技术来源服务器技术浏览发布时间 2012-07-11

点击浏览该文件

点击浏览该文件
Stage.scaleMode="noScale";
var nx=25; //地图横向格数
var ny=15; //地图纵向格数
var mmap=new Array(ny); //地图的数组
var vmap=new Array(4*ny*nx); //广度搜索的结点存储数组
var fmap=new Array(ny); //搜索过的结点及障碍标志
var parrow=new Array([1,0],[0,1],[-1,0],[0,-1]);//四个方向的行动参数
var cp=0; //当前到达的路径结点的指针
var finded=false; //搜索成功标志
_root.createEmptyMovieClip("mapbg",3); //创建背景地图mc
_root.createEmptyMovieClip("pathshadow",4); //创建路径显示mc
mapbg.useHandCursor;
//=======================================画方块函数
drawbox=function(obj,x,y,f){
var drawx=x*20;
var drawy=y*20;
with(obj){
lineStyle(1,0xcccccc,100);
moveTo(drawx,drawy);
beginFill(f,100);
lineTo(drawx+20,drawy);
lineTo(drawx+20,drawy+20);
lineTo(drawx,drawy+20);
lineTo(drawx,drawy);
endFill();
}
}
//=======================================在mapbg中生成随机地图，并把数据存进mmap
for(a=0;ammap[a]=new Array(nx);
fmap[a]=new Array(nx);
for(b=0;bif(a==0 && b==0){
mmap[a][b]=0;
}else{
mmap[a][b]=random(2)*random(2)*random(2);
}
fmap[a][b]=mmap[a][b];
if(mmap[a][b]==0){drawbox(mapbg,b,a,0xeeeeee);}else{drawbox(mapbg,b,a,0xbbbbbb);}
}
}
//=======================================创建一个代表人的小圆元件，用在地图上行走
_root.createEmptyMovieClip("man",5);
with(_root.man){
lineStyle(1,0xff9900,100);
beginFill(0xff9900);
moveTo(0,10);
curveTo(0,0,10,0);
curveTo(20,0,20,10);
curveTo(20,20,10,20);
curveTo(0,20,0,10);
endFill();
}
//===================
var bx=0;
var by=0;
var ex=0;
var ey=0;
//========================================鼠标点下的时候进行广度搜索
_root.onMouseDown=function(){
bx=int(_xmouse/20); //取得鼠标点下的格坐标及人的当前准备搜索
by=int(_ymouse/20);
ex=int(man._x/20);
ey=int(man._y/20);
finded=false; //搜索成功标志清掉
pathshadow.clear(); //路径阴影清空
for(a=0;avmap.splice(0); //结点存储数组清空
if(fmap[by][bx]==0){ //目标格为空格时才保存为广度搜索根结点
vmap[1]=[bx,by,1,0];fmap[by][bx]=1;
}
p=1;i=1;
while(vmap[i]!=undefined){ //广度搜索,根结点开始，每个结点四个方向如果为空格而且还没搜索过就把坐标和到根结点的距离及父结点记录进vmap
for(t=0;t<4;t++){
if(fmap[vmap[i][1]+parrow[t][1]][vmap[i][0]+parrow[t][0]]==0) {
p++;
vmap[p]=[vmap[i][0]+parrow[t][0],vmap[i][1]+parrow[t][1],vmap[i][2]+1,i];
fmap[vmap[i][1]+parrow[t][1]][vmap[i][0]+parrow[t][0]]=1;}
}
if(vmap[i][0]==ex && vmap[i][1]==ey) {finded=true;cp=i;break;}//找到了路径就马上退出搜索，置搜索成功标志，并记录最后搜索到的结点索引
i++;
}
tempcp=cp;
if(finded){ //搜索成功就画出路径阴影
while(tempcp>=1){
drawbox(pathshadow,vmap[tempcp][0],vmap[tempcp][1],0xccff99);
tempcp=vmap[tempcp][3];
}
}
}
//=====================================定时自运行函数，当找到路径后将代表人的圆mc一步步按路径走向目标点。
mango=function(){
if(finded){
cp=vmap[cp][3];
man._x=20*vmap[cp][0];
man._y=20*vmap[cp][1];
if(cp==1) {pathshadow.clear(); finded=false;} //行走结束的时候把路径阴影清空
}
}
setInterval(mango,50); 关键词：搜索

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!

分享到：更多

你可能对下面的文章感兴趣

上一篇: 《闪E》FLASH技术电子期刊第三期下一篇: 引导线显现的两种方法

关于寻路算法－广度搜索寻找最短路径的所有评论

随机推荐