Route.ts 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
  1. import { Injectable } from '@nestjs/common';
  2. import { CacheService } from 'src/cache/cache.service';
  3. export class Route{
  4. constructor(private cacheService: CacheService) {
  5. }
  6. async searchRoad(appId,startPointId,endPointId){
  7. const startPointRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +startPointId);
  8. const startPoint = JSON.parse(startPointRes);
  9. const endPointRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +endPointId);
  10. const endPoint = JSON.parse(endPointRes);
  11. var openList=[], //开启列表
  12. closeList=[], //关闭列表
  13. result=[], //结果数组
  14. result_index; //结果数组在开启列表中的序号
  15. //openList.push({x:startPoint.x,y:startPoint.y,G:0});//把当前点加入到开启列表中,并且G是0
  16. openList.push({breakPointId:startPointId,G:0});//把当前点加入到开启列表中,并且G是0
  17. do{
  18. var currentPointInfo = openList.pop();
  19. const currentPointRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +currentPointInfo.breakPointId);
  20. const currentPoint = JSON.parse(currentPointRes);
  21. closeList.push(currentPointInfo);
  22. var surroundPoint=this.SurroundPoint(appId,currentPointInfo.breakPointId);
  23. for(var i in surroundPoint) {
  24. var neighPointId = surroundPoint[i];
  25. const itemRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +neighPointId);
  26. const item = JSON.parse(itemRes);
  27. //g 到父节点的位置
  28. var g = currentPointInfo.G + Math.sqrt( (currentPoint.position.x - item.position.x) * (currentPoint.position.x - item.position.x)+(currentPoint.position.y - item.position.y)*(currentPoint.position.y - item.position.y));
  29. if (this.existList(item, openList)!=-1) { //如果不在开启列表中
  30. item['H'] = 0;
  31. item['G'] = g;
  32. item['F'] = item.H + item.G;
  33. item['parent'] = currentPoint;
  34. openList.push(item);
  35. }
  36. else { //存在在开启列表中,比较目前的g值和之前的g的大小
  37. var index = this.existList(item, openList);
  38. //如果当前点的g更小
  39. if (g < openList[index].G) {
  40. openList[index].parent = currentPoint;
  41. openList[index].G = g;
  42. openList[index].F=g+openList[index].H;
  43. }
  44. }
  45. }
  46. //如果开启列表空了,没有通路,结果为空
  47. if(openList.length==0) {
  48. break;
  49. }
  50. openList.sort(this.sortF);//这一步是为了循环回去的时候,找出 F 值最小的, 将它从 "开启列表" 中移掉
  51. }while(!(result_index=this.existList({x:endPoint.position.x,y:endPoint.position.y},openList)));
  52. //判断结果列表是否为空
  53. if(!result_index) {
  54. result=[];
  55. }
  56. else {
  57. var currentObj=openList[result_index];
  58. do{
  59. //把路劲节点添加到result当中
  60. result.unshift(currentObj.breakPointId);
  61. currentObj=currentObj.parent;
  62. }while (currentObj.position.x!=startPoint.position.x || currentObj.position.y!=startPoint.position.y);
  63. }
  64. return result;
  65. }
  66. //用F值对数组排序
  67. sortF(a,b){
  68. return b.F- a.F;
  69. }
  70. //获取周围点
  71. async SurroundPoint(appId,curPointId){
  72. //读redis里的数据
  73. const breakPointRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +curPointId);
  74. const breakPoint = JSON.parse(breakPointRes)
  75. return breakPoint.contact;
  76. }
  77. //判断点是否存在在列表中,是的话返回的是序列号
  78. existList(point,list) {
  79. for(var i =0;i<list.length;++i) {
  80. if(point.breakPointId==list[i].breakPointId) {
  81. return i;
  82. }
  83. }
  84. return -1;
  85. }
  86. }