A* アルゴリズムで迷路を解く

gistfile1.txt

scala> import maze._
import maze._

scala> val m = Mazes.load(new java.io.File("maze.txt"))
m: maze.Maze = maze.Maze@20ccb51

scala> Mazes.encodeRunLength(m.solve.get)
res0: List[(maze.Direction.Value, Int)] = List((S,1), (E,10), (S,2), (W,31), (N,4), (E,2), (S,2), (E,2), (N,4), (E,7), (N,1))

maze.scala

package maze

import scala.collection.mutable.PriorityQueue

case class Point(x: Int, y: Int) {
  def distance(other: Point): Int = math.abs(x - other.x) + math.abs(y - other.y)
  def moveN: Point = Point(x, y - 1)
  def moveE: Point = Point(x + 1, y)
  def moveS: Point = Point(x, y + 1)
  def moveW: Point = Point(x - 1, y)
}
case class Cell(point: Point, value: Char)

object Direction extends Enumeration {
  val N, E, S, W = Value
}
class DistanceOrdering(target: Point) extends Ordering[Point] {
  def compare(a: Point, b: Point) = a.distance(target).compare(b.distance(target))
}

class Maze(private val data: Array[Array[Char]]) {
  lazy val cells =
    for {
      (line, y) <- data.zipWithIndex
      (v, x) <- line.zipWithIndex
    } yield {
      Cell(Point(x, y), v)
    }
  def cellAt(point: Point): Option[(Cell, List[(Point, Direction.Value)])] = {
    cells.find { _.point == point } match {
      case Some(c@Cell(p, _)) =>
        val n = cells.find { _.point == Point(p.x, p.y - 1) }.map { (_, Direction.N) }
        val e = cells.find { _.point == Point(p.x + 1, p.y) }.map { (_, Direction.E) }
        val s = cells.find { _.point == Point(p.x, p.y + 1) }.map { (_, Direction.S) }
        val w = cells.find { _.point == Point(p.x - 1, p.y) }.map { (_, Direction.W) }
        Some((c, List(n, e, s, w).collect { case Some((c, d)) if c.value == '.' || c.value == 'G' => (c.point, d) }))
      case _ => None
    }
  }

  def start: Option[Point] = find('S')
  def goal: Option[Point] = find('G')
  private def find(value: Char): Option[Point] =
    cells.find { _.value == value }.map { _.point }

  def solve: Option[List[Direction.Value]] = {
    val s = start.get
    val g = goal.get
    val q = PriorityQueue(s)(new DistanceOrdering(g))

    explore(q, Map.empty, Set.empty, s, g)
  }

  @annotation.tailrec
  private def explore(q: PriorityQueue[Point], footprints: Map[Point, Direction.Value], visited: Set[Point], s: Point, g: Point): Option[List[Direction.Value]] = {
    if (q.isEmpty) None
    else {
      val p = q.dequeue
      val (c, links) = cellAt(p).get

      if (c.point == g) Some(path(footprints, s, g))
      else if (visited.contains(c.point)) {
        explore(q, footprints, visited, s, g)
      } else {
        links.foreach { x => q += x._1 }
        val f = links.foldLeft(footprints) { case (m, (p, d)) => if (!visited.contains(p)) m + (p -> d) else m }
        explore(q, f, visited + p, s, g)
      }
    }
  }

  private def path(footprints: Map[Point, Direction.Value], start: Point, goal: Point): List[Direction.Value] = {
    @annotation.tailrec
    def _path(acc: List[Direction.Value], footprints: Map[Point, Direction.Value], start: Point, p: Point): List[Direction.Value] = {
      if (p == start) acc
      else {
        footprints(p) match {
          case d@Direction.N => _path(d :: acc, footprints, start, p.moveS)
          case d@Direction.E => _path(d :: acc, footprints, start, p.moveW)
          case d@Direction.S => _path(d :: acc, footprints, start, p.moveN)
          case d@Direction.W => _path(d :: acc, footprints, start, p.moveE)
        }
      }
    }

    _path(List.empty, footprints, start, goal)
  }
}

object Mazes {
  import java.io.File
  import scalax.io._

  def load(file: File): Maze = {
    val cc = Resource.fromFile(file).lines().map { _ toCharArray }.toArray
    new Maze(cc)
  }

  def encodeRunLength(path: List[Direction.Value]): List[(Direction.Value, Int)] = {
    def pack[A](ls: List[A]): List[List[A]] = {
      if (ls.isEmpty) List(List())
      else {
        val (packed, next) = ls span { _ == ls.head }
        if (next == Nil) List(packed)
        else packed :: pack(next)
      }
    }
    pack(path).map { e => (e.head, e.length) }
  }
}

maze.txt

############G##################
#............#................#
#####.########.#######.######.#
#...#.#..............###......#
#.#.#.########.#######S######.####
#.#...#.#......#.....#...........#
#.#####.#.##########.###########.#
#................................#
##################################