Двунаправленный A* (A-Star), не возвращающий кратчайший путь

По какой-то причине моя реализация двунаправленного A* не возвращает кратчайший путь в очень специфических инициализациях графа.

Я выполняю два поиска A*, один из источника в пункт назначения и один из пункта назначения в источник. Из того, что я читал, когда замкнутые множества для обоих этих поисков пересекаются, мы соединяем кратчайшие пути из обоих поисков и находим кратчайший путь.

Проблема заключается в том, что в очень специфических ситуациях замкнутые наборы для обоих поисков пересекаются до того, как поиски могут фактически обнаружить узлы, которые должны быть включены в их соответствующие кратчайшие пути. Это означает, что A* не может исследовать достаточно узлов, чтобы найти кратчайший путь.

Является ли это условие пересечения правильным способом действий, или есть другое условие, которое я должен использовать, чтобы выяснить, когда остановить оба поиска?

Вы можете запустить мой код здесь: https://jasperhuangg.github.io/pathfinding-visualizer .

Случаи, в которых возникает эта проблема, — это определенные (не все) ситуации, когда на сетке размещены и стены, и грузы.

Вот код, если он поможет, извините, если он очень беспорядочный!:

async function bidirectionalAStar(graph, startNode, finishNode) {
  recolorGrid();
  searching = true;

  const infinity = Number.MAX_VALUE;
  var openSource = [];
  var openDest = [];
  var closedSource = [];
  var closedDest = [];

  var numSteps = -3; // -2 for both start and finish nodes + -1 for overlapping connecting node

  $("#steps-taken").html("Cells Examined: " + numSteps);

  const startX = startNode.x;
  const startY = startNode.y;

  const finishX = finishNode.x;
  const finishY = finishNode.y;

  var bidirectionalAStarGraph = shallowCopyGraph(graph, []);

  // initialize all nodes to dist infinity from the startNode
  for (let i = 0; i < bidirectionalAStarGraph.length; i++) {
    for (let j = 0; j < bidirectionalAStarGraph[i].length; j++) {
      bidirectionalAStarGraph[i][j].fSrc = infinity;
      bidirectionalAStarGraph[i][j].gSrc = infinity;
      bidirectionalAStarGraph[i][j].hSrc = infinity;
      bidirectionalAStarGraph[i][j].fDest = infinity;
      bidirectionalAStarGraph[i][j].gDest = infinity;
      bidirectionalAStarGraph[i][j].hDest = infinity;
      bidirectionalAStarGraph[i][j].setSource = "neither";
      bidirectionalAStarGraph[i][j].setDest = "neither";
    }
  }

  // initialize start/finish node distance from start/finish to 0
  bidirectionalAStarGraph[startX][startY].fSrc = 0;
  bidirectionalAStarGraph[startX][startY].gSrc = 0;
  bidirectionalAStarGraph[startX][startY].hSrc = 0;
  bidirectionalAStarGraph[startX][startY].setSource = "open";
  openSource.push(bidirectionalAStarGraph[startX][startY]);

  bidirectionalAStarGraph[finishX][finishY].fDest = 0;
  bidirectionalAStarGraph[finishX][finishY].gDest = 0;
  bidirectionalAStarGraph[finishX][finishY].hDest = 0;
  bidirectionalAStarGraph[finishX][finishY].setDest = "open";
  openDest.push(bidirectionalAStarGraph[finishX][finishY]);

  var lastNodeSource;
  var lastNodeDest;

  while (openSource.length > 0 && openDest.length > 0) {
    openSource.sort((a, b) => {
      if (a.fSrc !== b.fSrc) return a.fSrc - b.fSrc;
      else return a.hSrc - b.hSrc;
    });
    openDest.sort((a, b) => {
      if (a.fDest !== b.fDest) return a.fDest - b.fDest;
      else return a.hDest - b.hDest;
    });

    var currNodeSource = openSource.shift();
    var currNodeDest = openDest.shift();

    $(".currentNodeGray").removeClass("currentNodeGray");
    $(".currentNodeSunset").removeClass("currentNodeSunset");
    $(".currentNodeOcean").removeClass("currentNodeOcean");
    $(".currentNodeChaos").removeClass("currentNodeChaos");
    $(".currentNodeGreen").removeClass("currentNodeGreen");
    $(".currentNodeCottonCandy").removeClass("currentNodeCottonCandy");

    if (checkIntersection(closedSource, closedDest)) {
      break; // the paths have reached each other
    }
    numSteps += 2;

    $("#steps-taken").html("Cells Examined: " + numSteps);

    currNodeSource.setSource = "closed";
    currNodeDest.setDest = "closed";
    closedSource.push(currNodeSource);
    closedDest.push(currNodeDest);

    colorNode(currNodeSource, "currentNode");
    colorNode(currNodeDest, "currentNode");
    if (lastNodeSource !== undefined && currentSpeed !== "instantaneous")
      colorNode(lastNodeSource, "visited");
    if (lastNodeDest !== undefined && currentSpeed !== "instantaneous")
      colorNode(lastNodeDest, "visited");

    if (currentSpeed === "fast") await sleep(20);
    else if (currentSpeed === "medium") await sleep(180);
    else if (currentSpeed === "slow") await sleep(500);

    var validNeighborsSource = [];
    var validNeighborsDest = [];
    var left = currNodeSource.x - 1;
    var right = currNodeSource.x + 1;
    var up = currNodeSource.y - 1;
    var down = currNodeSource.y + 1;

    // consider all of the current node's (from source) valid neighbors
    if (left >= 0 && !bidirectionalAStarGraph[left][currNodeSource.y].blocked) {
      validNeighborsSource.push(
        bidirectionalAStarGraph[left][currNodeSource.y]
      );
    }
    if (
      right < grid_width &&
      !bidirectionalAStarGraph[right][currNodeSource.y].blocked
    ) {
      validNeighborsSource.push(
        bidirectionalAStarGraph[right][currNodeSource.y]
      );
    }
    if (up >= 0 && !bidirectionalAStarGraph[currNodeSource.x][up].blocked) {
      validNeighborsSource.push(bidirectionalAStarGraph[currNodeSource.x][up]);
    }
    if (
      down < grid_height &&
      !bidirectionalAStarGraph[currNodeSource.x][down].blocked
    ) {
      validNeighborsSource.push(
        bidirectionalAStarGraph[currNodeSource.x][down]
      );
    }

    left = currNodeDest.x - 1;
    right = currNodeDest.x + 1;
    up = currNodeDest.y - 1;
    down = currNodeDest.y + 1;

    // consider all of the current node's (from dest) valid neighbors
    if (left >= 0 && !bidirectionalAStarGraph[left][currNodeDest.y].blocked) {
      validNeighborsDest.push(bidirectionalAStarGraph[left][currNodeDest.y]);
    }
    if (
      right < grid_width &&
      !bidirectionalAStarGraph[right][currNodeDest.y].blocked
    ) {
      validNeighborsDest.push(bidirectionalAStarGraph[right][currNodeDest.y]);
    }
    if (up >= 0 && !bidirectionalAStarGraph[currNodeDest.x][up].blocked) {
      validNeighborsDest.push(bidirectionalAStarGraph[currNodeDest.x][up]);
    }
    if (
      down < grid_height &&
      !bidirectionalAStarGraph[currNodeDest.x][down].blocked
    ) {
      validNeighborsDest.push(bidirectionalAStarGraph[currNodeDest.x][down]);
    }

    // UPDATE NEIGHBORS FROM SOURCE
    for (let i = 0; i < validNeighborsSource.length; i++) {
      let neighbor = validNeighborsSource[i];

      if (neighbor.setSource === "closed") continue;

      let cost = 0;
      if (currNodeSource.weighted === true || neighbor.weighted === true)
        cost = currNodeSource.gSrc + 10;
      else cost = currNodeSource.gSrc + 1;

      if (neighbor.setSource === "open" && cost < neighbor.gSrc) {
        neighbor.setSource = "neither";
        neighbor.gSrc = cost;
        neighbor.fSrc = neighbor.gSrc + neighbor.hSrc;
        openSource.remove(neighbor);
      }
      if (neighbor.setSource === "neither") {
        openSource.push(neighbor);
        neighbor.setSource = "open";
        neighbor.gSrc = cost;
        neighbor.hSrc = calculateHeuristic(neighbor, finishNode);
        neighbor.fSrc = neighbor.gSrc + neighbor.hSrc;
        neighbor.predecessorSource = currNodeSource;
      }
    }
    lastNodeSource = currNodeSource;

    // UPDATE NEIGHBORS FROM DEST
    for (let i = 0; i < validNeighborsDest.length; i++) {
      let neighbor = validNeighborsDest[i];

      if (neighbor.setDest === "closed") continue;

      let cost = 0;
      if (currNodeDest.weighted === true || neighbor.weighted === true)
        cost = currNodeDest.gDest + 10;
      else cost = currNodeDest.gDest + 1;

      if (neighbor.setDest === "open" && cost < neighbor.gDest) {
        neighbor.setDest = "neither";
        neighbor.gDest = cost;
        neighbor.fDest = neighbor.gDest + neighbor.hDest;
        openDest.remove(neighbor);
      }
      if (neighbor.setDest === "neither") {
        openDest.push(neighbor);
        neighbor.setDest = "open";
        neighbor.gDest = cost;
        neighbor.hDest = calculateHeuristic(neighbor, startNode);
        neighbor.fDest = neighbor.gDest + neighbor.hDest;
        neighbor.predecessorDest = currNodeDest;
      }
    }
    lastNodeDest = currNodeDest;
  }