系统城装机大师 - 固镇县祥瑞电脑科技销售部宣传站!

当前位置:首页 > 网络编程 > 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. }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

分享到:

相关信息

系统教程栏目

栏目热门教程

人气教程排行

站长推荐

热门系统下载