CocosCreator_项目中运用A*算法做寻路设计

/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: ArrayList
*/
export class ArrayList {
    private _list: [any[]];
    private _row;//矩阵行
    private _colums;//矩阵列

    public constructor(rows: number, colums: number, defalut: any = 0) {
        this._list = [[]];
        this._row = rows;
        this._colums = colums;
        this.initRows(rows);
        this.initColumns(colums, defalut);
    }

    //初始化数组行
    initRows(rows: number) {
        if (rows < 1) {
            return;
        }
        for (let i = 0; i < this._row; i++) {
            let item:any[] = [];
            this._list.push(item);
        }
    }

    //初始化数组列
    initColumns(columns: number, value: any) {
        if (columns < 1) {
            return;
        }
        for (let i = 0; i < this._list.length; i++) {
            for (let j = 0; j < columns; j++) {
                this._list[i].push(value)
            }
        }
    }

    getValue(rows: number, colums: number) {
        if (rows < 0 || colums < 0 || rows >= this._row || colums >= this._colums) {
            console.error("IndexOutOfRangeException: Index was outside the bounds of the array.")
            return null;
        }
        return this._list[rows][colums];
    }

    setValue(rows: number, colums: number, value) {
        if (rows < 0 || colums < 0 || rows >= this._row || colums >= this._colums) {
            console.error("IndexOutOfRangeException: Index was outside the bounds of the array.")
            return;
        }
        this._list[rows][colums] = value;
    }

    getArrayList(): Array<Array<any>> {
        return this._list;
    }

}

import { GridNode } from "./GridNode";


/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: PriorityQueue
*/
export class PriorityQueue {

    private nodes: GridNode[] = [];


    public Length() {
        return this.nodes.length;
    }

    public Contains(node: GridNode) {
        return this.nodes.includes(node);
    }

    public First(): GridNode {
        if (this.nodes.length > 0) {
            return this.nodes[0];
        }
        return null;
    }

    public Add(node: GridNode) {
        this.nodes.push(node);
        this.sort();
    }

    public Remove(node: GridNode) {
        let index = this.nodes.indexOf(node);
        if (index > -1) {
            this.nodes.splice(index, 1);
        }
        this.sort();
    }

    private sort() {
        let sortCallFunc = (a, b) => {
            if (a.estimatedCost < b.estimatedCost) {
                return -1;
            }

            if (a.estimatedCost > b.estimatedCost) {
                return 1;
            }

            return 0;
        }
        this.nodes.sort(sortCallFunc)
    }
}

/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: GridNode
*/
export class GridNode {

    public nodeTotalCost: number;
    public estimatedCost: number;
    public bObstacle: boolean;
    public parent: GridNode;
    public position: cc.Vec2; //矩阵行列式，也可代表x,y轴

    public constructor() {
        this.estimatedCost = 0;
        this.nodeTotalCost = 1;
        this.bObstacle = false;
        this.parent = null;
    }

    public initWithPos(pos: cc.Vec2) {
        this.estimatedCost = 0;
        this.nodeTotalCost = 1;
        this.bObstacle = false;
        this.parent = null;
        this.position = pos;
    }

    public MarkAsObstacle() {
        this.bObstacle = true;
    }
}

import { ArrayList } from "./ArrayList";
import { GridNode } from "./GridNode";

/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: 地图网格化管理器
*/

export class GridManager {

    private static _instance: GridManager;
    public static getInstance(): GridManager {
        if (GridManager._instance == null) {
            GridManager._instance = new GridManager();
        }
        return GridManager._instance;
    }

    public numOfRows: number; //行数
    public numOfColumns: number;//列数
    public girdCellSize: number;
    public showGrid: boolean;

    nodes: ArrayList;
    public obstacleList: any[];


    public init(row: number, column: number, mapData: any) {
        if (!mapData) {
            console.error(‘地图数据加载失败‘);
            return;
        }
        this.numOfRows = row; // 53 (0,52)
        this.numOfColumns = column; //45(0-44)
        this.CalcuateGirdNodes(mapData);
    }

    /**
     * 初始化网格da
     * @param mapData json数据
     * @param 注:网格是严格按照x，y对应来进行初始化的，但是遍历map需要额外处理下
     */
    public CalcuateGirdNodes(mapData: any) {
        this.nodes = new ArrayList(this.numOfRows, this.numOfColumns);
        for (let i = 0; i < this.numOfColumns; i++) {
            for (let j = 0; j < this.numOfRows; j++) {
                let node: GridNode = new GridNode();
                node.initWithPos(cc.v2(j, i))
                //BlockType.disable 自己设计的标签，不可行走
                //BlockType.occlusion 障碍物
                //BlockType.Basket 其他
                if (mapData[i][j] == BlockType.disable || mapData[i][j] == BlockType.occlusion ||
                    mapData[i][j] == BlockType.Basket) {
                    node.MarkAsObstacle();
                }
                this.nodes.setValue(j, i, node);
            }
        }
    }

