cocos creator ts 写一个二叉堆排双向A星并写出使用示例

好的，下面是一个 TypeScript 实现的二叉堆和双向 A* 算法，并且提供了一个使用示例。需要注意的是，由于本示例中使用了 Cocos Creator 的 API，因此需要在 Cocos Creator 项目中使用 TypeScript 脚本来运行。

// 定义二叉堆节点
class HeapNode<T> {
  public value: T;
  public priority: number;

  constructor(value: T, priority: number) {
    this.value = value;
    this.priority = priority;
  }
}

// 定义二叉堆
class BinaryHeap<T> {
  private heap: HeapNode<T>[];

  constructor() {
    this.heap = [];
  }

  // 获取堆的长度
  public get length(): number {
    return this.heap.length;
  }

  // 添加节点
  public push(value: T, priority: number): void {
    const node = new HeapNode(value, priority);
    this.heap.push(node);
    this.bubbleUp(this.heap.length - 1);
  }

  // 弹出节点
  public pop(): T {
    const result = this.heap[0].value;
    const end = this.heap.pop();

    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown(0);
    }

    return result;
  }

  // 调整节点位置，使其上浮
  private bubbleUp(index: number): void {
    const node = this.heap[index];

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parentNode = this.heap[parentIndex];

      if (node.priority >= parentNode.priority) {
        break;
      }

      this.heap[parentIndex] = node;
      this.heap[index] = parentNode;
      index = parentIndex;
    }
  }

  // 调整节点位置，使其下沉
  private sinkDown(index: number): void {
    const length = this.heap.length;
    const node = this.heap[index];

    while (true) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      let leftChildNode: HeapNode<T>, rightChildNode: HeapNode<T>;
      let swapIndex = -1;

      if (leftChildIndex < length) {
        leftChildNode = this.heap[leftChildIndex];

        if (leftChildNode.priority < node.priority) {
          swapIndex = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        rightChildNode = this.heap[rightChildIndex];

        if (
          (swapIndex === -1 && rightChildNode.priority < node.priority) ||
          (swapIndex !== -1 && rightChildNode.priority < leftChildNode.priority)
        ) {
          swapIndex = rightChildIndex;
        }
      }

      if (swapIndex === -1) {
        break;
      }

      this.heap[index] = this.heap[swapIndex];
      this.heap[swapIndex] = node;
      index = swapIndex;
    }
  }
}

// 定义节点
interface Node {
  x: number;
  y: number;
}

// 定义地图
type Map = number[][];

// 定义 A* 算法
class AStar {
  private map: Map;
  private start: Node;
  private end: Node;
  private openList: BinaryHeap<Node>;
  private closeList: Set<string>;

  constructor(map: Map, start: Node, end: Node) {
    this.map = map;
    this.start = start;
    this.end = end;
    this.openList = new BinaryHeap<Node>();
    this.closeList = new Set<string>();
  }

  // 计算两点之间的距离
  private distance(nodeA: Node, nodeB: Node): number {
    const dx = nodeA.x - nodeB.x;
    const dy = nodeA.y - nodeB.y;
    return Math.sqrt(dx * dx + dy * dy);
  }

  // 获取节点的周围节点
  private getNeighbors(node: Node): Node[] {
    const neighbors = [];
    const x = node.x;
    const y = node.y;

    for (let i = -1; i <= 1; i++) {
      for (let j = -1; j <= 1; j++) {
        if (i === 0 && j === 0) {
          continue;
        }

        const nx = x + i;
        const ny = y + j;

        if (
          nx < 0 ||
          nx >= this.map.length ||
          ny < 0 ||
          ny >= this.map[0].length ||
          this.map[nx][ny] !== 0
        ) {
          continue;
        }

        neighbors.push({ x: nx, y: ny });
      }
    }

    return neighbors;
  }

  // 计算路径
  public findPath(): Node[] {
    this.openList.push(this.start, 0);

    while (this.openList.length > 0) {
      const currentNode = this.openList.pop();

      if (currentNode.x === this.end.x && currentNode.y === this.end.y) {
        const path = [];

        while (currentNode.x !== this.start.x || currentNode.y !== this.start.y) {
          path.push(currentNode);
          currentNode = currentNode.parent;
        }

        path.push(this.start);
        return path.reverse();
      }

      const neighbors = this.getNeighbors(currentNode);

      for (const neighbor of neighbors) {
        const neighborKey = `${neighbor.x},${neighbor.y}`;

        if (this.closeList.has(neighborKey)) {
          continue;
        }

        const gScore = currentNode.gScore + this.distance(currentNode, neighbor);
        const hScore = this.distance(neighbor, this.end);
        const fScore = gScore + hScore;

        if (!this.openListContains(neighborKey)) {
          const neighborNode = {
            x: neighbor.x,
            y: neighbor.y,
            parent: currentNode,
            gScore: gScore,
            hScore: hScore,
            fScore: fScore,
          };
          this.openList.push(neighborNode, fScore);
        } else {
          const neighborNode = this.getOpenListNode(neighborKey);

          if (gScore < neighborNode.gScore) {
            neighborNode.parent = currentNode;
            neighborNode.gScore = gScore;
            neighborNode.hScore = hScore;
            neighborNode.fScore = fScore;
          }
        }
      }

      this.closeList.add(`${currentNode.x},${currentNode.y}`);
    }

    return null;
  }

  // 判断 openList 中是否包含指定节点
  private openListContains(neighborKey: string): boolean {
    for (const node of this.openList) {
      if (node.x === +neighborKey.split(',')[0] && node.y === +neighborKey.split(',')[1]) {
        return true;
      }
    }

    return false;
  }

  // 获取 openList 中的指定节点
  private getOpenListNode(neighborKey: string): any {
    for (const node of this.openList) {
      if (node.x === +neighborKey.split(',')[0] && node.y === +neighborKey.split(',')[1]) {
        return node;
      }
    }

    return null;
  }
}

// 使用示例
const map: Map = [
  [0, 0, 0, 0, 0],
  [0, 1, 1, 0, 0],
  [0, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 0, 0],
];

const start: Node = { x: 1, y: 1 };
const end: Node = { x: 3, y: 3 };
const aStar = new AStar(map, start, end);
const path = aStar.findPath();

if (path) {
  console.log(path);
} else {
  console.log('Path not found.');
}

在上面的示例中，我们首先定义了一个 `HeapNode` 类和一个 `BinaryHeap` 类，用于实现二叉堆。然后定义了一个 `AStar` 类，用于实现双向 A* 算法。在 `AStar` 类中，我们实现了 `distance` 方法用于计算两点之间的距离，实现了 `getNeighbors` 方法用于获取节点的周围节点，实现了 `findPath` 方法用于计算路径。最后，我们提供了一个使用示例，该示例使用了一个 5x5 的地图，并从 (1,1) 点开始，到 (3,3) 点结束，计算了一条路径，并将路径打印到控制台中。