基于javascript实现获取最短路径算法代码实例
这篇文章主要介绍了基于javascript实现获取最短路径算法代码实例,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
代码如下
//A算法自动寻路路径
classGetAutoPath{
constructor(id,map,sPos,ePos,mapArr){
//this.type=id.type;
this.id=id;
this.map=map;
this.sPos=sPos;
this.ePos=ePos;
this.mapArr=mapArr;
this.maxMach=10000;
this.openArr=[];
this.closeArr=[];
this.minPath=[];
if(!this.isPath(this.sPos.x,this.sPos.y)){this.sPos=this.getNewDot(sPos,ePos);}
if(!this.isPath(this.ePos.x,this.ePos.y)){this.ePos=this.getNewDot(ePos,sPos);}
//console.log(this.mapArr);
returnthis.run();
}
posts(txt,arr){//post消息
//letid=this.id,sPos=this.sPos,ePos=this.ePos,arrs=arr||[];
return{id:this.id,map:this.map,arr:arr||[],sPos:this.sPos,ePos:this.ePos,txt:txt}
}
isPath(x,y){//isPath=true合法路径=isBanPath===undefined
letisPath=false,ym=this.mapArr.get(y),xm;//console.log(ym);debugger;
if(ym!==undefined){
xm=ym.get(x);
if(xm!==undefined){
if(xm.isBanPath===undefined){isPath=true;}
}
}
//if(this.mapArr[y]!==undefined&&this.mapArr[y][x]!==undefined&&this.mapArr[y][x].isPath===1){isPath=true;}
returnisPath;
}
getEqual(arr,x,y){//获取目标数组相同的坐标
letisPos=false;
if(arr.length===0){
isPos=false;
}else{
isPos=arr.some(function(o){returno.x===x&&o.y===y;});
}
returnisPos;
}
getDot(x,y){//获取周围8个方向坐标
return[{x:x-1,y:y},{x:x+1,y:y},{x:x,y:y-1},{x:x,y:y+1},{x:x-1,y:y-1},{x:x+1,y:y+1},{x:x+1,y:y-1},{x:x-1,y:y+1}]
}
getNewDot(setPos,pos){//重定义起点或终点
letdot=setPos,pointDot,k,arr=[],arrs=[],g,end,maxMachT=0;
while(!end&&maxMachT0){end=true;}
}
dot={x:arr[0].x,y:arr[0].y,g:arr[0].g};arr=[];
}
if(!arrs[0].x||!arrs[0].y){returnthis.posts("没有符合的坐标");}
return{x:arrs[0].x,y:arrs[0].y};
}
run(){
if(this.sPos.x===undefined||this.ePos.x===undefined){returnthis.posts("没有符合的坐标");}
letsPos=this.sPos,ePos=this.ePos,point,key,i,newPoint,ger,gers,g,h,f,maxMachT=0;
this.openArr[0]={x:sPos.x,y:sPos.y,f:0,p:0,ger:0}
while(this.openArr.length>0){
maxMachT++;
point=this.openArr[0];this.closeArr.push(point);this.openArr.splice(0,1);
key=this.closeArr.length-1;//设置当前节点
newPoint=this.getDot(point.x,point.y);//获取周围点
for(iinnewPoint){//设置周围点
ger=Math.round(Math.sqrt(Math.abs(newPoint[i].x-point.x)+Math.abs(newPoint[i].y-point.y))*100)/100;//到当前节点的曼哈顿距离,保留两位小数点
gers=ger+point.ger;
g=Math.round(gers*100)/100;
h=Math.abs(newPoint[i].x-ePos.x)+Math.abs(newPoint[i].y-ePos.y);
f=g+h;
if(this.isPath(newPoint[i].x,newPoint[i].y)&&!this.getEqual(this.openArr,newPoint[i].x,newPoint[i].y)&&!this.getEqual(this.closeArr,newPoint[i].x,newPoint[i].y)){this.openArr.push({x:newPoint[i].x,y:newPoint[i].y,f:f,p:key,ger:ger});}
}
this.openArr.sort(function(a,b){returna.f-b.f;});//排序
if(this.getEqual(this.closeArr,ePos.x,ePos.y)||this.getEqual(this.openArr,ePos.x,ePos.y)){//end
this.minPath.unshift(this.closeArr[key]);
while(this.minPath.length>0){
if(this.minPath[0].p==0){returnthis.posts('success',this.minPath);}else{this.minPath.unshift(this.closeArr[this.minPath[0].p]);}
}
}elseif(maxMachT===this.maxMach){
returnthis.posts("没有符合的坐标");
}
}
returnthis.posts("没有符合的坐标");
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。