    private GetRow(pos: cc.Vec2) {
        let row = pos.x
        return row;
    }

    private GetColumn(pos: cc.Vec2) {
        let colums = pos.y;
        return colums;
    }

    private GetGridNodeByRowColumn(row: number, column: number) {
        return this.nodes.getArrayList()[row][column];
    }


    /**
     * 取8个点
     * @param node 
     * @param neighbors 
     */
    public GetNeighbours(node: GridNode, neighbors: GridNode[]) {
        let neighborPos: cc.Vec2 = node.position;
        let row = this.GetRow(neighborPos); // 26
        let colum = this.GetColumn(neighborPos); //20
        //左
        let leftNodeRow = row - 2;
        let leftNodeColum = colum;
        this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
        //右
        leftNodeRow = row + 2;
        leftNodeColum = colum;
        this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
        //上
        leftNodeRow = row;
        leftNodeColum = colum + 1;
        this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
        //下
        leftNodeRow = row;
        leftNodeColum = colum - 1;
        this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
        //左上
        leftNodeRow = row - 1;
        leftNodeColum = colum;
        this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
        //右上
        leftNodeRow = row + 1;
        leftNodeColum = colum;
        this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
        //左下
        leftNodeRow = row - 1;
        leftNodeColum = colum - 1;
        this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
        //右下
        leftNodeRow = row + 1;
        leftNodeColum = colum - 1;
        this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
    }


    private AssignNeighbour(row: number, colum: number, neighbors: GridNode[]) {
        if (row != -1 && colum != -1 && row < this.numOfRows && colum < this.numOfColumns) {
            let nodeToAdd: GridNode = this.GetGridNodeByRowColumn(row, colum);
            if (!nodeToAdd.bObstacle) {
                neighbors.push(nodeToAdd);
            }
        }
    }

}

/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: A*
*/

import { GridManager } from "./GridManager";
import { GridNode } from "./GridNode";
import { PriorityQueue } from "./PriorityQueue";

export class AStar {

    private static openList: PriorityQueue;
    private static closeList: PriorityQueue;

    private static NodeCost(a: GridNode, b: GridNode): number {
        let vecCost: cc.Vec2 = a.position.sub(b.position);
        return vecCost.mag();
    }

    public static FindPath(start: GridNode, goal: GridNode): any {
        AStar.openList = new PriorityQueue();
        AStar.openList.Add(start);
        AStar.closeList = new PriorityQueue();
        start.nodeTotalCost = 0;
        start.estimatedCost = AStar.NodeCost(start, goal);
        let node: GridNode = null;
        while (AStar.openList.Length() != 0) {
            node = AStar.openList.First();
            if ((node.position.x == goal.position.x) && (node.position.y == goal.position.y)) {
                return AStar.CalculatePath(node);
            }
            let neighbours: GridNode[] = [];
            GridManager.getInstance().GetNeighbours(node, neighbours);
            for (let i = 0; i < neighbours.length; i++) {
                let neighbourNode: GridNode = neighbours[i];
                if (!AStar.closeList.Contains(neighbourNode)) {
                    let cost: number = AStar.NodeCost(node, neighbourNode);
                    let totalCost = node.nodeTotalCost + cost;
                    let neighbourNodeEstCost = AStar.NodeCost(neighbourNode, goal);
                    neighbourNode.nodeTotalCost = totalCost;
                    neighbourNode.estimatedCost = totalCost + neighbourNodeEstCost;
                    neighbourNode.parent = node;
                    if (!AStar.openList.Contains(neighbourNode)) {
                        AStar.openList.Add(neighbourNode);
                    }
                }
            }
            AStar.closeList.Add(node);
            AStar.openList.Remove(node);
        }
        if ((node.position.x == goal.position.x) && (node.position.y == goal.position.y)) {
            console.error("Arrived Goal Path Not Found");
            return null;
        }
        return AStar.CalculatePath(node);
    }

    private static CalculatePath(node: GridNode): any {
        let list: GridNode[] = [];
        while (node != null) {
            list.push(node);
            node = node.parent;
        }
        list.reverse();
        return list;
    }
}