found

描述

found 方法是 AStar 寻路算法中的一个内置函数，用于在开放列表中查找具有最小 f 值的节点。如果找到了，则会将该节点从开放列表中移除并将其添加到关闭列表中。该函数还用于判断当前节点是否已经在关闭列表中。

语法

found(currentNode: AStarNode, endNode: AStarNode, openList: AStarNode[], closedList: AStarNode[]): boolean

参数

• currentNode: 当前节点。
• endNode: 终点节点。
• openList: 开放列表。
• closedList: 关闭列表。

返回值

返回一个布尔值，表示是否找到了具有最小 f 值的节点，并将其添加到关闭列表中。

示例

let currentNode = new AStarNode(0, 0);
let endNode = new AStarNode(5, 5);

let openList = [];
let closedList = [];

// 将起点节点添加到开放列表中
openList.push(currentNode);

while (openList.length) {
  // 每次循环都找到具有最小 f 值的节点
  currentNode = openList[0];
  for (let i = 1; i < openList.length; i++) {
    if (openList[i].f < currentNode.f) {
      currentNode = openList[i];
    }
  }

  // 将当前节点从开放列表中移除
  openList.splice(openList.indexOf(currentNode), 1);

  // 将当前节点添加到关闭列表中
  closedList.push(currentNode);

  // 判断当前节点是否是终点节点
  if (currentNode.x === endNode.x && currentNode.y === endNode.y) {
    console.log("找到终点节点");
    break;
  }

  // 找到当前节点的邻居节点
  let neighbors = currentNode.getNeighbors();
  for (let i = 0; i < neighbors.length; i++) {
    let neighbor = neighbors[i];

    // 如果邻居节点已经在关闭列表中，则跳过该节点
    if (closedList.indexOf(neighbor) !== -1) {
      continue;
    }

    // 如果邻居节点不在开放列表中，则将其添加到开放列表中
    if (openList.indexOf(neighbor) === -1) {
      openList.push(neighbor);
    }

    // 计算邻居节点的 `g` 值、`h` 值和 `f` 值
    let tempG = currentNode.g + 1;
    let tempH = Math.abs(neighbor.x - endNode.x) + Math.abs(neighbor.y - endNode.y);
    let tempF = tempG + tempH;

    // 如果计算出来的 `f` 值大于邻居节点已经有的 `f` 值，则跳过该节点
    if (tempF >= neighbor.f) {
      continue;
    }

    // 更新邻居节点的 `g` 值、`h` 值和 `f` 值，并设置其父节点为当前节点
    neighbor.g = tempG;
    neighbor.h = tempH;
    neighbor.f = tempF;
    neighbor.parent = currentNode;
  }
}

参考文献

• A* search algorithm