Conway's game of life...in pure SQL [Postgres]! 💪🏼🤯
Tags: postgres, sql, webdev, programming
Published: 2023-08-27 11:52:02

OK, for those of you who are new here, I like to do things that have never been done (and should never be done again!)!

The stupid idea I had this time? 

**What if we could run Conway's game of life...in SQL?**

Now, they do say there is a fine line between genius and insanity...I will let you decide which side of the line this idea falls on!

In this first part we focus on the hard part. Writing a game in pure SQL! (In part 2 we will put a pretty front end on it!)

## Tell me again, WHY?
Oh, this is my way of learning stuff.

I think of something that seems super difficult and very silly and then try and implement it.

It forces me to learn things that are more complex and waaaay outside of my comfort zone. I think it helps me learn faster...even if it is far more difficult lol.

And the reason for learning Postgres? 

I am currently getting familiar with @supabase_io so needed to learn some Postgres and then work out how to build an API with their product (I am on that bit now).

**So need to learn + silly idea = this article!**

Anyway...on with the show!

## Writing a program in Postgres!
I mean, what do developers need, really?

Variables, loops and if statements!

Well Postgres has them all!

So, using nothing but Postgres functions and a little bit of swearing (as I am not great with Postgres...yet!) I created a fully functioning game of life (kind of).

I am still working on the visualisation part.

Let's break it down a little.

