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
One more time…
So the next approach, after Randomized depthfirst search, Randomized depthfirst search with stack shaking, Random spanning tree with Prim’s algorithm, to maze generation is Kruskal’s algorithm. Technically, it’s still the same thing: random spanning tree, it’s just different approach. This time the new tech to try was: Kotlin and Jade/Pug. I didn’t do too much Jade, I just wanted to try, but I have to say again: Kotlin… good stuff.
The algorithm
Kruskal algorithm, is quite simple to describe:
 Take edge with lowest weight
 if it would form a cycle, ignore it
 otherwise, add it to solution
 if there are still edges left, repeat
To apply Kruskal’s algorithm to maze generation we don’t need to do “minimum spanning tree” as “random spanning tree” is enough. So “take edge with lowest weight* should be replaced with “take any edge”. To achieve that we can just shuffle all the edges before feeding them to the algorithm. Let’s write a shuffle
method to shuffle array inplace, and shuffled
function returning a shuffled version of given sequence:


NOTE: If you are unfamiliar with Kotlin it might a little bit obscure. All three methods above are extension methods (familiar for C# users), and for all of them this is implicitly pointing to the object they have been executed for. So, this[x]
(in swap
) is accessing element x
in MutableList
, size
(in shuffle
) is the length of MutableList
. Extension method apply
is a different story.
The only challenge is “cycle detection”. I used disjointset data structure, and I strongly recommend reading my other blogpost.
For Kruskal’s algorithm we need to define an Edge
:


which is just an entity connecting two nodes, A
and B
. The algorithm itself is very simple:


One challenge, as mention before, is “cycle detection” which is handled by DisjointSet. It also, to allow animation, returns only one edge at the time (see next
). So what it does?
It takes a sequence of edges
as input. They are assumed to be in right order, sorted by weight for minimum spanning tree, and randomized for random spanning tree. It creates empty DisjointSet
to track cycles. On each step, it checks if there are still edges to test (iterator.hasNext
). If so, it takes next edge and check if it would form a cycle (sets.test
). If it would, it tries next
edge, if it wouldn’t it adds this edge to solution (sets.merge
) and returns it.
That’s kind of it. Rest is just presentation.
Hex tiles
All algorithms I was using so far were in square grid space, but they did not need to be. So for this one I decided to build a maze of hex tiles.
It added some complexity to coordinates and drawing. I won’t be getting into details as there is a lot of websites talking about hex tiles as they are foundation of many games. If you are interested just start here.
The domain model is quite trivial:


there are tiles and they are connected with doors. It is worth noting that Door
implements Edge<N>
interface.
Building the world in rectangular space wasn’t particularly tricky but required some pen and paper experiment to get connection right:


The method above returns a an ordered sequence of doors (we will need to shuffle them for the algorithm).
Presentation layer is a little bit messy to be honest, but I just wanted to make it work. Using image below and some primary school maths
we can calculate positions of tiles in pixels and needed size of canvas:


On top of that we can draw tiles as well:


Just note that these paint
functions are extension methods for Tile
and Door
respectively.
User interface
The only remaining thing is presentation and some user interaction.
We need to get references to some DOM elements:


then configure canvas:


and attach event listener to Restart button:


which will potentially kill previous animation, clear the canvas and start new animation.
Let’s implement those. Clearing canvas is just about painting it black:


Starting animation is a little bit more complex:


It does have a handle
(nullable int) to store timeout handler so we can cancel it if needed. We starting animation (launch
) it generates all the edges (buildWorld
) and shuffles them (shuffled
). Then passes this sequence of edges to animate
function which is handling one edge at the time using a timer (window.setTimeout
). It takes next edge (algorithm.next()
), paints it (paint
) and schedules next step (handle = window.setTimeout(...)
). It worth noting that when first null
edge is returned the whole loop stops.
Finally, the cancel
method:


which just cancels potentially scheduled “next step”, therefore cancelling whole animation.
Conclusion
This is very subjective but Kotlin seems to me to be most polished from all languages I’ve tried. But they are all really good. Fable has a lot of community behind it, Scala.js is backed by… you know… Scala and Kotlin is done by JetBrains. There is elephant in the room as well, and it is called TypeScript. Maybe next time.
Sources
You can find sources here or you can just use online demo