KnitFlow/assets/scripts/Util/AStar.ts

import { Component, Size, _decorator } from "cc";

const { ccclass, property } = _decorator;

export enum Direction {
    // 二进制，位操作，比较方便
    UP = 1,
    DOWN = 1 << 1,
    LEFT = 1 << 2,
    RIGHT = 1 << 3
}
export class Point {
    x: number;
    y: number;
    // 记录可行走的方向
    state: number;
    // 默认上下左右都可以
    constructor(x: number, y: number, state = Direction.UP | Direction.DOWN | Direction.LEFT | Direction.RIGHT) {
        this.x = x;
        this.y = y;
        this.state = state
    }
    G: number = 0;   //G = 从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。
    H: number = 0;   //H = 从网格上那个方格移动到终点B的预估移动耗费
    F: number = 0;   //F = G + H
    // 通行的方向性，有的点可能时单向通行
    father: Point = null;   //这个点的上一个点，通过回溯可以找到起点 
    is_close: boolean = false;   //是否关闭搜索
    //减去某些方向
    reduce(direction: number) {
        this.state = this.state & (~direction);
        return this;
    }
    // 加上某些方向
    add(direction: number) {
        this.state = this.state | direction;
        return this;
    }
    // 某方向是否可通行
    isPass(direction: number): boolean {
        return (this.state & direction) == direction;
    }

    copy() {
        let point = new Point(this.x, this.y, this.state);
        for (const propName in this) {
            point['' + propName] = this[propName]
        }
      
        return point;
    }
}

@ccclass
export default class AStar extends Component {

    static start: Point = null;      //起点
    static end: Point = null;        //终点
    static map: Map<number, Point> = null;   //地图point
    static size: Size = null;    //地图尺寸

    static arr_open: Array<Point> = [];  //开放队列
    static pppp: Point = null;       //执行完寻路，它就有值了，除非没找到


    /**
     * 获取路线 （此寻路不走斜线）
     */
    static getRoute(start: Point, end: Point, map: Map<number, Point>, size: Size = new Size(1, 1)) {
        //清空上次寻路，并赋值
        this.is_find = false;
        this.arr_open = [];
        this.pppp = null;
        this.start = start.copy();
        this.end = end.copy();
        this.map = new Map<number, Point>();
        map.forEach((value, key) => {
            this.map.set(key, value.copy());       //map 里放的是传过来的对象，使用深拷贝
        });
        this.size = size;
        map.get(this.start.x + this.start.y * this.size.width).G = 0;       //起点的G是0
        //开始寻路
        let route = new Array<Point>();
        try {
            this.search(this.start);     //内存不够会报错，一般是起点或终点封闭
        } catch (error) {
            console.error("位置不对");
            return route;
        }
        if (this.pppp) {
            this.getFather(this.pppp, route);
        }
        return route;
    }

    /**
     * 多Point寻路,多个不同起点寻找最优起点，的最优路线,statrs的优先收索权重应该给出，并且starts运算完成后会有修改
     */
    static getRouteByStars(starts: Point[], end: Point, map: Map<number, Point>, size: Size = new Size(1, 1)) {
        //清空上次寻路，并赋值
        this.is_find = false;
        this.arr_open = [];
        this.pppp = null;
        this.end = end.copy();
        this.map = new Map<number, Point>();
        map.forEach((value, key) => {
            this.map.set(key, value.copy());       //map 里放的是传过来的对象，使用深拷贝
        });
        this.size = size;
 
        //开始寻路
        let route = new Array<Point>();
        try {
            let arr = starts;
            arr.forEach(p => {
                this.setFather(p, p);
                p.father = null
            });
            //arr按照F排序 从小到大
            this.arr_open = arr;
            this.arr_open.sort(this.compare);
            for(let i =0;i<this.arr_open.length;i++){
                let pp = this.arr_open[i];
                if (pp.is_close) {        //删除没用的
                    this.arr_open.splice(i, 1); 
                    i--; //重置索引，或者倒序
                } else if (!this.is_find) {
                    this.search(pp);
                }
            }
        } catch (error) {
            console.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.arr_open.sort(this.compare);
        //递归继续找
        for(let i =0;i<this.arr_open.length;i++){
            let pp = this.arr_open[i];
            if (pp.is_close) {        //删除没用的
                this.arr_open.splice(i, 1); 
                i--;
            } else if (!this.is_find) {
                this.search(pp);
            }
        }
    }

    /**
     * 获取周围4个点，上下左右
     */
    static getAround(point: Point) {
        point.is_close = true;
        let arr = new Array<Point>();
        let index: number;
        let p: Point;
        // 这里上下是反向的， 以y轴以上是下 ，
        //上
        if (point.y != 0 && point.isPass(Direction.DOWN)) {     //到顶了，没有上
            index = point.x + (point.y - 1) * this.size.width;
            p = this.map.get(index)
            if (p && !p.is_close) {
                arr.push(this.map.get(index));
                this.arr_open.push(this.map.get(index));    //我也要一份
            }
        }
        //下
        if (point.y + 1 != this.size.height && point.isPass(Direction.UP)) {        //到底了，没有下
            index = point.x + (point.y + 1) * this.size.width;
            p = this.map.get(index)
            if (p && !p.is_close) {
                arr.push(this.map.get(index));
                this.arr_open.push(this.map.get(index));
            }
        }
        //左
        if (point.x != 0 && point.isPass(Direction.LEFT)) {            //同理
            index = point.x - 1 + point.y * this.size.width;
            p = this.map.get(index)
            if (p && !p.is_close) {
                arr.push(this.map.get(index));
                this.arr_open.push(this.map.get(index));
            }
        }
        //右
        if (point.x + 1 != this.size.width && point.isPass(Direction.RIGHT)) {             //同理
            index = point.x + 1 + point.y * this.size.width;
            p = this.map.get(index)
            if (p && !p.is_close) {
                arr.push(this.map.get(index));
                this.arr_open.push(this.map.get(index));
            }
        }
        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);
    }
}