mergeRPG_client/assets/script/manager/AStarManager.ts

class AStarNode {
    private _x:number = 0;
    private _y:number = 0;
    get x() {return this._x;}
    get y() {return this._y;}
    /**
     * @param x 节点横坐标
     * @param y 节点纵坐标
     */
    constructor(x:number, y:number) {
        this._x = x;
        this._y = y;
    }
    priority = 0;
}

class Frontier {
    private arr:AStarNode[] = [];//创建字典(数组)
    put(node:AStarNode, priority:number) {
        node.priority = priority;
        this.arr.push(node); //添加元素 
        this.arr.sort((a,b)=>b.priority - a.priority);
    }
    get() {
        return this.arr.pop();//删除元素
    }

    get size() {
        return this.arr.length;
    }

    reset(){
        this.arr = [];
    }
}

export default class AStarManager{
    private static instance:AStarManager = null;
   
    static Instance() {
        if (!this.instance) { 
            this.instance = new AStarManager(); 
        }
        return this.instance;
    };

    // 通过private修饰符，让类无法在外部创建新的实例
    private constructor() { 

    }
    

    private mSize:cc.Size = null;  // 寻路地图大小
    private mStart:cc.Vec2 = null; // 寻路起始点坐标
    private mEnd:cc.Vec2 = null;   // 寻路目标点坐标

    private mStartNode:AStarNode = null; // 起始点
    private mEndNode:AStarNode = null;   // 目标点
    /**
     * 设置地图横纵最大值
     * @param size      地图大小
     * @param start     寻路起始点
     * @param end       寻路目标点
     * @param obstacles 障碍物
     */
    public init(size:cc.Size, start:cc.Vec2, end:cc.Vec2, obstacles:cc.Vec2[] = []) {
        this.mSize = size;
        this.mStart = start;
        this.mEnd = end;
        this.obstacles = {};
        obstacles.forEach((ele) => {
            this.setObstacles(ele.x, ele.y);
        });

        this.nodePool = {};

        this.mStartNode = this.createNode(this.mStart.x, this.mStart.y);
        this.mEndNode   = this.createNode(this.mEnd.x, this.mEnd.y);
    }

    public clean(){
        this.mStartNode = null;
        this.mEndNode = null;
    }
    
    private obstacles:{[x_y:string]:boolean} = {};
    /**
     * 设置障碍物
     * @param x 障碍物横坐标
     * @param y 障碍物纵坐标
     */
    public setObstacles(x:number, y:number) {
        if (!this.checkNode(x, y)) return;
        this.obstacles[`${x}_${y}`] = true;
    }
    /**
     * 清除障碍物
     * @param x 障碍物横坐标
     * @param y 障碍物纵坐标
     */
    public clearObstacles(x:number, y:number) {
        delete this.obstacles[`${x}_${y}`];
    }
    /**
     * 检查是否有障碍物
     * @param x 障碍物横坐标
     * @param y 障碍物纵坐标
     */
    public checkObstacles(x:number, y:number) {
        return this.obstacles[`${x}_${y}`];
    }

    /**
     * 检查节点是否在地图内
     * @param x 节点横坐标
     * @param y 节点纵坐标
     */
    public checkNode(x:number, y:number) {
        return x >= 0 && y >= 0 && x <= this.mSize.width && y <= this.mSize.height;
    }

 
    ///////////////////////////// 寻路开始 ////////////////////
    // 节点池
    private nodePool:{[x_y:string]:AStarNode} = {};
    // 探索边界
    private frontier:Frontier = null;
    // 节点来向(路径)
    private cameForm:Map<AStarNode, AStarNode> = new Map();
    // 节点当前代价
    private costSoFar:Map<AStarNode, number> = new Map();
    // 寻路类型(4方向或8方向)
    private mType: 4|8;

    private closeList:string[] = [];

