// /**
//  * A 星算法 管理器， 提供路径查找等功能， 地图为内置， 属于定制化 Manager
//  * 
// */

// // 导入节点的数据结构
// import AStarNode from './AStarNode'
// import BinaryHeap from './BinaryHeap';

// const { ccclass, property } = cc._decorator;

// // 定义坐标接口
// interface Coordinate {
//   x: number,
//   y: number
// }

// @ccclass
// export default class AStarManager {

//   // 开放列表
//   public openList: Array<AStarNode> = null
//   // 关闭列表
//   public closeList: Array<AStarNode> = null

//   // 地图信息 是公共的 二维数组
//   public mapArr: Array<Array<Coordinate>> = []

//   // 遮挡物图层对象
//   wallLayer: cc.TiledLayer = null

//   // 单例
//   public static instance: AStarManager = null
//   // 访问实例的唯一方式
//   public static getInstance(): AStarManager {
//     if (this.instance === null) {
//       this.instance = new AStarManager()
//     }
//     return this.instance
//   }

//   // 私有化构造函数
//   private constructor() {
//     // 初始化信息
//     this.initData()
//     // 对于当前场景而言， 地图只需要初始化一次
//     this.initMap()
//   }

//   // 初始化需要动态加载的信息
//   public initData() {
//     // 获取节点
//     let node: cc.Node = cc.find('Canvas/Baseview/obj_map/map100')
//     // 获取节点下的遮挡物组件
//     this.wallLayer = node.getComponent(cc.TiledMap).getLayer('wall')
//   }

//   // 初始化地图 64 * 64 目前为手动设置
//   public initMap() {
//     let row = 70

//     // 初始化地图
//     for (let i = 0; i < 93; i++) {
//       this.mapArr[i] = []
//       for (let j = 0; j < 135; j++) {
//         // 初始化每一个点的坐标
//         this.mapArr[i][j] = {
//           x: i,
//           y: j
//         }
//       }
//     }

//   }

//   // 路径查找， 传入坐标点 
//   public findPath(beginPoint: Coordinate, endPoint: Coordinate): Array<Coordinate> {
//     // cc.log(beginPoint, endPoint)

//     let { closeList, openList, mapArr } = 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
//     }

//     // 初始化起点节点
//     let startNode: AStarNode = {
//       x: beginPoint.x,
//       y: beginPoint.y,
//       g: 0, h: 0, f: 0,
//       parent: null
//     }

//     // 将当前起点坐标传入关闭列表中
//     closeList.push(startNode)

//     // 开始寻路 当前场景不进行斜边寻路 如果在地图周围都围上一层空白的墙，可以减少掉很多程序判断的过程
//     while (true) {

//       let { x: startNodeX, y: startNodeY } = startNode
//       // {x-1,y}
//       this.findNearNodeToOpenList(startNodeX - 1, startNodeY, 1, endPoint, startNode)
//       // {x,y-1}
//       this.findNearNodeToOpenList(startNodeX, startNodeY - 1, 1, endPoint, startNode)
//       // {x,y+1}
//       this.findNearNodeToOpenList(startNodeX, startNodeY + 1, 1, endPoint, startNode)
//       // {x+1,y}
//       this.findNearNodeToOpenList(startNodeX + 1, startNodeY, 1, endPoint, startNode)

//       // 将开放列表作为升序排列
//       openList.sort((a, b) => a.f - b.f)
//       // 随机打乱路径 排序竟然占用了超过一半的执行时间
//       // openList.sort((a, b) => Math.random() - 0.5)
//       // 记录下一次的起点
//       startNode = openList.shift()

//       // 取出f值最小的那位， 放入closeList中
//       closeList.push(startNode)

//       // 判断起点是否和终点相同 或者循环次数达到性能峰值
//       if (startNode.x === endPoint.x && startNode.y === endPoint.y) {

//         // 查找到路径 存放的数组
//         let pathList = []

//         // 取出最后一位节点
//         let lastNode = closeList[closeList.length - 1]

//         pathList.push(lastNode)

//         // 开始回溯
//         while (lastNode.parent !== null) {
//           // 插入节点
//           pathList.unshift(lastNode.parent)
//           // 循环引用
//           lastNode = lastNode.parent
//         }

//         // 弹出路径列表
//         return pathList
//       } else if (openList.length <= 0) { // 是否没有寻找到路径
//         console.warn('未找到可行路径')
//         // console.log(endPoint)
//         // 路径被穷尽
//         return null
//       }

//     }

//   }

