Klover

• 1. Overview
• 2. Tangled File (klover.lua)
• 3. Generate Finite State machine for 2-bit rows
• 4. Operations
• 4.1. split4
• 4.2. xy2row
• 4.3. inner2
• 4.4. belongs
• 4.5. pstates
• 4.6. row2str
• 5. Generate Finite State Machine for 4-bit rows
• 6. Generate a Symbol
• 7. Demo: Proofsheet

1. Overview

(Pronounced like "clover", but with a K)

A procedurally generated system of 1-bit symbols. Suitable for large grid layouts. The hope is to make it simpler to auto-name things in this constrained interface with limited information density (letters take up too much screen space).

Klover symbols have a height of 4 bits, and variable width. Klovers, like lucky 4-leaf clovers, celebrate groups of 4. This is where the core of the name comes from.

Klover symbols use heuristics inspired by Square Kufic calligraphy to generate aesthetically pleasing symbols that are well balanced between black and white tiles. This is where Klover gets the "K".

There are many ways to generate 1-bit tilemaps that are "technically correct" Kufic. The heart of this algorithm is a finite state machine. A Klover symbol is produced one column at a time (called rows in the code sorry for the confusion). An initial column is chosen, and then the FSM is used to randomly choose which state to go to from a set of valid states. Since Klovers are 4 tiles high, they can be represented as a 4-bit number. The 4-bit FSM lookup table is dynamically generated from a 2-bit FSM.

Precursor found in the file scratch/kufbit4fsm.lua.

2. Tangled File (klover.lua)

Klover = {}

<<fsm_2bit_kufic>>
<<operations>>
<<fsm_4bit_kufic>>
<<generate_symbol>>
<<proofsheet>>

return Klover

3. Generate Finite State machine for 2-bit rows

-- 2 bit kufic fsm
-- 00 -> 01, 10, 11
-- 01 -> 00, 01, 11
-- 10 -> 00, 10, 11
-- 11 -> 00, 01, 10

kuf2 = {}
kuf2[0] = {1, 2, 3}
kuf2[1] = {0, 1, 3}
kuf2[2] = {0, 2, 3}
kuf2[3] = {0, 1, 2}

4. Operations

Low level operations used to manipulate rows.

4.1. split4

Splits a 4-bit row into 2 2-bit components x,y

function split4(row)
    local x = (row >> 2) & 3
    local y = row & 3
    return x, y
end

4.2. xy2row

base 4 xy pair to row

function xy2row(x, y)
    x = x & 3;
    y = y & 3;
    return x << 2 | y
end

4.3. inner2

get inner 2-bit shape in a 4-bit row.

AKA bits 'bc' in row 'abcb'

function inner2(row)
    return (row >> 1) & 3
end

4.4. belongs

check: does a value x belong to set 's'?

function belongs(x, s)
    for _, v in pairs(s) do
        if x == v then return true end
    end
    return false
end

4.5. pstates

Calculate possible states for a given 4-bit row.

function pstates(row)
    local ir = inner2(row)
    local x, y = split4(row)
    -- local m = kuf2[x]
    -- local n = kuf2[y]
    local s = {}
    for _,m in pairs(kuf2[x]) do
        for _, n in pairs(kuf2[y]) do
            local mn = xy2row(m, n)
            if belongs(inner2(mn), kuf2[ir]) then
                table.insert(s, mn)
            end
        end
    end

    return s
end

4.6. row2str

stringify a row, for (terminal) printing purposes

function row2str(row)
    local str = ""
    for i=1,4 do
        local x = "-"
        if (row & (1 << (4 - i))) > 0 then x = "#" end
        str = str .. x
    end

    return str
end

5. Generate Finite State Machine for 4-bit rows

The FSM structure for 4-bit columns are dynamically generated by breaking each column into 2 2-bit columns, and using the hard-coded 2-bit FSM lookup table to calculate the possible states.

-- create a 4-bit FSM that complies with kufic rules
-- use it to procedurally generate small bit patterns that
-- can be used as identifiers for tract shapes

function generate_kuf4()
    local kuf4 = {}
    for i=0,15 do
        kuf4[i] = pstates(i)
    end
    return kuf4
end

function Klover.generate_fsm()
    return generate_kuf4()
end

6. Generate a Symbol

Function used to generate a symbol.

function generate_symbol(kuf4, len)
    -- 1 thru 15 avoids 0
    local symbol = {}
    len = len or 6
    table.insert(symbol, math.random(15))
    for i=1,(len-1) do
        local possible = kuf4[symbol[i]]
        local next = 0
        while next == 0 do
            next = possible[math.random(#possible)]
        end
        table.insert(symbol, next)
    end
    return symbol
end

function Klover.generate_symbol(kuf4, len)
    return generate_symbol(kuf4, len)
end

7. Demo: Proofsheet

Generates the proofsheet seen at the top of this page.

function Klover.proofsheet(params)
    params = params or {}
    local nrows = 6
    local ncols = 5
    local border = 4
    local width = (ncols * (48 + border*2)) + (ncols - 1) * 8  + 2*8
    local height = (nrows * (32 + border*2)) + (nrows - 1) * 8  + 2*8
    lil ("bpnew bp " ..  width ..  " " .. height)

    function draw_symbol(symbol, xoff, yoff)
        lil("bpset [grab bp] 0 " ..
            8 + xoff * (48 + 8 + 2*border) .. " " ..
            8 + yoff * (32 + 8 + 2*border) .. " " ..
            48 + border*2 ..
            " " ..
            32+border*2)
        lil("bpoutline [bpget [grab bp] 0] 1")

        for y=1,4 do
            local rowstr = ""
            for x, row in pairs(symbol) do
                local bit = row & (1 << (y - 1))

                if bit > 0 then
                    lil(string.format("bprectf [bpget [grab bp] 0] %d %d 8 8 1",
                    (x - 1)*8 + border, (y - 1)*8 + border))
                end
            end
        end
    end

    local kuf4 = generate_kuf4()
    for row=1,nrows do
        for col=1,ncols do
            draw_symbol(generate_symbol(kuf4), col - 1, row - 1)
        end
    end

    local filename = params.filename or "klover_proofsheet.pbm"
    lil("bppng [grab bp] " .. filename)
end