How I built Conway's Game of Life

A small code walk-through of a small game
By Apan Trikha at Tue Sep 28 2021


This was originally made in 2018 on my WordPress site which I've switched from in favour of a static site generator, which turns out to be a much better decision by having full control over the presentation and the content without trackers, advertisements and other non-sense. I think it'll be better if I rework on it and present it in a better way. Nearly 3 years ago, I was fascinated by this fantasy computer called TIC-80 and saw some really good potential in it. I still see it today as a worthy rival to its proprietary and more popular counter-part, PICO-8. I made this tutorial back then as a way to challenge myself to create something simple but complex and visually appealing but that too under 80kB memory constraint. Turns out, I was able to do it under 5kB with under 2kB of Lua code.

In this blog, I'll walk you through the process of engineering one and how I built it with better visuals and making it concise without wasting further time. If you want to see the result in action, you can play it online over here.

Brief Intro to Game of Life and Cellular Automata

Cellular Automata are discrete computational models that are depicted on a grid with each unit (called a cell) having a state that changes according to the prescribed set of rules. That's a one liner definition of it and it's a rabbit hole by itself. If you think this is new, you would be wrong as the inception goes as far back as in 1940s with John von Neumann and Stainslaw Ulam, who where inspired by the idea of self replicating machines.

I started learning about Cellular Automata during my machine learning classes in 2018 (5th semester) when I was finding a practical implementation for predictive analysis. I was not alone as cellular automata has been used in wide variety of machine learning models including image recognition and other areas of deep learning. I would recommend you to read this article from Stanford University for further information as it's really easy to drift from the matter at hand.

Game of Life came way later in the 1970s by John Horton Conway (Rest In Peace, Sir) as a simpler implementation of cellular automata that can be easy to implement with 2 states (unlike von Neumann's implementation that had 29 states) but can do any form of computation. Now, we'll look at how I built it.

Making the Game of Life

If you follow and download the cart from here, you probably don't even need TIC-80 to study the code. You can read the code by opening the cartridge with any text editor. However, to see all of this in action, you must need TIC-80 to run this.

Setting up grids

The grid is where the cells will be represented. It is a 2D matrix that covers the screen of TIC-80, this will be 240x127. This resolution was chosen to accommodate text in the bottom which is 9 pixels high. The game of life is infamous for structures that can survive millions of generations. Considering we have only 80kB of addressable memory, storing all states will not be possible. However, we need to consider consider 2 states, the present and the next state. We can have 2 matrices that can alternate with each iteration in this way, we can represent millions of generations without compromising on the memory limit. This made the whole game function within 5kB of memory.

Imposing the rules

The rules of game of life are very simple, in fact there are 3 which are

The best example I can provide is the blinker structure, it never dies while abiding by the rules of life, once you'll look into the animation a little closer. You'll find:

Implementing this is simple. In the next matrix, the cells will be re-populated as follows.

If you want to follow, the core logic in Lua will be

-- ...
W = 240
H = 127
-- ...

function getNeighbours(xCo, yCo)
  local res = 0
  for dx = -1, 1 do
    for dy = -1, 1 do
      if (xCo + dx > 0 and xCo + dx < W and yCo + dy > 0 and yCo + dy < H) then
        res = res + board[currGrid][x + xCo][y + yCo]
      end
    end
  end
  return res
end

function update()
  local newGrid = (currGrid % 2) + 1
  for y = 1, H do
    for x = 1, W do
      local aliveNbh = getNeighbours(x, y)
      board[newGrid][x][y] = 0

      if aliveNbh == 3 or (aliveNbh == 2 and board[currGrid][x][y] == 1) then
        board[newGrid][x][y] = 1
      end
    end
  end

  currGrid = newGrid
end

Showing the cells

This one is straight forward, in the main TIC() function, we need to

And drawing screen is also easy using pix() function in TIC-80 which colors one pixel at a time. Since TIC-80 has no processing speed limit, this method will be acceptable. This will lead to following code snippet.

function draw()
  for y = 1, H do
    for x = 1, W do
      pix(x-1, y-1, board[currGrid][x][y] * aliveColor)
    end
  end
end

function TIC()
  cls(0)
  update()
  draw()
end

Keep in mind, that update() function has been defined above.

Following as a tutorial

To follow this as a tutorial, re-write these above code snippets as that's the core logic. However, for this please do the following preparations.

-- Initializing the grid and the values

aliveColor = 15
W = 240
H = 127

board = {{}, {}}

currGrid = 0

-- Re-write the snippets as is.

And you're ready to go.

Shaving memory from the cart

If you followed so far, you'll be curious as to how I was able to make it under 2kB? The answer lies in the peculiarity of the language, Lua is an interpreted language. The upside is that we can run the program as it is and the downside is that it can't be optimized.

For the "optimization", I have to do two things:

Conclusion

In conclusion, this is a shorter post than my regular articles on this website (all thanks to Vim and my mechanical keyboard) but had to keep it concise since there is not much to it. I'll end up with a lot of fluff that will make no sense and will distract new-comers of TIC-80. Okay that's about it and happy hacking!