时间戳

首页 > 解决方案 > 我将如何编写一个找到迷宫/网格路径的方法？之后我会怎么做？

algorithm - 我将如何编写一个找到迷宫/网格路径的方法？之后我会怎么做？

问题描述

我想实现一种方法，该方法采用地图上的起点和终点位置并返回从起点到终点导航地图的路径。（此路径不得包含任何无法通行的瓷砖（墙砖），并且必须尽可能短。）

所以对于这个实现，我只被允许使用 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
}

标签： algorithmscaladata-structuresbreadth-first-searchmaze

解决方案

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

  1. 新单元格在网格内，不是墙块。
  2. 以前没有访问过新的单元格。

要跟踪访问过的单元格，您可以使用网格大小的辅助数组，并将访问过的单元格标记为关闭1，未访问过的单元格标记为0。此外，为了存储路径，您可以保留另一个辅助数组，该数组为每个单元存储直接通向该单元的“父单元”，并且在完成 BFS 后，您可以从末端单元开始回溯父单元到起始单元格。

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

推荐阅读