Home / Python On Github

Conway's Game of Life in Python

Conway's Game of Life is a well-known cellular automaton in which you have a grid of cells that are all either "dead" or "alive". Each step of the simulation, we update each cell's state based on its neighbors in the previous state. TThe rules are typically given as follows:

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

Although, for programming purposes, I find that it's best to represent the rules like this:

  1. Any cell with fewer than two neighbors or more than three neighbors dies or remain dead.
  2. Any cell with three neighbors will become alive or stay alive.
  3. Any cell with two neighbors will stay the same.

This ruleset gives rise to large numbers of complex and interesting patterns, which in turn gives rise to lots of Conway's Game of Life simulators. This is an excellent ring to throw my hat into.

The Goals

I'd like to build a relatively feature-full simulator, with at least the following features:

Drawing

I threw together a quick test GUI in PyQt5 with a save/load dialogue and a single option along with a play/pause button.

What's not so easy is actually drawing tiles to that empty space. Clearly, I'll be using a widget with a custom QPixmap that I can draw to. The problem is that QPixmaps can't be resized. They can be scaled, but this operation is not done in-place and if the window is resized smoothly, this operation will have to be performed perhaps a couple dozen times, which will be slow and will also generate a huge pile of garbage for the GC to collect. Instead, the resize event will record the current time in a timer. After about 50 milliseconds pass without the timer getting reset, we'll resize the pixmap and set the timer to None. This should stop the pixmap from being resized too frequently.

Great! Now we just need a function to draw the Game of Life board. I'll start by implementing a camera class that we can manipulate in order to pan and zoom. This will be a simple class that stores the position, in grid space, of the center of the camera's view alongside a scale factor. A scale factor of 1 indicates that one tile in the Game of Life grid corresponds to one pixel on the display. These parameters should make it easy to ensure that our camera doesn't jump around when we resize the grid.

Implementing the Grid

This, I will say, took a lot more thought than I anticipated. You might assume that I'd use bools to represent cells, given that each one can either be alive or dead. However, bools in Python 3 are truly massive at 28 bytes. Integers are the same, but an integer can also store multiple bools in each of its bits, which is a trick I'll use for storing the grid's history more efficiently later. Needless to say, indexing the grids is a bit more complicated than usual.

That isn't the problem that this section will cover, however. In this section, I want to talk about how this program efficiently calculates and displays new frames. In order to do that, I'll want the function that actually calculates frames to run asynchronously. It needs to be able to notify the mainloop function whenever it finishes so that the mainloop can display the next frame - however, I don't want the frames to always advance whenever new frames are available because they will be available whenever you go back through the history.

The solution I came upon was this: Whenever it finishes a frame, it'll write that frame to the next grid after the one currently being viewed. Like in most applications, this will make redo'ing impossible. It'll then set the pointer to the last frame rendered to the one it just created, and set a variable to indicate that a new frame should be rendered. This variable will also be set whenever the user uses the redo command - it's just the variable that tells the mainloop to start showing the next frame at its earliest opportunity.

Below, I've included a screenshot of the application rendering a 40x30 grid, although it works just as well with grids of any size, only rendering the tiles that appear onscreen. It does start to lag a little bit if I halve the size of the tiles and fullscreen the application, and increase the grid size to fill the screen. Perhaps I'll try and find room for improvement in the future, but for now that's perfectly acceptable, especially considering that it only renders the live tiles and these renders include way, way more of them than would actually appear in a Game of Life simulation.

Simulating Frames & History

Game of Life's rules are fairly simple to implement, but it should be noted that they can't be implemented in-place, you must have two grids. Well, you can do it in-place. but there's not much of a point considering we'll need multiple grids to store the grid history anyways. The way we'll go about doing this is by storing an array of grid filled with integers that represent cells. Each int can effectively hold multiple booleans in each of its bits, so we could shrink the grid size drastically by packing the cells tightly in the bytes, so that each int stores multiple cells from the same grid. This, however, will make reading and writing a fairly slow process. Instead, one int will store a single cell and some of its previous values.

