# hexagonalen Gittergasautomaten (Zellulare Automat)



## manoo (27. Feb 2010)

Hallo,
ich muss für die Uni ein kleines (in meinen Augen, eher großes) Programm schreiben, es handelt sich hierbei um die Implementierung des Schadstofftransports in einem hexagonalen Gittergasautomaten . Zur vollständigen Bearbeitung sollen folgende Teilaufgaben bearbeitet werden:
•Implementierung des FHP-Modells zur Beschreibung der Schadstoffausbreitung in einem zwei-dimensionalem Gebiet
•Grafische Darstellung der Schadstoffdichte auf dem Gitter. Durch eine interaktive Oberfläche soll eine Variation der Eingabeparameter ermöglicht werden.
Theoretisch kann ich mir da schon was vorstellen, wie ich rangehen könnte, leider sind meine Java-Kenntnisse einfach viel zu gering und ich schaffe nicht den ersten Einstieg;(. 
Ich hoffe, dass mir jemand  helfen kann und eine Idee hat, wie dieses FHP-Modell implementiert werden kann.

Danke im voraus.


----------



## Momolin (1. Mrz 2010)

Hallo manoo
ich würde mal mit der Klasse für ein Teilchen anfangen.
Natürlich kenne ich das FHP Modell nicht, aber mit dem was ich in Wikipedia gefunden habe, würde ich die Klasse so definieren:

```
package fhpmodell;

import java.util.ArrayList;
import java.util.List;

public class Teilchen {

	private List<Teilchen> nachbarn = new ArrayList<Teilchen>();

	private Teilchen richtung;

	public void bewegeVorwaerts() {
		/*
		 * das muss implementiert werden: Die Teilchen werden rundenweise
		 * vorwärts bewegt. Zwischen den Zügen wird jeweils überprüft, ob es an
		 * einem Gitterpunkt zu einer Streuung kommt.
		 */
	}

	public int getAnzahlNachbarn() {
		return nachbarn.size();
	}
}
```

Nach Deinen Anforderungen würde ich den Gasautomaten dann so entwerfen:

```
package fhpmodell;

import java.util.ArrayList;
import java.util.List;

public class Automat {
	private List<Teilchen> teilchen = new ArrayList<Teilchen>();

	public void schadstoffAusbreiten(double eingabe1, double eingabe2){


	};

	public double getSchadstoffDichte(Teilchen wo){
		return 0.0;
	}
}
```

ein spannendes Problem, gerne helfe ich Dir weiter.

Viele Grüße
Momolin


----------



## Momolin (1. Mrz 2010)

die Klasse Teilchen einfacher

```
public class Teilchen {
	private Point gitterpunkt;
	private Richtung richtung;

	public Teilchen(Point gitterpunkt, Richtung richtung) {
		this.gitterpunkt = gitterpunkt;
		this.richtung = richtung;
	}

}
```

dafür die Richtung als Konstanten


```
public enum Richtung {
	_0_GRAD, _60_GRAD, _120_GRAD, 
	_180_GRAD, _240_GRAD, _300_GRAD
}
```

und wieder ein Modell:

```
public class Gasmodell {
	private Map<Point, List<Teilchen>> modell;

	/**
	 * einfaches Modell mit einem Teilchen / Gitterpunkt
	 */
	public Gasmodell(int sizeX, int sizeY) {
		modell = new HashMap<Point, List<Teilchen>>();

		for (int x = 0; x < sizeX; x++) {
			for (int y = 0; y < sizeY; y++) {
				Point pAktuell = new Point(x, y);
				List<Teilchen> teilchenProGitterPunkt =
						new ArrayList<Teilchen>();

				Teilchen t = new Teilchen(pAktuell, Richtung._60_GRAD);
				// usw. bis maximal 6 Teilchen

				teilchenProGitterPunkt.add(t);
				modell.put(pAktuell, teilchenProGitterPunkt);
			}
		}
	}

	public void bewegen() {
		// nun wir für jeden Gitterpunkt die Bewegung ausgeführt
		// und die Streung bestimmt
	}
}
```

nun gut, viel Erfolg erst mal

Grüße Momolin


----------



## manoo (1. Mrz 2010)

Vielen Dank Momolin für die Antwort:toll:

Die wesentlichen Eigenschaften der FHP-Modell sind :
* Die zugrunde liegenden regelmäßigen Gitter zeigt hexagonale Symmetrie.
* Knoten (auch Seiten) sind bis sechs nächste Nachbarn, die sich in Bezug auf die zentralen Knoten in gleiche Strecke befinden.
* Die Vektoren c_i verknüpft die nächsten Nachbarknoten werden als Gittervektoren oder Gitter-Geschwindigkeiten genannt.
(c_i= cos (pi/3*i) , sin(pi/3*i) für i=1,...,6 mit |c_i| = 1 für alle i.)
* Eine Zelle ist mit jedem Link alle Knoten verbunden sind
* Die Zellen können leer oder belegt mit höchstens einem Teilchen
* Alle Teilchen haben die gleiche Masse.
* Die Entwicklung in der Zeit geht durch das Kollisionprinzip und die Propagation.
* Die Kollisionen sind rein lokale, dh nur Teilchen von einem einzelnen Knoten beteiligt sind.

Die zellularer Automat wird durch die Zustandsübergangsfunktion definiert. In dem Fall von FHP-Model besteht der Zustandsübergang aus zwei Teilschritten. Im ersten Teilschritt führen die Teilchen an einem Knoten des Gitters Kollissionen aus. Dann fliegt jedes Teilchen in seiner Richtung zum nächsten Knoten. Kollisionen finden nur dann statt, wenn sich an einem Ort zwei, drei oder vier Teilchen befinden, deren Gesamtimpuls Null ist. In allen anderen Fallen bleibt der Zustand unverandert. Bei zwei Teilchen mit Gesamtimpuls Null mussen diese genau aufeinander zu fliegen. Beide Teilchen werden dann entweder um +60° oder um -60° gedreht. Dabei wird die Richtung zufallig ausgewahlt. Bei drei Teilchen mit Gesamtimpuls Null betragt der Winkel zwischen diesen 120°. Diese Konfiguration wird um +60° gedreht. Bei vier Teilchen mit Gesamtimpuls Null gibt es zwei gegenuberliegende unbesetzte Richtungen. Hier wird die gesamte Konfiguration mit Wahrscheinlichkeit 1/2 um +60°, bzw. mit Wahrscheinlichkeit 1/2 um -60° gedreht.

Ich hoffe, dass Sie mir mit dieser Eklärungen weiter helfen können.
vielen dank im voraus.


----------



## Momolin (2. Mrz 2010)

manoo hat gesagt.:


> Die zellularer Automat wird durch die Zustandsübergangsfunktion definiert. In dem Fall von FHP-Model besteht der Zustandsübergang aus zwei Teilschritten. Im ersten Teilschritt führen die Teilchen an einem Knoten des Gitters Kollissionen aus. Dann fliegt jedes Teilchen in seiner Richtung zum nächsten Knoten.



was passiert, wenn ein Teilchen in eine Richtung fliegen will, die schon besetzt ist,
oder kann es sein, dass die vorherigen Kollisionen so einen Fall ausschließen, was ich jetzt mal vermute,

Grüße
Momolin


----------



## manoo (2. Mrz 2010)

Hallo Momolin, 
du hast richtig gedacht. Wenn eine Zelle besitzt ist, wird dann die Kollisionsregel eingesetzt.

Grüße
manoo


----------



## Momolin (9. Mrz 2010)

Hallo,
ich denke das ist mal ein Ansatz:

zuerst eine Klasse Teilchen

```
package fhp;

import java.util.Random;

public class Teilchen {

	private static int winkel[] = { 0, 60, 120, 180, 240, 300 };

	public static int _60_GRAD = 60;
	/**
	 * sollte nur Werte annehmen, die vielfaches von 60 sind
	 */
	private int richtung = 60;

	public static Teilchen createRandomTeilchen() {
		Teilchen t = new Teilchen();
		Random random = new Random();
		int randomW = random.nextInt(winkel.length);
		t.setRichtung(winkel[randomW]);
		return t;
	}

	public static boolean isImpulsNull(Teilchen t1, Teilchen t2) {
		int summe = t1.getRichtung() + t2.getRichtung();

		if (summe == 180 || summe == 360)
			return true;
		else
			return false;
	}

	public static boolean isImpulsNull(Teilchen teilchen, Teilchen n1,
			Teilchen n2) {
		// ähnlich wie oben
		return false;
	}

	public void drehen(int winkel) {
		richtung += winkel;
	}

	public int getRichtung() {
		return richtung;
	}

	/**
	 *
	 * @param richtung
	 *            0, 60, 120, 180, 240, 300
	 */
	public void setRichtung(int richtung) {
		boolean ok = false;
		for (int w : winkel) {
			if (richtung == w)
				ok = true;
		}

		if (!ok)
			throw new IllegalArgumentException("Richtung "
					+ String.valueOf(richtung) + " ist nicht erlaubt");

		this.richtung = richtung;
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		return richtung + "°";
	}
}
```

dann die Klasse mit dem Modell

```
package fhp;

import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class FHPModell {

	private Map<Point, Teilchen> model;

	/**
	 * Modelle sollen nur mit Fabrikmethoden erzeugt werden.
	 */
	private FHPModell() {
		model = new HashMap<Point, Teilchen>();
	}

	/**
	 * Fabrik für ein 100 Knoten Modell.
	 * 
	 * @return Modell mit 100 Knoten
	 */
	public static FHPModell create10x10Model() {
		Random r = new Random();
		FHPModell m = new FHPModell();
		for (int y = 0; y < 10; y++) {
			for (int x = 0; x < 10; x++) {
				Point p = new Point(x, y);
				Teilchen t = Teilchen.createRandomTeilchen();

				if (r.nextInt(4) == 0)
					// Knoten ohne Teilchen
					m.model.put(p, null);
				else
					m.model.put(p, t);
			}
		}
		return m;
	}

	/**
	 * Fabrik für ein 16 Knoten Modell.
	 * 
	 * @return Modell mit 16 Knoten
	 */
	public static FHPModell create4x4Model() {
		Random r = new Random();
		FHPModell m = new FHPModell();
		for (int y = 0; y < 4; y++) {
			for (int x = 0; x < 4; x++) {
				Point p = new Point(x, y);
				Teilchen t = Teilchen.createRandomTeilchen();

				if (r.nextInt(4) == 0)
					// Knoten ohne Teilchen
					m.model.put(p, null);
				else
					m.model.put(p, t);
			}
		}
		return m;
	}

	public static void main(String[] args) {
		// FHPModell fhpModell = FHPModell.create4x4Model();
		FHPModell fhpModell = FHPModell.create10x10Model();

		System.out.println(fhpModell.toString());

		System.out.println("Zustand wechseln");
		fhpModell.wechselZustand();

		System.out.println(fhpModell.toString());

		System.out.println("...Ende");
	}

	private void bewege() {
		Map<Point, Teilchen> bewegtesModell = new HashMap<Point, Teilchen>();

		for (Point p : model.keySet()) {
			Teilchen teilchen = model.get(p);
			int x_neu = 0, y_neu = 0;
			if (teilchen == null) {
				x_neu = p.x;
				y_neu = p.y;
			} else {
				int richtung = teilchen.getRichtung();
				switch (richtung) {
				case 0:
					x_neu = p.x + 1;
					y_neu = p.y;
					break;
				case 60:
					x_neu = p.x + 1;
					y_neu = p.y + 1;
					break;
				// u.s.w
				default:
					break;
				}
			}

			Point p_neu = new Point(x_neu, y_neu);
			// laut FHP Modell sollte jetzt jede Bewegung möglich sein
			// deshalb wäre hier ein Test gut
			if (bewegtesModell.containsKey(p_neu)) {
				// Programmierfehler
			}
			bewegtesModell.put(p_neu, teilchen);
		}

		// nun noch den Zustand wechseln
		model = bewegtesModell;
	}

	private void kollidiere() {
		for (Point p : model.keySet()) {
			Teilchen teilchen = model.get(p);

			// Knoten ist leer
			if (teilchen == null)
				continue;
			else {
				List<Teilchen> nachbarn = getNachbarn(p);
				int anzahlNachbarn = 0;

				for (Teilchen nachbar : nachbarn) {
					if (nachbar != null)
						anzahlNachbarn++;
				}

				// zwei Teilchen
				if (anzahlNachbarn == 1) {
					Teilchen nachbar = null;
					for (Teilchen nachbarInListe : nachbarn) {
						if (nachbarInListe != null)
							nachbar = nachbarInListe;
					}

					if (Teilchen.isImpulsNull(teilchen, nachbar)) {
						// - Teilchen._60_GRAD kann auch sein
						nachbar.drehen(Teilchen._60_GRAD);
						teilchen.drehen(Teilchen._60_GRAD);
					}

				}
				// drei Teilchen
				else if (anzahlNachbarn == 2) {
					Teilchen n1 = null;
					Teilchen n2 = null;

					for (Teilchen nachbarInListe : nachbarn) {
						if (nachbarInListe != null) {
							if (n1 == null)
								n1 = nachbarInListe;
							else
								n2 = nachbarInListe;
						}
					}

					if (Teilchen.isImpulsNull(teilchen, n1, n2)) {
						teilchen.drehen(Teilchen._60_GRAD);
						n1.drehen(Teilchen._60_GRAD);
						n2.drehen(Teilchen._60_GRAD);
					}
				}
				// vier Teilchen
				else if (anzahlNachbarn == 3) {
					Teilchen n1 = null;
					Teilchen n2 = null;
					Teilchen n3 = null;
					for (Teilchen nachbarInListe : nachbarn) {
						if (nachbarInListe != null) {
							if (n1 == null)
								n1 = nachbarInListe;
							else if (n2 == null)
								n2 = nachbarInListe;
							else
								n3 = nachbarInListe;
						}
					}
                                         // hier fehtl noch die isImpulseNull für 4 Parameter
					// - Teilchen._60_GRAD kann auch sein
					teilchen.drehen(Teilchen._60_GRAD);
					n1.drehen(Teilchen._60_GRAD);
					n2.drehen(Teilchen._60_GRAD);
					n3.drehen(Teilchen._60_GRAD);
				}
				// ...sonst keine Kollision
			}

		}
	}

	public List<Teilchen> getNachbarn(Point knoten) {
		List<Teilchen> nachbarn = new ArrayList<Teilchen>();
		int x, y;
		int nx, ny;
		Point nachbarKnoten;
		Teilchen nachbarTeilchen = null;

		x = knoten.x;
		y = knoten.y;

		nx = x - 1;
		ny = y;
		nachbarKnoten = new Point(nx, ny);
		// wenn es zu dem Knoten kein Teilchen gibt ist der Rückgabewert null
		nachbarTeilchen = model.get(nachbarKnoten);
		nachbarn.add(nachbarTeilchen);

		nx = x + 1;
		ny = y;
		nachbarKnoten = new Point(nx, ny);
		// wenn es zu dem Knoten kein Teilchen gibt ist der Rückgabewert null
		nachbarTeilchen = model.get(nachbarKnoten);
		nachbarn.add(nachbarTeilchen);

		nx = x - 1;
		ny = y + 1;
		nachbarKnoten = new Point(nx, ny);
		// wenn es zu dem Knoten kein Teilchen gibt ist der Rückgabewert null
		nachbarTeilchen = model.get(nachbarKnoten);
		nachbarn.add(nachbarTeilchen);

		nx = x + 1;
		ny = y + 1;
		nachbarKnoten = new Point(nx, ny);
		// wenn es zu dem Knoten kein Teilchen gibt ist der Rückgabewert null
		nachbarTeilchen = model.get(nachbarKnoten);
		nachbarn.add(nachbarTeilchen);

		nx = x - 1;
		ny = y - 1;
		nachbarKnoten = new Point(nx, ny);
		// wenn es zu dem Knoten kein Teilchen gibt ist der Rückgabewert null
		nachbarTeilchen = model.get(nachbarKnoten);
		nachbarn.add(nachbarTeilchen);

		nx = x + 1;
		ny = y - 1;
		nachbarKnoten = new Point(nx, ny);
		// wenn es zu dem Knoten kein Teilchen gibt ist der Rückgabewert null
		nachbarTeilchen = model.get(nachbarKnoten);
		nachbarn.add(nachbarTeilchen);

		return nachbarn;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		String result = "";
		int y_max = 0;
		int x_max = 0;

		for (Point p : model.keySet()) {
			y_max = Math.max(y_max, p.y);
			x_max = Math.max(x_max, p.x);
		}

		for (int y = 0; y <= y_max; y++) {
			for (int x = 0; x <= x_max; x++) {
				Point p = new Point(x, y);
				Teilchen t = model.get(p);
				result += String.valueOf(t) + " --- ";
			}
			if (y % 2 == 0)
				result += "\n --- ";
			else
				result += "\n";
		}
		return result;
	}

	public void wechselZustand() {
		kollidiere();
		bewege();
	}
}
```

ich habe natürlich nicht alles ausprogrammiert. Aber die main ist schon ausführbar und gibt einen ersten Eindruck. Insbesondere die Methoden bewege von FHPModell und die statischen Methoden isImpulseNull von Teilchen müssen fertig gemacht werden.

nun dann viel Erfolg


----------



## manoo (9. Mrz 2010)

Vielen Dank Momolin für die Antwort :toll:


----------

