Maze generator again this time with Scala.js

Background

So last week I was doing maze generator using randomizes depth first search with Fable. Then, to increase “branching factor” I’ve added stack shaking. Today it’s time for slightly different approach.

As I said before this task was just kind of excuse technologies which I never used before. So far, I managed to scratch the surface of Fable, Webpack and VirtualDOM. For performance reasons VirtualDOM got replaced by jCanvas.

So, today’s new tech is Scala.js! Yay! I’m a big fan of Scala although I did not have a chance to use it for anything bigger than HelloWorld so far. I’m not saying that this task is much bigger, but at least it does something. Anyway, Scala.js, here I come!

Setting environement up

It was not trivial to set up the environment. I actually struggled with the environment for couple of days before I managed to make it run. Making it work with Webpack was painful, especially because I’m not proficient in either of those. Apparently, Scala.js does not produce modular JavaScript and expects everything to be in global, so instead of:

1
2
var jquery = require("jquery");
var scalajs = require("scalajs")(jquery);

we need this:

1
2
3
4
5
// not actual code!
var jquery = require("jquery");
global.jQuery = jquery;
require("scalajs");
var scalajs = global.scalajs;

Quite nasty. Maybe there is easier way, but it wasn’t obvious. If you know how to do it better let me know, but if you have similar problem you can use my generic empty project, but be aware - is highly opinionated.

Let’s do some coding now…

The algorithm

Most of maze generation algorithms on Wikipedia are building spanning trees for graphs where vertices are representing rooms and edges are representing doors.

Last week’s approach was randomized depth first search now it’s time for Prim’s algorithm.

Prim’s algorithm is building minimum spanning tree. We don’t need minimum, we need random spanning tree (that’s what randomized depth first search was doing). To achieve that, we can assign random weights to edges so minimum spanning tree will actually become random spanning tree. I didn’t but it could be actually interesting to play with different random distributions.

Let’s start with modelling the Node (or Vertex) and Edge:

1
2
3
4
5
6
7
8
9
trait Node[E] {
    def edges: Seq[E]
}

trait Edge[N] {
    def A: N
    def B: N
    def weight: Double
}

If you don’t know what trait is, you can think about this as interface from Java or C#. It is a little bit more complicated than that, but it is good enough aproximation, at least for this model. So, Node (vertex) has a sequence (list?) of edges going out, and Edge has two nodes, beginning and end, plus weight. That’s what Prim’s algorithm needs to work.

Actually, Edge.weight does not need to be modelled as Double. It could be declared as type parameter, let’s say W:

1
2
3
4
5
trait Edge[N, W] {
    def A: N
    def B: N
    def weight: W
}

In such case implementation of Prim’s algorithm would need a way to compare two Ws (Ordering[W] or IComparator<W>) but, for simplicity, I’ve implemented it as Double so let’s leave it like this.

So, let’s start with Prim’s solver:

1
2
3
class Prim[N <: Node[E], E <: Edge[N]](val node: N) {
    // ...
}

So, what we have is a generic class which take two types N and E where N is Node of E and E is Edge of N. We are just making sure types are consistent.

How Prim’s algorithm work? It starts with a single node and marks it as visisted. On every step it choses an edge with minimum weight which connects visited node to not visited node.

That’s kind of it and it can be derived from the name: minimum spanning tree. We know that every node needs to be in solution (the word: spanning), we don’t take edges with both ends already visited as we don’t want cycles (the word: tree), we don’t take edges with both ends not visited as it could create disjoint graph (the word spanning again, and tree but not forest). We also take lightests edge available as we need it to be minimum. Don’t quote this though, it is not formal proof of correctness :)

So this description suggests the solution needs: set of visited nodes and ordered queue of edges. 

1
2
3
4
5
6
7
8
9
import scala.collection.{mutable => c}

class Prim[N <: Node[E], E <: Edge[N]](val node: N) {
    private val ordering: Ordering[E] = Ordering.by(e => -e.weight)
    private val queue = c.PriorityQueue.empty(ordering)
    private val visited = c.HashSet.empty[N]

    //...
}

Nothing fancy. We have set of visited nodes (visited), we have ordered queue of edges (queue). To make it ordered we use PriorityQueue provide a way to compare edges (ordering) by comparing weights. As PriorityQueue puts heaviest first we need to reverse it. I used -weight but Ordering has actually a method reverse (I just found it out too late).

As I said last week I like one-liners to remove clutter from business code, so let’s define few for this task:

