An example of this applet can be viewed running from here http://www.chillipower.com/examples/maze/maze1.html to give an illustration of what it does. This uses a maze space of 100x100 cells on a regular grid.
The applet illustrates 2 aspects of GUI programming in Scala, the first is how to interact with basic javax.swing APIs directly and the second is how to go one step further and achieve the same effect using the scala.swing wrapper API instead.
The function of the Applet can be broken down into 3 simple steps:
Step 1: Produce a random maze. This uses a modified version of Prim's algorithm, running backwards from the exit until all of the available space has been covered. This will produce a simple path from the source to the exit, which is the path we seek when we try to solve the maze by starting at the start. The standard Prim's algorithm is used to produce a minimum spanning tree from a directed acyclic graph by recursively adding safe edges to the current minimum spanning tree recursively, starting at a source node.
Step 2: Use a regular (recursive) DFS algorithm to search the maze, stopping only when the exit is reached (or all paths are explored fully if there were no reachable exit).
Step 3: Remove all backtrack paths and show the single simple path from start to exit as the solution to the maze.
During maze exploration, the parts of the maze explored are marked with coloured breadcrumbs, red indicates a forward search path and blue a backtracking path (which happens when a path reaches a dead-end).
In step 2, in order to stop immediately when the exit is found (rather than conclude all other possible search branches) the recursive maze solving function throws an exception to escape out of the call stack immediately.
The code given is compatible with the very latest Scala 2.8.x trunk development builds, and with 2.7.6 the latest stable release (some 2.7.6 only versions of functions such as shuffle are commented out in preference to the newer and better 2.8 versions). Note that there are currently some issues with Arrays in 2.8.x causing run time errors with trying to create a multidimensional array. The solution that still works with current 2.8 builds is to use the Array.tabulate function.
i.e. the following works in 2.7.6 but not currently in 2.8:
var cells : Array[Array[Cell]] = new Array[Array[Cell]](WIDTH, HEIGHT)
and there are similar problems with the new Array.ofDims function too. These issues should be resolved in 2.8 final release but recently arrays in scala have been undergoing some re-factoring and so stability in this area has not been too strong.
One interesting thing to note is the use of the new Scala 2.8+ Stream.iterate function to avoid undesirable vars instead of vals, here is an example of that extracted from the code.
A typical iterative piece of code, the while loops is used to iterate over some code block whilst a particular condition is met for a given variable. For this to work the variable n needs to be updated in the loop, hence it can't be a val and has to be a var instead. This is somewhat paradigmatic of iterative imperative programming, but doesn't sit well with the strive for a more functional style.
var n = cells(exit.x)(exit.y)
while (n != null) {
n.trail = Forward
n = n.pi
update
}
What we can do here is make use of the Stream.iterate function to avoid the unsightly var n, as follows:
Stream.iterate(cells(exit.x)(exit.y))(_.pi).takeWhile(_ != null).foreach{
n => {
n.trail = Forward
update
}
}
Given that this is new in Scala 2.8 and 2.8 isn't released yet, you can augment existing 2.7.6 code with a helper function to aid the transition and improve 2.7 based code in readiness for 2.8. Here is an example of a util class that defines iterate so the same idea can be used in 2.7 based code:
def iterate[T](x:T)(f : T => T) : Stream[T] =
Stream.cons(x, iterate(f(x))(f))
Another interesting thing to note in the code is the use of a permutation on a list (to create random directions when generating or exploring the maze), here is the code:
def shuffle[T](xs: List[T], r: scala.util.Random) = {
xs.toStream.zip(Stream.const(r.nextDouble _).map(_())).toList.sort(_._2 < _._2).map(_._1)
}
The code maps the elements with a stream of random real numbers and then permutes by sorting the list, extracting the sorted items to create the random permutation (neat huh!)
The above code is 2.7.x & 2.8+ compatible, but perhaps even better is the following 2.8+ code that makes use of the new Stream.continually function:
def shuffle[T](xs: List[T])(implicit r: scala.util.Random) = {
xs.zip(Stream.continually(r.nextDouble)).sortWith(_._2 < _._2).map(_._1)
}
In terms of the GUI aspects, the application is an applet, and the example code shows 2 ways of achieving this in Scala. The first, using the swing API directly is as follows:
class MazeApplet2 extends JApplet {
override def init() {
...
}
override def start() {
}
}
Which is familiar to any Java programmer, but the more interesting approach is using the scala.swing API instead, whereby we have:
class MazeApplet extends Applet {
object ui extends UI with Reactor {
def init() = {
...
}
override def start() = {
}
}
}
Where the abstract ui attribute (of type UI) is implemented using the Reactor mixin trait (http://www.scala-lang.org/docu/files/api/scala/swing/Reactor.html), to provide the framework for event handling.
One thing that's quite clear is the obviously similarity between the function to generate and the function to solve the maze. Using the DSL-like features of Scala it should be possible to extract the common control structure / algorithm and create a new utility function to provide built-in like support for this, passing in a body function to provide the difference implementation of maze generate vs. solve.
Full code example:
/**
* Scala 2.8+ Maze Applet v0.1 20-09-2009 Louis Botterill
*/
package maze
import scala.swing.Applet
import scala.swing.Panel
import scala.swing.Reactor
import javax.swing._;
import java.awt.Graphics;
import java.awt.Color;
object Direction extends Enumeration {
type Direction = Value
val North, South, East, West = Value
}
object Breadcrumb extends Enumeration {
type Breadcrumb = Value
val Forward, Backward, Clear = Value
}
import Direction._
import Breadcrumb._
class MazeModel {
val HEIGHT = 100
val WIDTH = 100
// instantiate and initialise the 2d array - there is a direct 2d version but not working currently in scala 2.8.x
var cells = Array.tabulate(WIDTH)(i => Array.tabulate(HEIGHT)(j => Cell(i, j)))
// set everything as not visited and with no trail
def clearVisited() = {
cells.foreach(_.foreach(c => {
c.visited = false;
c.trail = Clear
}))
}
// generate maze
def generateMaze(update : => Unit) {
val exit = new Point(WIDTH - 1, HEIGHT - 1)
val start = new Point(0, 0)
// 1. Start at a particular cell, call it the "exit"
// 2. Mark the current cell as visited, and get a list of all its neighbors.
// For each neighbor, starting with a randomly selected neighbor:
// 1. If that neighbor hasn't been visited,
// remove the wall between this cell and that neighbor,
// and then recurse with that neighbor as the current cell.
// cell 0,0 is the start, open the north wall to highlight this
var s = cells(0)(0)
s.clear(North);
// cell width-1,height-1 is the exit, open the south wall to highlight this
val c = cells(exit.x)(exit.y)
c.clear(South);
// recursively process the next cell
def doNextCell(c : Cell) {
c.visited = true
c.trail = Forward
var dirs = c.getRndDirections()
while (!(dirs isEmpty)) {
val dir = dirs.head
val x = getCell(c, dir)
x match {
case Some(n) =>
if (n.visited != true) {
n.visited = true
c.clear(dir)
n.clear(getInv(dir))
n.trail = Forward
update
doNextCell(n)
n.trail = Clear
update
}
case None =>
}
dirs = dirs.tail
//Thread.sleep(1)
}
}
doNextCell(c)
}
// find the maze solution using dfs from the start node until the end
// node is located
def solveMaze(update : => Unit) {
val start = new Point(0, 0)
val exit = new Point(WIDTH - 1, HEIGHT - 1)
val s = cells(0)(0)
s.clear(North);
def doNextCell(c : Cell) {
c.visited = true
c.trail = Forward
var dirs = c.getDirections()
while (!(dirs isEmpty)) {
val dir = dirs.head
val x = getCell(c, dir)
x match {
case Some(n) =>
if (n.visited != true) {
n.visited = true
n.pi = c // set predecessor node
n.trail = Forward
update
if (n.i == exit.x && n.j == exit.y) throw new Exception("Done")
doNextCell(n)
n.trail = Backward
update
}
case _ =>
}
// take the top item off and use the rest of the list
dirs = dirs.tail
Thread.sleep(1) // add a little delay so we can watch the dfs explore and find the solution
}
}
doNextCell(s)
}
// from the exit recurse over the trail of predecessors,
// marking with a forward trail
def showSolution(update : => Unit) {
val exit = new Point(WIDTH - 1, HEIGHT - 1)
// 2.8 avoid var using Stream
// Stream.iterate(cells(exit.x)(exit.y))(_.pi).takeWhile(_ != null)
Stream.iterate(cells(exit.x)(exit.y))(_.pi).takeWhile(_ != null).foreach{
n => {
n.trail = Forward
update
}
}
// the following works fine but replaced with the above to avoid unnecessary var
/*
var n = cells(exit.x)(exit.y)
while (n != null) {
n.trail = Forward
n = n.pi
update
}
*/
}
// get the cell if possible based on current cell and the given direction
def getCell(c : Cell, dir : Direction) : Option[Cell] = dir match {
case North => if (c.j > 0) Some(cells(c.i)(c.j-1)) else None
case South => if (c.j < east =""> if (c.i < west =""> if (c.i > 0) Some(cells(c.i-1)(c.j)) else None
}
// find the inverse direction for a given direction
def getInv(dir : Direction) = dir match {
case North => Direction.South
case South => Direction.North
case East => Direction.West
case West => Direction.East
}
}
// a scala.swing.Panel, override paint(Graphics2D) to paint each of the cells
class MazePanel(m : MazeModel) extends Panel {
override def paint(g : java.awt.Graphics2D) {
m.cells.foreach(_.foreach(_.draw(g)))
}
}
// a javax.swing.JPanel, override paint(Graphics) to paint each of the cells
class MazePanel2(m : MazeModel) extends JPanel {
override def paint(g : Graphics) {
m.cells.foreach(_.foreach(_.draw(g)))
}
}
// a scala.swing.Applet based applet using scala swing wrappers
class MazeApplet extends Applet {
val m = new MazeModel()
lazy val mp = new MazePanel(m)
object ui extends UI with Reactor {
def init() = {
contents = mp
}
override def start() = {
def update = {
this.repaint()
}
m.generateMaze(update)
Thread.sleep(2000)
m.clearVisited
try {
m.solveMaze(update);
}
catch {
case e : Exception =>
}
Thread.sleep(2000)
m.clearVisited
m.showSolution(update)
mp.repaint()
this.repaint()
}
}
}
// standard javax.swing.JApplet of the maze
class MazeApplet2 extends JApplet {
val m = new MazeModel()
lazy val mp = new MazePanel2(m)
def MazeApplet2 = {
}
override def init() {
this.add(mp)
}
override def start() {
def update = {
this.repaint()
}
m.generateMaze(update)
Thread.sleep(2000)
m.clearVisited
try {
m.solveMaze(update);
}
catch {
case e : Exception =>
}
Thread.sleep(2000)
m.clearVisited
m.showSolution(update)
mp.repaint()
this.invalidate()
this.repaint()
}
override def stop() {
}
override def destroy() {
}
}
// standard Java app of the maze using JFrame
object Maze {
def main(args: Array[String]) {
val mazeApplet = new MazeApplet()
val frame = new JFrame()
frame.setBounds(50, 50, 750, 750)
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.add(mazeApplet)
frame.setVisible(true)
mazeApplet.init
mazeApplet.start
}
}
// represent a Cell of the maze
case class Cell(i: Int, j : Int) {
val size = 7; // each cell is 7px by 7px
var north : Boolean = true
var south : Boolean = true
var east : Boolean = true
var west : Boolean = true
var visited : Boolean = false
var pi : Cell = null // predecessor cell
var trail : Breadcrumb = Clear;
def draw(g : Graphics) {
val x = i * size
val y = j * size
trail match {
case Forward => {
g.setColor(Color.RED);
g.fillRect(x + 2, y + 2, size - 4, size - 4)
}
case Backward => {
g.setColor(Color.BLUE);
g.fillRect(x + 2, y + 2, size - 4, size - 4)
}
case _ =>
}
g.setColor(Color.BLACK);
if (north) {
g.drawLine(x, y, x + size, y);
}
if (south) {
g.drawLine(x, y + size, x + size, y + size);
}
if (east) {
g.drawLine(x + size, y, x + size, y + size);
}
if (west) {
g.drawLine(x, y, x, y + size);
}
}
def clear(dir : Direction) = dir match {
case North => north = false
case South => south = false
case East => east = false
case West => west = false
}
def getDirections() : scala.List[Direction] = {
var d = scala.List[Direction]()
if (!north) d = North :: d
if (!south) d = South :: d
if (!east) d = East :: d
if (!west) d = West :: d
d
}
def getRndDirections() : scala.List[Direction] = {
val directions = North :: South :: East :: West :: Nil
implicit val r = Rand.rand
Utils.shuffle(directions) //, Rand.rand)
}
}
// represent a 2d point
case class Point(x : Int, y : Int)
// init a random generator singleton
object Rand {
val rand : scala.util.Random = new scala.util.Random();
}
object Utils {
// ref: http://okmij.org/ftp/Haskell/perfect-shuffle.txt
// scala 2.7+ here's an O(n log n) solution:
/*
def shuffle[T](xs: List[T], r: scala.util.Random) = {
xs.toStream.zip(Stream.const(r.nextDouble _).map(_())).toList.sort(_._2 < nil =""> scala.List(Nil)
case _ => xs.flatMap(x => permute(xs.filter(_ != x)).map(x :: _))
}
// make a stream of x, f(x), f(f(x)), etc.
// in Haskell this is called "iterate". it ought to be in the standard library
// as Stream.iterate. "unfold" should be more general, but nonetheless I'm
// going to call this unfold for the moment...
def unfold[T](x:T)(f:T=>T):Stream[T] =
Stream.cons(x,unfold(f(x))(f))
def iterate[T](x:T)(f:T=>T):Stream[T] =
Stream.cons(x,iterate(f(x))(f))
}
.
Posts
