Das Spiel simulieren

Verwaltung der Daten mit Listen

Ziel ist es, einen Simulationsschritt zum Spiel des Lebens automatisiert durchzuführen.

Ein erster (fehlerhafter) Algorithmus

Ein Algorithmus zur Durchführung eines Simulationsschritts könnte so aussehen:

ALGORITHMUS neueWelt:
Übergabe: welt
FÜR i von 0 bis 4:
    FÜR j von 0 bis 4:
        anzahl = Anzahl der lebenden Nachbarn von welt[i][j]
        # Eine tote Zelle mit genau drei lebenden Nachbarn
        # wird in der Folgegeneration neu geboren.
        WENN welt[i][j] == 0 und anzahl == 3:
            welt[i][j] = 1
        # Lebende Zellen mit weniger als zwei lebenden Nachbarn
        # sterben in der Folgegeneration an Einsamkeit.
        SONST WENN welt[i][j] == 1 und anzahl < 2:
            welt[i][j] = 0
        # ...
Rückgabe: welt

Aber Vorsicht, hier ist ein Fehler versteckt, den man u.U. nur schwer findet: In einem Schleifendurchlauf kann die Variable welt verändert werden. Hierdurch erhält man beim nächsten Schleifendurchlauf evtl. eine falsche Anzahl von lebenden Nachbarn.

Aufgabe 1

Mache dir die hier vorliegende Schwierigkeit an einem Beispiel klar.

Ein zweiter (verbesserter) Algorithmus

Die oben beschriebene Schwierigkeit wird behoben, wenn man zunächst eine Kopie der Liste, die die Welt beschreibt, erzeugt.

ALGORITHMUS neueWelt:
Übergabe: welt
kopie = Kopie der Liste welt
FÜR i von 0 bis 4:
    FÜR j von 0 bis 4:
        anzahl = Anzahl der lebenden Nachbarn von welt[i][j]
        # Eine tote Zelle mit genau drei lebenden Nachbarn
        # wird in der Folgegeneration neu geboren.
        WENN welt[i][j] == 0 und anzahl == 3:
            kopie[i][j] = 1
        # Lebende Zellen mit weniger als zwei lebenden Nachbarn
        # sterben in der Folgegeneration an Einsamkeit.
        SONST WENN welt[i][j] == 1 und anzahl < 2:
            kopie[i][j] = 0
        # ...
Rückgabe: kopie

Aufgabe 2

Warum tritt die oben beschriebene Schwierigkeit hier nicht mehr auf?

Eine Kopie der Welt erzeugen

Es ist gar nicht so einfach, eine Kopie der geschachtelten Listen, die die Welt beschreiben, zu erzeugen.

Aufgabe 3

(a) Erläutere die Schwierigkeit, die hier auftritt. Vielleicht hilft dir die folgende (nicht ganz einfach zu durchschauende) Veranschaulichung der Verarbeitung.

(b) Teste die folgende Hilfsfunktion zum Erzeugen einer Kopie. Erkläre, was hier anders gemacht wird als im ersten Ansatz oben.

Die Anzahl der Nachbarn zählen

Bei der Erzeugung der neuen Welt in einem Simulationsschritt muss man für jede Zelle die Anzahl der lebenden Nachbarn bestimmen. Das realisiert man am besten mit einer eigenen Funktion:

Beachte, dass die Zellen an den Rändern der Welt weniger Nachbarn haben.

Aufgabe 4

Entwickle eine Funktionsdefinition zu der beschriebenen Funktion und teste sie mit verschiedenen Übergabedaten.

Eine neue Welt erzeugen

Wir kommen jetzt zum eigentlichen Simulationsschritt. Auch hier ist es sinnvoll, eine eigene Funktion für diese Aufgabe zu entwickeln.

Aufgabe 5

Implementiere diese Funktion. Du kannst dich dabei an dem oben gezeigten (verbesserten) Algorithmus orientieren.

Aufgabe 6

Es gibt zahlreiche interessante Fragestellungen zum Spiel des Lebens, z.B.: Gibt es Welten, die sich nicht verändern? Weitere Fragestellungen ergeben sich aus dem Artikel bei Wikipedia.

Entwickle dein Simulationsprogramm entsprechend selbstständig weiter.