A* （AStar） 寻路

//调用工具类获取路线
        let route = AStarSearch.getRoute(start_point, end_point, this.mapFloor.map_point);
map_point 是所有可走点的集合

1. import { _decorator, Component, Node, Prefab, instantiate, v3, Vec2 } from 'cc';
2. import { oops } from "../../../../../extensions/oops-plugin-framework/assets/core/Oops";
3. import { GameWorld } from "../../../GameWorld";
4. import { MapFloor, RowColData } from "../../../../Scripts/MapEditor/MapFloor";
6. export class Point {
7.     x: number;
8.     y: number;
9.     constructor(x: number, y: number) {
10.         this.x = x;
11.         this.y = y;
12.     }
13.     G: number = 0;   //G = 从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。
14.     H: number = 0;   //H = 从网格上那个方格移动到终点B的预估移动耗费
15.     F: number = 0;   //F = G + H
16.     father: Point = null;   //这个点的上一个点，通过回溯可以找到起点
17.     is_close: boolean = false;   //是否关闭搜索
18. }
20. export class AStarSearch {
22.     static start: Point = null;      //起点
23.     static end: Point = null;        //终点
24.     static map: Map<string, Point> = null;   //地图point
26.     static openSet: Set<Point> = new Set();  //开放队列
28.     static pppp: Point = null;       //执行完寻路，它就有值了，除非没找到
30.     /**
31.      * 获取路线 （此寻路不走斜线）
32.      */
33.     static getRoute(start: Point, end: Point, map_point: Map<string, { row: number, col: number }>): Point[] {
34.         //清空上次寻路，并赋值
35.         this.is_find = false;
36.         this.openSet.clear();
37.         this.pppp = null;
38.         this.start = { ...start };
39.         this.end = { ...end };
40.         this.map = new Map<string, Point>();
41.         map_point.forEach((value, key) => {
42.             let point = new Point(value.row, value.col);
43.             this.map.set(key, point);
44.         });
46.         let route = new Array<Point>();
47.         let keyStr = this.start.x + "_" + this.start.y;
48.         if (!this.map.has(keyStr)) {
49.             return route;
50.         }
51.         this.map.get(keyStr).G = 0;       //起点的G是0
52.         //开始寻路
53.         try {
54.             this.search(this.start);     //内存不够会报错，一般是起点或终点封闭
55.         } catch (error) {
56.             console.warn("位置不对", error);
57.             return route;
58.         }
59.         if (this.pppp) {
60.             this.getFather(this.pppp, route);
61.         }
62.         return route;
63.     }
65.     /**
66.      * 寻路
67.      */
68.     static is_find = false;    //是否已经找到路线
69.     static search(point: Point) {
70.         if (point.x == this.end.x && point.y == this.end.y) {
71.             this.is_find = true;
72.             this.pppp = point;
73.             return;
74.         }
75.         let arr = this.getAround(point);
76.         arr.forEach(p => {
77.             this.setFather(p, point);
78.         });
79.         //arr按照F排序 从小到大
80.         this.openSet = new Set([...this.openSet].sort(this.compare));
81.         //递归继续找
82.         this.openSet.forEach((pp, index, arr) => {
83.             if (pp.is_close) {        //删除没用的
84.                 this.openSet.delete(pp);
85.             }
86.             if (!this.is_find) {
87.                 this.search(pp);
88.             }
89.         });
90.     }
92.     /**
93.      * 获取周围4个点，上下左右
94.      */
95.     static getAround(point: Point) {
96.         point.is_close = true;
97.         let arr = new Array<Point>();
98.         let index: string;
99.         let p: Point;
101.         //上、下、左、右
102.         let aroundPos = [
103.             { x: point.x, y: point.y - 1 },
104.             { x: point.x, y: point.y + 1 },
105.             { x: point.x - 1, y: point.y },
106.             { x: point.x + 1, y: point.y }
107.         ]
108.         aroundPos.forEach(point => {
109.             index = point.x + "_" + point.y;
110.             p = this.map.get(index);
111.             if (p && !p.is_close) {
112.                 arr.push(p);
113.                 this.openSet.add(p);
114.             }
115.         })
116.         return arr;
117.     }
119.     /**
120.      * point换父亲,并重新计算G、H、F
121.      */
122.     static setFather(son: Point, father: Point) {
123.         if (!son.father || son.father.G > father.G) {
124.             son.father = father;
125.             son.G = son.father.G + 1;
126.             son.H = Math.abs(son.x - this.end.x) + Math.abs(son.y - this.end.y);
127.             son.F = son.G + son.H;
128.         }
129.     }
131.     /**
132.      * 比较器
133.      */
134.     static compare(p1: Point, p2: Point) {
135.         if (p1.F > p2.F) {
136.             return 1;
137.         } else {
138.             return -1;
139.         }
140.     }
142.     /**
143.      * 递归 把祖宗放进route里面
144.      */
145.     static getFather(point: Point, route: Array<Point>) {
146.         let father = point.father;
147.         if (father) {
148.             this.getFather(father, route);
149.         }
150.         route.push(point);
151.     }
152. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。