基于javascript实现获取最短路径算法代码实例

这篇文章主要介绍了基于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. }

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