矩阵中两个单元格之间的最短路径

Question

我有一个二维数组，用于表示角色在游戏中的位置，我将其称为网格。网格是一个 5x5 大小的网格。并非网格上的所有 tiles/locations 都是角色可以穿越的可行位置。在示例图像中，您可以看到其中三个位置是水而不是陆地，表示角色无法访问的位置。

在穿越网格时，仅使用四个主要方向（上、下、左、右）我希望角色找到到达目的地的最短可行路径。例如，如果它从 [1,2] 开始并需要到达位置 [3,2]，我希望它移动：向上 -> 向右 -> 向右 -> 向下。

以下是我目前用于确定可行解决方案的信息；有些地方不太对劲，但我想不出我的逻辑哪里出了问题：

DartPad Example用于交互功能代码。

import 'dart:collection';

class Point {
  int x;
  int y;
  Point({required this.y,required this.x});
}

void main() {
  print('Finding a viable solution for the shortest path...');
  
  var grid = [
    ['','','','',''],
    ['','','','',''],
    ['','','','',''], // Character is at position grid[2][1]
    ['','','','',''], // Destination is position grid[2][3]
    ['','','','',''],
  ];
  
  var characterPosition = Point(y: 2, x: 1);
  var characterDestination = Point(y: 2, x: 3);
  
  PathFinder pathFinder = PathFinder(grid, characterPosition, characterDestination);
  if (pathFinder.solutionExists) {
    print('...Solution exists!');
    for (Point point in pathFinder.solution) {
      print('(${point.y},${point.x})');
    }
  }
  else {
    print('...No solution exists.');
  }
}

class PathFinder {
  late Queue<Point> solution;
  late bool solutionExists;

  PathFinder(grid, characterPosition, characterDestination) {

    // Applying BFS on matrix cells.
    Queue<Point> queue = Queue<Point>();
    queue.add(new Point(y: characterPosition.y, x: characterPosition.x));

    List<List<bool>> visited = List.generate(
      grid.length,
      (index) => List.generate(
        grid[0].length,
        (index) => false,
        growable: false,
      ),
      growable: false,
    );

    visited[characterPosition.y][characterPosition.x] =
        true;

    while (queue.isNotEmpty) {
      Point point = queue.removeLast();

      // Destination found
      if (point.x == characterDestination.x &&
          point.y == characterDestination.y) {
        this.solutionExists = true;
        this.solution = queue;
        return;
      }

      // moving up
      if (_isValid(x: point.x, y: point.y - 1, grid: grid, visited: visited)) {
        queue.add(new Point(y: point.y - 1, x: point.x));
        visited[point.y - 1][point.x] = true;
      }

      // moving down
      if (_isValid(x: point.x, y: point.y + 1, grid: grid, visited: visited)) {
        queue.add(new Point(y: point.y + 1, x: point.x));
        visited[point.y + 1][point.x] = true;
      }

      // moving left
      if (_isValid(x: point.x - 1, y: point.y, grid: grid, visited: visited)) {
        queue.add(new Point(y: point.y, x: point.x - 1));
        visited[point.y][point.x - 1] = true;
      }

      // moving right
      if (_isValid(x: point.x + 1, y: point.y, grid: grid, visited: visited)) {
        queue.add(new Point(y: point.y, x: point.x + 1));
        visited[point.y][point.x + 1] = true;
      }
    }

    this.solutionExists = false;
    this.solution = queue;
    return;
  }

  bool _isValid({required int x, required int y, required List<List<String>> grid, required List<List<bool>> visited}) {
    if (x >= 0 &&
        y >= 0 &&
        x < grid[0].length &&
        y < grid.length &&
        grid[y][x] != '' &&
        visited[y][x] == false) {
      return true;
    }
    return false;
  }
}

如果你运行这个（使用DartPad），你可以看到输出是：

Finding a viable solution for the shortest path...
...Solution exists!
(1,1)
(3,3)
(1,4)

此输出与我预期的不完全相同，这意味着我显然搞砸了。我无法弄清楚我到底应该怎么做才能正确实施这个寻路算法，所以任何见解、建议或帮助都将不胜感激！提前致谢！！

Answer 1

逻辑是“广度优先搜索”。 List cameFrom 将每个节点元素设置为它来自的节点元素。图片：

现在重建整个路径，从目的地到起始节点。

DartPad 上的 Dart 解决方案。

Dart 不是我的第一语言，所以请随意改变方法...

import 'dart:collection';

