pythonopencvconways-game-of-life

Conway's GOL rules not implemented correctly


I am using OpenCV and a kernel to count neighbors of each pixel, the pixel's value then becomes the number of neighbors that it has, and then I apply Conway's rules, but the output is not as expected, everything just expands. Here is my code:

import cv2
import numpy as np

world = cv2.imread("start.png", cv2.IMREAD_GRAYSCALE)

for x in range(100):
    
    world = np.uint8(world / 255)

    kernel = np.array([
        [1, 1, 1],
        [1, 0, 1],
        [1, 1, 1]
    ])

    world = cv2.filter2D(src=world, ddepth=-1, kernel=kernel)

    world[(world < 2) | (world > 3)] = 0
    world[(world == 3) | (world == 2)] = 1

    world *= 255
    cv2.imwrite(f".\OUTPUT\stage {str(x).zfill(5)}.png", world)
    print(f"Frame {x}")

Reproducible example

To test this yourself, here is a hard-coded input with a glider, and one iteration -- no image file needed:

import cv2
import numpy as np

world = np.array([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]) * 255

for x in range(1):
    
    world = np.uint8(world / 255)

    kernel = np.array([
        [1, 1, 1],
        [1, 0, 1],
        [1, 1, 1]
    ])

    world = cv2.filter2D(src=world, ddepth=-1, kernel=kernel)

    world[(world < 2) | (world > 3)] = 0
    world[(world == 3) | (world == 2)] = 1

    print(world)
    world *= 255

This prints the following, with 16 alive cells:

[[0 1 1 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 1 0 0 0 0 0 0 0 0 0 0]
 [1 1 0 1 1 0 0 0 0 0 0 0 0 0]
 [1 0 1 1 1 0 0 0 0 0 0 0 0 0]
 [1 1 1 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

...while I expect it to print the next generation of the moving glider, with just 5 cells that are alive:

[[0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 1 0 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 1 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 1 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

Solution

  • The following statement does not correctly implement a Game of Life rule:

    world[(world == 3) | (world == 2)] = 1
    

    In case the number of live neighbors is two, you need to keep the current cell unchanged: when it was alive it should stay alive, when it was dead it should stay dead.

    As your kernel ignores the current cell's value, you will not be able to produce a correct next generation after you have applied the filter.

    In order to fix the situation, you could apply a different kernel, one that has a non-zero value at the center. As you need to specifically be able to detect the state of the center cell, you could use 2 instead of 1 for the boundary, so the neighbors always add up to an even number, and use 1 at the center. That way you know when the cell was alive or not by looking at the parity after the filter has been applied.

    Specifically, a cell should be alive when the application of the kernel results in 5, 6 or 7. In all other cases it should be dead.

    At the boundaries you probably want to count the outside pixels as zeroes (i.e. dead). This is not the default behaviour of filter2D. You can override that with the parameter borderType=cv2.BORDER_CONSTANT.

    The definition of kernel can be moved out of the loop. That leads to this code:

    import cv2
    import numpy as np
    
    kernel = np.array([
        [2, 2, 2],
        [2, 1, 2],
        [2, 2, 2]
    ])
    
    world = cv2.imread("start.png", cv2.IMREAD_GRAYSCALE)
    
    for x in range(10):
        world = np.uint8(world / 255)
        world = cv2.filter2D(src=world, ddepth=-1, kernel=kernel, borderType=cv2.BORDER_CONSTANT)
        world[(world < 5) | (world > 7)] = 0
        world[world > 0] = 255
    
        cv2.imwrite(f"stage {str(x).zfill(5)}.png", world)
        print(f"Frame {x}")
    

    I tested this with a glider like this:

    enter image description here

    ...and the images created by the program were as expected.