aStar2D function

Queue<Tile> aStar2D(Maze maze)

This algorithm works only for 2D grids. There is a lot of room to optimize this further.

Implementation

Queue<Tile> aStar2D(Maze maze) {
  final map = maze.tiles;
  final start = maze.start;
  final goal = maze.goal;
  final numRows = map.length;
  final numColumns = map[0].length;

  final open = <Tile>[];
  final closed = <Tile>[];

  open.add(start);

  while (open.isNotEmpty) {
    var bestCost = open[0]._f;
    var bestTileIndex = 0;

    for (var i = 1; i < open.length; i++) {
      if (open[i]._f < bestCost) {
        bestCost = open[i]._f;
        bestTileIndex = i;
      }
    }

    var currentTile = open[bestTileIndex];

    if (currentTile == goal) {
      // queues are more performant when adding to the front
      final path = Queue<Tile>.from([goal]);

      // Go up the chain to recreate the path
      while (currentTile._parentIndex != -1) {
        currentTile = closed[currentTile._parentIndex];
        path.addFirst(currentTile);
      }

      return path;
    }

    open.removeAt(bestTileIndex);

    closed.add(currentTile);

    for (var newX = math.max(0, currentTile.x - 1);
        newX <= math.min(numColumns - 1, currentTile.x + 1);
        newX++) {
      for (var newY = math.max(0, currentTile.y - 1);
          newY <= math.min(numRows - 1, currentTile.y + 1);
          newY++) {
        if (!map[newY][newX].obstacle // If the new node is open
            ||
            (goal.x == newX && goal.y == newY)) {
          // or the new node is our destination
          //See if the node is already in our closed list. If so, skip it.
          var foundInClosed = false;
          for (var i = 0; i < closed.length; i++) {
            if (closed[i].x == newX && closed[i].y == newY) {
              foundInClosed = true;
              break;
            }
          }

          if (foundInClosed) {
            continue;
          }

          //See if the node is in our open list. If not, use it.
          var foundInOpen = false;
          for (var i = 0; i < open.length; i++) {
            if (open[i].x == newX && open[i].y == newY) {
              foundInOpen = true;
              break;
            }
          }

          if (!foundInOpen) {
            final tile = map[newY][newX].._parentIndex = closed.length - 1;

            tile
              .._g = currentTile._g +
                  math.sqrt(math.pow(tile.x - currentTile.x, 2) +
                      math.pow(tile.y - currentTile.y, 2))
              .._h = heuristic(tile, goal)
              .._f = tile._g + tile._h;

            open.add(tile);
          }
        }
      }
    }
  }

  return Queue<Tile>();
}