- 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
I’ve found Redgate’s first ever coding challenge on LinkedIn and I decided to do it with Fable in the browser. The challenge is about writing an application to generate mazes (thus the Daedalus reference). I wasn’t going to apply as my solution is probably the most trivial one using “randomized DFS”, so there is nothing to show off, but, I wanted to use those tools.
EDIT: eventually, it did apply
Initially solution was building SVG with VirtualDOM. It was very neat as Fable/VirtualDOM uses Elm architecture (check Fable samples page). It was fast enough to solve the problem but unfortunatelly, for bigger mazes (>50x50), not fast enough for live animation. Changing multiple
<rect> to one long multipart
<path> made it a little bit faster (~20%) but it still wasn’t good enough and it was definitely slowing down further it went.
The final version is not as ambitious, uses jQuery and jCanvas. Presentation layer is very old school, but it works and is very fast (relatively speaking, of course). Note, I could deal with the
“You’re very clever, young man, very clever,” said the old lady. “But it’s functions all the way down!”
Scott Wlaschin says “No abstraction is too small”. I agree, I’m a big fan of “extracting abstraction” and I’m so glad F# supports and encourages local one-liners. I believe problems should be decomposed into small managable chunks first and then composed back into solution. Things should be named appropriately as well. Let me use example given by Kevlin Henney (it’s actually Dan North’s example but I have no link):
Even if we understand every single word in this statement, it is still unclear what purpose it serves. It is not abstract enough, it contains too much of “implementation”. Maybe we should consider this as an alternative:
Yup, that’s much better.
For every solution, at some point there will be a need for some “ugly implementation details”. It is just nicer when you can push it far away from business logic so it does not get in a way when you try to reason about what this code “actually does”.
In this article I will use a some one-liners. They might seem like overkill for this task but this is primarily fun project and using them is fun!
There are few algorithms listed on Wikipedia and randomized depth-first search is probably the simplest one.
It has two disadvantages:
- solution has a low branching factor and contain many long corridors (please note, that this issue was addressed in following blogpost)
- solution does not contain cycles - This problem applies to most of solutions from Wikipedia. It seems that “maze generation problem” is perceived as “random spanning tree”. Cycles can be seen as shortcuts, therefore making it easier to solve for potential maze explorer, but also they open the door to “be lost forever”, making it infinitely harder. Trade-offs, trade-off, trade-offs.
I’m going to decompose the solution into smaller pieces instead of using single monolithic function.
A physicist and a mathematician setting in a faculty lounge. Suddenly, the coffee machine catches on fire. The physicist grabs a bucket and leaps towards the sink, fills the bucket with water and puts out the fire. The second day, the same two sit in the same lounge. Again, the coffee machine catches on fire. This time, the mathematician stands up, gets a bucket, hands the bucket to the physicist, thus reducing the problem to a previously solved one.
Let’s start with generic depth-first search then:
mark: 'T -> unit is the function which will take a node and mark it as visited,
test: 'T -> bool will test is node has been visisted already,
fanout: 'T -> 'T seq will take a node and return a sequence of connected nodes (neighbours?) and finally
node: 'T is just a starting point.
The algorithm goes like this:
- if node has not been visited yet (
node |> test) mark it as visisted (
apply mark) and return it (
- for every connected node (
node |> fanout), rinse and repeat (
Seq.collect traverse mark test fanout)
If you don’t know what
apply does I would recommend my other post.
Done. We can go home… OK, I’m just joking.
NOTE: This solution is vulnerable to stack overflow as it goes deeper and deeper with every visited node. The actual solution uses different implementation of DFS which is using
while loop and lists to simulate call stack (I called it
stackless which is a little self contradicting, isn’t it?). Idea is absolutely the same though, but code is less elegant.
So, we have an algorithms. Now we need domain model.
Initially, the domain of this problem consisted of the
World, which is a collection of
Rooms which in turn have their
Location and are connected (or not) through
Exits. Not all of those concepts are needed for the algorithm. They may or may not be needed by presentation layer but we probably shouldn’t jump ahead, I guess.
So, let’s start with
Location (x and y coordinates) and
Direction (north, east, etc…):
There is also a relation between directions (
opposite) and a function allowing to move from one location in given direction (
Traversing a maze is about actions (or moves). Theoretically, we could model it with single type of action (move south from 5,4 to 5,5), but first move (which is start at 0,0) does not have source nor direction and with language like F# you should not compromise on domain model aka make illegal state unrepresentable.
So, I ended up with two possible actions: teleporting to starting location and moving from one location to another:
Action has it’s “property” called target, the
Location where it ends:
It is important to realize, that DFS in this case does not really traverse rooms (graph nodes), it actually traverses actions (graph edges), although it is the room which is visted (not action).
Long story short, there is some glue needed between “The algorithm” and “The domain” presented above.
Let’s start with some one-liners for solution:
Set which does not use structural equality (I learnt it the hard way). Therefore two identical tuples would not be recognised as such. We need to
encode tuple value as something which is properly handled by
Set. Encoding tuple as single
int is one options, encoding it as
string would be also valid (but a little but slower, I suppose).
We have function to test is given location is valid for given maze size (
isValid), we can test if action points to a room which has been visisted before (
test) and mark the location as visisted if needed (
mark). That is just a small vocabulary for our problem.
It’s time to define
fanout method which will return all valid the neighbours:
As you can see, it takes a source location, then generates a sequence of
MoveTo actions in every direction and then eliminates the ones with invalid target locations (the ones which would point outside the maze). You may wonder why
fanout returns candidates in pretty deterministic order. And that’s fair question. I just don’t think randomization stategy is responsibility of
fanout function, I think we can postpone this decision (at least for 5 more seconds).
We have all building blocks ready now and it’s time to call
DFS.stackless). As I said before
traverse operate on actions (not locations), and functions we defined so far work on locations. We will need some adapters, and some randomization of
Functional composition to the rescue:
It starts with action (
InitAt (0, 0)), and uses composition to adapt input argument of
fanout. It also randomizes the output of
And this sequence of actions it the result of
Done, again. OK, we need presentation.
Without getting into much details we need a
<button> and a
That’s the UI. Right? Yeah, kind of. Be aware that the code here is for illustration only, please refer to github for actual working sources.
.d.ts definition files into Fable to have strongly typed interfaces. In this case though, I used so little of it, that I could manage dynamic invocation.
Long story short,
importDefault get’s translated into
$ operator is invoke,
? operator is get and
<- is set.
$ operator in many cases can be ommited.
a ? b ? c(77) would be translated to
a ? b ? c <- 11 would be translated to
a.b.c = 11;.
Please note, that as there is an assumptions that everything returns
obj -> obj which is also an
obj). F# does not like dangling result values so you need to
ignore results you don’t care about. I definitely recommend referring to Fable website for more details.
Let’s define some constants:
and a simple function to convert world location to coordinates in pixels:
Let’s set the
<canvas> up, by setting
viewport (using jQuery):
click event on “Restart” button:
The thing with
cancel might be a little bit unclear. Function
startAnimation will return a function (function returning function, yes) which can be called to cancel animation. So next time
Restart button is pressed previous animation will be cancelled before starting new one. To avoid
None) checking (on first run)
cancel just gets initialized with function which does nothing (yes,
id is a function which does nothing).
Back to solution, when button is pressed potential old animation is cancelled (
cancel()), canvas is cleared (
canvas ? clearCanvas () |> ignore) and new animation is started (
cancel <- startAnimation canvas).
There is only one method left, then:
Please note, the code below in the scope of
We will definitely need to draw rectangles on canvas, and that’s kind of all we are going to do. I will use
jCanvas to do this, but it is an overkill, of course, it could (and should?) be done with browser API, but I’m exploring here, right?
As with dynamic invocation eveything is
jCanvas.drawRect first into
Yup. Done. Not pretty but done. We can forget about this traumatic experience now. It actually generates quite readable code:
drawBox and implement
drawRoom to draw a room, and
drawDoor to draw a door:
Room is drawn as big square, while
Door is just a slim rectangle (depends on relation between
ROOM_SIZE). As you can see doors have different shape depending on direction (for example: North vs East).
Now, we need to start traversing the maze:
You can notice
Enumerator here, which might be a little bit cryptic but it just provides slighlty more F#-ish way to use
The last part is the animation loop, we need to draw actions as they come. Let’s schedule a callback every 1/60th of a second (should I use
requestAnimationFrame here?) which will take current frame (well… action), draw adequate objects (
drawDoor) and then proceed to next action (
action <- action |> Option.bind Enumerator.next):
The last line returns
cancel (returns a function, but does not call it) from
startAnimation so animation can be externally cancelled.
Time.interval is just a wrapper for
clearInterval to have more F#-ish experience:
I guess that’s it.
You can find solution on github. It actually has many branches as I was trying many approaches. I started with “Immutable domain with VirtualDOM to generate SVG”, then I switched to “Mutable domain with VirtualDOM to generate SVG paths”, then I switched to “Mutable domain with jCanvas” and then I realized that half of domain was actually needed by VirtualDOM approach only. So, last incarnation if Daedalus is “Mutable mini domain with jCanvas”.
If you want to just see it work, you can find it here
As mentioned DFS has a problem with low branching factor. I’ll try to address the problem in next blogpost.