This way, we can take all of the numbers in a grid and rshift them once to get the previous grid, and again to get the grid before that. Python3 ints have no theoretical limit to their size, and their storage efficiency gets a bit better as they get larger, so in theory we could store arbitrary-length histories in a single grid, although i want my code to be flexible enough to use multiple grids. the grid bit_width should also be set to a multiple of 30, because python ints grow in storage space about every 30 increases in bit_width.

Now that we have the ability to index our history, we can start simulating grids. We'll create a function that will calculate the next frame while we continue rendering the GUI and responding to requests. If the user performs any action that should stop processing, we'll simply kill the thread, it will not need to perform any cleanup. When its done, it sets a variable to indicate that the mainloop should advance to the next frame.

As you can see, the code has no trouble with some fairly large grids. In fact, this grid is 800 by 600 tiles, we can only see the middle 380 by 220 or so in this video. This is honestly more than I expected out of Python, and the UI remains responsive while the simulation occurs!

Interactivity

Now we need to be able to pan and zoom the camera, as well as flip tiles by clicking on them. We'll associate mouse events with these actions. At first, I wanted to give the application access to the camera so it could modify it directly, but if the renders are taking a while to complete then you might pan the camera and queue like 40 of them that you now have to wait for. Instead, I'll give the application access to a dummy camera and the mainloop will copy it into the real camera and call the render function - you guessed it - in a new thread, because now that I have the framework set up for threading I want to make everything its own thread. I can already tell that this a dangerous path to follow. Nonetheless, it will ensure that the GUI remains responsive regardless of whether the screen is currently being rendered. This means you can pan and zoom the camera all you want, and the program will render as many intermediary frames as it can without queuing up so many that it ends up with a backlog to work through.

I thought for a while that clicking would cause a delay between frames but I don't think that it does... Whenever I click it feels like the next frame takes longer but I pulled up a metronome and matched it to the simulation speed and it's just an illusion. Thank God I figured that out before getting deep into the debugging. It reminds me a lot of the Stopped Clock Illusion. Anyways, it isn't an issue anymore now that clicking halts the simulation.

I was going to build a system for clicking and, if you released the mouse within a brief time period after that, it would flip that pixel. Then, I realized that clicking for each individual pixel is actually awful, especially since the first thing a person naturally does when they open a CGoL simulator is doodle something and simulate it. So, I'll implement drawing by holding the mouse down, and we'll pan with the middle mouse button. This will implement a lock system that makes it so that, if the first pixel selected is off, then you will only be able to turn pixels on until the mouse is released, and it's the opposite if the first pixel clicked is on.

Now we're getting somewhere! This is really good progress, but we still have two big features left: Saving/Loading patterns, Undo/Redo, and resizeable grids. I'll start with... A bunch of QOL improvements. I'll add a button for randomizing and clearing and maybe some other stuff if I think of anything.

Final Features

Now that I've done that, i need to implement the history. Stepping backwards through the frames is actually the easy part, I've already been saving many versions of the frames as the simulation progresses and I already have a variable whose sole job is to tell the render function which of the frames we should render. The harder part is implementing the changes to the size of the grid, the edits to what pixels are set, and so on. We'll start with stepping through the frames because that's the best part. Implementing the history was a pretty big pain but I was able to get it working without too much issue.

Next up, resizeable grids. This will be implemented as a function that can insert rows or columns on any side of the grid. This step can also be undone as part of the program's history by simply removing the added rows. However, decreasing the grid size and then undoing will not bring back the removed data.

Finally, we'll implement saving and loading patterns. When saving, the pattern will be cropped to the its bounding box. When loading, the application will show a preview of what the pattern will look like while placing and place the pattern on left click, or not on right click.

Cleanup

At this point, the code is a huge mess. It's got a few cut corners and I only have this to say: I knew at the outset exactly how shoddy my could could be while still remaining workable until I achieved the goals that I had set. That said, it certainly could stand to be cleaned up a bit, and I will certainly do some basic cleanup and search for bugs a little before calling it wraps. However, I don't have many plans to continue this project in the future, so any beautification is purely for beauty's sake. If I ever decide to build an actual Conway's Game of Life simulator, with features such as copy/paste or the ability to simulate only a portion of the grid, it will be done in C++.