最短路径搜索

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;a<ny;a++){
mmap[a]=new Array(nx);
fmap[a]=new Array(nx);
for(b=0;b<nx;b++){
if(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;a<ny;a++) for(b=0;b<nx;b++) fmap[a][b]=mmap[a][b]; //障碍及搜索过的结点标志数组重置
vmap.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
if(mmap[vmap[i][1]+parrow[0][1]][vmap[i][0]+parrow[0][0]]==0 && fmap[vmap[i][1]+parrow[0][1]][vmap[i][0]+parrow[0][0]]==0) {
p++;
vmap[p]=[vmap[i][0]+parrow[0][0],vmap[i][1]+parrow[0][1],vmap[i][2]+1,i];
fmap[vmap[i][1]+parrow[0][1]][vmap[i][0]+parrow[0][0]]=1;}
if(mmap[vmap[i][1]+parrow[1][1]][vmap[i][0]+parrow[1][0]]==0 && fmap[vmap[i][1]+parrow[1][1]][vmap[i][0]+parrow[1][0]]==0) {
p++;
vmap[p]=[vmap[i][0]+parrow[1][0],vmap[i][1]+parrow[1][1],vmap[i][2]+1,i];
fmap[vmap[i][1]+parrow[1][1]][vmap[i][0]+parrow[1][0]]=1;}
if(mmap[vmap[i][1]+parrow[2][1]][vmap[i][0]+parrow[2][0]]==0 && fmap[vmap[i][1]+parrow[2][1]][vmap[i][0]+parrow[2][0]]==0) {
p++;
vmap[p]=[vmap[i][0]+parrow[2][0],vmap[i][1]+parrow[2][1],vmap[i][2]+1,i];
fmap[vmap[i][1]+parrow[2][1]][vmap[i][0]+parrow[2][0]]=1;}
if(mmap[vmap[i][1]+parrow[3][1]][vmap[i][0]+parrow[3][0]]==0 && fmap[vmap[i][1]+parrow[3][1]][vmap[i][0]+parrow[3][0]]==0) {
p++;
vmap[p]=[vmap[i][0]+parrow[3][0],vmap[i][1]+parrow[3][1],vmap[i][2]+1,i];
fmap[vmap[i][1]+parrow[3][1]][vmap[i][0]+parrow[3][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(); //行走结束的时候把路径阴影清空
}
}
setInterval(mango,50);