A* （AStar） 寻路

//调用工具类获取路线

        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);}
}