tower_client/assets/script/framework/navi/AStar.ts

import { Size, TiledMap, UITransform, v3, Vec2 } from "cc";
import { BinaryHeap } from "./BinaryHeap";

export namespace AStar {
    //寻路方向
    export enum Type {
        error = 0,
        four,                   //4个方向
        eight,                  //8个方向
    }

    //寻路节点
    export class Node {
        x: number = 0;
        y: number = 0;
        f: number = 0;                  //总消耗
        g: number = 0;                  //起点到当前点的消耗
        h: number = 0;                  //当前点到终点的距离
        close: boolean = false;         //是否被访问过
        prev: Node = null;              //该节点的上个节点
        idx: number = 0;                //在地图中的下标
        open: boolean = false;          //是否是在开放列表中

        constructor(x: number, y: number, idx: number) {
            this.x = x;
            this.y = y;
            this.idx = idx;
        }

        clear() {
            this.f = this.g = this.h = 0;
            this.open = this.close = false;
            this.prev = null;
        }
    }

    const oblique_cost = 1.25;                              //斜走消耗
    const straight_cost = 1;                                //直走消耗

    export class Path {
        private _node_list = new Map<number, Node>();       //节点列表
        private _found_node: Node = null;                   //找到的节点(递归用)
        private _map_size: Size = null;                     //地图尺寸
        private _tile_size: Size = null;                    //地图块尺寸
        private _start_node = new Node(0, 0, 0);            //起点节点
        private _end_node = new Node(0, 0, 0);              //终点节点
        private _path_type = Type.four;                     //寻路方向
        private _find_path: Node[] = [];                    //路径列表(tiledmap坐标)
        private _min_heap = new BinaryHeap<Node>((node: Node) => { return node.f });//开放列表二叉堆
        private _tiled_map: TiledMap = null;

        /**
         * 寻路初始化函数
         * @param nodes 地图数据(只包含可走的节点)
         * @param map 地图
         * @param type 寻路方向
         */
        constructor(nodes: Map<number, Node>, map: TiledMap, type: Type = Type.four) {
            this._node_list = nodes;
            this._tiled_map = map;
            this._map_size = this._tiled_map.getMapSize();
            this._tile_size = this._tiled_map.getTileSize();
            this._path_type = type;
        }

        /**
         * 搜索路径
         * @param start 起点(tiledmap坐标)
         * @param end 终点(tiledmap坐标)
         */
        async search(start: Vec2, end: Vec2): Promise<Node[]> {
            //清理路径节点
            this._node_list.forEach((value) => {
                value.clear();
            });
            //清理列表
            this._min_heap.clear();
            this._find_path = [];

            this._start_node.x = start.x;
            this._start_node.y = start.y;
            this._start_node.idx = this._start_node.x + this._start_node.y * this._map_size.width;
            this._start_node.clear();

            this._end_node.x = end.x;
            this._end_node.y = end.y;
            this._end_node.idx = this._end_node.x + this._end_node.y * this._map_size.width;
            this._end_node.clear();

            //开始寻路
            this._search(this._start_node);
            //删除起点
            this._find_path.shift();

            return this._find_path;
        }

        private _search(start: Node) {
            if (start.x == this._end_node.x && start.y == this._end_node.y) {
                this._found_node = start;
                this._getPrev(this._found_node);
                return true;
            }
            this._getRoundNodes(start);

            let node = this._min_heap.root();
            (node) && this._search(node);
        }

        //依次获取上个节点
        private _getPrev(node: Node) {
            if (node.prev) this._getPrev(node.prev);
            this._find_path.push(node);
        }

        //获取周围的节点
        private _getRoundNodes(current: Node) {
            current.close = true;
            current.open = false;
            //四个方向
            //上
            if (current.y != 0) {
                this._addToHeap(current.idx - this._map_size.width, current, straight_cost);
            }
            //右
            if (current.x != this._map_size.width - 1) {
                this._addToHeap(current.idx + 1, current, straight_cost);
            }
            //下
            if (current.y != this._map_size.height - 1) {
                this._addToHeap(current.idx + this._map_size.width, current, straight_cost);
            }
            //左
            if (current.x != 0) {
                this._addToHeap(current.idx - 1, current, straight_cost);
            }
            if (this._path_type == Type.eight) {
                //右上
                if (current.y != 0 && current.x != this._map_size.width - 1) {
                    this._addToHeap(current.idx - this._map_size.width + 1, current, oblique_cost);
                }
                //右下
                if (current.x != this._map_size.width - 1 && current.y != this._map_size.height - 1) {
                    this._addToHeap(current.idx + this._map_size.width + 1, current, oblique_cost);
                }
                //左下
                if (current.x != 0 && current.y != this._map_size.height - 1) {
                    this._addToHeap(current.idx + this._map_size.width - 1, current, oblique_cost);
                }
                //左上
                if (current.x != 0 && current.y != 0) {
                    this._addToHeap(current.idx - this._map_size.width - 1, current, oblique_cost);
                }
            }
        }

        private _addToHeap(idx: number, current: Node, cost: number) {
            let node = this._node_list.get(idx);
            if (node && !node.close) {
                //如果在开放列表中则从表中移除
                (node.open) && this._min_heap.remove(node);
                //更新权重
                node.prev = current;
                node.g = current.g + cost;
                node.h = Math.abs(node.x - this._end_node.x) + Math.abs(node.y - this._end_node.y);
                node.f = node.g + node.h;
                node.open = true;
                this._min_heap.insert(node);
            }
        }
    }
}