// *****************************************************************************
// ***** class Point
class Point {
  int x;
  int y;
  Point({required this.y, required this.x});
}

// *****************************************************************************
// ***** class PathFinder
class PathFinder {
  List<List<String>> grid;
  int gridWidth = 0;
  int gridHeight = 0;

  late Queue<Point> solution;
  late bool solutionExists;

  // ---------------------------------------------------------------------------
  // ----- constructor
  PathFinder(this.grid, characterPosition, characterDestination) {
    // integers for easier manipulation
    Queue<int> frontier = Queue<int>();
    List<int> cameFrom = List.generate(
      this.grid[0].length * this.grid.length,
      (int index) => -1,
      growable: false,
    );

    this.gridWidth = this.grid[0].length;
    this.gridHeight = this.grid.length;

    frontier.add(this._convert2dto1d(characterPosition));

    // +++++ Breadth First Search Logic begin
    while (frontier.isNotEmpty) {
      int current = frontier.removeFirst();
      Queue<Point> neighbors = this._neighbors(_convert1dto2d(current));

      for (Point node in neighbors) {
        int node1d = this._convert2dto1d(node);

        if (cameFrom[node1d] == -1) {
          frontier.add(node1d);
          cameFrom[node1d] = current;
        }
      }
    }
    // +++++ Breadth First Search Logic end

    this.solutionExists = true;

    // +++++ copy solution to 2d Queue<Point> begin
    this.solution = Queue<Point>();
    Point endNode = characterDestination;
    this.solution.add(endNode);
    while (
        endNode.x != characterPosition.x || endNode.y != characterPosition.y) {
      int endNode1d = this._convert2dto1d(endNode);

      if (cameFrom[endNode1d] == -1) {
        this.solutionExists = false;
        break;
      }

      endNode = this._convert1dto2d(cameFrom[endNode1d]);
      this.solution.addFirst(endNode);
    }
    // +++++ copy solution to 2d Queue<Point> end

    return;
  }

  // ---------------------------------------------------------------------------
  // ----- _convert2dto1d
  // ----- Convert point to integer for easier manipulation
  int _convert2dto1d(Point node) {
    return node.y * this.gridWidth + node.x;
  }

  // ---------------------------------------------------------------------------
  // ----- _convert1dto2d
  // ----- Convert integer back to point
  Point _convert1dto2d(int node1d) {
    if (this.gridWidth == 0) {
      return new Point(y: -1, x: -1);
    }

    int y = node1d ~/ this.gridWidth;
    int x = node1d - y * this.gridWidth;

    return new Point(y: y, x: x);
  }

  // ---------------------------------------------------------------------------
  // ----- _neighbors
  Queue<Point> _neighbors(Point node) {
    Queue<Point> neighbors = Queue<Point>();

    for (int dx = -1; dx <= 1; dx += 2) {
      Point neighborNode = new Point(y: node.y, x: node.x + dx);
      if (_isValidNode(neighborNode)) {
        neighbors.add(neighborNode);
      }
    }
    for (int dy = -1; dy <= 1; dy += 2) {
      Point neighborNode = new Point(y: node.y + dy, x: node.x);
      if (_isValidNode(neighborNode)) {
        neighbors.add(neighborNode);
      }
    }

    return neighbors;
  }

  // ---------------------------------------------------------------------------
  // ----- _isValidNode
  bool _isValidNode(Point node) {
    if (node.x >= 0 &&
        node.y >= 0 &&
        node.x < this.gridWidth &&
        node.y < this.gridHeight &&
        this.grid[node.y][node.x] != '') {
      return true;
    }
    return false;
  }
}

// *****************************************************************************
// ***** main
void main() {
  print('Finding a viable solution for the shortest path...');

  var grid = [
    ['', '', '', '', ''],
    ['', '', '', '', ''],
    ['', '', '', '', ''], // Character is at position grid[2][1]
    ['', '', '', '', ''], // Destination is position grid[2][3]
    ['', '', '', '', ''],
  ];

  var characterPosition = Point(y: 2, x: 1);
  var characterDestination = Point(y: 2, x: 3);

  PathFinder pathFinder =
      PathFinder(grid, characterPosition, characterDestination);
  if (pathFinder.solutionExists) {
    print('...Solution exists!');
    for (Point point in pathFinder.solution) {
      print('(${point.y},${point.x})');
    }
  } else {
    print('...No solution exists.');
  }
}

矩阵中两个单元格之间的最短路径

Shortest path between two cells in a matrix

algorithm

breadth-first-search

depth-first-search

dart

flutter