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.

A bit-field grid

As it stands, the current implementation of Grid is a 2-dimentional array of cells - where each cell maintains a list of its neighbours and which ones it links to. This is very flexible and can support one-way passages, but much more than what we require for implementing BinaryTree.

BinaryTree

Quick recap on the BinaryTree algorithm:

  1. pick a cell
  2. create a passage between one of north, east (whichever ones are valid)
  3. repeat for each unvisited cell

Two things to note:

  • we can iterate over each cell one-by-bone
  • we keep track of whether a cell is linked either of 2 directions (:north, :east)

BitfieldGrid

Note: instead of :north, I find using :south easier to follow given we’ll start iterating from the top-left corner.

If you read this a little too quick, you might have read this as a “bit” grid - but we need at least 3 values to figure out which neighbours a cell is connected to. We can do this with 2 bits!

  • 0x00: no passageways to :south,:east
  • 0x01: passageway to the :east
  • 0x10: passageway to the :south

Let’s start by inheriting from Grid and storing integers (not Cells) in our 2D Arrays.

class BitfieldGrid < Grid
    attr_reader :rows, :columns

    def initialize(rows, columns)
        @rows = rows
        @columns = columns
        @grid = prepare_grid
    end

    def prepare_grid
        Array.new(@rows) do |row|
            Array.new(@columns) do |column|
                0
            end
        end
    end
end

We already inherit the [](row, col) getter from Grid, but we need a setter:

    def []=(row, column, val)
        @grid[row][column] = val
    end

When displaying the grid, just like the original implementation, we only need to know if it has a :south passageway or an :east one.

Note: not being familiar with trusty/falsy values in Ruby was a bit of a gotcha here - hence the explicit == in the code:

irb(main):034:0> 0 ? "0 is true" : "0 is false"
=> "0 is true"

We can just cycle through each cell, left to right, top-down:

    def to_s
        output = "+" + "---+" * columns + "\n"

        (0..@rows-1).each do |row_idx|
            top = "|"
            bottom = "+"

            @grid[row_idx].each_index do |col_idx|
                body = "   "
                cell = self[row_idx,col_idx]
                east_boundary = (cell & 0x1 == 0x1) ? " " : "|"
                top << body << east_boundary
                
                south_bounary = (cell & 0x10 == 0x10) ? "   " : "---"
                corner = "+"
                bottom << south_bounary << corner
            end

            output << top << "\n"
            output << bottom << "\n"
        end

        output
    end

BinaryTree.onBitfieldGrid

For this we’ll mirror the current implementation:

    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

Our new onBitGrid method looks like this:

    def self.onBitGrid(grid)
        grid.each_cell do |row_idx, col_idx|
            neighbors = []
            neighbors << :south if grid[row_idx+1,col_idx]
            neighbors << :east if grid[row_idx,col_idx+1]

            neighbor = neighbors.sample
            if neighbor == :south
                grid[row_idx,col_idx] = 0x10
            elsif neighbor == :east
                grid[row_idx,col_idx] = 0x1
            end
        end
    end

The only real difference is that instead of linking cells, we store the “link” value described above.

Validation

Let’s apply BinaryTree first to a normal grid, and then a bit-field one:

grid = BitfieldGrid.new(10,10)
BinaryTree.onBitGrid(grid)
puts grid
grid2 = Grid.new(10,10)
BinaryTree.on(grid2)
puts grid2
❯ ruby -I. binary_tree_bitfield_gird_demo.rb
+---+---+---+---+---+---+---+---+---+---+
|       |   |           |   |       |   |
+---+   +   +---+---+   +   +---+   +   +
|           |   |   |   |       |       |
+---+---+   +   +   +   +---+   +---+   +
|   |       |   |               |   |   |
+   +---+   +   +---+---+---+   +   +   +
|   |       |   |   |   |   |       |   |
+   +---+   +   +   +   +   +---+   +   +
|       |       |   |       |   |       |
+---+   +---+   +   +---+   +   +---+   +
|   |           |   |   |   |       |   |
+   +---+---+   +   +   +   +---+   +   +
|       |   |   |       |       |   |   |
+---+   +   +   +---+   +---+   +   +   +
|   |   |                           |   |
+   +   +---+---+---+---+---+---+   +   +
|       |   |   |   |                   |
+---+   +   +   +   +---+---+---+---+   +
|                                       |
+---+---+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+---+---+
|                                       |
+   +   +---+---+   +   +---+   +---+   +
|   |   |           |   |       |       |
+---+---+   +   +---+---+---+---+---+   +
|           |   |                       |
+---+---+   +---+---+---+   +   +---+   +
|           |               |   |       |
+   +---+   +   +   +---+   +   +   +   +
|   |       |   |   |       |   |   |   |
+   +---+---+---+   +   +---+   +---+   +
|   |               |   |       |       |
+   +---+   +   +---+---+---+---+---+   +
|   |       |   |                       |
+---+   +   +---+---+---+   +---+---+   +
|       |   |               |           |
+   +   +---+   +---+   +---+   +   +   +
|   |   |       |       |       |   |   |
+---+---+---+   +   +---+   +   +---+   +
|               |   |       |   |       |
+---+---+---+---+---+---+---+---+---+---+

Yay! They look pretty much identical in structure and we’re done. Almost.

Metrics

After all this (hard?) work, let’s try to understand how much we saved in terms of (1) memory and (2) CPU. For simplicity we won’t bother displaying the grid, we’ll just call on and onBitGird respectively.

Now we could look at profilers like memory_profiler for memory or rbspy for CPU but we can get a pretty good idea just using /usr/bin/time:

# using `BinaryTree` with a `1000x1000 Grid`
3.79s
439MB

# using `BinaryTree` with a `1000x1000 BitfieldGrid`
0.94s
21MB

That’s a massive difference! One thing to note though is that this is the total process size - it’s not necessarily what was actually used (because for arrays we may overallocate for instance), but it’s a pretty good indicator.