You are given as input a greyscale image. Your task is to find a static or looping pattern in Conway's Game of Life that resembles the input image as closely as possible.

Your output can be either a still image or a looping animation in some format that can be converted to gif. The output image dimensions should be the same as the input, and it must contain only black and white pixels.

If the output is an animation, each frame must be generated from the previous one according to the Game of Life rules, with one cell per pixel. The animation must loop, with the first frame being generated from the last frame by the same rules.

If the output is a still image, applying the game-of-life rules to it must produce the same image. This means that no 'alive' cell may have more than three or less than two 'alive' neighbours, and no 'dead' cell may have exactly three 'alive' neighbours. (Note that this is basically the same as an animation as described above, but with only one frame.)

Extra rules and clarifications:

  • You (or your program) may choose whether 'alive' cells are represented as white and 'dead' as black, or vice versa. That is, you can either hard-code this or your program can choose it based on the input image. (But it must be the same for every frame of the animation.)

  • The boundary conditions should be periodic, meaning that cells on the rightmost column have neighbours on the leftmost column, etc.

  • For animations, the frame rate is up to you (or your program); I imagine fast frame rates will work well for approximating grey pixels.

  • Please post at least two results embedded in your answer. If you can post results from all of the input images below, it's preferable.

  • It is acceptable to scale down the test images if this is necessary in order to achieve gifs with small enough file sizes. If you want to link to larger files as well, that's fine. If you want to show off, feel free to find some higher-resolution source files.

  • Please try to avoid having too many controllable parameters in your code - it's best if your program's only input is the image. The exception is if you want to have a parameter for controlling the number of animation frames, since that will affect the file size.

  • You may use external programs to change the format of the input and output files, and/or compile output frames into an animation if you want. (This is not a file-format-handling challenge.)

  • This is , so the answer with the most votes wins.

