John Conways "Game of Life" in Python

Ein sogenanntes "Raumschiffmuster" in Game of Life

Das "Spiel des Lebens"

Eine Seite Python code für die Implementierung von John H. Conways "Game of Life". (Klicken zum vergrößern)

Das vom englischen Mathematiker John Horton Conway entwickelte "Game of Life" ist ein zellularer Automat. Zellulare Automaten sind diskrete Modelle, die aus einem regelmäßigen Gitter bestehen, indem jede Zelle einen definierten Zustand hat. Die Simulation schreitet in diskreten Zeitschritten voran. Der neue Zustand einer Zelle hängt lediglich vom Zustand der Nachbarzellen im vorangegangenen Zeitschritt ab. Die Simulation kann mittels einfeacher Regeln komplexe Muster erstellen. Eine ausführliche Beschreibung des "Game of Life" befindet sich in einem eigenen Artikel auf dieser Webseite.

John Conway fand einen Satz einfacher Regeln, mit dem es möglich ist, innerhalb der Simulation Strukturen zu erzeugen, die sich selbst replizieren, fortbewegen oder miteinander interagieren können. Später wurde bewiesen, dass das Spiel des Lebens mit diesem Regelsatz "Turing-Vollständig" ist. Mit einer Turing-Vollständigen Maschine kann man theoretisch beliebige Berechnungen durchführen. Man kann also sagen, das eine Maschine oder Software, welche das "Game of Life" implementiert selbst ein Computer ist, wenn auch einer, der aussergewöhnlich kompliziert zu programmieren ist.

Regeln

Die Simulation started im ersten Zeitschritt mit einem Vorgegebenen Anfangszustand. Jede Zelle im Spiel hat einen der beiden Zustände: "Am Leben" oder "Tot". Im der Python Beispielimplementierung werden diese Zustände durch die Zahlen 0 und 1 ausgedrückt. Für den nächsten Zeitschritt werden die Zustände der Zellen nach folgenden Regeln berechnet:

Eine lebendige Zelle stirbt, wenn sie weniger als zwei lebendige Nachbarzellen hat.
Eine lebendige Zelle mit zwei oder drei lebendigen Nachbarn lebt weiter.
Eine lebendige Zelle mit mehr als drei lebenden Nachbarzellen stirbt im nächsten Zeitschritt.
Eine tote Zelle wird wiederbelebt, wenn sie genau drei lebende Nachbarzellen hat.

Python-Quellcode

Der Python Quellcode für Game of Life kann auf GitHub heruntergeladen werden. Hier ist ein Beispielbild, inklusive des Quellcodes dargestellt.

import pygame
import numpy as np

col_about_to_die = (200, 200, 225)
col_alive = (255, 255, 215)
col_background = (10, 10, 40)
col_grid = (30, 30, 60)

def update(surface, cur, sz):
    nxt = np.zeros((cur.shape[0], cur.shape[1]))

    for r, c in np.ndindex(cur.shape):
        num_alive = np.sum(cur[r-1:r+2, c-1:c+2]) - cur[r, c]

        if cur[r, c] == 1 and num_alive < 2 or num_alive > 3:
            col = col_about_to_die
        elif (cur[r, c] == 1 and 2 <= num_alive <= 3) or (cur[r, c] == 0 and num_alive == 3):
            nxt[r, c] = 1
            col = col_alive

        col = col if cur[r, c] == 1 else col_background
        pygame.draw.rect(surface, col, (c*sz, r*sz, sz-1, sz-1))

    return nxt