//   // 寻找周围的坐标， 并且将其加入openList中
//   public findNearNodeToOpenList(x: number, y: number, g: number, endNode: Coordinate, parentNode: AStarNode) {
//     let { mapArr, wallLayer, openList, closeList } = this

//     // 判断传入的数值是否是非法 坐标超出边界
//     if (x >= mapArr.length ||
//       x < 0 ||
//       y >= mapArr[0].length ||
//       y < 0) {
//       return null
//     }

//     // 再次判断当前点是否是可通行路径，  
//     if (wallLayer.getTileGIDAt(x, y) !== 0) {
//       // 不可通路
//       return null
//     }

//     // 判断当前点是否存在于 开放列表或者关闭列表中 优化版本2 速度提升大约2毫秒
//     let isFlag = false
//     if (openList.length >= closeList.length) {
//       openList.find((item, index) => {
//         // 记录临时变量
//         let temp = closeList[index]
//         // 比对当前
//         if (x === item.x && y === item.y) {
//           return isFlag = true
//         } else if (temp && x === temp.x && y === temp.y) {
//           return isFlag = true
//         }
//       })

//     } else {
//       closeList.find((item, index) => {
//         // 记录临时变量
//         let temp = openList[index]
//         // 比对当前
//         if (x === item.x && y === item.y) {
//           return isFlag = true
//         } else if (temp && x === temp.x && y === temp.y) {
//           return isFlag = true
//         }
//       })

//     }
//     if (isFlag) {
//       return null
//     }

//     // 通路， 计算 g， f， h
//     // 计算离起点距离， 起点距离就是 当前点的g值， 加上父节点的g值
//     g = g + parentNode.g
//     // 离终点距离 曼哈顿式
//     let h = Math.abs(x - endNode.x) + Math.abs(y - endNode.y)
//     // 欧几里得式
//     // let h = Math.sqrt(Math.abs(x - endNode.x) ** 2 + Math.abs(y - endNode.y) ** 2)

//     let pathNode: AStarNode = {
//       x, y, g, h,
//       f: g + h,
//       // 回溯所需父节点
//       parent: parentNode
//     }

//     // 加入开放列表中
//     openList.push(pathNode)

//     return true
//   }

// }

// // 调用方式
// // AStarManager.getInstance().findPath(起点坐标， 终点坐标)



// /**
//  * A 星算法 管理器， 提供路径查找等功能， 地图为内置， 属于定制化 Manager
//  * 优化版本 1 二叉堆优化
// */

// // 导入节点的数据结构
// import AStarNode from './AStarNode'
// import BinaryHeap from './BinaryHeap';

// const { ccclass, property } = cc._decorator;

// // 定义坐标接口
// interface Coordinate {
//   x: number,
//   y: number
// }

// @ccclass
// export default class AStarManager {

//   // 开放列表
//   protected openList: BinaryHeap = new BinaryHeap()
//   // 关闭列表
//   protected closeList: Array<AStarNode> = null

//   // 地图信息 是公共的 二维数组
//   public mapArr: Array<Array<Coordinate>> = []

//   // 遮挡物图层对象
//   wallLayer: cc.TiledLayer = null

//   // 单例
//   public static instance: AStarManager = null
//   // 访问实例的唯一方式
//   public static getInstance(): AStarManager {
//     if (this.instance === null) {
//       this.instance = new AStarManager()
//     }
//     return this.instance
//   }

//   // 私有化构造函数
//   private constructor() {
//     // 初始化信息
//     this.initData()
//     // 对于当前场景而言， 地图只需要初始化一次
//     this.initMap()
//   }

//   // 初始化需要动态加载的信息
//   public initData() {
//     // 获取节点
//     let node: cc.Node = cc.find('Canvas/Baseview/obj_map/map100')
//     // 获取节点下的遮挡物组件
//     this.wallLayer = node.getComponent(cc.TiledMap).getLayer('wall')
//   }

//   // 初始化地图 64 * 64 目前为手动设置
//   public initMap() {
//     let row = 70

//     // 初始化地图
//     for (let i = 0; i < 93; i++) {
//       this.mapArr[i] = []
//       for (let j = 0; j < 135; j++) {
//         // 初始化每一个点的坐标
//         this.mapArr[i][j] = {
//           x: i,
//           y: j
//         }
//       }
//     }

//   }

//   // 路径查找， 传入坐标点 
//   public findPath(beginPoint: Coordinate, endPoint: Coordinate): Array<Coordinate> {
//     let { closeList, openList, mapArr } = this

//     // 先清除一遍
//     this.openList.clear()

//     // 重置开放列表和关闭列表
//     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
//     }

//     // 初始化起点节点
//     let startNode: AStarNode = {
//       x: beginPoint.x,
//       y: beginPoint.y,
//       g: 0, h: 0, f: 0,
//       parent: null
//     }

