LabyrinthMaker

LabyrinthMaker.scala

package personal.ayaeiya.minos

import scala.util.Random
import scala.xml._
import scala.collection.mutable.ListMap

/*****************
* Setting Object *
******************/
object Setting{
  val fieldSize = 10
  val doorOpenProbability = 0.4
  val saveAsSVGFile = """c:\tmp\LabyrinthMaker.svg"""
//val saveAsSVGFile = null
}

/***************
* Util Object  *
****************/
object Util{
  def addLists(l1:List[Int],l2:List[Int]):List[Int] = for((a,b)<-l1 zip l2) yield a+b
  def getRandomList2:List[Int] = List(1+Random.nextInt(Setting.fieldSize),1+Random.nextInt(Setting.fieldSize))
}

/**********************
* Define Cell *
***********************/
object Cell{
  def getWayCountMap = {for(c<-Cell.cellList ;cs<-c.walls.map(_.move) if cs!=c) yield cs}.groupBy(v=>v).map(f=>f._1->f._2.length)
  def getLonely = Cell.cellList.filter(cell => {for(c<-Cell.cellList ;cs<-c.walls.map(_.move) if cs!=c) yield cs==cell}.forall(!_) )
  def get(target:List[Int]):Cell = cellList.find(_.position==target).get
  def getNeighbor(c:Cell):List[Cell] = Arrow.values.map(a=>cellList.filter(_.position == Util.addLists(c.position,Arrow.toList(a)))).reduceLeft(_:::_)
  private var _cellList:List[Cell] = Nil
  def cellList:List[Cell] = _cellList
  def canMoveTo(cell:Cell,arrow:Arrow.Value):Boolean = Util.addLists(cell.position,Arrow.toList(arrow)).forall(i=> 1 <= i && i <= Setting.fieldSize )
  def doorOpenProbability = cellList.map(_.getDoorOpenProbability).reduceLeft{_+_}/Cell.cellList.length
}
class Cell(list:List[Int]){
  val position = list
  // var for toggling between Wall and Door
  val walls = List[Wall](Wall(this,Arrow.e),Wall(this,Arrow.w),Wall(this,Arrow.s),Wall(this,Arrow.n))
  def getDoorOpenProbability = walls.count(_.isDoor).floatValue/Arrow.lengthAt(this)
  def canMoveTo(arrow:Arrow.Value):Boolean = Util.addLists(this.position,Arrow.toList(arrow)).forall(i=> 1 <= i && i <= Setting.fieldSize )
  def getNeighbor = Cell.getNeighbor(this)
  Cell._cellList = Cell._cellList ::: List(this)
}
/**********************
* Define Door & Wall *
**********************/
case class Wall(cell:Cell,arrow:Arrow.Value){
  private var locked = true
  def move:Cell = if(locked) cell else Cell.get( Util.addLists(cell.position , Arrow.toList(arrow)) )
  def lock = { locked = true }
  // If this is by a wall,this can't be unlocked.
  def unlock = if( cell.canMoveTo(arrow) ) locked = false
  def isDoor = !locked
}

/************************
* Define Arrow to Move *
************************/
object Arrow extends Enumeration{
  val e = Value("East")
  val w = Value("West")
  val s = Value("South")
  val n = Value("North")
  def length = values.size
  def lengthAt(c:Cell):Int = values.count(c.canMoveTo(_))
  def random = Arrow.values.find(_.id==Random.nextInt(length))
  def randomAt(c:Cell):Arrow.Value = random match {case Some(a) if c.canMoveTo(a) => a case _ => Arrow.randomAt(c) }
  def toList(v:Arrow.Value):List[Int] ={
    v match {
      case Arrow.e => List( 1, 0)
      case Arrow.w => List(-1, 0)
      case Arrow.s => List( 0, 1)
      case Arrow.n => List( 0,-1)
      case _ => List( 0, 0) // Just in case
    }
  }
}

/********************************
* Define Digger (route search) *
********************************/
object Digger{
  private var successList:List[Cell] = Nil
  def reset = {successList = Nil}
  def isSucceeded(cell:Cell):Boolean = successList.exists(_==cell)
}

class Digger(start:Cell){
  private var pastCellList:List[Cell] = Nil
  private val cell = start

  // get PastCellList Length
  def dugLength:Int = pastCellList.length
  // clear passCellList
  def reset = {pastCellList = Nil}

  // add to pastCellList
  private def pass(cell:Cell) = (pastCellList = pastCellList ::: List(cell))
  // check cell was past
  private def past(cell:Cell):Boolean = pastCellList.exists(_==cell)
  // search all route from cell
  private def dig(cell:Cell):Boolean = {
    if(!Digger.isSucceeded(cell) && !past(cell)){
      pass(cell)
      for(d<-cell.walls ;c = d.move) if(c!=cell)dig(c)
    }
    if(dugLength == Cell.cellList.length || Digger.isSucceeded(cell)){
      Digger.successList = Digger.successList ::: List(this.cell)
    }
    Digger.isSucceeded(cell)
  }
  def dig:Boolean = dig(cell)
}

/*****************************
* Entry point definition *
*****************************/
object Main{
  def main(arg:Array[String]){
    for(i<- 1 to Setting.fieldSize;j<- 1 to Setting.fieldSize){ new Cell(List(j,i)) }
    assert(Cell.cellList.length == Setting.fieldSize * Setting.fieldSize)

    // init cells have one door at least
    def reset = {
      Digger.reset
      for(c<-Cell.cellList){val v=Arrow.randomAt(c);c.walls.foreach(m=>if(m.arrow == v) m.unlock else m.lock)}
      for(c<-Cell.getLonely){
        val arw = Arrow.toList(Arrow.randomAt(c))
        for(cs<-Cell.getNeighbor(c) if arw == Util.addLists(cs.position,c.position.map(-_))){
          for(d <- cs.walls if !d.isDoor){d.unlock;if(d.move!=c)d.lock}
        }
      }
      assert(Cell.getLonely.length==0)
    }
    //
    val diggers = Cell.cellList.map(new Digger(_))
    def isClear = diggers.forall(d=>{d.reset;d.dig})
    // CHI-KA-RA-WA-ZA !!
    reset
    while(!isClear){
      // random unlock
      val cMap = Cell.getWayCountMap
      val cList = cMap.filter(map=>map._2 == cMap.foldLeft(Int.MaxValue)((f:Int,g)=>List(f,g._2) min)).map(_._1).toList
      assert(cList.length > 0)
      val c = cList(Random.nextInt(cList.length))
      val arw = Arrow.toList(Arrow.randomAt(c))
      for(cs<-Cell.getNeighbor(c) if arw == Util.addLists(cs.position,c.position.map(-_))){
        for(d <- cs.walls if !d.isDoor){
          d.unlock
          if(d.move!=c) d.lock else assert(d.isDoor)
        }
      }
      // relock 
      if(isClear){
        for(c<-Cell.cellList;d<-c.walls if d.isDoor){
          Digger.reset
          d.lock
          if(!isClear) d.unlock
        }
        if(Cell.doorOpenProbability > Setting.doorOpenProbability) reset
      }
    }
    println("complexity:"+Cell.cellList.map(_.getDoorOpenProbability).reduceLeft{_+_}/Cell.cellList.length)
    // build xml
    val xml = {
      {for(c<-Cell.cellList) yield{
            <cell
            position={c.position.mkString(",")}
            doors={c.walls.map(d => d.arrow + ":" + d.isDoor ).mkString(",")}
            />
      }
      }.reduceLeft{
        (f,g)=>f match {
          case <labyrinth>{ p @ _*}</labyrinth> => <labyrinth>{p}{g}</labyrinth>
          case _=> <labyrinth>{f}{g}</labyrinth>
        }
      }
    }
    println(xml)
    if(Setting.saveAsSVGFile != null) XML.save(Setting.saveAsSVGFile,drawSVG(xml.child),"UTF-8")
//    LabyrinthChecker.main(Array(null,xml.toString))
  }