Here is a selection of test images, mostly taken from other questions on this site. (It's possible that I will add additional "bonus" input images later.)

enter image description here enter image description here enter image description here enter image description here enter image description here

Just to get things started, here's a very dumb reference attempt in Python 2, which takes advantage of the fact that a block of four squares is a stable structure in the Game of Life. It just rescales the input image by a factor of 4, then draws a block if the corresponding pixel is darker than 0.5.

from skimage import io
from skimage import transform
import sys

img = io.imread(sys.argv[1],as_grey=True)

source = transform.resize(img, [i/4 for i in img.shape])

for x in xrange(source.shape[0]):
    for y in xrange(source.shape[1]):
        if source[x,y]<0.5:
            img[x*4, y*4] = 0
            img[x*4+1, y*4] = 0
            img[x*4, y*4+1] = 0
            img[x*4+1, y*4+1] = 0

io.imsave(sys.argv[2], img)

Here are some outputs from the example code. I'm sure that much better results are possible.

enter image description here enter image description here

  • 2
    \$\begingroup\$ Here's some high density still life segments: en.wikipedia.org/wiki/…. You can't get more than density 1/2 in the limit. \$\endgroup\$
    – xnor
    Commented Oct 6, 2014 at 5:09
  • \$\begingroup\$ In your example, aren't new cells born at the junction of three squares? \$\endgroup\$
    – xnor
    Commented Oct 6, 2014 at 8:42
  • \$\begingroup\$ @xnor oh yes, you're right. I'd better remove the example for now in that case. (I should also start writing some verification code!) \$\endgroup\$
    – N. Virgo
    Commented Oct 6, 2014 at 8:48
  • 3
    \$\begingroup\$ Not sure how that would help, since none of the garden of eden patterns are still lives. (which would make them their own predecessor) Similar reasoning for why they are not oscillators either. \$\endgroup\$
    – Tally
    Commented Oct 6, 2014 at 23:24
  • 1
    \$\begingroup\$ Some further inspiration for contestants: tlrobinson.net/blog/2009/02/game-of-life-generator \$\endgroup\$
    – Abulafia
    Commented Oct 8, 2014 at 10:51

3 Answers 3



import sys, random, itertools
from PIL import Image

filename, cutoff = sys.argv[1], int(sys.argv[2]) if len(sys.argv) > 2 else 128

# load command-line arg as image
src = Image.open(sys.argv[1]).convert("L") # grayscale
(w, h), src = src.size, src.load()
# flatten
src = bytearray(src[x, y] for y in range(h) for x in range(w))
size = len(src)
neighbour_offsets = (-w-1,-w,-w+1,-1,1,w-1,w,w+1)    

shapes = set()
max_shape_x, max_shape_y = 0, 0
for shape in (((1, 1), (1, 1), "b"), # block
    ((0,1,1,0),(1,0,0,1),(0,1,1,0), "h"), # hive
    ((0,0,1,0),(0,1,0,1),(1,0,0,1),(0,1,1,0), "l"), # loaf
    ((0,1,0),(1,0,1),(0,1,0), "t"), # tub
    ((1,1,0),(1,0,1),(0,1,0), "B"), # boat
    ((1,1,0),(1,0,1),(0,1,1), "s"), # ship
    ((1,1,0,1,1),(0,1,0,1,0),(0,1,0,1,0),(1,1,0,1,1), "I"), # II
    ((0,0,0,1,1),(0,0,0,0,1),(0,0,0,1,0),(1,0,1,0,0),(1,1,0,0,0), "c"), # canoe sinking
    ((1,1,0,0),(1,0,0,1),(0,0,1,1), "a"), # aircraft carrier
    ((0,1,1,0,0),(1,0,0,1,0),(0,1,0,0,1),(0,0,1,1,0), "m"), # mango
    ((0,1,1,0),(1,0,0,1),(1,0,0,1),(0,1,1,0), "p"), # pond
    ((0,0,0,1,1),(0,0,1,0,1),(0,0,1,0,0),(1,0,1,0,0),(1,1,0,0,0), "i"), # integral
    ((1,1,0,1),(1,0,1,1), "S"), # snake
    ((1,1,0,0),(1,0,1,0),(0,0,1,0),(0,0,1,1), "f"), # fish hook
    X, Y = len(shape[0]), len(shape)-1
    max_shape_x, max_shape_y = max(X, max_shape_x), max(Y, max_shape_y)
    shapes.add(((X, Y), tuple(y*w+x for y in range(Y) for x in range(X) if shape[y][x]), shape[:-1], shape[-1]))
    shapes.add(((X, Y), tuple(y*w+x for y in range(Y) for x in range(X-1,-1,-1) if shape[y][x]), shape[:-1], shape[-1]))
    shapes.add(((X, Y), tuple(y*w+x for y in range(Y-1,-1,-1) for x in range(X) if shape[y][x]), shape[:-1], shape[-1]))
    shapes.add(((X, Y), tuple(y*w+x for y in range(Y-1,-1,-1) for x in range(X-1,-1,-1) if shape[y][x]), shape[:-1], shape[-1]))

def torus(i, *indices):
    if len(indices) == 1:
        return (i + indices[0]) % size
    return [(i + n) % size for n in indices]

def iter_neighbours(i):
    return torus(i, *neighbour_offsets)

def conway(src, dest):
    for i in range(size):
        alive = count_alive(src, i)
        dest[i] = (alive == 2 or alive == 3) if src[i] else (alive == 3)

def calc_score(i, set):
    return 255-src[i] if not set else src[i]

def count_alive(board, i, *also):
    alive = 0
    for j in iter_neighbours(i):
        if board[j] or (j in also):
            alive += 1
    return alive

def count_dead(board, i, *also):
    dead = 0
    for j in iter_neighbours(i):
        if (not board[j]) and (j not in also):
            dead += 1
    return dead

def iter_alive(board, i, *also):
    for j in iter_neighbours(i):
        if board[j] or (j in also):
            yield j

def iter_dead(board, i, *also):
    for j in iter_neighbours(i):
        if (not board[j]) and (j not in also):
            yield j

def check(board):
    for i in range(size):
        alive = count_alive(board, i)
        if board[i]:
            assert alive == 2 or alive == 3, "alive %d has %d neighbours %s" % (i, alive, list(iter_alive(board, i)))
            assert alive != 3, "dead %d has 3 neighbours %s" % (i, list(iter_alive(board, i)))

dest = bytearray(size)

if False:
    # turn into contrast
    for i in range(size):
        mx = max(src[i], max(src[j] for j in iter_neighbours(i)))
        mn = min(src[i], min(src[j] for j in iter_neighbours(i)))
        dest[i] = int((0.5 * src[i]) + (128 * (1 - float(src[i] - mn) / max(1, mx - mn))))
    src, dest = dest, bytearray(size)

    checked, bad, score_cache = set(), set(), {}
    next = sorted((calc_score(i, True), i) for i in range(size))
    while next:
        best, best_score = None, sys.maxint
        current, next = next, []
        for at, (score, i) in enumerate(current):
            if score > cutoff:
            if best and best_score < score:
            if not dest[i] and not count_alive(dest, i):
                do_nothing_score = calc_score(i, False)
                clean = True
                for y in range(-max_shape_y-1, max_shape_y+2):
                    for x in range(-max_shape_x-1, max_shape_x+2):
                        if dest[torus(i, y*w+x)]:
                            clean = False
                    if not clean:
                any_ok = False
                for (X, Y), shape, mask, label in shapes:
                    for y in range(Y):
                        for x in range(X):
                            if mask[y][x]:
                                pos, ok = torus(i, -y*w-x), True
                                if (pos, label) in bad:
                                if clean and (pos, label) in score_cache:
                                    score = score_cache[pos, label]
                                    paint = torus(pos, *shape)
                                    for j in paint:
                                        for k in iter_alive(dest, j, *paint):
                                            if count_alive(dest, k, *paint) not in (2, 3):
                                                ok = False
                                        if not ok:
                                        for k in iter_dead(dest, j, *paint):
                                            if count_alive(dest, k, *paint) == 3:
                                                ok = False
                                        if not ok:
                                    if ok:
                                        score = 0
                                        any_ok = True
                                        for x in range(X):
                                            for y in range(Y):
                                                score += calc_score(torus(pos, y*w+x), mask[y][x])
                                            score /= Y*X
                                        if clean:
                                            score_cache[pos, label] = score
                                        bad.add((pos, label))
                                if ok and best_score > score and do_nothing_score > score:
                                    best, best_score = (pos, shape, label), score
                if any_ok:
                    next.append((score, i))
        if best:
            pos, shape, label = best
            shape = torus(pos, *shape)
            for j in shape:
                dest[j] = True
            next += current[at+1:]
except KeyboardInterrupt:

if True:
    anim = False
    while dest != src:
        if anim:
            raise Exception("animation!")
            anim = True
        sys.stdout.write("x"); sys.stdout.flush()
        conway(dest, src)
        dest, src = src, dest

# canvas
out = Image.new("1", (w, h))
out.putdata([not i for i in dest])

# tk UI
Tkinter = None
    import Tkinter
    from PIL import ImageTk
    root = Tkinter.Tk()
    root.bind("<Button>", lambda event: event.widget.quit())
    root.geometry("%dx%d" % (w, h))
    show = ImageTk.PhotoImage(out)
    label = Tkinter.Label(root, image=show)
except Exception as e:
    print "(no Tkinter)", e
    Tkinter = False

if len(sys.argv) > 3:

if not Tkinter:

Please squint:

enter image description here enter image description here

enter image description here enter image description here

enter image description here enter image description here

The code stamps on the whitest pixels with the best-fitting standard still life. There's a cut-off argument so you get to decide were the rounding to black-white threshold goes. I've experimented with living-is-white and the outcome is much the same.

  • 9
    \$\begingroup\$ It's best to include your code in your post, and to title your post with the language name. e.g. #Python \$\endgroup\$ Commented Oct 6, 2014 at 20:52
  • \$\begingroup\$ My validator script says you have some bad pixels at the left and right edges. It looks like when pixels wrap around from right to left, they also move one pixel downwards. \$\endgroup\$
    – N. Virgo
    Commented Oct 7, 2014 at 1:32
  • \$\begingroup\$ +1 though - thanks for the very quick answer! \$\endgroup\$
    – N. Virgo
    Commented Oct 7, 2014 at 2:40
  • \$\begingroup\$ @Nathaniel thx for introducing me to implementing GoL. A fairly straightforward misunderstanding. The output would be much the same and I have no lust to wait for them to render all over again :( This challenge has the same flaw as my own animation one - people really imagine they want to see the results, but it takes far to much investment to actually enter. The complexity space of this particular problem makes the azspcs.net contests look tame. Its a shame that GoL is monochrome and, to be honest, a poor fit for still images. SmoothLife seems fun; but not for drawing pics with. \$\endgroup\$
    – Will
    Commented Oct 7, 2014 at 5:43
  • \$\begingroup\$ @Will no need to worry about fixing the bug, I just felt compelled to mention it since I'd gone to the trouble of writing a program to check it! \$\endgroup\$
    – N. Virgo
    Commented Oct 7, 2014 at 6:10


An edge-detection-based approach. Requires this text file in the running directory.

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.*;

import javax.imageio.ImageIO;

public class StillLifer{
    private static List<boolean[][]>patterns=new ArrayList<>();
    private static boolean[][] copy(boolean[][]b,int x,int y){
        boolean[][]r=new boolean[6][6];
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
        return r;
    private static void paste(boolean[][]from,boolean[][]to,int x,int y){
        for(int i=0;i<from.length;i++)for(int j=0;j<from[0].length;j++){
    private static boolean[][]findClosest(boolean[][]b){
        int d=999999;
            int d2=editDistance(b,k);
        return c;
    private static boolean[][]decode(String s){
        boolean[][]r=new boolean[6][6];
        int k=0;
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
        return r;
    private static class EdgeDetectEntry{
        int l;
        int x;
        int y;
        public EdgeDetectEntry(int m,int x,int y){
    private static Random rand;
    private static int w,h;
    private static BufferedImage img;
    private static boolean[][]grid;
    private static File file;
    private static int editDistance(boolean[][]from,boolean[][]to){
        int w=from.length;
        int h=from[0].length;
        int k=0;
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
        return k;
    private static int colorDistance(Color from,Color to){
        return from.getRed()-to.getRed();
    private static int edgeDetectWeight(int x,int y){
        int k=0;
        Color c=new Color(img.getRGB(x, y));
        for(int x2=Math.max(0,x-1);x2<Math.min(w,x+2);x2++){
            for(int y2=Math.max(0,y-1);y2<Math.min(h,y+2);y2++){
                int l=colorDistance(c,new Color(img.getRGB(x2, y2)));
        return k;
    private static void save() throws Exception{
        int bk=Color.BLACK.getRGB();
        int wt=Color.WHITE.getRGB();
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
        String k=file.getName().split("\\.")[0];
        ImageIO.write(img,"png",new File(k="out_"+k+".png"));
    private static String rle(boolean[][]grid){
        StringBuilder st=new StringBuilder();
            for(int j=0;j<row.length;j++){
                int k=1;
        return st.toString();
    private static int getVal(boolean[][]grid,int x,int y){
        return grid[y][x]?1:0;
    private static boolean newState(boolean[][]grid,int x,int y,String rule){
        int k=0;
        for(int a=-1;a<=1;a++)for(int b=-1;a<=1;a++)k+=(a|b)==0?0:getVal(grid,x+a,y+b);
        String s=Integer.toString(k);
        return grid[y][x]?r[1].contains(s):r[0].contains(s);
    private static boolean[][] next(boolean[][]grid,String rule){
        boolean[][]r=new boolean[h][w];
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
        return r;
    private static void loadPatterns() throws Exception{
        Scanner reader=new Scanner(new File("lib.txt"));
            String line=reader.nextLine();
    public static void main(String[]a) throws Exception{
        Scanner in=new Scanner(System.in);
        img=ImageIO.read(file=new File(in.nextLine()));
        grid=new boolean[h][w];
        final int npix=w*h;
        rand=new Random(npix*(long)img.hashCode());
        List<EdgeDetectEntry> list=new ArrayList<>();
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
                list.add(new EdgeDetectEntry(edgeDetectWeight(x,y),x,y));
        list.sort((one,two)->{int k=two.l-one.l;if(k>0)return 1;if(k<0)return -1;return 0;});
        for(int i=Math.max(Math.min(3,npix),npix/5);i>0;i--){
            EdgeDetectEntry e=list.get(i);
        boolean[][]d=new boolean[h][w];
        for(int i=0;i<w/6;i++){
            for(int j=0;j<h/6;j++){

Some results:

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here



Straightforward pixelation approach using the average of each 8x8 grid to select an 8x8 output grid (a "color texture"). Each 8x8 output grid has a 2 cell separator at the top and right. Grids were designed ranging from 4 cell still lifes to 18 cell still lifes within the remaining 6x6 pixels.

The program acts as a filter from binary PGM to binary PBM. By default, images are "dark"; black is death and white is life; -i inverts this. -g [value] adds a gamma, which is used to pre-weight averages before selecting the color textures.

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>

// colors 4 through 18 have 4 through 18 live cells
// colors 1-3 are repetitions of 0 or 4 used
// as artificially weighted bins
unsigned char gol_colors[]={
      0,  0,  0,  0,  0,  0,  0,  0 // Color  0
   ,  0,  0,  0,  0,  0,  0,  0,  0 // Color  1
   ,  0,  0,  0, 16, 40, 16,  0,  0 // Color  2
   ,  0,  0,  0, 16, 40, 16,  0,  0 // Color  3
   ,  0,  0,  0, 16, 40, 16,  0,  0 // Color  4
   ,  0,  0,  0, 24, 40, 16,  0,  0 // Color  5
   ,  0,  0,  0, 16, 40, 80, 32,  0 // Color  6
   ,  0,  0,  0, 48, 72, 40, 16,  0 // Color  7
   ,  0,  0,  8, 20,  8, 64,160, 64 // Color  8
   ,  0,  0,  8, 20,  8, 64,160, 96 // Color  9
   ,  0,  0, 12, 20,  8, 64,160, 96 // Color 10
   ,  0,  0, 12, 20,  8,192,160, 96 // Color 11
   ,  0,  0,204,204,  0,  0, 48, 48 // Color 12
   ,  0,  0,204,204,  0,192,160, 64 // Color 13
   ,  0,  0,  0,108,168,168,108,  0 // Color 14
   ,  0,  0, 96,144,104, 40,172,192 // Color 15
   ,  0,  0,204,204,  0,  0,204,204 // Color 16
   ,  0,  0,216,216,  0,216,212,  8 // Color 17
   ,  0,  0,204,164, 40, 80,148,204 // Color 18

enum { gol_bins = sizeof(gol_colors)/(sizeof(*gol_colors))/8 };

bool inverted=false;

bool applygamma=false;
double gammasetting=0.0;

unsigned int corrected(unsigned int i, unsigned int r) {
   return static_cast<unsigned int>(r*std::pow(i/static_cast<double>(r), gammasetting));

int main(int argc, char** argv) {
   std::vector<unsigned short> pgm_data;
   unsigned pgm_width;
   unsigned pgm_height;
   unsigned pgm_vpp;

   std::vector<unsigned char> pbm_data;
   unsigned pbm_width;
   unsigned pbm_height;

   unsigned int doublings=0;

   std::vector<std::string> args(argv+1, argv+argc);
   for (unsigned int i=0, e=args.size(); i<e; ++i) {
      if (args[i]=="-i") { inverted=true; continue; }
      if (args[i]=="-g") {
         if (i+1==e) continue;
         std::stringstream ss;
         ss << args[++i];
         if (ss >> gammasetting) applygamma = true;

   std::string line;
   std::getline(std::cin, line);
   if (line!="P5") return 1;
   enum { nothing, have_w, have_h, have_bpp } readstate = nothing;
   while (std::cin) {
      std::getline(std::cin, line);
      if (line.empty()) continue;
      if (line[0]=='#') continue;
      std::stringstream ss; ss << line;
      for(;;) {
         switch (readstate) {
         case nothing: if (ss >> pgm_width) readstate = have_w; break;
         case have_w:  if (ss >> pgm_height) readstate = have_h; break;
         case have_h:  if (ss >> pgm_vpp) readstate = have_bpp; break;
         if (readstate==have_bpp) break;
         if (ss) continue;
      if (readstate==have_bpp) break;
   if (readstate!=have_bpp) return 1;
   // Fill pgm data
   for (unsigned i=0, e=pgm_width*pgm_height; i<e; ++i) {
      int v = std::cin.get();
      if (v==std::char_traits<char>::eof()) return 1;
      pgm_data[i] = static_cast<unsigned int>(std::char_traits<char>::to_char_type(v))&0xFFU;
   pbm_width  = pgm_width/8*8;
   pbm_height = pgm_height/8*8;
   for (unsigned x=0, xe=pbm_width/8; x<xe; ++x) {
      for (unsigned y=0, ye=pbm_height/8; y<ye; ++y) {
         // Calculate the average of this 8x8 area
         unsigned int total=0;
         for (unsigned int xd=0; xd<8; ++xd) {
            for (unsigned int yd=0; yd<8; ++yd) {
               unsigned int c = x+xd+(y+yd)*pgm_width;
               unsigned int pv = pgm_data[x*8+xd+(y*8+yd)*pgm_width];
               // Apply gamma prior to averaging
               if (applygamma) pv=corrected(pv, pgm_vpp);
               total += pv;
         total /= 64;
         // Invert average if inverting colors (white on black)
         if (inverted) total=pgm_vpp-total;
         total *= gol_bins;
         total /= (pgm_vpp+1);
         // Fill 8x8 areas with gol color texture
         for (unsigned int yd=0; yd<8; ++yd) {
            pbm_data[x+(y*8+yd)*pbm_width/8] = gol_colors[total*8+yd];
   // Now, write a pbm
      << "P4\n"
      << "# generated by pgm2gol\n"
      << pbm_width << " " << pbm_height << "\n";
   for (unsigned i=0, e=pbm_data.size(); i<e; ++i) {
      unsigned char data=pbm_data[i];
      if (!inverted) { data=pbm_data[i]^0xFF; }

Selected results (note: all pbm's were converted to png's using a third party program for upload):

Escher, gamma 2.2

Mona Lisa, gamma 2.2

Ocean, gamma 2.2 inverted

Puppy, gamma 2.2

Treachery of Images, gamma 2.2 inverted

Mona Lisa gamma 2.2, inverted, for comparison


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.