//     // 将当前起点坐标传入关闭列表中
//     closeList.push(startNode)

//     // 初始化hash

//     // 开始寻路 当前场景不进行斜边寻路 如果在地图周围都围上一层空白的墙，可以减少掉很多程序判断的过程
//     while (true) {
//       let { x: startNodeX, y: startNodeY } = startNode

//       // {x-1,y} 
//       this.findNearNodeToOpenList(startNodeX - 1, startNodeY, 1, endPoint, startNode)
//       // {x,y-1}
//       this.findNearNodeToOpenList(startNodeX, startNodeY - 1, 1, endPoint, startNode)
//       // {x,y+1}
//       this.findNearNodeToOpenList(startNodeX, startNodeY + 1, 1, endPoint, startNode)
//       // {x+1,y}
//       this.findNearNodeToOpenList(startNodeX + 1, startNodeY, 1, endPoint, startNode)

//       // hash(startNode)

//       // 记录下一次的起点
//       startNode = openList.shift()

//       // 取出f值最小的那位， 放入closeList中
//       closeList.push(startNode)

//       // 判断起点是否和终点相同 或者循环次数达到性能峰值
//       if (startNode.x === endPoint.x && startNode.y === endPoint.y) {

//         // 查找到路径 存放的数组
//         let pathList = []

//         // 取出最后一位节点
//         let lastNode = closeList[closeList.length - 1]

//         pathList.push(lastNode)

//         // 开始回溯
//         while (lastNode.parent !== null) {
//           // 插入节点
//           pathList.unshift(lastNode.parent)
//           // 循环引用
//           lastNode = lastNode.parent
//         }

//         // 弹出路径列表
//         return pathList
//       } else if (openList.getLength() <= 0) { // 是否没有寻找到路径
//         console.warn('未找到可行路径')
//         // console.log(endPoint)
//         // 路径被穷尽
//         return null
//       }

//     }

//   }

//   // 寻找周围的坐标， 并且将其加入openList中
//   public findNearNodeToOpenList(x: number, y: number, g: number, endNode: Coordinate, parentNode: AStarNode) {
//     let { mapArr, wallLayer, openList, closeList } = this

//     // 判断传入的数值是否是非法 坐标超出边界
//     if (x >= mapArr.length ||
//       x < 0 ||
//       y >= mapArr[0].length ||
//       y < 0) {
//       return null
//     }

//     // 再次判断当前点是否是可通行路径，  
//     if (wallLayer.getTileGIDAt(x, y) !== 0) {
//       // 不可通路
//       return null
//     }

//     // 判断当前点是否存在于 开放列表或者关闭列表中
//     let isFlag = false
//     if (openList.getLength() >= closeList.length) {
//       openList.find((item, index) => {
//         // 记录临时变量
//         let temp = closeList[index]
//         // 比对当前
//         if (x === item.x && y === item.y) {
//           return isFlag = true
//         } else if (temp && x === temp.x && y === temp.y) {
//           return isFlag = true
//         }
//       })

//     } else {
//       closeList.find((item, index) => {
//         // 记录临时变量
//         let temp = openList.getOfIndex(index)
//         // 比对当前
//         if (x === item.x && y === item.y) {
//           return isFlag = true
//         } else if (temp && x === temp.x && y === temp.y) {
//           return isFlag = true
//         }
//       })

//     }
//     if (isFlag) {
//       return null
//     }

//     // 通路， 计算 g， f， h
//     // 计算离起点距离， 起点距离就是 当前点的g值， 加上父节点的g值
//     g = g + parentNode.g
//     // 离终点距离 曼哈顿式
//     let h = Math.abs(x - endNode.x) + Math.abs(y - endNode.y)
//     // 欧几里得式
//     // let h = Math.sqrt(Math.abs(x - endNode.x) ** 2 + Math.abs(y - endNode.y) ** 2)

//     let pathNode: AStarNode = {
//       x, y, g, h,
//       f: g + h,
//       // 回溯所需父节点
//       parent: parentNode
//     }

//     // 加入开放列表中
//     openList.insert(pathNode)
//     // 2存入hash

//     return true
//   }

// }

// 调用方式
// AStarManager.getInstance().findPath(起点坐标， 终点坐标)

/**
 * 目前还可以再优化的地方就是数据查找的情况
 * 数组的查找效率一般
 *  希望能有一种更快的方式查找数据，比方说直接传入对象
 *  用空间换时间
 * 
 * 
 *  判断当前点是否存在于开放列表或者关闭列表中：
 *  
 *   hash(node) -> 121xxxx8381
 *   判断某个对象中是否存在有这个键值
 *   对象通用
 *     // 哈希表 提升查找性能
  protected nodeSet = new Set()
 *   
 * 
*/


