Cells, Queries, and Chaos: The Game of Life in SQL!

Github Repo: https://github.com/Hetarth02/game-of-life-sql

👾History

I have always been fascinated with cellular automaton, it’s so cool seeing how life can emerge from such simple rules. To give you a brief context, many people think Conway was the first person to coin this theory but it is not correct while Conway was the reason this branch got so famous but he was not the first. The idea of Cellular Automata first took birth around late 1950s inside the minds of Stanislaw Ulam and John von Neumann. While working together on a particular project both of these created the first automaton. It would be in the 1970s that mathematician John Conway would invent his now famous Game of Life.

🎮What’s the game?

Alright, now that we know a bit of history let’s talk briefly talk about the game.

It is a zero-player game meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.

Source: Game of Life WIkipedia

🗒️Rules

You start with an infinite 2D grid in which each cell will have two states either 0(dead) or 1(alive). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent.

At each update, a new generation of cells are born, continue to live or die based on the following rules:

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.

2. Any live cell with two or three live neighbours lives on to the next generation.

3. Any live cell with more than three live neighbours dies, as if by overpopulation.

4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

And that’s it, that’s the entire game. You gave it an initial configuration and it will play itself.

😃So why it’s called “Game of Life”?

Even though it is this simple, the game when played mimicks “Life” itself in a way. Cells get born, die, depend on their neighbours.Moreover, it has another fantastic property which make this game unique, which is 🤖Turing Completeness. Yup, so basically you can create computers inside game of life and people have done so and if you want to have mindf*ck moment, you can simulate “Game of Life” inside “Game of Life”.🤯

There are many more generalised forms of Game of Life which come pretty close behaving like organic life itself and have been known as digital life or artifical life or algorithmic life.

I very highly recommend you give these videos a watch!

💻Why SQL and what’s the twist?

Just for the sake of it! It’s easy to find the implementation in any other languages and I just wanted to have a fun challenge. The twist is, usually when you implement this game you have a two storages, one which stores the current generation and another which stores the next generation well; I will not only use just a single table, but only a singular column too.(I could have also gone for just using a single DB cell but DBs usually have limitations on how much you can store in a single cell.)

What followed next was late night debugging sessions, bit ops and me pulling my hair out on calculations!!!

#️Creating the Grid

Alright, let’s get into the code.

The very first step is to create the world. Ok, so usually you would create a 2D array and call it a day(or night) not me though! We already have rows inside postgres. I see you asking, “We also have columns”. I mean yeah, but I ain’t gonna store each cell in single columns…let alone you need to name those columns and have to dynamically create them everytime.

Instead what we will do is, use bitstrings. Bitstrings are basically binary sequence of 0s and 1s. Ok, so 2 columns one for current gen and another for next gen right? Nope! As said earlier, we will use only one! Here’s how we will manage the game state,

• Each game cell will be assigned 2 bits, one for next gen(left/odd) and one for current gen(right/even).

• We will calculate next gen using the right bit which is current gen.

• We will store the value of next gen in the left bit .

• Once, all calculations are done for all current gen(right/even bits) cells, we will drop their values and assign them the value of the next gen(left/odd bits)

• Reset all next gen bits.

So, for a 5 × 5 world, there will be 1 column and 5 rows each with 10 bits of data(because each cell stores 2 states so 5 cells × 2 bits = 10 bits).

We have our world ready. Next task is to generate an initial random state for the world, so we write a random number generator. I have made all the code as much read-friendly as possible.

drop function if exists generate_random_int;

create or replace function generate_random_int(min_num integer, max_num integer) returns integer
as $$
begin
    -- explanation: https://stackoverflow.com/questions/62981108/how-does-math-floormath-random-max-min-1-min-work-in-javascript
    return (select floor(random() * (max_num - min_num + 1)) + min_num);
end
$$ language plpgsql;

But we store bitstrings inside the columns, hence we gotta create a bitstring for each row with all left bits 0 because initially the next gen will not have any data.

create or replace function generate_random_bitstring(str_length integer) returns text
as $$
declare
    str text := '';
begin
    for i in 1 .. str_length loop
        -- Concate str with a '0' attached
        str := str || 0 || generate_random_int(0,1);
    end loop;
    return str;
end
$$ language plpgsql;

Alright, everything is going smooth as butter. Next up is creating the grid(table) and inserting the initial state to into it.

drop function if exists create_grid;

