|
Game of Life |
|
|
|
Ausgedacht hat sich dieses "Spiel" der amerikanische Mathematiker John Horton Conway (geb. am 26.12.1937).
Bekannt wurde das Game of Life, als es im Jahr 1970 im Wissenschaftsmagazin Scientific American
(dessen deutsche Ausgabe heute Spektrum der Wissenschaft heißt) vorgestellt wurde.
Die Regeln sind einfach: Gespielt wird auf einem Feld, das wie ein Schachbrett in lauter quadratische Zellen eingeteilt ist.
Eine Zelle ist entweder besetzt oder unbesetzt. Eine Konfiguration von besetzten und unbesetzten Zellen
kann man sich als Generation von Lebewesen vorstellen, aus der sich die nächste Generation nach folgenden Regeln entwickelt.
|
Die Regeln
1. Eine leere Zelle wird in der nächsten Generation besetzt, wenn sie genau drei besetzte Nachbarzellen hat.
2. Eine besetzte Zelle bleibt auch in der nächsten Generation besetzt, wenn sie zwei oder drei besetzte Nachbarzellen hat.
3. Alle Zellen, bei denen die Voraussetzungen der Regeln 1 und 2 nicht zutreffen, sind in der nächsten Generation unbesetzt.
|
|
J. H. Conway,
geb. 26.12.1937, englischer Mathematiker
|
|
Der Ablauf des Programms
Als erstes wird ein Gitter mit einer bestimmten Anzahl von quadratischen Zellen gezeichnet. Danach
werden mit der Maus die gewünschten Zellen markiert. Dann müssen die Nachbarzellen auf Belegung
oder Nichtbelegung überprüft werden.
Die Anzahl der lebenden Zellen wird in einem Feld gespeichert. Anschließend wird abhängig von der Anzahl der
lebenden Zellen die Zelle besetzt oder nicht besetzt. Diese Reihenfolge Überprüfung - Neu-Zeichnen kann dann
beliebig oft wiederholt werden. Damit können dann die folgenden Generationen gezeichnet werden. Mit Hilfe des Befehls
gifsave können die einzelnen Bilder der jeweiligen Generationen zu einer Gif-Animation zusammengefügt werden.
Für die zu berücksichtigen Nachbarzellen wird die Moore-Umgebung zugrundegelegt. Es sind demnach (s.Abb.) 8 Zellennachbarn,
deren Zustand überprüft werden muss.
|
to raster
cs
make "yoben 400
;; oberster Y-Wert – bleibt konstant
make "yunten -400
;; unterster Y-Wert – bleibt konstant
make "xanfang -400
;; hier beginnen die senkrechten Linien
make "xende 400
;; hier ist die letzte senkrechte Linie
for[ix :xanfang :xende 20][pu setpos(list :ix :yoben)
pd setpos(list :ix :yunten)]
make "xlinks -400
;; hier beginnt die waagerechte Linie links – bleibt konstant
make "xrechts 400
;; hier endet die waagerechte Linie rechts – bleibt konstant
make "yanfang -400
;; die erste waagerechte Linie – beginnt unten
make "yende 400
;; die letzte waagerechte Linie - oben
for[iy :yanfang :yende 20][pu setpos(list :xlinks :iy)
pd setpos(list :xrechts :iy)]
end
|
|
Edward Forrest Moore,
geb. 23.11.1925 in Baltimore/USA, gest. 14.06.2003 in Madison/USA.
E. F. Moore war einer der Mitbegründer der Automatentheorie, Erfinder des nach ihm benannten
Moore-Automaten und ein früher Pionier des künstlichen Lebens
|
Moore-Umgebung
|
Markieren der Zelle
Mit mouseon wird das Kästchen, in dem sich die Maus befindet, durch fill mit der entsprechenden
Farbe ([0 0 255] – also blau) eingefärbt – dazu muss die linke Maustaste in dem Kästchen gedrückt werden.
Danach wird einfaerben rekursiv aufgerufen und mann kann weitere Zellen markieren.
Achtung:
Man darf beim Markieren der Zelle nicht auf eine Gitterlinie klicken.
|
Löschen der Zelle
Mit mouseon wird das Kästchen, in dem sich die Maus befindet, durch fill mit der entsprechenden
Farbe ([255 255 255] – also weiß) eingefärbt – dazu muss die linke Maustaste in dem Kästchen gedrückt werden.
Danach wird loeschen rekursiv aufgerufen und man kann weitere Zellen löschen.
|
|
|
Programm zum Markieren der Zellen
to einfaerben
pu
mouseon[setpos mousepos pd setfc[0 0 255]fill pu][ ][ ][ ][ ]
einfaerben
end
Programm zum Löschen der Zellen
to loeschen
pu
mouseon[setpos mousepos pd setfc[255 255 255]fill pu][ ][ ][ ][ ]
loeschen
end
|
Jetzt muss jede Zelle auf mögliche Nachbarn überprüft werden. Dabei bedeutet weiß – nicht besetzt
und blau – besetzt.
Über die Anzahl der Nachbarn wird bestimmt, ob diese Zelle in der nächsten Generation besetzt ist oder nicht.
Beim Programm NeueGeneration werden jetzt alle Zellen der Reihe danach überprüft wie viele belegte Nachbarn jede besitzt.
Dieser Wert wird in einem zweidimensionalen Feld (anzahlFeld) abgespeichert.
Ablauf der Überprüfung
Die Zellen das Gitters werden wie folgt durchlaufen. Man beginnt mit der linken unteren Zelle,
dann wird die untere Zeile nach rechts durchlaufen. Danach geht es bei der darüber liegenden Zeile
weiter bis zur obersten Zeile. Dafür eignen sich zwei For-Schleifen.
|
Moore-Umgebung
|
Für alle 8 Nachbarzellen gibt es Positionen, in denen die jeweilige Zelle nicht im vorgegebenen Raster liegt.
Für diese Fälle muss sicher gestellt werden,
dass diese bei der Abfrage bzgl. der Farbe nicht berücksichtigt werden.
Beispiel
Die rote Zelle befinde sich im vorgegebenen Raster ganz unten links. Dann befinden sich folgende
blaue Zellen nicht in diesem Raster: 2, 3, 4, 5 und 6. Befindet sich die rote Zelle ganz rechts unten,
so sind dies: 4, 5, 6, 7 und 8. Man sieht also, dass die Lage der betrachteten Zelle auf dem Rand gesondert betrachtet
werden muss.
|
|
Die Überprüfung
Ausgehend von den Koordinaten der roten Zelle (diese heißen hier xko und yko) werden jetzt nacheinander
die (blauen) Zellen 1 bis 8 nach deren Farbe abgefragt. Wenn die rote Zelle mit setpos(list :xko :yko) angesprochen wird,
so ist die Zelle 5 mit setpos(list :xko :yko-20) zu erreichen. Man mache sich klar, wie der Aufruf mit setpos der
anderen 7 Zellen aussieht.
|
Wir betrachten den Fall: die rote Zelle befindet sich unten links. Es soll die Zelle 5 überprüft werden.
pu setpos(list :xko :yko-20)
ifelse (:yko-20<-400) [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld) ] [~
pd if pixel=[0 0 255] [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1 ]]
|
In der ifelse-Bedingung wird abgefragt ob die Zelle nicht im Raster liegt.
Ist dies der Fall – die Bedingung ist also True – dann wird das entsprechende Element im Array AnzahlFeld nicht verändert.
Liegt die Zelle 5 dagegen im Raster, so wird abgefragt ob die Farbe blau ist (pixel=[0 0 255]). Trifft dies zu,
wird das entsprechende Array-Element um 1 erhöht.
|
|
Programm Teil 1
to NeueGeneration
make "AnzahlFeld (mdarray[42 42] 1)
make "ymin -390 make "ymax 390
make "xmin -390 make "xmax 390
make "xNr 1 make "yNr 1
for[i 1 40 1][for[j 1 40 1][mdsetitem (list :i :j) :AnzahlFeld 0]]
for[yko :ymin :ymax 20] [for[xko :xmin :xmax 20][~
pu setpos(list :xko-20 :yko)
ifelse (:xko-20<-400) [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld) ] [~
pd if pixel=[0 0 255] [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1]]
|
Überprüfung
Bei den Zellen 2, 4, 6 und 8 werden sowohl die x-Koordinate als auch die y-Koordinate verändert.
Damit ändert sich auch die If-Abfrage.
Wir betrachten den Fall: die rote Zelle befindet sich unten links. Es soll die Zelle 4 überprüft werden.
pu setpos(list :xko-20 :yko-20)
ifelse (or (:xko-20<-400) (:yko-20<-400))
[mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld) ] [~
pd if pixel=[0 0 255]
[mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1]]
|
Da sich die Zelle 4 nicht im Raster befindet (beide Bedingungen sind erfüllt), wird der If-Teil abgearbeitet.
Nach Abarbeitung des Programms NeueGeneration sind im 2-dimensionalen Feld AnzahlFeld die Anzahl der
belegten Nachbarn jeder Zelle gespeichert.
Jetzt muss in einer Abfrage, die die Bedingungen der Regeln enthalten, die Belegung der Zellen des Rasters festgestellt werden.
|
|
Programm Teil 2
pu setpos(list :xko+20 :yko)
ifelse (:xko+20>400) [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)] [~
pd if pixel=[0 0 255] [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1]]
pu setpos(list :xko :yko-20)
ifelse (:yko-20<-400) [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld) ] [~
pd if pixel=[0 0 255] [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1 ]]
pu setpos(list :xko :yko+20)
ifelse (:yko+20>400) [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld) ] [~
pd if pixel=[0 0 255] [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1 ]]
|
Neue Generation
Abhängig von der Anzahl der besetzten Nachbarzellen wird die Zelle entweder weiß (=gestorben) oder blau
(=Geburt oder lebt weiter) eingefärbt. Durch geschickte Verschachtelung der If-Abfragen kann dieser Teil relativ
kurz gehalten werden.
|
Programm Teil 3
pu setpos(list :xko-20 :yko+20)
ifelse (or (:xko-20<-400) (:yko+20>400))[mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld) ] [~
pd if pixel=[0 0 255] [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1]]
pu setpos(list :xko-20 :yko-20)
ifelse (or (:xko-20<-400) (:yko-20<-400))
[mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld) ] [~
pd if pixel=[0 0 255] [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1]]
pu setpos(list :xko+20 :yko+20)
ifelse (or (:xko+20>400) (:yko+20>400))
[mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld) ] [~
pd if pixel=[0 0 255] [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1]]
pu setpos(list :xko+20 :yko-20)
ifelse (or (:xko+20>400) (:yko-20<-400))
[mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld) ] [~
pd if pixel=[0 0 255] [mdsetitem (list :yNr :xNr) :AnzahlFeld (mditem( list :yNr :xNr) :AnzahlFeld)+1]]
make "xNr :xNr+1]
make "yNr :yNr+1 make "xNr 1]
|
|
Programm Teil 4
;; Jetzt wird die neue Generation gezeichnet
make "xwert -390 make "ywert -390
for[yko 1 40 1][for [xko 1 40 1][~
pu setpos(list :xwert :ywert) pd
ifelse ((mditem (list :yko :xko) :anzahlFeld)=3) [~
pu setpos (list :xwert :ywert) pd setfc[0 0 255] fill][~
ifelse and pixel=[0 0 255] (mditem (list :yko :xko) :anzahlFeld)=2 [~
pu setpos (list :xwert :ywert) pd setfc[0 0 255] fill]
[ pu setpos (list :xwert :ywert) pd setfc[255 255 255] fill]
]
make "xwert :xwert+20 ]
make "xwert -390 make "ywert :ywert+20]
end
|
Auswahlmenue
In einem Menue werden die verschiedenen Operationen mit Hilfe von Schaltern ausgewählt.
Dabei wird das Zeichnen des Gitters im Hauptprogramm durchgeführt. Folgende Operationen können
durchgeführt werden:
1.Zellen markieren
2.Zellen löschen
3.Neue Generation erstellen, dieses beinhaltet die Überprüfung und das anschließende Färben der
entsprechenden Zellen.
4.Beenden des Programms
|
Programm Teil 5
to menue
windowcreate "main1 "Fenster [Menue1] 500 300 200 100[ ]
buttoncreate "Fenster "Button01 [Zellen erzeugen] 20 10 70 20[einfaerben]
buttoncreate "Fenster "Button02 [Zellen loeschen] 110 10 70 20[loeschen]
buttoncreate "Fenster "Button03 [Neue Generation] 20 40 70 20[NeueGeneration10]
buttoncreate "Fenster "Button04 [Fenster Zu] 110 40 70 20[FensterZu]
end
to FensterZu
windowdelete "Fenster
end
|
|
Programm Teil 6 - Das Hauptprogramm
to main
cs
setpensize[1 1]
raster
make "anzahl 0
make "zahl 0
menue
end
|
|
Gif - Animation |
|
|
Menue-Programm
to menue
windowcreate "main1 "Fenster [Menue1] 500 300 200 100[ ]
buttoncreate "Fenster "Button01 [Zellen erzeugen] 20 10 70 20[einfaerben]
buttoncreate "Fenster "Button02 [Zellen loeschen] 110 10 70 20[loeschen]
buttoncreate "Fenster "Button03 [Gif Animation] 20 40 70 20[GifAnimation]
buttoncreate "Fenster "Button04 [Fenster Zu] 110 40 70 20[FensterZu]
end
Achtung
Wenn beim gifsave-Befehl nur der Gif-Datei-Name angegeben wird, ist der Speicherplatz der Gif-Datei nicht der
Ordner, in dem sich die Programmdatei befindet (lgo-Datei). Die Gif-Datei befindet sich beim Betriebssystem
Windows 7 etc. im Ordner
C:\Users\..UserName\AppData\Local\VirtualStore\Windows\System32
Besser ist es, direkt den Pfad anzugeben z.B.:
J:/Sporenberg/PowerPoint_Einfuehrungen/MSWLogo/Programme/Mouseon/Animation.gif
|
GIF - Animation
Mit Hilfe des implementierten Befehls gifsave können die verschiedenen Bilder der Generationen zu
einer Animation mit Hilfe von Gif-Dateien zusammengefügt werden.
Dazu benötigt man lediglich ein neues Programm (hier GifAnimation), das Menue-Programm muss leicht geändert werden und
die bisherigen Programme einfaerben, loeschen, FensterZu und NeueGeneration10 können unverändert übernommen
werden.
Um Speicherplatz bei der Gif-Datei zu sparen, sollte man mit setactivearea das aktive Fenster möglichst
klein halten (Zeile 2). In einer For-Schleife wird dann neueGeneration aufgerufen und die Grafik der Gif-Datei hinzugefügt.
Der Parameter der For-Schleife gibt die Anzahl der Bilder an (hier sind es 30).
|
|
Das Programm GifAnimation
(1)to GifAnimation
(2)setactivearea [-420 -420 -120 -160]
(3)make "append "false
(4)for [i 1 30 1][neueGeneration (gifsave "Animation.gif 0 :append 0)
(5)make "append "true wait 1]
(6)end
Achtung: in Zeile (4) sollte besser der Pfad für die Datei Animation.gif angegeben werden.
Dann weiß man wo die Datei sich befindet.
|
|
Von Neumann-Nachbarschaft |
|
|
John von Neumann
|
John von Neumann war ein ungarisch-US-amerikanischer Mathematiker. Er leistete bedeutende Beiträge
zur mathematischen Logik, Funktionalanalysis, Quantenmechanik und Spieltheorie und gilt als einer der Väter
der Informatik (geb. 28.12.1903 in Budapest, gest. 08.02.1957 in Washington). Alle Rechner arbeiten noch heute nach
dem sog. von-Neumann-Prinzip.
|
|
Neumann - Nachbarschaft
Die Von-Neumann-Nachbarschaft ist eine Nachbarschaftsbeziehung in einem quadratischen Raster.
Lediglich die Flächen, welche eine Kante mit der Basisfläche gemeinsam haben, gelten als Nachbarn.
Bei der Abfrage in der Prozedur neueGeneration werden die ifelse-Abfragen für die Eckzellen gelöscht.
Alle anderen Programme können komplett so übernommen werden.
|
von Neumann-Nachbarschaft
|
|
|
Programm Code
Bei der Abfrage in der Prozedur neueGeneration werden die ifelse-Abfragen für die Eckzellen gelöscht.
Somit ergibt sich ein wesentlch kürzerer Programm-Code. Das ist die einzige Änderung.
|
|
Andere Regeln |
|
|
Schreibweise
Um sich beim Vergleich unterschiedlichster Regelwerke eine umständliche Umschreibung der Regeln zu ersparen,
existiert eine Kurzschreibweise für die Regeln von Game of Life: Man zählt zunächst die Anzahl von Nachbarn auf,
bei der eine Zelle nicht stirbt, und später, durch einen Schrägstrich abgetrennt, die Anzahl der Nachbarn, bei der eine Zelle geboren wird. Diese werden einfach aufgezählt und als Zahl behandelt.
|
Die klassische Conway-Welt ist in der Kurzschreibweise
23/3 – nämlich bei 2 oder 3 Nachbarzellen stirbt die Zelle nicht,
bei genau 3 Nachbarzellen wird eine neue Zelle erzeugt
|
|
Die Kopier-Regel
Löschregel: Eine Zelle mit genau 0,2,4,6 oder 8 Nachbarn stirbt
Geburtsregel: 1,3,5 oder 7 Nachbarn erzeugen eine lebende Zelle.
Diese Regel hat folgende Kurzschreibweise: 1357/1357
|
Bei der Programmierung sind die Bedingungen entsprechend abzuändern. Dies geschieht mit einer Ifelse-Abfrage,
in der 4 Bedingungen durch or verbunden werden.
Achtung: Werden mehrere Bedingungen durch and oder or verbunden, so gibt es häufig
Probleme beim Setzen der Klammern.
|
|
|
Der zu verändernde Programmcode
;; Jetzt wird die neue Generation gezeichnet
make "xwert -390 make "ywert -390
for[yko 1 40 1][for [xko 1 40 1][ pu setpos(list :xwert :ywert) pd ~
ifelse (or ((mditem(list :yko :xko) :anzahlFeld)=1) ((mditem(list :yko :xko) :anzahlFeld)=3)
((mditem(list :yko :xko) :anzahlFeld)=5) ((mditem(list :yko :xko) :anzahlFeld)=7)) [~
pu setpos (list :xwert :ywert) pd setfc[0 0 255] fill] ~
[ pu setpos (list :xwert :ywert) pd setfc[255 255 255] fill]
make "xwert :xwert+20 ]
make "xwert -390 make "ywert :ywert+20]
end
|
