Animate a QR code using Conway’s game of Life:
Conway’s game of Life
John Conway, a British mathematician, discovered a beautifully simple phenomenon he dubbed the game of life. Long story short, given a grid of live or dead cells, and with a sprinkle of simple rules, “life-like” kind of structures emerge over time. It’s one example of something called cellular automatons, which themselves might warrant their own blog post (hint to future me…).
Implementing the game of Life isn’t difficult, it’s just a few rules that you have to respect, namely:
- Any live cell with two or three live neighbours survives.
- Any dead cell with three live neighbours becomes a live cell.
- All other live cells die in the next generation. Similarly, all other dead cells stay dead. 1
The only thing left is to find the right starting point. I guess you see where this is going…
QR codes are everywhere these days. At restaurants, on boarding passes, on billboards, even on vaccine passports. These are all binary maps full of entropy gifted to us by the universe, so let’s put them to good use and use them in our game of life.
To fetch our QR code, we use
PIL to load the image. We then binarize it by thresholding using the mean grayscale value.
This is a gross approximation - we are not replicating 1:1 the binary map, we’re just using an approximation that’s good enough to play the game.
def URL_to_pil_img(URL): """Fetch an image from a URL and load it as a PIL Image.""" urllib.request.urlretrieve(URL, "qrcode.png") pil_img = Image.open("qrcode.png") # .resize((new_w, new_h), Image.ANTIALIAS) return pil_img def binarize_qr_code(pil_img): """Convert a qr code to a binary map + resize it.""" # resize old_w, old_h = pil_img.size new_w = 400 new_h = int(new_w / old_w * old_h) pil_img = pil_img.resize((new_w, new_h), Image.ANTIALIAS) # convert to grayscale gray_image = np.array(ImageOps.grayscale(pil_img)) # convert to binary map game_array = (gray_image > np.mean(gray_image)).astype(int) return game_array
Implementing the game of Life
We need to count the number of live and dead neighbours at each generation and then implement our rules.
Instead of doing nested
for loops and dealing with edge cases,
we’ll simply using a convolution between the current game state and this kernel:
kernel = [ [1, 1, 1], [1, 0, 1], [1, 1, 1] ]
This is done in the
count_neighbors method of the game:
def count_neighbors(self): ''' Count the number of live neighbors each cell in self.state has with convolutions. ''' self.neighbors = ( signal.convolve2d(self.state, self.kernel, boundary='fill', fillvalue=0, mode='same').astype('int') )
We are setting a zero padding boundary with the
fillvalue parameters, and the
same means our output is the same dimension as our input.
Pretty neat trick to count neighbours, right?
Next, to change values to dead or alive, we apply our rules and update our grid:
def step(self): '''Update the game based on conway game of life rules''' # Count the number of neighbors each cell has via convolution self.count_neighbors() # Copy of initial state self.new_state = self.state # Rebirth if cell is dead and has three live neighbors self.new_state += np.logical_and(self.neighbors == 3, self.state == 0) # Death if cell has less than 2 neighbors self.new_state -= np.logical_and(self.neighbors < 2, self.state == 1) # Death if cell has more than 3 neighbors self.new_state -= np.logical_and(self.neighbors > 3, self.state == 1) # Update game state self.state = self.new_state
All of the methods are wrapped in a class for convenience.
Putting it all together
In the colab, we can set the length of the game to be as long as we want using the
n_steps parameter. Let’s see the evolution of our QR code over a longer period of time:
Ah, so satisfying!
All the code to reproduce this is on Colab: