Kruskal, Kotlin, and Hex Tiles

One more time…

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.

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 in-place, and shuffled function returning a shuffled version of given sequence:

1
2
3
4
5
6
7
8
9
10
11
12
13
fun <T> MutableList<T>.swap(x: Int, y: Int) {
    val t = this[x]
    this[x] = this[y]
    this[y] = t
}

fun <T> MutableList<T>.shuffle() {
    fun random(range: Int) = Math.floor((Math.random() * range) + 1.0)
    for (i in size - 1 downTo 0) swap(i, random(i))
}

fun <T> Sequence<T>.shuffled(): Sequence<T> =
        this.toMutableList().apply { shuffle() }.asSequence()

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 disjoint-set data structure, and I strongly recommend reading my other blogpost.

For Kruskal’s algorithm we need to define an Edge:

1
2
3
4
interface Edge<N> {
    val A: N
    val B: N
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Kruskal<N, E : Edge<N>>(edges: Sequence<E>) {
    val iterator = edges.iterator()
    val sets = DisjointSet<N>()

    fun next(): E? {
        if (!iterator.hasNext())
            return null

        val edge = iterator.next()
        if (sets.test(edge.A, edge.B))
            return next()

        sets.merge(edge.A, edge.B)
        return edge
    }
}

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.

Hex tiles 5x5

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:

1
2
data class Tile(val x: Int, val y: Int)
data class Door(override val A: Tile, override val B: Tile) : Edge<Tile>

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fun buildWorld(width: Int, height: Int): Sequence<Door> {
    val result = mutableListOf<Door>()
    val map = mutableMapOf<Int, Tile>()

    fun encode(x: Int, y: Int) = y * (width + 1) + x
    fun tileAt(x: Int, y: Int) = map.getOrPut(encode(x, y)) { Tile(x, y) }

    for (y in 0..height) {
        for (x in 0..width) {
            val tile = tileAt(x, y)
            if (x > 0) result.add(Door(tile, tileAt(x - 1, y)))
            if (y > 0) result.add(Door(tile, tileAt(x, y - 1)))
            if (x < width && y > 0 && x % 2 == 0) result.add(Door(tile, tileAt(x + 1, y - 1)))
            if (x > 0 && y > 0 && x % 2 == 0) result.add(Door(tile, tileAt(x - 1, y - 1)))
        }
    }

    return result.asSequence()
}

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

Geometry

we can calculate positions of tiles in pixels and needed size of canvas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
val TILE_COLOR = "#fff"
val DOOR_COLOR = "#eee"

val TILE_R = 8.0
val TILE_H = TILE_R * Math.sqrt(3.0) / 2
val TILE_MARGIN = (TILE_R - TILE_H) * 2

data class Point(val x: Double, val y: Double)

fun Tile.center(): Point {
    val rx = x * TILE_H * 2 + TILE_R
    val ry = y * TILE_R * 2 + TILE_H + (x % 2) * TILE_R
    return Point(rx + TILE_MARGIN, ry + TILE_MARGIN)
}

fun worldSize(width: Int, height: Int): Point {
    val rx = width * TILE_H * 2 + TILE_R * 2
    val ry = height * TILE_R * 2 + TILE_H * 2 + TILE_R
    return Point(rx + TILE_MARGIN * 2, ry + TILE_MARGIN * 2)
}

On top of that we can draw tiles as well:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
fun Tile.paint(context: CanvasRenderingContext2D) {
    val (x, y) = center()
    val r = TILE_R
    val h = TILE_H
    context.fillStyle = TILE_COLOR
    context.beginPath()
    context.moveTo(x + r, y)
    context.lineTo(x + r / 2, y + h)
    context.lineTo(x - r / 2, y + h)
    context.lineTo(x - r, y)
    context.lineTo(x - r / 2, y - h)
    context.lineTo(x + r / 2, y - h)
    context.closePath()
    context.fill()
}

fun Door.paint(context: CanvasRenderingContext2D) {
    val (sx, sy) = A.center()
    val (ex, ey) = B.center()
    context.strokeStyle = DOOR_COLOR
    context.lineWidth = TILE_R
    context.beginPath()
    context.moveTo(sx, sy)
    context.lineTo(ex, ey)
    context.closePath()
    context.stroke()
    A.paint(context)
    B.paint(context)
}

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:

1
2
3
val canvas = document.getElementById("main") as HTMLCanvasElement
val context = canvas.getContext("2d") as CanvasRenderingContext2D
val button = document.getElementById("restart") as HTMLButtonElement

then configure canvas:

1
2
3
val size = worldSize(WORLD_WIDTH, WORLD_HEIGHT)
canvas.width = size.x.toInt()
canvas.height = size.y.toInt()

and attach event listener to Restart button:

1
2
3
4
5
button.onClick {
    cancel()
    clear()
    launch()
}

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:

1
2
3
4
fun clear() {
    context.fillStyle = "#000"
    context.fillRect(0.0, 0.0, size.x, size.y)
}

Starting animation is a little bit more complex:

1
2
3
4
5
6
7
8
9
10
11
12
var handle: Int? = null

fun animate(algorithm: Kruskal<Tile, Door>) {
    algorithm.next()?.apply {
        paint(context)
        handle = window.setTimeout({ animate(algorithm) }, 0)
    }
}

fun launch() {
    animate(Kruskal(buildWorld(WORLD_WIDTH, WORLD_HEIGHT).shuffled()))
}

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:

1
2
3
4
5
6
fun cancel() {
    if (handle != null) {
        window.clearTimeout(handle!!)
        handle = null
    }
}

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