読者です 読者をやめる 読者になる 読者になる

迷路作成&探索

プログラミング

迷路作成&探索をScalaで行った。

import scala.swing._
import scala.math._
import java.awt.Color
import scala.collection.mutable.Queue
import scala.util.control.Breaks.{break,breakable}

abstract class MazeMaker(val step:Int){
  val field=Array.ofDim[Int](2*step+1,2*step+1)
  def next
  def isFinished:Boolean
  def status:Array[Array[Int]]=field
}
class PoleDown(step:Int) extends MazeMaker(step){
  private var x=2
  private var y=2
  for (i <- 0 until step*2+1){
    field(i)(0) = -1
    field(i)(2*step) = -1
    field(0)(i) = -1
    field(2*step)(i) = -1
  }
  for (i <- 2 until 2*step+1 by 2){
    for (j <- 2 until 2*step+1 by 2){
      field(i)(j) = -1
    }
  }
  def next={
    _next
    y+=2
    if (y==2*step){
      y=2
      x+=2
    }
    def _next:Unit={
      if (x==2){
        floor(random*4).toInt match{
          case 0=> field(x-1)(y)= -1
          case 1=> field(x+1)(y)= -1
          case 2=>{
            if (field(x)(y-1)== -1)_next
            else field(x)(y-1) = -1
          }
          case 3=>field(x)(y+1) = -1
        }
      }else{
        floor(random*3).toInt match{
          case 0=>field(x+1)(y) = -1
          case 1=>{
            if (field(x)(y-1)== -1)_next
            else field(x)(y-1) = -1
          }
          case 2=> field(x)(y+1)= -1
        }
      }
    }
  }
  def isFinished:Boolean={
    if (x==2*step && y==2)return true
    return false
  }
}
abstract class MazeSolver(val step:Int,val start:(Int,Int),val goal:(Int,Int)){
  val field=Array.ofDim[Int](2*step+1,2*step+1)
  def init(initfield:Array[Array[Int]])
  def next
  def isFinished:Boolean
  def status:Array[Array[Int]]=field
}

class BFS(step:Int,start:(Int,Int),goal:(Int,Int)) extends MazeSolver(step,start,goal){
  val queue=new Queue[(Int,Int)]
  def init(initfield:Array[Array[Int]]){
    for (i <- 0 until 2*step+1){
      for (j <- 0 until 2*step+1){
        field(i)(j)=initfield(i)(j)
        if(field(i)(j)==0){
          field(i)(j)=Int.MaxValue
        }
      }
    }
    queue.enqueue(start)
    field(start._1)(start._2)=1
    
  }
  
  def next={
    val (x,y)=queue.dequeue()
    for ((dx,dy) <- List((0,1),(1,0),(-1,0),(0,-1))){
      try{
        if(field(x+dx)(y+dy) > field(x)(y)+1){
          field(x+dx)(y+dy)=field(x)(y)+1
          queue.enqueue((x+dx,y+dy))
        }
        
      }catch{
        case _=>
      }
    }
    
  }
  def isFinished:Boolean={
   
   return queue.isEmpty
  }
  override def status:Array[Array[Int]]={
    val rfield=Array.ofDim[Int](2*step+1,2*step+1)
    for (i <- 0 until 2*step+1){
      for (j <- 0 until 2*step+1){
        field(i)(j) match{
          case Int.MaxValue=>rfield(i)(j)=0
          case -1=>rfield(i)(j) = -1
          case _=>rfield(i)(j)=1
        }
      }
    }
    if(isFinished){
     var (nx,ny)=goal
     rfield(nx)(ny)=2
     while((nx,ny)!=start){
       breakable{
       for ((dx,dy)<- List((0,1),(1,0),(-1,0),(0,-1))){
         try{
           if(field(nx)(ny)-1==field(nx-dx)(ny-dy)){
             nx=nx-dx
             ny=ny-dy
             rfield(nx)(ny)=2
             break
           }
         }catch{
           case _=>
         }
       }
       }
     }
    }
    return rfield
  }
}
class Maze(val step:Int,val maker:MazeMaker,val solver:MazeSolver){
  var field=Array.ofDim[Int](step,step)
  def apply(x:Int,y:Int)=field(x)(y)
  
  def startMake=field=maker.status
  def makeStep:Boolean={
    if(maker.isFinished)return false
    else{
      maker.next
      field=maker.status
      return true
    }
  }
  def startSolve:Boolean={
    if(maker.isFinished){
      solver.init(field)
      return true
    }else return false
  }
  def solveStep:Boolean={
    if(solver.isFinished)return false
    else{
      solver.next
      field=solver.status
      return true
    }
  }
}
class MazeCanvas(val maze:Maze) extends Component {
  preferredSize=new Dimension(420,420)
  
  private def squareGeometry:(Int,Int,Int,Int)={
    val d = size
    val squareSide=d.height min d.width
    val x0=(d.width-squareSide)/2
    val y0=(d.height-squareSide)/2
    (squareSide,x0,y0,squareSide/(maze.step*2+1))
  }
  override def paintComponent(g:Graphics2D){

    g.setRenderingHint(
        java.awt.RenderingHints.KEY_ANTIALIASING,
        java.awt.RenderingHints.VALUE_ANTIALIAS_ON
    )
    val (squareSide,x0,y0,wid)=squareGeometry
    for (x <- 0 until maze.step*2+1){
      for (y <- 0 until maze.step*2+1){
        if (maze(x,y)== -1){
          g.setColor(Color.BLACK)
        }else if (maze(x,y)==0){
          g.setColor(Color.WHITE)
        }else if(maze(x,y)==1){
          g.setColor(Color.RED)
        }else if (maze(x,y)==2){
          g.setColor(Color.GREEN)
        }else if (maze(x,y)==3){
          
        }
        g.fillRect(x0+x*wid,y0+y*wid,wid,wid)
      }
    }
  }
}

class MazeFrame(val maze:Maze) extends MainFrame{
   private def restrictHeight(s:Component){
    s.maximumSize = new Dimension(Short.MaxValue,s.preferredSize.height)
  }
   title="MAZE"
   resizable=false
   val canvas=new MazeCanvas(maze)
   contents=new BoxPanel(Orientation.Vertical){
     contents+=canvas
   }
}

object Main{
  def main(args:Array[String]){
    val maze=new Maze(10,new PoleDown(10),new BFS(10,(1,1),(19,19)))
    maze.startMake
    while(maze.makeStep){}
    maze.startSolve
    while(maze.solveStep){}
    
    val ui=new MazeFrame(maze)
    ui.visible=true
  }
}

探索済経路が赤、最短経路が緑で表示される。
f:id:lilyext:20170307154224p:plain
以下のサイトを参考にした。
自動生成迷路