系統城裝機大師 - 唯一官網:www.farandoo.com!

當前位置:首頁 > 網絡編程 > JavaScript > 詳細頁面

基于javascript實現獲取最短路徑算法代碼實例

時間:2020-02-20來源:系統城作者:電腦系統城

這篇文章主要介紹了基于javascript實現獲取最短路徑算法代碼實例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

代碼如下


 
  1. //A算法 自動尋路 路徑
  2. class GetAutoPath{
  3.  
  4. constructor(id, map, sPos, ePos, mapArr){
  5. //this.type = id.type;
  6. this.id = id;
  7. this.map = map;
  8. this.sPos = sPos;
  9. this.ePos = ePos;
  10. this.mapArr = mapArr;
  11. this.maxMach = 10000;
  12. this.openArr = [];
  13. this.closeArr = [];
  14. this.minPath = [];
  15. if(!this.isPath(this.sPos.x, this.sPos.y)){this.sPos = this.getNewDot(sPos, ePos);}
  16. if(!this.isPath(this.ePos.x, this.ePos.y)){this.ePos = this.getNewDot(ePos, sPos);}
  17. //console.log(this.mapArr);
  18. return this.run();
  19. }
  20.  
  21. posts(txt, arr){//post消息
  22. //let id = this.id, sPos = this.sPos, ePos = this.ePos, arrs = arr || [];
  23. return {id:this.id, map:this.map, arr:arr || [], sPos:this.sPos, ePos:this.ePos, txt:txt}
  24. }
  25.  
  26. isPath(x, y){//isPath = true 合法路徑 = isBanPath === undefined
  27. let isPath = false, ym = this.mapArr.get(y), xm; //console.log(ym); debugger;
  28. if(ym !== undefined){
  29. xm = ym.get(x);
  30. if(xm !== undefined){
  31. if(xm.isBanPath === undefined){isPath = true;}
  32. }
  33. }
  34. //if(this.mapArr[y] !== undefined && this.mapArr[y][x] !== undefined && this.mapArr[y][x].isPath === 1){isPath = true;}
  35. return isPath;
  36. }
  37.  
  38. getEqual(arr, x, y){//獲取目標數組相同的坐標
  39. let isPos = false;
  40. if(arr.length === 0){
  41. isPos = false;
  42. }else{
  43. isPos = arr.some(function (o){return o.x === x && o.y === y;});
  44. }
  45. return isPos;
  46. }
  47.  
  48. getDot(x, y){//獲取周圍8個方向坐標
  49. 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}]
  50. }
  51.  
  52. getNewDot(setPos, pos){//重定義起點或終點
  53. let dot = setPos, pointDot, k, arr = [], arrs = [], g, end, maxMachT = 0;
  54. while(!end && maxMachT < this.maxMach){
  55. maxMachT++;
  56. pointDot = this.getDot(dot.x, dot.y);
  57. for(k in pointDot){
  58. g = Math.round(Math.sqrt(Math.abs(pointDot[k].x - pos.x) + Math.abs(pointDot[k].y -pos.y)) * 100) / 100;
  59. if(!this.isPath(pointDot[k].x, pointDot[k].y)){//不合法
  60. arr.push({x:pointDot[k].x, y:pointDot[k].y, g:g});
  61. arr.sort(function(a, b){return a.g - b.g;});
  62. }else{//合法
  63. arrs.push({x:pointDot[k].x, y:pointDot[k].y, g:g});
  64. arrs.sort(function(a, b){return a.g - b.g;});
  65. }
  66. if(arrs.length > 0){end = true;}
  67. }
  68. dot = {x:arr[0].x, y:arr[0].y, g:arr[0].g}; arr = [];
  69. }
  70. if(!arrs[0].x || !arrs[0].y){return this.posts("沒有符合的坐標");}
  71. return {x:arrs[0].x, y:arrs[0].y};
  72. }
  73.  
  74. run(){
  75. if(this.sPos.x === undefined || this.ePos.x === undefined){return this.posts("沒有符合的坐標");}
  76. let sPos = this.sPos, ePos = this.ePos, point, key, i, newPoint, ger, gers, g, h, f, maxMachT =0;
  77. this.openArr[0] = {x : sPos.x, y : sPos.y, f : 0, p : 0, ger : 0}
  78. while(this.openArr.length > 0){
  79. maxMachT++;
  80. point = this.openArr[0]; this.closeArr.push(point); this.openArr.splice(0,1);
  81. key = this.closeArr.length - 1;//設置當前節點
  82. newPoint = this.getDot(point.x, point.y);//獲取周圍點
  83. for(i in newPoint){//設置周圍點
  84. ger = Math.round(Math.sqrt(Math.abs(newPoint[i].x - point.x) + Math.abs(newPoint[i].y -point.y)) * 100) / 100;//到當前節點的曼哈頓距離,保留兩位小數點
  85. gers = ger + point.ger;
  86. g = Math.round(gers * 100) / 100;
  87. h = Math.abs(newPoint[i].x - ePos.x) + Math.abs(newPoint[i].y - ePos.y);
  88. f = g + h;
  89. 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});}
  90. }
  91. this.openArr.sort(function(a, b){return a.f - b.f;});//排序
  92. if(this.getEqual(this.closeArr, ePos.x, ePos.y) || this.getEqual(this.openArr, ePos.x, ePos.y)){//end
  93. this.minPath.unshift(this.closeArr[key]);
  94. while(this.minPath.length > 0){
  95. if(this.minPath[0].p == 0){return this.posts('success',this.minPath);}else{this.minPath.unshift(this.closeArr[this.minPath[0].p]);}
  96. }
  97. }else if(maxMachT === this.maxMach){
  98. return this.posts("沒有符合的坐標");
  99. }
  100. }
  101. return this.posts("沒有符合的坐標");
  102. }
  103.  
  104. }

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持我們。

分享到:

相關信息

系統教程欄目

欄目熱門教程

人氣教程排行

站長推薦

熱門系統下載

jlzzjlzz亚洲乱熟在线播放