    /**
     * 开始寻路
     * @param type 寻路类型，4方向或8方向
     */
    public run(type:4|8 = 4) {
        this.mType = type;

        // console.log('##### 寻路开始 #####');

        // console.log('地图大小:', this.mSize);
        // console.log('寻路类型:', this.mType + '方向');
        // console.log(`出发点X:${this.mStart.x}_Y:${this.mStart.y}`);
        // console.log(`目标点:X:${this.mEnd.x}_Y:${this.mEnd.y}`);
        // console.log('障碍物:', this.obstacles);


        const start = this.mStartNode;
        const goal = this.mEndNode;
        if (this.frontier)
            this.frontier.reset();
        else
            this.frontier = new Frontier();

        this.frontier.put(start, 0);//将起始点加入openList，表示我们从这里触发，是我们第一步可以走的点

        this.cameForm.clear();
        this.cameForm.set(start, null);
        this.costSoFar.clear();
        this.costSoFar.set(start, 0);
        this.closeList = [];

        while (this.frontier.size > 0) {
            let curr = this.frontier.get();  // 每次都取出f值最小的节点进行查找
            if (curr === goal) {
                break;
            }
            let nextList = this.getNeighbors(curr); //从openList中取出一个点作为nextNode，获取这个点下一步所有可走的点，存入nextList
            for (let next of nextList) {//如果nextList长度为0，说明没有路可走了;长度为大于0，则将nextList中的点都放入openList
                if(this.closeList.indexOf(this.getNodeKey(next.x,next.y)) < 0){
                    const nextCost = this.costSoFar.get(curr) + this.getCost(curr, next);
                    // console.log("next的索引:"+this.getNodeKey(next.x,next.y)+",开销:"+nextCost+"父节点索引:"+this.getNodeKey(curr.x,curr.y))
                    if (!this.costSoFar.has(next) || nextCost < this.costSoFar.get(next)) {
                        this.costSoFar.set(next, nextCost);
                        const preCost = this.getCost(next, goal);
                        this.frontier.put(next, nextCost + preCost);//内部根据开销进行了自动排序(从小到大)
                        this.cameForm.set(next, curr);
                    }
                }
            }
            this.closeList.push(this.getNodeKey(curr.x,curr.y));
        }
    }

    public getPath() {
        const arr = [];
        let node = this.mEndNode;
        arr.push(node);
        while (this.cameForm.has(node)) {
            node = this.cameForm.get(node);
            node && arr.push(node);
        }
        return arr;
    }

    getNeighbors(node:AStarNode) {
        const neighbors = [];

        if (this.mType === 8) {
            const upright = this.getNode(node.x + 1, node.y + 1);
            upright && neighbors.push(upright);
            
            const upleft = this.getNode(node.x - 1, node.y + 1);
            upleft && neighbors.push(upleft);
    
            const downleft = this.getNode(node.x - 1, node.y - 1);
            downleft && neighbors.push(downleft);
    
            const downright = this.getNode(node.x + 1, node.y - 1);
            downright && neighbors.push(downright);
        }

        const up = this.getNode(node.x, node.y + 1);
        up && neighbors.push(up);
        
        const down = this.getNode(node.x, node.y - 1);
        down && neighbors.push(down);
        
        const left = this.getNode(node.x - 1, node.y);
        left && neighbors.push(left);
        
        const right = this.getNode(node.x + 1, node.y);
        right && neighbors.push(right);

        return neighbors;
    }

    getCost(node1:AStarNode, node2:AStarNode) {
        return cc.Vec2.distance(new cc.Vec2(node1.x, node1.y), new cc.Vec2(node2.x, node2.y));
    }

    // 寻找下一个点
    public next() {
        
    }

    private getNode(x:number, y:number): AStarNode {
        if (!this.checkNode(x, y)) return;
        if (this.checkObstacles(x, y)) return;
        const key = this.getNodeKey(x, y);
        return this.nodePool[key] || this.createNode(x, y); 
    }
    private createNode(x:number, y:number) {
        const key = this.getNodeKey(x, y);
        this.nodePool[key] = new AStarNode(x, y);
        return this.nodePool[key];
    }

    private getNodeKey(x:number, y:number) {
        return `${x}_${y}`;
    }
}