我将如何编码找到迷宫/网格路径的方法？我该怎么办？

Question

我想实现一种方法，该方法获取地图上的开始和结束位置，并返回从头到尾导航地图的路径。 （此路径不得包含任何不可逾越的磁贴（墙贴​​），并且必须尽可能短。）

因此，对于此实现，我只能使用BFS。我的第一步是将迷宫转换成图形，但我不确定如何开始。然后，我必须在包含迷宫赛跑者的图块上运行BFS。最后，我将不得不从目标区域回溯以构建路径。我觉得有很多步骤，因此我真的需要一些帮助来处理。

class GridLocation(val x: Int, val y: Int){

  override def toString = s"($x, $y)"

  override def equals(that: Any): Boolean = {
    that match {
      case other: GridLocation =>
        this.x == other.x && this.y == other.y
      case _ => false
    }
  }
}

object MapTile {

  def generateRow(row: String): List[MapTile] = {
    row.map((ch: Char) => MapTile(ch.toString)).toList
  }

  def apply(tileType: String): MapTile = {
    tileType match {
      case "-" => new MapTile("ground", true)
      case "G" => new MapTile("goal", true)
      case "O" => new MapTile("wall", false)
    }
  }

}

class MapTile(val tileType: String, val passable: Boolean) {

}

def findPath(start: GridLocation, end: GridLocation, map: List[List[MapTile]]): List[GridLocation] = {
  //code starts here
}

Answer 1

而不是显式地构建图，您可以通过在每个单元格上尝试沿四个基本方向[y+1,x],[y-1,x],[y,x+1],[y,x-1]中的每一个方向移动并仅将满足以下条件的新单元格添加到队列中，来使该图保持隐式：

1. 新单元格位于网格内，不是墙块。
2. 以前未访问过新单元格。

要跟踪访问的单元格，可以使用网格大小的辅助数组，并将访问的单元格标记为1，将未访问的单元格标记为0。此外，要存储路径，您可以保留另一个辅助数组，该数组为每个单元格存储直接导致该单元格的“父级单元格”，并且在完成BFS后，您可以从结束单元格一直追溯到父级。到起始单元格。

为清楚起见，单元格x的“父单元格是将x添加到队列时要考虑的单元格。