Я хочу реализовать метод, который берет начальные и конечные местоположения на карте и возвращает путь, который перемещается по карте от начала до конца. (Этот путь не должен содержать непроходимых плиток (настенных плиток) и должен быть как можно короче.)
Так что для этой реализации мне разрешено использовать только 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
}