Quick links
 Randomized depthfirst search
 Randomized depthfirst search with stack shaking
 Random spanning tree with Prim’s algorithm
 Random spanning tree using Kruskal’s algorithm
 Hybrid of depthfirst search and Kruskal’s algorithm
 Source code
 Online demo
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:


we need this:


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
:


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
:


In such case implementation of Prim’s algorithm would need a way to compare two W
s (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:


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.


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 oneliners to remove clutter from business code, so let’s define few for this task:


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 nontrivial 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 googlefoo 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:


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:


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


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):


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


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) clutterfree. 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:


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


to translate between room location to pixel position (toPixel
).
We need to intialize canvas:


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
).


We will also need to actually draw rooms and doors:


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


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.