## Conway's game of life?
If you know the game [skip this section](#creating-a-grid), but if not, here is a quick explainer.

The "game" consists of generations of squares (cells) on a grid. 

At each update, a new generation of squares / cells are born, continue to live or die.

Based solely on the following rules and the positions of your starting cells, there are some amazing simulations that can take place:
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.

Here is an amazing video of what you can achieve with these rules, when taken to the extreme!

{% youtube https://youtu.be/C2vgICfQawE?t=73 %}

We aren't going to be that ambitious today though...we just want something that functions lol. 

Let's get to it!

## Creating a "grid"
So the first thing we need is a way to create a simple grid of cells and store the state of each cell in that grid. 

Luckily we can store this grid information in a table using just 3 columns:
- the x coordinate (column) of a cell
- the y coordinate (row) of a cell
- the state of the cell (alive or dead)

So first thing we need to do is create that table:

```sql
create table grid 
  (id integer PRIMARY KEY, 
   xpos integer, 
   ypos integer, 
   val integer);
```

We added an `id` column as a primary key too.

Now the fun part, we have a way to store the grid info...but how do we create and populate that grid?

Also how do we make it so we can make a grid of any size?

### Random state
Before we build a grid, we need some initial states for our cells.

Now we could hard code some values with a load of `INSERT` statements...but that is a lot of work and pretty boring.

So we need to generate a random number, which will be either a "1" for "alive" or "0" for "dead".

So let's write a random integer generator, with a min and max, and use that to create some "booleans" by passing Min=0 and Max=1 (I say "boolean" as it isn't strictly a boolean as it isn't `true` or `false` and I am storing it as an integer).

```sql
create or replace function rand_int (min_num integer, max_num integer)
RETURNS integer 
LANGUAGE plpgsql 
as $$
BEGIN
  return (SELECT FLOOR(RANDOM()*(max_num - min_num + 1)) + min_num);
END;
$$;
```

It may take a minute to understand if you aren't familiar with Postgres (or an hour if you are like me!), but the code in the `return` statement should look familiar as well as the function declaration.

### Grid creation
Now that we have a working random **integer** generator, we need to create a grid of "X" by "Y" columns and rows.

```sql
create or replace function create_grid (col_num integer, row_num integer) 
RETURNS void 
LANGUAGE plpgsql 
as $$
BEGIN
  TRUNCATE grid RESTART IDENTITY CASCADE;
  FOR col_counter IN 1 .. col_num BY 1
  LOOP
    FOR row_counter IN 1 .. row_num BY 1
    LOOP
      INSERT INTO grid (xpos, ypos, val) values(col_counter, row_counter, rand_int(0,1));
    END LOOP;
  END LOOP;
end;   
$$;
```

There are two things to note here:
- `TRUNCATE grid RESTART IDENTITY CASCADE;` is used to clear all the data from the table `grid` we created earlier. The `RESTART IDENTITY CASCADE;` part is used to reset our auto incrementing ID column to 1 each time.
- `INSERT INTO grid (xpos, ypos, val) values(col_counter, row_counter, rand_int(0,1));` - notice we call our `rand_int` function we created earlier here.

Now we have a table that goes something like:

| ID  | xpos | ypos | val |
| --- | ---  | ---  | --- |
| 1   | 1    | 1    | 0   |
| 2   | 1    | 2    | 0   |
| 3   | 1    | 3    | 1   |
| 4   | 2    | 1    | 0   |
| 5   | 2    | 2    | 1   |
| 6   | 2    | 3    | 0   |
| 7   | 3    | 1    | 1   |
| 8   | 3    | 2    | 1   |
| 9   | 3    | 3    | 0   |

For a 3 by 3 grid.

## Counting neighbours
Earlier, when we covered the rules of the game, we found out what happens to a cell is dependant on the number of neighbouring cells that were "alive" or "dead" (plus the state of the current cell).

So we need a way of returning that.

So to get the neighbours we need:
- the 3 cells in the row above this one (one to the left, directly above and one to the right on the previous row)
- the two cells before and after this one on the same row 
- the three cells in the row below this one.

Normally there would be a huge "gotchya" here. 

For example, if we were in the first cell of an array of values when we did this check, we would have an issue with "the previous row" as it would not exist. 

So we would have to write a load of checks and conditional statements to get around this.

Luckily we are working with SQL, so we can rely on the fact that if a `WHERE` statement does not match something, it just returns no value, or an empty row.

This actually makes our "neighbours" checking function more simple.

```sql
create or replace function get_neighbours_count (row_num integer, col_num integer) 
RETURNS integer 
LANGUAGE plpgsql 
as $$
DECLARE
   neighbours_count integer;
BEGIN
  SELECT sum(val)::int
  INTO neighbours_count
  FROM temp_grid
  WHERE 
    (xpos = (row_num - 1) AND ypos = (col_num - 1)) OR
    (xpos = (row_num - 1) AND ypos = col_num) OR 
    (xpos = (row_num - 1) AND ypos = (col_num + 1)) OR
    (xpos = (row_num) AND ypos = (col_num - 1)) OR
    (xpos = (row_num) AND ypos = (col_num + 1)) OR
    (xpos = (row_num + 1) AND ypos = (col_num - 1)) OR
    (xpos = (row_num + 1) AND ypos = col_num) OR 
    (xpos = (row_num + 1) AND ypos = (col_num + 1));

  return neighbours_count;
end;   
$$;
```

This checks all the surrounding cells and returns a total count of neighbours whose value is 1 (alive).

Now onto the fun part, creating the next generation!

## Creating the next generation!
Now we have all we need to create the actual game engine.

Previously I stated there were 4 rules. However, we can actually reduce those down to 2 rules / checks, as long as we start with the assumption that a cell will die / is in 0 state (and then only update the state to alive if we pass one of the following conditions!):
- Does the cell have 2 alive neighbours? At the same time, is the current cell currently alive? If both are true, the cell is alive / in the 1 state (continues to live).
- Does the cell have exactly 3 alive neighbours? If so it is either born or continues to live, so both result in a 1 / live state.

These 2 checks actually give us the same result as the original 4 rules (albeit we are not tracking whether a cell is born or dies in any way...but yet again, even that would be straight forward if we added each generation to a "history" table).

So to complete our game engine, given the above checks, the steps we need to take are:
- Grab the current state of the game board.
- Loop through each cell:
  - set the default state to 0 / dead
  - Check the number of neighbours (using our `get_neighbours_count` function)
    - if neighbours == 2 and the cell is currently alive, set to 1
    - or if there are exactly 3 neighbours set to 1 also
    - update that row in the database.

### `next_generation` function, v1
Putting it all together the function looks like this:

```sql
create or replace function next_generation () 
RETURNS void
LANGUAGE plpgsql 
as $$
DECLARE
    grid_row RECORD;
    neighbours_count integer;
    current_state integer;
    new_state integer;
BEGIN
  FOR grid_row in SELECT * FROM grid
  LOOP
    neighbours_count := get_neighbours_count(grid_row.xpos, grid_row.ypos);
    current_state := grid_row.val;

    --assume that the cell dies
    new_state := 0;

    --if the cell is alive with 2 neighbours it lives
    IF neighbours_count = 2 THEN
      IF current_state = 1 THEN
        new_state := 1;
      END IF;
    END IF;  

    -- if the cell has exactly 3 neighbours it either lives or is born
    IF neighbours_count = 3 THEN
      new_state := 1;
    END IF;  

    UPDATE grid SET
    val = new_state
    WHERE id = grid_row.id; 


  END LOOP;
end; 
$$;

```

The logic is sound...but this will not quite work?

### A quick "gotchya"
The code logic is sound, but we are dealing with a database and live data.

So in the last step if we update the database directly then we change the state of that particular cell. Then when we check the next cell, it's neighbours count will be incorrect (as it will now count a cell that was previously "0" and is now "1" for example, as it has been updated) and we will get incorrect behaviour.

To correct for this, we just need to clone the current table into a temporary table. 

Then we run the neighbours check on our temporary table, and update the original table. 

Once we are done with our temporary table, we `DROP` it and we are done.

### `next_generation` function, v2
I have marked the two places where we changed the function with comments `--START ADDITION` and `--END ADDITION` in the below snippet.

```sql
create or replace function next_generation () 
RETURNS void
LANGUAGE plpgsql 
as $$
DECLARE
    grid_row RECORD;
    neighbours_count integer;
    current_state integer;
    new_state integer;
BEGIN
  -- START ADDITION
  -- We added this to clone the `grid` table
  CREATE TEMP TABLE temp_grid AS TABLE grid;
  -- We also updated where we select the data from
  FOR grid_row in SELECT * FROM temp_grid
  -- END ADDITION 
  LOOP
    neighbours_count := get_neighbours_count(grid_row.xpos, grid_row.ypos);
    current_state := grid_row.val;

    --assume that the cell dies
    new_state := 0;

    --if the cell is alive with 2 neighbours it lives
    IF neighbours_count = 2 THEN
      IF current_state = 1 THEN
        new_state := 1;
      END IF;
    END IF;  

    -- if the cell has exactly 3 neighbours it either lives or is born
    IF neighbours_count = 3 THEN
      new_state := 1;
    END IF;  

    UPDATE grid SET
    val = new_state
    WHERE id = grid_row.id; 


  END LOOP;
  -- START ADDITION
  -- We drop the temporary table to clean up
  DROP TABLE temp_grid;
  -- END ADDITION
end; 
$$;
```
 
## Getting the current state and running the game
So we now have nearly everything we need.

The final thing we need is a quick function we can call to get the current state of the board!

```sql
create or replace function current_generation () 
RETURNS setof grid 
LANGUAGE plpgsql 
as $$
BEGIN
  --grab current board
   RETURN QUERY SELECT * FROM grid;
end; 
$$;
```

And now we can play the game!

## Running the game!
So now we can run the game with functions really easily.

### 0. create the table
**You only need to do this once**, but you do need to create the table! 

I didn't make that into a function as it is only needed once, so here is a reminder:

```sql
create table grid 
  (id integer PRIMARY KEY, 
   xpos integer, 
   ypos integer, 
   val integer);
```

### 1. Create a new random game
We can create a grid of X by Y cols and rows with the `create_grid` function.

Let's do a 20 by 20 grid!

```sql
select create_grid(20, 20); 
```

**You can also call this function to reset the game with a new random grid!**

### 2. Get the current / initial generation
We can grab the initial generation (and display it...which we will do in part 2!)

```sql
select current_generation();
```

### 3. Generate the next generation
We call the `next_generation` function
```sql
select next_generation ();
```

### 4. Display the new generation
Once the new generation has been created, we display that instead by just selecting the `current_generation` again!
```sql
select current_generation();
``` 

### 5. Repeat steps 3 and 4 forever!
Now we can just keep calling `next_generation` and `current_generation` to display each lifecycle of the game.


---

## What is next
Next is to put a pretty interface on it!

It is very difficult to transpose X and Y coordinates in a list into a game board in your head!

However, I wanted to share the main engine with you now as I think it is a great way to learn the basics of Postgres functions!

**Important Note:** As I said, I am still new to Postgres, there may be things I am doing here that are unnecessary or even wrong. Do you own research and understand that this "tutorial" is more to showcase programming concepts and for fun, rather than a "best practices" tutorial.

## What do you think?
Let me know what you think in the comments below. 

Is it a 💗 for the silliness or a 🤮 for how horribly inefficient and what a terrible idea it is! 😂