一方通行を許可した迷路を作成

make_labyrinth.scala

// お題：一方通行を許可した迷路を作成
// <http://d.hatena.ne.jp/aya_eiya/20110329/1301406161>
// に対する答案 by @akihiro4chawon

// 基本方針：力押し（グラフ連結に関する理論は一切使っていない）
// ポイント：掘るんじゃない、閉ざしていくんだ！

// requires scala 2.9.0 RC1 or later
// scala 2.8.1 には、Enumeration にバグがあるので scala 2.9.0 RC1 を使用した

/** 方向 */
object Direction extends Enumeration {
  type Direction = Value
  val North, South, East, West = Value
  def random: Direction = Direction(util.Random.nextInt(maxId))
}
import Direction.{ValueSet => DirectionSet, _}

/** 座標 */
case class Location(val x: Int, val y: Int) extends Iterable[Int] {
  def +(dir: Direction) = dir match {
    case North => Location(x, y - 1)
    case South => Location(x, y + 1)
    case East  => Location(x + 1, y)
    case West  => Location(x - 1, y)
  }
  override def iterator = Iterator(x, y)
}

/** 世界 */
class Labyrinth private (val width: Int, val height: Int) {
  import util.Random.nextInt
  val rooms = Array.tabulate(width, height){ (x, y) =>
    new Room(Location(x, y), DirectionSet.empty)
  }
  
  // お部屋
  class Room private[Labyrinth] (
    val location: Location,
    var doors: DirectionSet
  ) {
    def nextTo(dir: Direction) = Room(location + dir)
    def toXml = <cell
      position={location map {_ + 1} mkString ","}
      doors={doors map {_+":true"} mkString ","}            
    />
  }
  object Room {
    def apply(loc: Location) = rooms lift loc.x flatMap {_ lift loc.y}
  }
  
  def randomRoom = rooms(nextInt(width))(nextInt(height))
  def iterator = rooms.iterator flatMap {_.iterator}
  def countRooms = width * height
  def countWalls = 4 * countRooms - 2 * (width + height)
  def countDoors = iterator.map{_.doors.size}.sum
  def ratioOfDoor = countDoors.toDouble / countWalls
  
  // 指定の部屋がつながっているか (from -> goal の方向)
  def hasConnectionTo(from: Room, goal: Room) = {
    val seen = collection.mutable.Set.empty[Room]
    def recurse(room: Room): Boolean = {
      seen += room // constructor の隠蔽により、同じ部屋は単一のインスタンスを保証。よって、参照透過性の比較でOK
      (room == goal) || (room.doors flatMap room.nextTo filterNot seen exists recurse)
    }
    recurse(from)
  }
  
  def openAllDoors() {
    iterator foreach {_.doors ++= Direction.values}
    rooms.head foreach {_.doors -= Direction.West}
    rooms.last foreach {_.doors -= Direction.East}
    rooms foreach {_.head.doors -= Direction.North}
    rooms foreach {_.last.doors -= Direction.South}
  }
  def toXml = <labyrinth>{iterator map {_.toXml}}</labyrinth>
}
object Labyrinth {
  // 縦横を指定しての生成
  def apply(w: Int, h: Int) = new Labyrinth(w, h)
  // ToDo: XML からの生成?
  //def fromXml(e: xml.Elem)
}


object Main extends App {
  val m, n = 10
  val lab = Labyrinth(m, n)
  lab.openAllDoors()
  
  var idx = 1
  while (lab.ratioOfDoor > 0.4) {
    val from = lab.randomRoom
    for {
      dir <- Some(Direction.random) filter from.doors
      to <- from nextTo dir
    } {
      from.doors -= dir
      if (!lab.hasConnectionTo(from, to))
        from.doors += dir
      else {
        // 途中経過を保存（出題者である aya_eiya さんの SVG 化ルーチンを呼出）
//        scala.xml.XML.save("x%03d.svg".format(idx), personal.ayaeiya.minos.Main.drawSVG(lab.toXml.child), "UTF-8");
        idx += 1          
      }
    }
  }
    println("Ratio: "+lab.ratioOfDoor+" (doors = "+lab.countDoors+" / walls = "+lab.countWalls+")")
    println(lab.toXml)
    // 最終図面の保存（出題者である aya_eiya さんの SVG 化ルーチンを呼出）
//    scala.xml.XML.save("hogeg.svg", personal.ayaeiya.minos.Main.drawSVG(lab.toXml.child), "UTF-8")
}