123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104 |
- import { Injectable } from '@nestjs/common';
- import { CacheService } from 'src/cache/cache.service';
- export class Route{
- constructor(private cacheService: CacheService) {
-
- }
-
- async searchRoad(appId,startPointId,endPointId){
- const startPointRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +startPointId);
- const startPoint = JSON.parse(startPointRes);
- const endPointRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +endPointId);
- const endPoint = JSON.parse(endPointRes);
- var openList=[], //开启列表
- closeList=[], //关闭列表
- result=[], //结果数组
- result_index; //结果数组在开启列表中的序号
- //openList.push({x:startPoint.x,y:startPoint.y,G:0});//把当前点加入到开启列表中,并且G是0
- openList.push({breakPointId:startPointId,G:0});//把当前点加入到开启列表中,并且G是0
- do{
- var currentPointInfo = openList.pop();
- const currentPointRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +currentPointInfo.breakPointId);
- const currentPoint = JSON.parse(currentPointRes);
- closeList.push(currentPointInfo);
- var surroundPoint=this.SurroundPoint(appId,currentPointInfo.breakPointId);
- for(var i in surroundPoint) {
- var neighPointId = surroundPoint[i];
- const itemRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +neighPointId);
- const item = JSON.parse(itemRes);
- //g 到父节点的位置
- 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));
-
- if (this.existList(item, openList)!=-1) { //如果不在开启列表中
- item['H'] = 0;
- item['G'] = g;
- item['F'] = item.H + item.G;
- item['parent'] = currentPoint;
- openList.push(item);
- }
- else { //存在在开启列表中,比较目前的g值和之前的g的大小
- var index = this.existList(item, openList);
- //如果当前点的g更小
- if (g < openList[index].G) {
- openList[index].parent = currentPoint;
- openList[index].G = g;
- openList[index].F=g+openList[index].H;
- }
- }
- }
- //如果开启列表空了,没有通路,结果为空
- if(openList.length==0) {
- break;
- }
- openList.sort(this.sortF);//这一步是为了循环回去的时候,找出 F 值最小的, 将它从 "开启列表" 中移掉
- }while(!(result_index=this.existList({x:endPoint.position.x,y:endPoint.position.y},openList)));
- //判断结果列表是否为空
- if(!result_index) {
- result=[];
- }
- else {
- var currentObj=openList[result_index];
- do{
- //把路劲节点添加到result当中
- result.unshift(currentObj.breakPointId);
- currentObj=currentObj.parent;
- }while (currentObj.position.x!=startPoint.position.x || currentObj.position.y!=startPoint.position.y);
- }
- return result;
- }
- //用F值对数组排序
- sortF(a,b){
- return b.F- a.F;
- }
- //获取周围点
- async SurroundPoint(appId,curPointId){
- //读redis里的数据
- const breakPointRes = await this.cacheService.get('breakpoints:app_id:' +appId +':break_point_id:' +curPointId);
- const breakPoint = JSON.parse(breakPointRes)
- return breakPoint.contact;
- }
- //判断点是否存在在列表中,是的话返回的是序列号
- existList(point,list) {
- for(var i =0;i<list.length;++i) {
- if(point.breakPointId==list[i].breakPointId) {
- return i;
- }
- }
- return -1;
- }
- }
|