Submitted by voxpoplar in just_post

This is a rechost of a chost that you can view here.


Something that I made a few years ago that I’m still quite proud of is an implementation of Conway’s Game of Life in 138 characters in Pico-8. You can run it here. Here’s the whole source code:

k=2^13::s::for a=0,k do
n=0 for x=0,8 do
n+=peek(k*3+a+x/3+x%3*64-65)end
poke(a,n==12 and 4 or n==16 and peek(a))end
memcpy(k*3,0,k)goto s

So let’s run through how this works!


The Game of Life is a type of cellular automation, a simulation consisting of a grid of cells. Each cell is either alive or dead and updates constantly with the following rules, as copied from Wikipedia:

  • Any live cell with fewer than two live neighbours dies, as if by underpopulation.
  • Any live cell with two or three live neighbours lives on to the next generation.
  • Any live cell with more than three live neighbours dies, as if by overpopulation.
  • Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

It’s pretty hard to see how those rules translate to the above code, so I’ll try to explain it as best I can. It relies on some tricks specific to Pico-8.

The first thing in the code is is setting k=2^13, that is 8,192. This is a magic number that is going to have a few uses.

Then we set a label ::s::. This is a point we can use goto later on in the code to return to.

Then we start a for loop, for a=0,k do, counting from 0 to 8,192. This is the length, in bytes, of the part of the the Pico-8 virtual machine’s memory that holds the current screen state. Pico-8 has a resolution of 128×128 pixels, for 16,384 pixels total, and each pixel can have one of 16 colours. That means that the colour of each pixel can be stored in 4 bits - half a byte - and therefore the full screen information can be stored in 8,192 bytes. We are going to treat every byte as a single cell, which means every cell is actually made of two pixels. You can see how every cell in the simulation is one brown and one black pixel side-by-side.

The reason we’re doing this is so that we can iterate over the current screen state in order to determine the next iteration and which cells survive or die. By examining the screen memory directly we don’t have to create a different data structure for storing the cell information; it’s just whatever’s currently on screen. This saves an awful lot of characters.

Then, inside the loop, we start by setting n=0, this is going to be used to track the number of neighbours that every cell has.

Then we start up a new loop, for x=0,8 do, to iterate over all the neighbouring cells.

Which brings us to the first complicated expression, n+=peek(k*3+a+x/3+x%3*64-65). This is adding up the values of all the neighbours (for the purposes of this implementation, each cell is considered to be be one of its own neighbours). It peeks at the memory addresses of each of the neighbours, then adds it to the running total, stored in n.

k*3 (24,576 or 0x6000) is the start of the screen memory, the starting point for iterating over the screen data. Adding a to it is iterating over each cell in sequence in the memory.

Every byte (cell) is going to have a value of 0, for dead, or 4, for alive. I’ll explain why I used the value of 4 rather than the more obvious value of 1 later.

The screen memory is arranged in the order you would probably expect, it starts in the top left corner and scans left to right, top to bottom. The first 64 bytes are the first line of the screen, the next 64 bytes are the second line, etc. As such getting the cells to the left and right of the left and right of the current one is just a matter of taking away or adding one to the address we're querying. Getting the cells above and below means adding subtracting or adding 64, respectively.

To get all nine neighbours (including the current cell itself) we need to check nine memory addresses: The current address, k*3+a, and offsets of -1, +1, -64, +64, -65, -63, +63, +65. This is accomplished with the +x/3+x%3*64-65 part of the expression as it iterates from 0 to 8. +x/3 will go from +0, +1, +2 over the course of the loop (peek thankfully ignores and fractional values, so we can act as if these are being rounded). +x%3*64 cycles through +0, +64 and +128. Then the -65 corrects these to be centred around 0 (-1 for the horizontal and -64 for the vertical).

You may notice that this is going to behave weirdly at screen edges: For the first and last row it will be checking for “neighbours” in memory before and after the screen data. These are simply going to be blank as they aren’t otherwise being used for this programme and due to the layout of the memory the left and right edges will wrap around and be treated as neighbours of each other, with a one pixel vertical offset. This weird behaviour is going to be the price we have to pay for trying to fit a mathematical simulation into a Twitter post (or at least, what a Twitter post used to be before they doubled the character limit).

Once we have the total value of n totted up it’s time to write the next iteration of the simulation: poke(a,n==12 and 4 or n==16 and peek(a)).

Poke is the opposite of peak, it lets us write to a value in memory, and we’re going to just starting writing at address 0x0, which in Pico-8 is normally spritesheet data, but we’re not using sprites in this programme so we can treat it as effectively free memory.

The poke expression is a bit weird but effectively we're either going to poke a value of 4, 0 or the current value of the cell (peek(a)).

Let’s go back to our bullet points from Wikipedia for a second. We need to rewrite them slightly because we've changed the way we counted living neighbours to include the cell itself as its own neighbour. So we need to rephrase our rules as something like:

  • A live cell with fewer than three live neighbours dies.
  • A live cell with three or four neighbours lives.
  • A live cell with more than four neighbours dies.
  • A dead cell with exactly three live neighbours lives.

Or, simplifying it:

  • Any cell with three live neighbours is alive in the next iteration.
  • Any cell with four live neighbours keeps its current value in the next iteration.
  • Any other cell is dead in the next iteration.

Or, n==12 and 4 or n==16 and peek(a). If n==12 this evaluates as 4, the value we're using for a living cell. If n==16 this evaluates as peek(a), write whatever the value for the cell is currently. Otherwise this evaluates as nil, and fortunately for us Pico-8 treats poke(a,nil) as being equivalent to poke(a,0), meaning every other case produces a dead cell.

Now we’ve iterated across the entire screen and made the next iteration of our simulation, the only thing left to do is copy the new iteration into the screen memory (memcpy(k*3,0,k)) and then start our loop again (goto s).

That’s it! Except, you might wonder, what about our starting state? We didn’t set any initial data, so why is there anything here in the first place when you run it? Well, our initial data is whatever is on screen when we run the code. You can have any starting state you want simply by having something different drawn to the screen when you hit run. And that’s also why I used 4 for the value of a living cell: it produced interesting results when running directly after Pico-8’s boot screen rather than dying instantly, which happens if you used 1 (which would have shaved off two two more characters). 4 was chosen by trial and error. It’s also a bit easier to look at than using 1, which uses a dark blue colour rather than brown that’s harder to see against the black.

And that’s (actually) it! I hope you found this interesting.

6

Comments

You must log in or register to comment.

twovests wrote

i love this so much and im so happy you shared this

2