  def drawSVG(nodeSeq:Seq[Node]):Node = {
    var svgSize = (0d,0d)
    val s = 0.2 // zoom
    def max(d1:Double,d2:Double) = if(d1>d2) d1 else d2
    def put(pos:(Int,Int))(e:Boolean)(w:Boolean)(s:Boolean)(n:Boolean)(scl:Double):Node ={
      val (x,y) = pos
      val (px,py) = ((x-1)*scl*300,(y-1)*scl*300)
      svgSize = (max(svgSize._1,px+300*scl),max(svgSize._2,py+300*scl))
      <g id={"cell_"+x+"_"+y} transform={format("translate(%f,%f) scale(%f)",px,py,scl)}>
          <rect width="180" height="180" x="120" y="120" style="fill:#eeccff;stroke:#000000;stroke-width:1;"></rect>
        {if(e){<g class="toEast">
            <rect width="120" height="40"  x="300" y="225" style="fill:#9999ff;stroke:#000000;stroke-width:1;"></rect>
            <path d="m 340,225 0,5 15,15 -15,15 0,5 20,-20 z" style="fill:#000000;" />
            <path d="m 360,225 0,5 15,15 -15,15 0,5 20,-20 z" style="fill:#000000;" />
          </g>}else ""
        }
        {if(w){<g id="toWest">
            <rect width="120" height="40"  x="0"   y="155" style="fill:#99ff99;stroke:#000000;stroke-width:1;"></rect>
            <path d="m 60,155 0,5 -15,15 15,15 0,5 -20,-20 z" style="fill:#000000;" />
            <path d="m 80,155 0,5 -15,15 15,15 0,5 -20,-20 z" style="fill:#000000;" />
          </g>}else ""
        }
        {if(s){<g class="toSouth">
            <rect width="40"  height="120" x="155" y="300" style="fill:#66ffff;stroke:#000000;stroke-width:1;"></rect>
            <path d="m 155,340 5,0 15,15 15,-15 5,0 -20,20 z" style="fill:#000000;" />
            <path d="m 155,360 5,0 15,15 15,-15 5,0 -20,20 z" style="fill:#000000;" />
          </g>}else ""
        }
        {if(n){<g class="toNorth">
            <rect width="40"  height="120" x="225" y="0"   style="fill:#ff9999;stroke:#000000;stroke-width:1;"></rect>
            <path d="m 225,60 5,0 15,-15 15,15 5,0 -20,-20 z" style="fill:#000000;" />
            <path d="m 225,80 5,0 15,-15 15,15 5,0 -20,-20 z" style="fill:#000000;" />
          </g>}else ""
        }
      </g>
    }
    val nodes = for(node<-nodeSeq if node.label == "cell") yield {
        node.attribute("position") match{
          case Some(p) if p.toString.matches("^[0-9]+,[0-9]+$")=>{
            val ps = p.toString.split(",",2).map(_.toInt)
            val arwMap = ListMap("East"->false,"West"->false,"South"->false,"North"->false)
            node.attribute("doors") match{
              case Some(d) if d.toString.matches("^((East|West|South|North):(true|false),)*((East|West|South|North):(true|false),?)$")=>{
                for(v <- d.toString.split(",")){
                 val arw = v.split(":",2)
                 arwMap(arw(0)) = arw(1).toBoolean
                }
                Unit
              }
              case _=> Unit
            }
            put((ps(0),ps(1)))(arwMap("East"))(arwMap("West"))(arwMap("South"))(arwMap("North"))(s)
          }
          case _ => Null
        }
     }
     nodes.foldLeft(<svg />){ (f,g)=> f match{case <svg>{c @ _*}</svg> => <svg>{c}{g}</svg> } }.%{
      new UnprefixedAttribute("xmlns"    ,"http://www.w3.org/2000/svg"
      , new UnprefixedAttribute("width"    , svgSize._1.toString
      , new UnprefixedAttribute("height"   , svgSize._2.toString
      , new UnprefixedAttribute("viewBox"  , "0 0 " + svgSize._1.toString +" "+ svgSize._2.toString
      , new UnprefixedAttribute("version"  ,"1.1",Null)))))}
  }
}