"use strict";
cc._RF.push(module, '7fbcfPuElhNDr5d2sH+uzyy', 'AStarManager');
// scripts/AStar/AStarManager.ts

"use strict";
// /**
//  * A 星算法 管理器， 提供路径查找等功能， 地图为内置， 属于定制化 Manager
//  * 
// */
var __decorate = (this && this.__decorate) || function (decorators, target, key, desc) {
    var c = arguments.length, r = c < 3 ? target : desc === null ? desc = Object.getOwnPropertyDescriptor(target, key) : desc, d;
    if (typeof Reflect === "object" && typeof Reflect.decorate === "function") r = Reflect.decorate(decorators, target, key, desc);
    else for (var i = decorators.length - 1; i >= 0; i--) if (d = decorators[i]) r = (c < 3 ? d(r) : c > 3 ? d(target, key, r) : d(target, key)) || r;
    return c > 3 && r && Object.defineProperty(target, key, r), r;
};
Object.defineProperty(exports, "__esModule", { value: true });
var BinaryHeap_1 = require("./BinaryHeap");
var _a = cc._decorator, ccclass = _a.ccclass, property = _a.property;
var AStarManager = /** @class */ (function () {
    // 私有化构造函数
    function AStarManager() {
        // 开放列表
        this.openList = new BinaryHeap_1.default();
        // 关闭列表
        this.closeList = null;
        // 哈希表 提升查找性能
        this.nodeSet = new Map();
        // 地图信息 是公共的 二维数组
        this.mapArr = [];
        // 遮挡物图层对象
        this.wallLayer = null;
        // 初始化信息
        this.initData();
        // 对于当前场景而言， 地图只需要初始化一次
        this.initMap();
    }
    AStarManager_1 = AStarManager;
    // 访问实例的唯一方式
    AStarManager.getInstance = function () {
        if (this.instance === null) {
            this.instance = new AStarManager_1();
        }
        return this.instance;
    };
    // 初始化需要动态加载的信息
    AStarManager.prototype.initData = function () {
        // 获取节点
        var node = cc.find('Canvas/Baseview/obj_map/map100');
        // 获取节点下的遮挡物组件
        this.wallLayer = node.getComponent(cc.TiledMap).getLayer('wall');
    };
    // 初始化地图 64 * 64 目前为手动设置
    AStarManager.prototype.initMap = function () {
        // 初始化地图
        for (var i = 0; i < 145; i++) { //93
            this.mapArr[i] = [];
            for (var j = 0; j < 29; j++) { // 145/5    135 / 5   27
                // 减少计算
                var temp = j * 5;
                // 初始化每一个点的坐标
                this.mapArr[i][temp] = {
                    x: i,
                    y: temp
                };
                this.mapArr[i][temp + 1] = {
                    x: i,
                    y: temp + 1
                };
                this.mapArr[i][temp + 2] = {
                    x: i,
                    y: temp + 2
                };
                this.mapArr[i][temp + 3] = {
                    x: i,
                    y: temp + 3
                };
                this.mapArr[i][temp + 4] = {
                    x: i,
                    y: temp + 4
                };
            }
        }
    };
    // 路径查找， 传入坐标点 
    AStarManager.prototype.findPath = function (beginPoint, endPoint) {
        var _a = this, closeList = _a.closeList, openList = _a.openList, mapArr = _a.mapArr, nodeSet = _a.nodeSet, findNearNodeToOpenList = this.findNearNodeToOpenList.bind(this);
        // 先清除一遍
        this.openList.clear();
        // hast表清空
        nodeSet.clear();
        // 绑定this
        // 重置开放列表和关闭列表
        closeList = this.closeList = [];
        openList = this.openList;
        // 传入的起点坐标和终点坐标一致，应该如何处理
        if (beginPoint.x === endPoint.x && beginPoint.y === endPoint.y) {
            console.log('起点和终点位置相同');
            return null;
        }
        // 判断传入的数值是否是非法
        if (beginPoint.x >= mapArr.length ||
            endPoint.x >= mapArr.length ||
            beginPoint.y >= mapArr[0].length ||
            endPoint.y >= mapArr[0].length) {
            console.log('传入坐标非法');
            return null;
        }
        // 初始化起点节点
        var startNode = {
            x: beginPoint.x,
            y: beginPoint.y,
            g: 0, h: 0, f: 0,
            parent: null
        };
        // 将当前起点坐标传入关闭列表中
        closeList.push(startNode);
        // 初始化hash
        nodeSet.set(startNode.x + ',' + startNode.y, 1);
        // 开始寻路 当前场景不进行斜边寻路 如果在地图周围都围上一层空白的墙，可以减少掉很多程序判断的过程
        while (true) {
            var startNodeX = startNode.x, startNodeY = startNode.y;
            // {x-1,y} 
            findNearNodeToOpenList(startNodeX - 1, startNodeY, endPoint, startNode);
            // {x,y-1}
            findNearNodeToOpenList(startNodeX, startNodeY - 1, endPoint, startNode);
            // {x,y+1}
            findNearNodeToOpenList(startNodeX, startNodeY + 1, endPoint, startNode);
            // {x+1,y}
            findNearNodeToOpenList(startNodeX + 1, startNodeY, endPoint, startNode);
            // 记录下一次的起点
            startNode = openList.shift();
            // 取出f值最小的那位， 放入closeList中
            closeList.push(startNode);
            if (!startNode) {
                return null;
            }
            // 判断起点是否和终点相同 或者循环次数达到性能峰值
            if (openList.getLength() <= 0) {
                console.warn('未找到可行路径');
                // 路径被穷尽
                return null;
            }
            else if (startNode.x === endPoint.x && startNode.y === endPoint.y) { // 是否没有寻找到路径
                // 查找到路径 存放的数组
                var pathList = [];
                // 取出最后一位节点
                var lastNode = closeList[closeList.length - 1];
                pathList.push(lastNode);
                // 开始回溯
                while (lastNode.parent !== null) {
                    // 插入节点
                    pathList.unshift(lastNode.parent);
                    // 循环引用
                    lastNode = lastNode.parent;
                }
                // 弹出路径列表
                return pathList;
            }
        }
    };
    // 寻找周围的坐标， 并且将其加入openList中
    AStarManager.prototype.findNearNodeToOpenList = function (x, y, endNode, parentNode) {
        var _a = this, mapArr = _a.mapArr, wallLayer = _a.wallLayer, openList = _a.openList, nodeSet = _a.nodeSet, g = 1, key, h, pathNode;
        // 判断传入的数值是否是非法 坐标超出边界
        if (x >= mapArr.length ||
            x < 0 ||
            y >= mapArr[0].length ||
            y < 0)
            return null;
        // 再次判断当前点是否是可通行路径，  
        if (wallLayer.getTileGIDAt(x, y) !== 0)
            return;
        //根据房间是否解锁来解锁寻路
        // if (wallLayer.getTileGIDAt(x, y) == 0) return
        // if (wallLayer.getTileGIDAt(x, y) == 17) return;
        // if (wallLayer.getTileGIDAt(x, y) == 18) return;
        // if (wallLayer.getTileGIDAt(x, y) == 19) return;
        // if (wallLayer.getTileGIDAt(x, y) == 20) return;
        // 保存下key，后面还要使用
        key = x + ',' + y;
        // 判断当前点是否存在于 开放列表或者关闭列表中 如果存在则直接返回
        if (nodeSet.has(key))
            return;
        // 通路， 计算 g， f， h
        // 计算离起点距离， 起点距离就是 当前点的g值， 加上父节点的g值
        g = g + parentNode.g;
        // 离终点距离 曼哈顿式
        h = Math.abs(x - endNode.x) + Math.abs(y - endNode.y);
        // h = (x - endNode.x) * (((x - endNode.x) >> 31 << 1) + 1) + (x - endNode.x) * (((x - endNode.x) >> 31 << 1) + 1)
        // 路径节点
        pathNode = {
            x: x, y: y, g: g, h: h,
            f: g + h,
            // 回溯所需父节点
            parent: parentNode
        };
        // 加入开放列表中
        openList.insert(pathNode);
        // 存入hash
        nodeSet.set(key, 1);
        return true;
    };
    var AStarManager_1;
    // 单例
    AStarManager.instance = null;
    AStarManager = AStarManager_1 = __decorate([
        ccclass
    ], AStarManager);
    return AStarManager;
}());
exports.default = AStarManager;
/**
 * hash 表查找优化
 *  A 星查找路径中，当其获取到一个点，他要去开放列表和关闭列表中查看是否有这个值，比对的就是x，y值
 *  如果有就退出程序，如果没有则加入开放列表
 *  存储的key 以这种形式 x + ',' + y -> 3,23 保证不重复 字符串形式
 *
 *  经数据证实， 大数据下Map的查找比Set快
 *
 *  大体优化已完成
 *    细节优化：
 *      1. 减少while 中的function，set，get
 *          function 的执行会进入调用栈，减少function可以减少调用栈
 *
 *  初始化优化：
 *    一开始生成地图数组信息，需要双层循环，这两层循环数量太大，93 * 135 = 12555 初始化需要上万次循环
 *
 *    减少循环次数，在同一个循环中处理更多的事情 在第二层for循环中，减少循环次数，增加每次循环做的事情， 那么初始化循环只需要执行 2000多次
 *
 *
*/

cc._RF.pop();