def init(dimx, dimy):
    cells = np.zeros((dimy, dimx))
    pattern = np.array([[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,0,0,0,0,0,0,0,0,0,0,0,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,0,0],
                        [0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,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,0,0,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
                        [1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
                        [1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,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,1,0,0,0,0,0,1,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,1,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,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]]);
    pos = (3,3)
    cells[pos[0]:pos[0]+pattern.shape[0], pos[1]:pos[1]+pattern.shape[1]] = pattern
    return cells

def main(dimx, dimy, cellsize):
    pygame.init()
    surface = pygame.display.set_mode((dimx * cellsize, dimy * cellsize))
    pygame.display.set_caption("John Conway's Game of Life")

    cells = init(dimx, dimy)

    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                return

        surface.fill(col_grid)
        cells = update(surface, cells, cellsize)
        pygame.display.update()

if __name__ == "__main__":
    main(120, 90, 8)

Erläuterungen zum Quellcode

Die Gosper Gleiterkanone

Dieses Programm verwendet die Bibliotheken "pygame" und "numpy". Diese Bibliotheken müssen mittels PIP in der verwendeten Python Entwicklungsumgebung installiert werden.


import pygame
import numpy as np

In der init-Funktion werden die Variablen initialisiert. Als Startzustand der Simulation wird ein Muster gewählt, das "Gosper Gleiterkanone" heißt. Dieses einfache Startmuster erzeugt kleinere Muster, sogenannte Gleiter, die sich auf einer Geraden von der "Kanone" wegbewegen. Der Zustand der Zellen wird in einem Zweidimensionalen Feld names cells gespeichert.

Das Muster der Gleiterkanone in der Variable pattern gespeichert und in der linken oberen Ecke des Feldes mit dem Startzustand der Simulation kopiert. Danach wird das Feld cells mittels return Anweisung zurückgegeben.


def init(dimx, dimy):
    cells = np.zeros((dimy, dimx))
    pattern = np.array([[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,0,0,0,0,0,0,0,0,0,0,0,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,0,0],
                        [0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,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,0,0,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
                        [1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
                        [1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,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,1,0,0,0,0,0,1,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,1,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,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]]);
    pos = (3,3)
    cells[pos[0]:pos[0]+pattern.shape[0], pos[1]:pos[1]+pattern.shape[1]] = pattern
    return cells

Die update-Funktion ist der Kern der Simulation. Diese Funktion berechnet den Status der Zellen im nächsten Zeitschritt und wendet dafür die Regeln des Spiels des Lebens auf alle Zellen an. Am Beginn der Funktion wird ein neues zweidimensionales Feld namens nxt erzeugt und mit Nullen initialisiert. In diesem Feld wird später der neue Zustand der Zellen abgespeichert um diesen am Ende der Funktion zurück geben zu können.

Danach wird in einer Schleife über alle Zellen iteriert. Für jede Zelle wird die Anzahl der lebenden Nachbarzellen ermittelt. Anschließend werden die Regeln angewendet:

Eine lebendige Zelle stirbt, wenn sie weniger als zwei lebendige Nachbarzellen hat.
Eine lebendige Zelle mit zwei oder drei lebendigen Nachbarn lebt weiter.
Eine lebendige Zelle mit mehr als drei lebenden Nachbarzellen stirbt im nächsten Zeitschritt.
Eine tote Zelle wird wiederbelebt, wenn sie genau drei lebende Nachbarzellen hat.

Da das Feld nxt bereits mit Nullen initialisiert ist, werden tote Zellen nicht extra hineingeschrieben. Abschließend wird jeder Zelle eine, ihrem Status entsprechede Farbe zugewiesen. Nach Abschluss der Berechnung wird der neue Zustand der Simulation zurück gegeben. Die Zeitschrittberechnung ist komplett.


def update(surface, cur, sz):
    nxt = np.zeros((cur.shape[0], cur.shape[1]))

    for r, c in np.ndindex(cur.shape):
        num_alive = np.sum(cur[r-1:r+2, c-1:c+2]) - cur[r, c]

        if cur[r, c] == 1 and num_alive < 2 or num_alive > 3:
            col = col_about_to_die
        elif (cur[r, c] == 1 and 2 <= num_alive <= 3) or (cur[r, c] == 0 and num_alive == 3):
            nxt[r, c] = 1
            col = col_alive

        col = col if cur[r, c] == 1 else col_background
        pygame.draw.rect(surface, col, (c*sz, r*sz, sz-1, sz-1))

    return nxt

Die Hauptschleife des Programmes ist kurz. Sie initialisiert das Programm und enthält eine Ereignisschleife, mit der pygame überprüft, ob das Programm durch den Benutzer beendet wurde. Solange das Programm nicht beendet wurde wird die update Funktion aufgerufen und die Simulation fortgesetzt.


def main(dimx, dimy, cellsize):
    pygame.init()
    surface = pygame.display.set_mode((dimx * cellsize, dimy * cellsize))
    pygame.display.set_caption("John Conway's Game of Life")

    cells = init(dimx, dimy)

    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                return

        surface.fill(col_grid)
        cells = update(surface, cells, cellsize)
        pygame.display.update()

Weblinks

Eine kürzere Version der Implementierung von Game of Life in Python wird von Jack Diederich in dem Video Stop Writing Classes des Youtube Kanals Next Day Video beschrieben.