Conway’s QR Codes of Life
TL;DR
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
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 requests
and 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 fill
and 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:
Comments