Mathesis Wiki

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Zelluläre Automaten [WS19/20] ======



Projektteilnehmende: Hanna, Mazal, Richard, Leroy und (Lars)


====== **Grundidee:** ======


Im Allgemeinen haben wir uns sehr für verschiedene Simulationen interessiert, wie zum Beispiel der Stau- oder Fluchtsimulationen. Beides sind Zelluläre Automaten. 
Die Grundidee von Zelluläre Automaten ist, dass bei einem Feld von toten und lebendigen Zellen, welches sich mit jedem Zeitschritt verändert, die neue Generation von der vorherigen abhängig ist. Dabei bestimmt der Zustand einer Zelle und die Zustände ihrer Nachbarn, ob diese Zelle im nächsten Zeitschritt lebt oder stirbt.
Wir haben uns erst mit dem NaSch-Modell zur Stausimulation und dann als Hauptprojekt mit dem zweisimensionalen Game Of Life von John Conway befasst.

**Das Nagel-Schreckenberg-Modell**

Das Nagel-Schreckenberg-Modell ist ein eindimensionaler zellulärer Automat, mit dem Stausimulationen ausgeführt werden können. Das Prinzip dabei ist, dass es eine Anzahl von Autos gibt, denen jeweils eine Geschwindigkeit zwischen 1 und einer festgelegten Höchstgeschwindigkeit zugeordnet ist. Mit jedem Zeitschritt werden immer vier verschiedene Regeln angewendet:
1. Beschleunigen: Jedes Auto beschleunigt, indem falls die Maximalgeschwindigkeit noch nicht erreicht ist, die Geschwindigkeit um eins erhöht wird.
2. Verlangsamen/Abbremsen: Falls die Lücke bis zum nächsten Auto kleiner ist, als seine eigene Geschwindigkeit, wird die Geschwindigkeit auf die Größe der Lücke reduziert.
3. Zufallsanteil: Mit einer bestimmten Wahrscheinlichkeit wird die Geschwindigkeit von den Autos um eins verringert.
4. Bewegung: Jedes Auto bewegt sich um seine Geschwindigkeit nach vorne.

**Unser Projekt:**

Durch unsere Faszination für Zelluläre Automaten, sind wir auf das Game of Life vom Mathematiker John Conway gestoßen. Dieser zweidimensionale Zelluläre Automat richtet sich nach folgenden Regeln um die nächste Generation und somit den Wert einer jeden Zelle in Abhängigkeit von ihren 8 Nachbarzellen zu bestimmen:
  - Eine tote Zelle mit drei lebenden Nachbarn wird im nächsten Zeitschritt lebendig
  - Eine lebende Zelle mit weniger als zwei lebenden Nachbarn wird im nächsten Zeitschritt zu einer toten Zelle
  - Eine lebende Zelle mit zwei oder drei lebenden Nachbarn wird im nächsten Zeitschritt lebendig
  - Eine lebende Zelle mit mehr als drei lebenden Nachbarn wird im nächsten Zeitschritt zu einer toten Zelle

**Methode zum Updaten:**

In unserer Version wird das Updaten der Zellwerte durch zwei Matrixmultiplikationen und eine Boolesche Abfrage gewährleistet. 
$$ MT=Z $$
Zu erst wird die Matrix $M$, in der die Zustände der Zellen gespeichert sind, mit der Tridiagonalmatrix $T$ multipliziert. Diese ist mit Nullen gefüllt, abgesehen von der Diagonalen, den beiden Nebendiagonalen und den anderen zwei Ecken. 
$$ TZ=S $$
In der entstandenen Matrix $Z$ ist in jedem Feld die Summe der Zelle selbst und ihrer direkten horizontalen Nachbarn. Diese Matrix wird wieder mit der Tridiagonalmatrix, nun aber von der anderen Seite multipliziert um vertikal aufzuaddieren. Die entstandene Matrix $S$ hat in jedem Feld die Summe der ursprünglichen Zelle und ihrer 8 Partner. Um herauszufinden ob ein Zellwert im nächsten Zeitschritt 0 oder 1 ist, muss man nur noch mit einer booleschen Abfrage die obenbeschriebenen Regeln anwenden.

Zusätzlich haben wir verschiedene Anfangskonfigurationen eingerichtet. Man kann auswählen zwischen einer zufällig Generierten, einer Alternierenden oder eine durch das Einlesen von Bildern oder Matrizen entstehende Konfiguration. Die Größe des Spielfeldes kann man festlegen und eine zufällige wechselnde Colormap bestimmt die Farbe. Es gibt außerdem die Möglichkeit während des Spiels, durch die Nutzung der Maus, den Zustand mehrere Zellen zu wechseln und durch die Nutzung der Leertaste das Spiel zu stoppen. 


__**Protokolle:**__
  * [[Erster Gruppentermin (21.11.2019)]]
  * 
  * [[Zweiter Gruppentermin (28.11.2019)]]
  * 
  * [[Dritter Gruppentermin (05.12.2019)]]
  * 
  * [[Vierter Gruppentermin (12.12.2019)]]
  * 
  * [[Fünfter Gruppentermin (19.12.19)]]
  * 
  * [[Sechster Gruppentermin (09.01.2020)]]
  * 
  * [[Siebter Gruppentermin (16.01.20)]]
  * 
  * [[Achte Gruppentermin (19.12.19)]]
  * 
  * [[Neunter Gruppentermin(30.01.2020)]]
  * 
  * [[Zehnter Gruppentermin (06.02.2020)]]
  * 
  * [[Elfter Gruppentermin (13.02.2020)]]


__**Finaler Code:**__

[[Dokumentierter Code(finale Version)]]

{{ :ws1920:gol_random.gif?nolink |}}

{{ :ws1920:gol_alternating.gif?nolink |}}

__**Fazit:**__

Wir sind sehr zufrieden mit unserem Endergebnis. Unsere Gruppendynamik hat es uns erlaubt unsere Ziele nach und nach zu erarbeiten. Wir haben die Zeit im Labor optimal genutzt und so kann unser Programm jetzt fast alles, was wir uns vorgenommen hatten. Als Verbesserungsvorschlag an unseren Code hätten wir uns gewünscht, dass man nicht nur periodische Randbedingungen und auch nicht quadratische Matrizen hätte verwenden können. 

**[[Quellen]]**

[[**Hinweise von Stefan Born**]]
Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Seiten-Werkzeuge