/**
 * A 星算法 管理器， 提供路径查找等功能， 地图为内置， 属于定制化 Manager
 * 优化版本 2 hash表查找优化
*/

// 导入节点的数据结构
import AStarNode from './AStarNode'
import BinaryHeap from './BinaryHeap';

const { ccclass, property } = cc._decorator;

// 定义坐标接口
interface Coordinate {
  x: number,
  y: number
}

@ccclass
export default class AStarManager {

  // 开放列表
  protected openList: BinaryHeap = new BinaryHeap()
  // 关闭列表
  protected closeList: Array<AStarNode> = null
  // 哈希表 提升查找性能
  protected nodeSet = new Map()

  // 地图信息 是公共的 二维数组
  public mapArr: Array<Array<Coordinate>> = []

  // 遮挡物图层对象
  wallLayer: cc.TiledLayer = null

  // 单例
  public static instance: AStarManager = null
  // 访问实例的唯一方式
  public static getInstance(): AStarManager {
    if (this.instance === null) {
      this.instance = new AStarManager()
    }
    return this.instance
  }

  // 私有化构造函数
  private constructor() {
    // 初始化信息
    this.initData()
    // 对于当前场景而言， 地图只需要初始化一次
    this.initMap()
  }

  // 初始化需要动态加载的信息
  public initData() {
    // 获取节点
    let node: cc.Node = cc.find('Canvas/Baseview/obj_map/map100')
    // 获取节点下的遮挡物组件
    this.wallLayer = node.getComponent(cc.TiledMap).getLayer('wall')
  }

  // 初始化地图 64 * 64 目前为手动设置
  public initMap() {
    // 初始化地图
    for (let i = 0; i < 145; i++) {    //93
      this.mapArr[i] = []
      for (let j = 0; j < 29; j++) { // 145/5    135 / 5   27
        // 减少计算
        let 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
        }
      }
    }

  }

  // 路径查找， 传入坐标点 
  public findPath(beginPoint: Coordinate, endPoint: Coordinate): Array<Coordinate> {
    let { closeList, openList, mapArr, nodeSet } = this,
      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
    }

    // 初始化起点节点
    let startNode: AStarNode = {
      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) {
      let { x: startNodeX, y: startNodeY } = startNode
      // {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) { // 是否没有寻找到路径
        // 查找到路径 存放的数组
        let pathList = []

        // 取出最后一位节点
        let lastNode = closeList[closeList.length - 1]

        pathList.push(lastNode)
        // 开始回溯
        while (lastNode.parent !== null) {
          // 插入节点
          pathList.unshift(lastNode.parent)
          // 循环引用
          lastNode = lastNode.parent
        }
        // 弹出路径列表
        return pathList
      }

    }

  }

  // 寻找周围的坐标， 并且将其加入openList中
  public findNearNodeToOpenList(x: number, y: number, endNode: Coordinate, parentNode: AStarNode) {
    let { mapArr, wallLayer, openList, nodeSet } = this,
      g = 1, key, h, pathNode: AStarNode;

    // 判断传入的数值是否是非法 坐标超出边界
    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, y, g, h,
      f: g + h,
      // 回溯所需父节点
      parent: parentNode
    }

    // 加入开放列表中
    openList.insert(pathNode)
    // 存入hash
    nodeSet.set(key, 1)

    return true
  }

  // 输入x,y -> 转出 'x,y'
  // private _trans(x, y): string {
  //   return x + ',' + y
  // }

}

/**
 * hash 表查找优化
 *  A 星查找路径中，当其获取到一个点，他要去开放列表和关闭列表中查看是否有这个值，比对的就是x，y值
 *  如果有就退出程序，如果没有则加入开放列表
 *  存储的key 以这种形式 x + ',' + y -> 3,23 保证不重复 字符串形式
 *
 *  经数据证实， 大数据下Map的查找比Set快
 *
 *  大体优化已完成
 *    细节优化：
 *      1. 减少while 中的function，set，get
 *          function 的执行会进入调用栈，减少function可以减少调用栈
 *
 *  初始化优化：
 *    一开始生成地图数组信息，需要双层循环，这两层循环数量太大，93 * 135 = 12555 初始化需要上万次循环
 *
 *    减少循环次数，在同一个循环中处理更多的事情 在第二层for循环中，减少循环次数，增加每次循环做的事情， 那么初始化循环只需要执行 2000多次
 * 
 *
*/
