This post follows the Mazes for Programmers book - if you haven’t gone through the book/written the suggested code, you can find the required sources on this page.

Note: you’ll need to have gone through Chapter 2 for the code - those are the exercises at the end of Chapter 1, but it only really makes sense to implement them once you have completed Chapter 2 (so you can visualise the changes)

Note 2: I don’t use ruby much, if at all. If there’s a more idiomatic way to do something, let me know!

BinaryTree

This is (roughly) the code you should have by the end of Chapter 2:

class BinaryTree
    def self.on(grid)
        grid.each_cell do |cell|
            neighbors = []

            neighbors << cell.north if cell.north
            neighbors << cell.east if cell.east

            neighbor = neighbors.sample
            cell.link(neighbor) if neighbor
        end
    end
end

And it generates mazes like:

❯ ruby -I. binary_tree_demo.rb
+---+---+---+---+---+---+---+---+---+---+---+---+
|                                               |
+   +---+   +   +   +---+---+---+---+   +   +   +
|   |       |   |   |                   |   |   |
+   +---+   +   +   +   +---+---+---+   +---+   +
|   |       |   |   |   |               |       |
+---+---+   +---+   +---+   +   +---+   +   +   +
|           |       |       |   |       |   |   |
+   +---+   +---+   +---+---+   +   +   +   +   +
|   |       |       |           |   |   |   |   |
+   +   +   +   +---+   +   +---+---+   +   +   +
|   |   |   |   |       |   |           |   |   |
+---+   +   +   +   +   +---+   +   +---+---+   +
|       |   |   |   |   |       |   |           |
+---+---+---+---+---+   +   +   +---+---+---+   +
|                       |   |   |               |
+---+   +---+   +   +   +   +---+   +---+   +   +
|       |       |   |   |   |       |       |   |
+   +---+---+   +   +---+   +---+---+   +   +   +
|   |           |   |       |           |   |   |
+   +---+---+   +---+   +---+   +   +---+---+   +
|   |           |       |       |   |           |
+   +---+---+   +   +---+---+   +---+---+   +   +
|   |           |   |           |           |   |
+---+---+---+---+---+---+---+---+---+---+---+---+

Reorient the Passages

The logic selecting passages to link together is hard-coded in the tree itself - namely:

            neighbors = []

            neighbors << cell.north if cell.north
            neighbors << cell.east if cell.east

            neighbor = neighbors.sample
            cell.link(neighbor) if neighbor

Let’s start by abstracting that away such that we take a variable number of biases. On a square grid the options are limited but if we had something hexagonal, you can see how it scale:

class BinaryTreeWithBias
    attr_reader :biases
    def initialize(*biases)
        @biases = biases.to_a
    end

    def on(grid)
        grid.each_cell do |cell|
            neighbors = []
            @biases.each do |bias|
                neighbors << cell.public_send(bias) if defined? cell.public_send(bias)
            end

            neighbor = neighbors.sample
            cell.link(neighbor) if neighbor
        end
    end
end

Side note, see the use of public_send - it’s one of those things that show ruby’s roots in oop languages like smalltalk.

Just for kicks, let’s create a tree with :north and :south biases:

grid = Grid.new(12,12)
BinaryTreeWithBias.new(:north, :south).on(grid)

yielding:

❯ ruby -I. binary_tree_demo.rb
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |
+---+   +   +---+   +   +---+   +---+   +   +   +
|   |   |   |   |   |   |   |   |   |   |   |   |
+   +   +   +   +   +   +   +---+   +   +---+   +
|   |   |   |   |   |   |   |   |   |   |   |   |
+---+---+   +   +---+   +---+   +   +---+   +   +
|   |   |   |   |   |   |   |   |   |   |   |   |
+   +   +---+---+   +   +   +   +   +   +   +---+
|   |   |   |   |   |   |   |   |   |   |   |   |
+---+   +   +   +   +---+   +---+   +   +   +   +
|   |   |   |   |   |   |   |   |   |   |   |   |
+   +   +   +   +---+   +   +   +   +   +   +---+
|   |   |   |   |   |   |   |   |   |   |   |   |
+---+   +   +   +   +   +   +   +   +   +   +   +
|   |   |   |   |   |   |   |   |   |   |   |   |
+   +---+---+   +   +   +   +   +   +   +   +   +
|   |   |   |   |   |   |   |   |   |   |   |   |
+---+   +   +---+   +---+   +   +---+   +---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |
+   +   +---+   +   +   +   +---+   +---+   +   +
|   |   |   |   |   |   |   |   |   |   |   |   |
+   +   +   +---+   +   +   +   +---+   +   +   +
|   |   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+

Changing the Bias

How do we bias our BinaryTree towards maybe more horizontal or vertical pages? As it stands we sample the biases with uniform probability. That is, if the choice is between :north and :east, both are equally likely to be chosen.

Let’s try assigning weights to each bias - for instance, we may want the likelihood of a passage extending vertically to be twice as much as horizontally. We could represent this as {:north => 2, :east => 1}.

Sampling because a case of (1) generating a random number with 0 <-> total weight (3 in the above) and (2) building the relevant intervals (so here, [0-2] => :north and (2-3] => :east). Depending on where the sample falls within that range, it will dictate the direction we take.

I didn’t find an elegant way to do a running sum, but we can be explicit:

class BinaryTreeWithBiasAndWeights 
    attr_reader :weights, :biases

    def initialize(direction_to_weights)
        @weights = direction_to_weights
        @biases = @weights.keys
    end

    def on(grid)
        grid.each_cell do |cell|
            neighbors = {}
            @biases.each do |bias|
                neighbors[bias] = cell.public_send(bias) if defined? cell.public_send(bias)
            end

            # do a weighted sample
            running_sum = 0
            biases_boundaries = []
            @biases.each do |bias|
                running_sum += @weights[bias]
                biases_boundaries << running_sum
            end

            total_weights = @biases.map { |bias| @weights[bias]}.sum()
            selection = rand(total_weights+1) # because rand doesn't include the max
            neighbor = neighbors[@biases[biases_boundaries.bsearch_index{|elem| elem >= selection}]]
            cell.link(neighbor) if neighbor
        end
    end
end

Running it:

grid = Grid.new(12,12)
BinaryTreeWithBiasAndWeights.new({:north =>2, :east => 1}).on(grid)

and there we have it:

❯ ruby -I. binary_tree_demo.rb
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |       |   |
+   +---+   +   +   +---+   +---+   +   +   +   +
|   |       |   |   |       |       |   |   |   |
+   +   +   +   +   +---+   +   +   +---+   +---+
|   |   |   |   |   |       |   |   |       |   |
+---+   +---+   +   +   +   +   +   +   +---+---+
|       |       |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +---+   +   +   +
|   |   |   |   |   |   |   |   |       |   |   |
+   +---+   +   +   +---+   +   +   +   +   +   +
|   |       |   |   |       |   |   |   |   |   |
+   +   +   +   +   +   +   +   +---+   +   +   +
|   |   |   |   |   |   |   |   |       |   |   |
+   +   +   +   +---+   +   +---+   +   +   +---+
|   |   |   |   |       |   |       |   |   |   |
+   +   +   +   +   +---+---+   +   +   +---+   +
|   |   |   |   |   |           |   |   |       |
+---+   +   +   +---+   +   +---+   +   +   +   +
|       |   |   |       |   |       |   |   |   |
+   +---+   +   +   +---+   +   +   +---+   +   +
|   |       |   |   |       |   |   |       |   |
+   +   +   +---+---+   +   +---+---+   +   +   +
|   |   |   |           |   |           |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+

Fancy!