//調用工具類獲取路線

? ? ? ? let route = AStarSearch.getRoute(start_point, end_point, this.mapFloor.map_point);

map_point 是所有可走點的集合

import { _decorator, Component, Node, Prefab, instantiate, v3, Vec2 } from 'cc';
import { oops } from "../../../../../extensions/oops-plugin-framework/assets/core/Oops";
import { GameWorld } from "../../../GameWorld";
import { MapFloor, RowColData } from "../../../../Scripts/MapEditor/MapFloor";export class Point {x: number;y: number;constructor(x: number, y: number) {this.x = x;this.y = y;}G: number = 0;   //G = 從起點A，沿著產生的路徑，移動到網格上指定方格的移動耗費。H: number = 0;   //H = 從網格上那個方格移動到終點B的預估移動耗費F: number = 0;   //F = G + Hfather: Point = null;   //這個點的上一個點，通過回溯可以找到起點 is_close: boolean = false;   //是否關閉搜索
}export class AStarSearch {static start: Point = null;      //起點static end: Point = null;        //終點static map: Map<string, Point> = null;   //地圖pointstatic openSet: Set<Point> = new Set();  //開放隊列static pppp: Point = null;       //執行完尋路，它就有值了，除非沒找到/*** 獲取路線 （此尋路不走斜線）*/static getRoute(start: Point, end: Point, map_point: Map<string, { row: number, col: number }>): Point[] {//清空上次尋路，并賦值this.is_find = false;this.openSet.clear();this.pppp = null;this.start = { ...start };this.end = { ...end };this.map = new Map<string, Point>();map_point.forEach((value, key) => {let point = new Point(value.row, value.col);this.map.set(key, point);});let route = new Array<Point>();let keyStr = this.start.x + "_" + this.start.y;if (!this.map.has(keyStr)) {return route;}this.map.get(keyStr).G = 0;       //起點的G是0//開始尋路try {this.search(this.start);     //內存不夠會報錯，一般是起點或終點封閉} catch (error) {console.warn("位置不對", error);return route;}if (this.pppp) {this.getFather(this.pppp, route);}return route;}/*** 尋路*/static is_find = false;    //是否已經找到路線static search(point: Point) {if (point.x == this.end.x && point.y == this.end.y) {this.is_find = true;this.pppp = point;return;}let arr = this.getAround(point);arr.forEach(p => {this.setFather(p, point);});//arr按照F排序 從小到大this.openSet = new Set([...this.openSet].sort(this.compare));//遞歸繼續找this.openSet.forEach((pp, index, arr) => {if (pp.is_close) {        //刪除沒用的this.openSet.delete(pp);}if (!this.is_find) {this.search(pp);}});}/*** 獲取周圍4個點，上下左右*/static getAround(point: Point) {point.is_close = true;let arr = new Array<Point>();let index: string;let p: Point;//上、下、左、右let aroundPos = [{ x: point.x, y: point.y - 1 },{ x: point.x, y: point.y + 1 },{ x: point.x - 1, y: point.y },{ x: point.x + 1, y: point.y }]aroundPos.forEach(point => {index = point.x + "_" + point.y;p = this.map.get(index);if (p && !p.is_close) {arr.push(p);this.openSet.add(p);}})return arr;}/*** point換父親,并重新計算G、H、F*/static setFather(son: Point, father: Point) {if (!son.father || son.father.G > father.G) {son.father = father;son.G = son.father.G + 1;son.H = Math.abs(son.x - this.end.x) + Math.abs(son.y - this.end.y);son.F = son.G + son.H;}}/*** 比較器*/static compare(p1: Point, p2: Point) {if (p1.F > p2.F) {return 1;} else {return -1;}}/*** 遞歸 把祖宗放進route里面*/static getFather(point: Point, route: Array<Point>) {let father = point.father;if (father) {this.getFather(father, route);}route.push(point);}
}