建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
基于javascript實(shí)現(xiàn)獲取最短路徑算法代碼實(shí)例-創(chuàng)新互聯(lián)
這篇文章主要介紹了基于javascript實(shí)現(xiàn)獲取最短路徑算法代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
代碼如下
//A算法 自動尋路 路徑
class GetAutoPath{
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);
return this.run();
}
posts(txt, arr){//post消息
//let id = 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
let isPath = 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;}
return isPath;
}
getEqual(arr, x, y){//獲取目標(biāo)數(shù)組相同的坐標(biāo)
let isPos = false;
if(arr.length === 0){
isPos = false;
}else{
isPos = arr.some(function (o){return o.x === x && o.y === y;});
}
return isPos;
}
getDot(x, y){//獲取周圍8個方向坐標(biāo)
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){//重定義起點(diǎn)或終點(diǎn)
let dot = setPos, pointDot, k, arr = [], arrs = [], g, end, maxMachT = 0;
while(!end && maxMachT < this.maxMach){
maxMachT++;
pointDot = this.getDot(dot.x, dot.y);
for(k in pointDot){
g = Math.round(Math.sqrt(Math.abs(pointDot[k].x - pos.x) + Math.abs(pointDot[k].y - pos.y)) * 100) / 100;
if(!this.isPath(pointDot[k].x, pointDot[k].y)){//不合法
arr.push({x:pointDot[k].x, y:pointDot[k].y, g:g});
arr.sort(function(a, b){return a.g - b.g;});
}else{//合法
arrs.push({x:pointDot[k].x, y:pointDot[k].y, g:g});
arrs.sort(function(a, b){return a.g - b.g;});
}
if(arrs.length > 0){end = true;}
}
dot = {x:arr[0].x, y:arr[0].y, g:arr[0].g}; arr = [];
}
if(!arrs[0].x || !arrs[0].y){return this.posts("沒有符合的坐標(biāo)");}
return {x:arrs[0].x, y:arrs[0].y};
}
run(){
if(this.sPos.x === undefined || this.ePos.x === undefined){return this.posts("沒有符合的坐標(biāo)");}
let sPos = 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;//設(shè)置當(dāng)前節(jié)點(diǎn)
newPoint = this.getDot(point.x, point.y);//獲取周圍點(diǎn)
for(i in newPoint){//設(shè)置周圍點(diǎn)
ger = Math.round(Math.sqrt(Math.abs(newPoint[i].x - point.x) + Math.abs(newPoint[i].y - point.y)) * 100) / 100;//到當(dāng)前節(jié)點(diǎn)的曼哈頓距離,保留兩位小數(shù)點(diǎn)
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){return a.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){return this.posts('success', this.minPath);}else{this.minPath.unshift(this.closeArr[this.minPath[0].p]);}
}
}else if(maxMachT === this.maxMach){
return this.posts("沒有符合的坐標(biāo)");
}
}
return this.posts("沒有符合的坐標(biāo)");
}
}另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
網(wǎng)頁名稱：基于javascript實(shí)現(xiàn)獲取最短路徑算法代碼實(shí)例-創(chuàng)新互聯(lián)
URL標(biāo)題：http://www.dlmjj.cn/article/eeojj.html
