- 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 the next approach, after Randomized depth-first search, Randomized depth-first 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.
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 in-place, 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,
swap) is accessing element
shuffle) is the length of
MutableList. Extension method
apply is a different story.
The only challenge is “cycle detection”. I used disjoint-set data structure, and I strongly recommend reading my other blogpost.
For Kruskal’s algorithm we need to define an
which is just an entity connecting two nodes,
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.
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
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
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.
which just cancels potentially scheduled “next step”, therefore cancelling whole animation.
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.