create or replace function create_grid(grid_rows integer, grid_cols integer) returns void
as $$
declare
    data_str text := '';
begin
    drop table if exists grid;

    execute 'create table if not exists grid (cell_values bit(' || 2 * grid_cols || '));';

    for row_counter in 1 .. grid_rows loop
        data_str := generate_random_bitstring(grid_cols);
        data_str := 'insert into grid (cell_values) values (' || E'b\'' || data_str || E'\'' || ');';
        execute data_str;
    end loop;
end
$$ language plpgsql;

You are probably wondering why do we need that weird E’b\’’ thing?🤔

So, E marks the starts of an string in which we can escape characters. The b part is us saying to postgres that this is a binary string and not just a string, otherwise postgres will store the binary value of the string and not what we supply it.

Now, we just make a small function which fetches the current table and displays all the records to use.

drop function if exists current_generation;

create or replace function current_generation() returns table (cells text)
as $$
begin
    return query (select cell_values::text from grid);
end
$$ language plpgsql;

To execute we do the the following,

do $$
begin
    -- Executes the function, discards the return value
    perform create_grid(5, 5);
end;
$$ language plpgsql;

select current_generation() as cells;

It will look something like this,

📐Debugging and Maths

All right now comes the hardest part, usually it’s not hard to calculate neighbours because you have nice grid structure in a 2D array and with arrays come certain perks like there’s not -1 index, etc. But for us, we have two bits representing single cell and it’s just a single column hence a fake(believed) 2D array.

So, at first I searched if anyone did this kind of thing within any language but couldn’t find it…forget SQL. Also, AI is not that helpful…(I personally don’t like using AI because I want to learn by myself whether its by making mistakes, print debugging or reading through reddit comments)

Ok, didn’t have much help in directly finding the answer back to board…so, I took a pen and paper and started jotting down a matrix numbered each cell and did all the maths for it. I didn’t wanted to call each row every time inside a loop so I just fetched all data at once and calculated total_rows and total_cols using it which is essentially just what dimensions our matrix(grid) was, don’t forget to divide by 2 else the maths gets crazy in iterating rows and columns.

So, at first I tried many different complex and smart approaches to calculate neighbours and especially dealing with the boundaries, edge cases and everything else…but at the end to preserve my sanity I just went the simple route.

Simplicity is the best complexity.

Ok, so my main problem was calculating boundaries of the world when iterating through the top/bottom row/column and those pesky corners.

Simply put, I started with 3 variables top_row, current_row and bottom_row. Always initialise those rows to be entirely dead(0’s) and then check if the indexes were out of bounds or not. If the indexes are out of bounds then do nothing, else we use our current row_index to find out top_row, current_row and bottom_row and put our index at the start and fetch the substring from the entire data string using total_cols.

We now have our rows, let’s move forward with columns. First, we get the current_value and then go with the same approach as we did during row, initialise all the neighbouring values as dead → check if column are within bounds → if they are fetch their values.

You need to double everything coz we have 2 bits per cell.

After having all 8 neighbours it’s just a matter of summing them up, and using the game of life rules!

We now have old and new generations in a single string new_all_data. Here comes the fun part, we now need to swap the new(left bits) and old generation(right bits) then reset the new generation(left bits) back to dead(0), so how do we do that? The answer is…

Bitmasking!!!

For those who don’t know what it is it’s super simple; bitmasking is nothing but hiding of unwanted bits using clever masks(we will see how we can create these).

Bitmasking uses AND operation to achieve masking because the logic for AND gate is if one of the inputs is 0 then the output will be 0.

In our case, we don’t care about the right(even) bits. So, we will use a mask which hides all the even bits i.e. 1010101010. We will create this mask for each row with the length of total_cols and AND it with the substrings of each row. After that we just we will have a bitstring for each row with all even bits 0 so, we will just do a bit-wise right shift by 1 to shift all odd bits to even positions and we don’t even need to reset the odd bits because it happens automatically!🎉

Now, all that’s left is to clear the current grid and insert the new rows into the table.

drop function if exists next_generation;

create or replace function next_generation() returns void
as $$
declare
    all_data text := '';
    new_all_data text := '';

    total_cols integer := 0;
    total_rows integer := 0;

    top_row text := 0;
    current_row text := 0;
    bottom_row text := 0;

    current_value integer := 0;

    top_left integer := 0;
    top_middle integer := 0;
    top_right integer := 0;

    middle_left integer := 0;
    middle_right integer := 0;

    bottom_left integer := 0;
    bottom_middle integer := 0;
    bottom_right integer := 0;

    live_neighbours integer := 0;

    bitmask text := '';