1
2
3
4
5
private def test(node: N) = visited.contains(node)
private def mark(node: N) = visited.add(node)
private def dequeue(): Option[E] = if (queue.isEmpty) None else Some(queue.dequeue())
private def fanout(node: N) = queue.enqueue(node.edges: _*)
private def visit(node: N) = { mark(node); fanout(node) }

We can test the node if it was visited, we can mark the node as such, we dequeue the edge from queue of lightests edges, and we can fanout from given node by adding all outgoing edges to the queue of lightests edges. As last one we have full definition what a visit means, it is marking and then fanning out (I use this word wrongly, don’t I?).

Two non-trivial things. My reimplementation of deqeue returns Option[E]. I actually still don’t belive that there is no dequeue returning option on PriorirtyQueue. I missed it, right? For those who don’t know what I’m whining about let me explain. In functional languages, and Scala claims to be one, exceptions are for trully exceptional situations like, “cosmic ray just hit the CPU”. The expected situations should be handled by type system, and dequeue is perfect example of it: queue can be empty and when you try to get something from it the result should be “nada, come back later”. And that’s exactly what Option type gives us.

The other thing (Am I digressing all the time?) is the splat operator (:_*) in fanout. I actually spent good 15 minutes looking for it as my google-foo failed me. Apparently, enqueue takes multiple arguments (varargs in Java or params in C#) but all I had was a sequence (one argument). C# deals with that implicitly but Scala requires this… thing. I’m actually not sure what it is, maybe something like static cast in F# (:>) with wilcard (_) as a type? Anyway, it works as expected.

So we have mini language for domain of Prim’s algorithm. Let’s do the algorithm then. If it was about solving the problem I would use a for loop (while, foreach whatever). If it was a language with lazy generators or coroutines I would reuse the for loop with yield, but Scala does not have lazy generators. I guess “yet”, as every language is getting them (JavaScript and Kotlin). Anyway, that’s why we need to store the state (visited and queue) as class members and not inside a generator function.

Let’s go: 

1
2
3
4
5
6
7
8
9
10
def next(): Option[E] = {
    dequeue().flatMap { edge =>
        (test(edge.A), test(edge.B)) match {
            case (true, true) => next()
            case (false, true) => visit(edge.A); Some(edge)
            case (true, false) => visit(edge.B); Some(edge)
            case _ => throw new IllegalArgumentException("Not a valid graph")
        }
    }
}

So this method potentially returns next edge. Potentially as we may run out of edges and that’s the stop condition for algorithm. So it takes next edge (dequeue) and if there are no more edges it just returns None and that’s it (flatMap). If there was an edge still available it tests both ends (test(edge.X)). If both are already visited (true, true) this edge is not good let’s take next one. If only one of them is visited (true, false and false, true) mark visit the unvisited one and return this edge (Some(edge)). If both of them seems to be not visited yet something went horribly wrong (cosmic ray?) and it’s time to panic (throw).

Nice.

The domain

We have generic Prim’s algorithm implemented so far but we need to use to solve very specific problem. Building a maze. So let’s deal with the domain.

Let’s start with Point with geometric coordinates:

1
case class Point(x: Int, y: Int)

a Room which is a Node (has trait or implements interface) in a graph:

1
2
3
4
5
6
7
8
9
class Room(val position: Point) extends Node[Door] {
    val edges = c.ArrayBuffer.empty[Door]

    def add(other: Room, weight: Double) = {
        val door = new Door(this, other, weight)
        edges += door
        other.edges += door
    }
}

It additionally, defines add method (I should have named it connect I guess) which creates door connecting two rooms. I’m actually quite impressed how flexible scala is in this respect. Node trait defines edges as def edges: Seq[E] (a method returning sequence) but Room class implements it as val edges: ArrayBuffer[Door] (a field holding mutable collection of Door). No implicit interface implementation or shadowing was needed, it just worked.

The last one is Door (or edge):

1
class Door(val A: Room, val B: Room, val weight: Double) extends Edge[Room]

The last thing we need for domain is the way to create the graph:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Model(size: Point, random: () => Double) {
    private val rooms = Array.tabulate(size.x, size.y) { (x, y) => new Room(Point(x, y)) }

    private def at(x: Int, y: Int): Room = rooms(x)(y)
    private def connect(room: Room, other: Room, weight: Double) = room.add(other, weight)

    for (x <- 0 until size.x; y <- 0 until size.y) {
        if (x > 0) connect(at(x, y), at(x - 1, y), random())
        if (y > 0) connect(at(x, y), at(x, y - 1), random())
    }

    def room00 = rooms(0)(0)
}

Model object takes a size of the world and random number generator (so we can use any generator we want). It creates two dimensional array of rooms (Array.tabulate) initializes it (new Room(x, y)). If provides a function get room object at given location (at(...): Room) and connect two rooms. Both methods are kind of overkill but make the business logic (the for loop) clutter-free. We also export starting room (room00). If you really wanted to you could implement this Model class as a single function: createModel: (Point, () => Double) => Room, but old habits die hard.

So, once again, the domain is implemented. All what is left is the UI or presentation layer.

The presentation layer

I won’t be describing UI in details, so please refer to Github for actual sources. In general it goes like this…

We have some constants:

1
2
3
4
5
6
7
val WORLD_SIZE = Point(100, 100)

val ROOM_COLOR = "#fff"
val DOOR_COLOR = "#eee"

val ROOM_SIZE = 6
val DOOR_SIZE = 1

defining size of the universe (WORLD_SIZE), some colors, dimensions in pixels (DOOR_SIZE and ROOM_SIZE), and helper functions: 

1
2
def toPixel(v: Int): Int = v * ROOM_SIZE + (v + 1) * DOOR_SIZE
def toPixel(p: Point): Point = Point(toPixel(p.x), toPixel(p.y))

to translate between room location to pixel position (toPixel).

We need to intialize canvas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def initialize() = {
    val size = toPixel(WORLD_SIZE)
    val (width, height) = (size.x, size.y)
    val view = s"0 0 $width $height"

    jQuery("#canvas")
            .attr("width", width).attr("height", height)
            .attr("viewbox", view).attr("viewport", view)

    val context =
        document.getElementById("canvas").asInstanceOf[Canvas]
                .getContext("2d").asInstanceOf[CanvasRenderingContext2D]

    jQuery("#restart").click((e: Any) => restart(context, width, height))
}

by setting width, height and viewbox, and attach restart method as a handler for click event on Restart button.

Restart shuts down previous animation (shutdown), sets up the drawing context of the canvas (context), initializes the model and algorithm and starts animation on interval (window.setInterval). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var handle: Option[Int] = None

def restart(context: CanvasRenderingContext2D, width: Int, height: Int) = {
    shutdown()

    context.clearRect(0, 0, width, height)

    val model = new Model(WORLD_SIZE, Random.nextDouble)
    val algorithm = new Prim[Room, Door](model.room00)

    handle = Some(window.setInterval(() => step(algorithm, context), 0))
}

def shutdown() = {
    handle.foreach(window.clearInterval)
    handle = None
}

We will also need to actually draw rooms and doors:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def drawRoom(context: CanvasRenderingContext2D, room: Room) = {
    val p = toPixel(room.position)
    context.fillStyle = ROOM_COLOR
    context.fillRect(p.x, p.y, ROOM_SIZE, ROOM_SIZE)
}

def drawDoor(context: CanvasRenderingContext2D, door: Door) = {
    val a = toPixel(door.A.position)
    val b = toPixel(door.B.position)
    val o = ROOM_SIZE / 2
    context.strokeStyle = DOOR_COLOR
    context.lineWidth = ROOM_SIZE
    context.beginPath()
    context.moveTo(a.x + o, a.y + o)
    context.lineTo(b.x + o, b.y + o)
    context.closePath()
    context.stroke()
}

The last part is the single step of animation, which takes algorithm and drawing context:

1
2
3
4
5
6
7
8
9
def step(algorithm: Prim[Room, Door], context: CanvasRenderingContext2D) = {
    algorithm.next() match {
        case None => shutdown()
        case Some(door) => 
            drawDoor(context, door)
            drawRoom(context, door.A)
            drawRoom(context, door.B)
    }
}

If next edge/door (algorithm.next()) cannot be found (case None) then animation is stopped (shutdown()) otherwise it just draws door and two rooms.

And yet again: that’s it.

Online demo

You can get your own copy from Github or you can just watch it working here

Conclusion

I really loved the fact that I had access to Scala collections and they worked as expected. It gives you this warm feeling when you can just use PriorirtyQueue of the shelf. The code Scala.js produces is not nearly as readable as Fable gives us. Is actually pretty awful with horribly mangled names. That’s why I was struggling to understand why it does not see jQuery and how to make it work with Webpack. I do now, but it took me a while.