CocosCreator中使用A*进行物体寻路

摘要

使用前需要先生成对应的网格坐标信息。

版本说明

使用 CocosCreator 的 2.4.3 版本。

开始

效果演示：

介绍：

1.红色点代表空白可执行区域

2.蓝色点代表障碍物

3.如何生成对应方格

代码：

import { Data } from "./Data";

const {ccclass, property} = cc._decorator;

@ccclass
export default class NewClass extends cc.Component {

    // @property(cc.Label)
    // label: cc.Label = null;
    @property(cc.Node) startNode:cc.Node = null;
    @property(cc.Node) endNode:cc.Node = null;

    // onLoad () {}
    queueArr = [];
    lcArr =[];
    atSquareWidth = 0;
    forNode = {};
    isEnd = false;

    test = null;
    start () {
        this.lcArr = Data.lcArr;
        this.atSquareWidth = Data.squareWidth;
    }
    startBtn(){
        let _rowColumn = this.xyTransitionRowColum(this.startNode.x,this.startNode.y,Data.squareWidth);
        // 开始使用A*进行寻路
        // this.AStartSeek(_rowColumn);
        this.test = this.AStarSearch(_rowColumn);
        this.test.next();
    }

    *AStarSearch(start){
        let _end = this.xyTransitionRowColum(this.endNode.x,this.endNode.y,Data.squareWidth);
        // 存放所有探索中的方块 根据代价排序 去除代价最低的方块
        let frontier = this.queueArr;
        let _rowColumn = this.xyTransitionRowColum(this.startNode.x,this.startNode.y,Data.squareWidth);
        // 先存放一个元素，起点，代价为0
        this.enqueue(_rowColumn,0);
        // 当前方块到之前方块的映射,代表路径的来向
        let came_from = {};
        // 代表了方块的当前代价
        let cost_so_far = {};
        let _far = `${_rowColumn.row}*${_rowColumn.column}`;
        // 起点的来向置空
        came_from[_far] = null;
        // 当前代价为0
        cost_so_far[_far] = 0;
        while(frontier.length){
            // 从优先队列中取出代价最小的出列
            let current = this.dequeue();
            // 检测方块是否为终点块
            if(current.row == _end.row && current.column == _end.column){
                current.node.color = new cc.Color(211,25,215);
                break;
            }
            let g_cost = this.getNeighbors(current);
            for(let next in g_cost){
                // 计算当前方块的新代价,之前代价 + 网格  因为用的是网格这里是+1
                let new_cost = cost_so_far[`${current.row}*${current.column}`] + 1;
                // 把行列组成字符串用作key值
                let nextRCString = `${g_cost[next].row}*${g_cost[next].column}`;
                // 如果next没有被探索 或者next的当前代价比之前得到的代价还要低
                if(!cost_so_far[nextRCString] || new_cost < cost_so_far[nextRCString]){
                    // 更新最新代价
                    cost_so_far[nextRCString] = new_cost;
                    console.log(new_cost);
                    // 使用曼哈顿得到预估代价
                    let priority = new_cost + this.heuristic(_end,g_cost[next]);
                    this.enqueue(g_cost[next],priority);
                    g_cost[next].node.color = new cc.Color(255,25,255);
                    this.scheduleOnce(()=>{
                        this.test.next();
                    },0.02);
                    yield 
                    came_from[nextRCString] = current;
                }
            }
        }
        // 倒推得到路径
        // 要寻找的目标位置
        let _curr = `${_end.row}*${_end.column}`;
        // 开始时的目标位置
        let _sta = `${_rowColumn.row}*${_rowColumn.column}`;
        // 存储路径数组
        let path = [];
        while (_curr != _sta){
            if(came_from[_curr].node){
                came_from[_curr].node.color = new cc.Color(65,25,215);
            }
            path.push(_curr);
            _curr = `${came_from[_curr].row}*${came_from[_curr].column}`;
            
        }
        console.log('------完成',path);
        console.log('------完成',Object.keys(came_from).length);
        console.log('------完成',came_from);
        console.log('------完成',cost_so_far);
    }

    /**
     * 根据一个点获取周围的四个点，不包括障碍物
     * @param _rowColumn {row,column}当前网格的行列
     */
    getNeighbors(_rowColumn){
        let next = [
            {row:0,column:+1},// 右
            {row:-1,column:0}, // 下
            {row:0,column:-1}, // 左
            {row:+1,column:0} // 上
        ];
        let _arr = [];
        for(let i = 0;i<4;i++){
            let _row = _rowColumn.row + next[i]['row'];
            let _column = _rowColumn.column + next[i]['column'];
            let _nodeData = this.lcArr[ _row -1];
            let nextRow = _nodeData;
            let nextColum = _column - 1;
            if(nextRow && nextRow[nextColum] && nextRow[nextColum]['type'] != undefined && nextRow[nextColum]['type'] != 1){
                // 拿到新的
                let node = nextRow[nextColum]['node'];
                _arr.push({row:_row,column:_column,node:node});
            } else {
                continue;
            }
        }
        return _arr;
    }
    /**
     * 曼哈顿距离计算
     * @param a {row，column} 结束物品的行列
     * @param b {row，column} 当前网格的行列
     * @returns 
     */
    heuristic(a,b){
       let x1 = a.row;
       let y1 = a.column;
       let x2 = b.row;
       let y2 = b.column;
       return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }
    /**
     * 队列入列
     * @param data 
     */
    enqueue(data, priority){
        let node = {data:data,priority:priority};
        if (!this.queueArr.length) {
            this.queueArr.push(node);
        } else {
            let isEnqueue = false; // 是否已入队
            for (let i = 0; i < this.queueArr.length; i++) {
                if (this.queueArr[i].priority < node.priority) {
                  this.queueArr.splice(i, 0, node);
                  isEnqueue = true;
                  break;
                }
            }
            // 循环后未入队，即优先级最小，插入队尾
            if (!isEnqueue) {
                this.queueArr.push(node);
            }
        }
    }
    /**
     * 队列出列从尾部出
     * @returns 
     */
    dequeue() {
        if (this.queueArr.length) {
        //   let _arr = this.queueArr.shift();
          let _arr = this.queueArr.pop();
          return _arr['data'];
        }
      }
    /**
     * x，y 转换成行 列
     * @param x      需要转换行列的x位置
     * @param y      需要转换行列的y位置
     * @param width  正方形的宽度边长
     */
    xyTransitionRowColum (x,y,width){
        // 根据x判断第几列
        let _x = Math.ceil(x / width); 
        // 判断是第几行
        let _y = Math.ceil(y / width); 
        return {row:_y,column:_x};
    }
    /**
     * 行列转换成 x y 当前方块的中心位置
     * @param x      需要转换行列的x位置
     * @param y      需要转换行列的y位置
     */
     rowColumTransitionXY (r,c){
        let _b = this.atSquareWidth / 2;
        let _row = r * this.atSquareWidth - _b;
        let _column = c * this.atSquareWidth - _b;
        return {x:_column,y:_row};
    }

}