最短路径搜索

作者佚名技术来源服务器技术浏览发布时间 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
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]][vm

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

1 2 下一页

分享到：更多

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

上一篇: 入门教程－闪出文字下一篇: 鼠标跟随之粒子扩散效果

关于最短路径搜索的所有评论

随机推荐