DEV Community

Cover image for Conway's game of life...in pure SQL [Postgres]! 💪🏼🤯
GrahamTheDev
GrahamTheDev

Posted on

Conway's game of life...in pure SQL [Postgres]! 💪🏼🤯

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, 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!

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:

create table grid 
  (id integer PRIMARY KEY, 
   xpos integer, 
   ypos integer, 
   val integer);
Enter fullscreen mode Exit fullscreen mode

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).

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;
$$;
Enter fullscreen mode Exit fullscreen mode

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.

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;   
$$;
Enter fullscreen mode Exit fullscreen mode

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.

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;   
$$;
Enter fullscreen mode Exit fullscreen mode

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:

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; 
$$;

Enter fullscreen mode Exit fullscreen mode

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.

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; 
$$;
Enter fullscreen mode Exit fullscreen mode

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!

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

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:

create table grid 
  (id integer PRIMARY KEY, 
   xpos integer, 
   ypos integer, 
   val integer);
Enter fullscreen mode Exit fullscreen mode

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!

select create_grid(20, 20); 
Enter fullscreen mode Exit fullscreen mode

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!)

select current_generation();
Enter fullscreen mode Exit fullscreen mode

3. Generate the next generation

We call the next_generation function

select next_generation ();
Enter fullscreen mode Exit fullscreen mode

4. Display the new generation

Once the new generation has been created, we display that instead by just selecting the current_generation again!

select current_generation();
Enter fullscreen mode Exit fullscreen mode

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! 😂

Top comments (20)

Collapse
 
janeori profile image
Jane Ori

Oooh! Kindred soul making GoL in unexpected languages! This was fun to read!

I did it in 100% CSS not long ago :)

100% CSS GoL Demo
codepen.io/propjockey/pen/NWEYdjY?...

Collapse
 
grahamthedev profile image
GrahamTheDev

I saw this and loved it...in fact I was originally going to do it in CSS until I saw this, and so I chose SQL instead!

Amazing work! 💪🏼💗

Collapse
 
cicirello profile image
Vincent A. Cicirello • Edited

Very cool. If you really want to drive yourself nuts with this, try doing the same without using PL/pgSQL. Using common table expressions, you can use recursion, which makes PostgresSQL a Turing Complete language without PL/pgSQL.

Example demonstrating Turing Completeness: wiki.postgresql.org/wiki/Cyclic_Ta...

Related Stackoverflow answer that happens to include a link to the Mandelbrot set in PostgresSQL: stackoverflow.com/a/7580013

Direct link to the Mandelbrot example: wiki.postgresql.org/wiki/Mandelbro...

Collapse
 
mmetc profile image
mmetc • Edited

This reminded me of something I wrote 12 years go. It should still work, no procedural code. I went and found the source:

-- schema.sql

DROP TABLE IF EXISTS cells;

CREATE TABLE cells (
    x INTEGER,
    y INTEGER,
    state BOOLEAN NOT NULL,
    PRIMARY KEY (x, y)
);

DROP AGGREGATE IF EXISTS concat (text);

CREATE AGGREGATE concat (
    BASETYPE = text,
    SFUNC = textcat,
    STYPE = text,
    INITCOND = ''
);

-- soup.sql

DELETE FROM cells;

INSERT INTO cells
     SELECT x, y, random()<.375
       FROM generate_series(0, 20) x
 CROSS JOIN generate_series(0, 20) y;

-- evolve.sql

UPDATE cells
   SET state = (
                 state,
                 (SELECT SUM(state::INT)
                    FROM cells nb
                   WHERE (ABS(nb.x-cells.x), ABS(nb.y-cells.y)) IN ((0, 1), (1, 0), (1, 1)))
               ) IN ((true, 2), (true, 3), (false, 3));

-- watch.sql

SELECT y, concat(CASE WHEN state THEN 'O' ELSE '.' END)
  FROM (SELECT * FROM cells ORDER BY x) foo
 GROUP BY y
 ORDER BY y;
Enter fullscreen mode Exit fullscreen mode

These days I don't do much SQL anymore, but I used to treat every query as a puzzle :)

Collapse
 
grahamthedev profile image
GrahamTheDev

Nice, few tricks in there for me to learn from! 💗

Collapse
 
grahamthedev profile image
GrahamTheDev

Ooohhh, perhaps not this, but I can think of some fun things to try using Recursion! Thanks! 💗

Collapse
 
cicirello profile image
Vincent A. Cicirello

You're welcome

Collapse
 
techthatconnect profile image
TechThatConnect

Its very nice to see others learning this way. I love to come up with silly ideas and then learn by implimenting them. I am currently making a turn based castle builder game that runs in a browser using pure vanilla js.

Collapse
 
grahamthedev profile image
GrahamTheDev

Nice, I hope to see you post it here when it is done! 💪🏼💗

Collapse
 
techthatconnect profile image
TechThatConnect

Thats the plan!

Collapse
 
zeal2end profile image
Vivek Kumar

It's So Cool, I have also done something similar unique I've created the Convoy's game of life in command line. Medium

Collapse
 
nicolello profile image
Nicola Migone

Just FYI, PostgreSQL supports points as datatypes, which might be more efficient for this :) Read more on their documentation at here

This aside, interesting article. Great job!

Collapse
 
grahamthedev profile image
GrahamTheDev

Do you have any examples of usage as just by definition alone I am not seeing how points vs 2 columns for x and y save any operations.

The inefficiency in my code is from loops and lots of UPDATES and my WHERE query? Is there any specific "function" that I can use (like SERIES) with these.

As I said, just learning so I am far from understanding all of the parts!

Thanks in advance! 💗💗

Collapse
 
nicolello profile image
Nicola Migone • Edited

I modified the schema a bit, assuming that all points in the table are assumed to be alive, and if a point isn't there, then it is dead.
New schema:

CREATE TABLE points (
    id SERIAL PRIMARY KEY, 
    p POINT NOT NULL
);
Enter fullscreen mode Exit fullscreen mode

and now the power of it.. To get all adjacent points that are alive, I just need to run this:

SELECT p FROM points WHERE p <-> POINT '(0, 0)' = 1
Enter fullscreen mode Exit fullscreen mode

the <-> operator returns the distance of two geometric objects, points in this case.
You can probably figure out how to go on :)

Relevant documentation: postgresql.org/docs/current/functi...

Collapse
 
karishmashukla profile image
Karishma Shukla

This is cool. I am going to try this for fun

Collapse
 
grahamthedev profile image
GrahamTheDev

Haha, let me know how you get on! 😂💗

Collapse
 
chiragagg5k profile image
Chirag Aggarwal

Using tools to make applications it was never intended for. Funny and really interesting at the same time. Amazing post ❤️

Collapse
 
joao9aulo profile image
João Paulo Martins Silva

Very cool and creative, congrats

Collapse
 
baptistsec profile image
William Baptist

Impressive article, lots of detail here for people to get their teeth into. Thanks for sharing!

Collapse
 
grahamthedev profile image
GrahamTheDev

On a scale from silly to spectacular...how do you rate this one then? 😂💗