begin
    select string_agg(grid.cell_values::text, '') into all_data from grid;
    select bit_length(grid.cell_values) / 2 into total_cols from grid limit 1;
    total_rows := length(all_data)::integer / (2 * total_cols);

    for row_index in 1 .. total_rows loop
        top_row := repeat('0', total_cols * 2);
        if row_index - 1 != 0 then
            top_row := substr(all_data, ((row_index - 1) * total_cols * 2) - (total_cols * 2) + 1, total_cols * 2);
        end if;

        current_row := substr(all_data, (row_index * total_cols * 2) - (total_cols * 2) + 1, total_cols * 2);

        bottom_row := repeat('0', total_cols * 2);
        if row_index + 1 <= total_rows then
            bottom_row := substr(all_data, ((row_index + 1) * total_cols * 2) - (total_cols * 2) + 1, total_cols * 2);
        end if;

        for col_index in 1 .. total_cols loop
            -- We store the current value in right bit
            current_value := substr(current_row, (col_index * 2), 1)::integer;

            top_left := 0;
            middle_left := 0;
            bottom_left := 0;

            top_middle := 0;
            bottom_middle := 0;

            top_right := 0;
            middle_right := 0;
            bottom_right := 0;

            if col_index - 1 != 0 then
                top_left := substr(top_row, (col_index * 2) - 2, 1)::integer;
                middle_left := substr(current_row, (col_index * 2) - 2, 1)::integer;
                bottom_left := substr(bottom_row, (col_index * 2) - 2, 1)::integer;
            end if;

            top_middle := substr(top_row, (col_index * 2), 1)::integer;
            bottom_middle := substr(bottom_row, (col_index * 2), 1)::integer;

            if col_index + 1 <= total_cols then
                top_right := substr(top_row, (col_index * 2) + 2, 1)::integer;
                middle_right := substr(current_row, (col_index * 2) + 2, 1)::integer;
                bottom_right := substr(bottom_row, (col_index * 2) + 2, 1)::integer;
            end if;

            live_neighbours := 0;
            live_neighbours := top_left + top_middle + top_right + middle_left + middle_right + bottom_left + bottom_middle + bottom_right;

            -- We store the next value in left bit, hence only -1
            if current_value = 1 and (live_neighbours = 2 or live_neighbours = 3) then
                current_row := overlay(current_row placing '1' from (col_index * 2) - 1 for 1);
            elsif current_value = 0 and live_neighbours = 3 then
                current_row := overlay(current_row placing '1' from (col_index * 2) - 1 for 1);
            else
                current_row := overlay(current_row placing '0' from (col_index * 2) - 1 for 1);
            end if;
        end loop;

        new_all_data := new_all_data || current_row;
    end loop;

    execute 'truncate grid;';

    for i in 1 .. (total_cols * 2) loop
        if i % 2 = 1 then
            bitmask := bitmask || 1;
        else
            bitmask := bitmask || 0;
        end if;
    end loop;

    bitmask := E'b\'' || bitmask || E'\''; 

    for row_counter in 1 .. total_rows loop
        current_row := substr(new_all_data, (row_counter * total_cols * 2) - (total_cols * 2) + 1, total_cols * 2);
        current_row := E'b\'' || current_row || E'\'';
        current_row := '(' || current_row || ' & ' || bitmask || ') >> 1';
        current_row := 'insert into grid (cell_values) values (' || current_row || ');';
        execute current_row;
    end loop;
end
$$ language plpgsql;

You can run it using same method as before, just need to repeat these for infinity that’s all!😄

do $$
begin
    -- Executes the function, discards the return value
    perform next_generation();
end;
$$ language plpgsql;

select current_generation() as cells;

And that’s all!!!

🗒️Conclusion

Honestly, there might be more optimisations and improvements which can be done to this code but for now I am happy with what I have and I honestly had so much fun implementing this. Figuring out the mathematics, learning bitmasking everything was so fun and I hope you the reader will also try doing this or any other quirky project just for the sake of it!

Have a nice day!❤️

---

If you’d like to know more about my journey, please feel free to reach out or follow me!

Github: Hetarth02

LinkedIn: Hetarth Shah

Website: Portfolio

💖Thank you for joining me on this journey, and look forward to more interesting articles!