- Randomized depth-first search
- Randomized depth-first search with stack shaking
- Random spanning tree with Prim’s algorithm
- Random spanning tree using Kruskal’s algorithm
- Hybrid of depth-first search and Kruskal’s algorithm
- Source code
- Online demo
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!
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…
Most of maze generation algorithms on Wikipedia are building spanning trees for graphs where vertices are representing rooms and edges are representing doors.
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
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.
Edge.weight does not need to be modelled as
Double. It could be declared as type parameter, let’s say
In such case implementation of Prim’s algorithm would need a way to compare two
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
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
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:
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
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 (
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 (
foreach whatever). If it was a language with lazy generators or coroutines I would reuse the
for loop with
queue) as class members and not inside a generator function.
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 (
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:
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
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) 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.
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 (
ROOM_SIZE), and helper functions:
to translate between room location to pixel position (
We need to intialize canvas:
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
algorithm and starts animation on interval (
We will also need to actually draw rooms and doors:
The last part is the single step of animation, which takes
algorithm and drawing
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.
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.