Javakurs/Übungsaufgaben/DiffusionLimitedAggregation

Einleitung

Als Diffusion Limited Aggregation, kurz DLA, bezeichnet man physikalische Vorgaenge bei denen sich Teilchen durch Brownsche Bewegung zufaellig bewegen und bei Kontakt mit anderen Teilchen anlagern. Diese Vorgaenge koennen leicht am Computer simuliert werden und erzeugen sehr schoene Gebilde. In dieser Aufgabe soll es darum gehen eine solche DLA Simulation zu programmieren.

Eine solches Programm koennte z.B. so aussehen:

Die Theorie

Um ein moeglichst gleichmaessiges Wachstum des DLA Fraktals zu erreichen, setzt man in der Mitte des Bildschirms einen Keim und laesst auf einer Kreisbahn (gruen) um das Zentrum einen neuen Partikel erscheinen. Diesen Partikel bewegt man zufaellig ueber die Ebene (blaue Bahnen). Entfernt sich der Partikel zu weit vom Zentrum (schwarzer Kreis), so wird er verworfen (rote Bahn) und ein neuer Partikel erzeugt.

Die Radien der Kreise sollten mit der Groesse des DLA Fraktals wachsen. Dazu ueberprueft man bei jeder Anlagerung eine Partikels ob sich das Fraktal vergroessert hat und vergroessert gegebenenfalls den Radius. Ein Partikel hat ausser seiner Existenz keine weiteren besonderen Eigenschaften.

Vorueberlegungen

Soweit so gut. Nun bist du ein wenig gefragt!
Lies dir die folgenden Fragestellungen durch, und denke ein wenig darueber nach.

1. Die Partikel werden in einer 2-dimensionalen Ebene gespeichert. Welche Datenstruktur aus Java kann man besonders gut verwenden um viele Partikel abzuspeichern?
2. Wie wuerde man ueberpruefen ob ein Partikel einen anderen beruehrt?
3. Wie kann man einen Partikel ueber die Flaeche bewegen? Wie erzeugt man eine Brownsche Bewegung?

.

.

.

.

.

.

.

.

Loesungen

1. Ein 2-dimensionales Array von genau der Groesse der zu simulierenden Flaeche bietet sich an. Als Datentyp wuerde boolean genugen, denn wir wollen nur wissen ob sich an der Position (x,y) ein Partikel befindet oder nicht. Dem Autor ist aber int sympathischer ;)
   int[][] field = new int[256][256];
2. Jedes der 8 benachbarten Felder um die Position des gerade betrachteten Partikels muss ueberprueft werden. Ist dort ein Partikel vorhanden, so enthaellt das Feld einen Wert >0.
3. Math.random() erzeugt zufaellige Zahlen. Mit deren Hilfe kann man ueber eine Fallunterscheidung die X- und Y-Koordinate des Partikels inkrementieren oder dekrementieren. Dadurch bewegt sich das Teilchen einen Schritt weiter.

Die Praxis

Da diese Aufgabe ziemlich komplex ist, werden Schrittweise alle noetigen Bausteine entwickelt.

Grafik

Zur Grafikdarstellung gibt es die einfach zu bedienende Klasse "Pad", die ein Fenster erstellt in dem du mit einfachen Routinen zeichnen kannst.

Falls du noch nicht die UEBB-Klassen in deinem Javakurs Verzeichnis hast, lade dir von http://uebb.cs.tu-berlin.de/books/java/ die Klassen Pad, Point unter Terminal herunter und lege sie in das Verzeichnis ab, in dem auch dein Programm entstehen soll. Wenn du dies getan hast, steht dir die Grafikfunktionalitaet zur Verfuegung. In dieser Aufgabe werden die notwendigen Grafikbefehle vorgeben, du musst dir keine Sorgen machen, dass du dies nicht schaffst.

Schritt fuer Schritt

1. Erstelle eine Klasse DLA
2. Fuegen in der ersten Zeile folgenden import hinzu: import java.awt.Color;. Was genau dies bedeutet wird in LE6 erklaert.
3. Schreibe eine Methode public static int limit(int value, int lower, int upper), die ueberprueft ob sich der Wert value innerhalb der Grenzen lower und upper befindet. Ist dies nicht der Fall, soll der Wert auf diesen Bereich beschraenkt zurueckgegeben werden.
4. Schreibe eine Methode public static boolean testPixel(int[][]field, int x, int y) die ueberprueft ob an einem bestimmten Punkt im 2-dimenstionalen Array ein Wert >0 vorliegt. Fange dabei ungueltige Werte fuer x und y ab. Benutze dazu die limit Methode.
5. Teste die testPixel(...) Methode!
6. Schreibe eine Methode public static boolean isTouching(int[][] field, int x, int y) die ueberprueft ob sich in einem der 8 umliegenden Felder ein Partikel befindet. Benutzte dabei die testPixel(...) Methode.
7. Teste diese Methode!
8. Schreibe eine Methode public static boolean inRange(int x, int y, int maxR, int maxX, int maxY) die ueberprueft ob sich die Koordination x und y in einem Rechteck der Seitenlaenge maxX und maxY innerhalb eines Abstandes maxR vom Mittelpunkt befindet.
9. Teste diese Methode!
10. Schreibe eine Methode public static int moveRandom(int movePixel) die ein Zahl (Koordinatenkomponente) mit gleichen Wahrscheinlichkeiten inkrementiert (+1), unveraendert laesst (+/-0) oder erniedrigt (-1).
11. Test kurz diese Methode.
12. Schreibe die Methode public static void setPixel(Pad drawPad, int[][]field, int x, int y, Color c). Diese ueberprueft noch einmal die Gueltigkeit der Koordinaten x und y, platziert dann im Array field an diesen Koordinaten einen Partikel und zeichnet den Partikel auf dem drawPad wie folgt:

drawPad.setColor(c);
drawPad.drawDot(x, y);

Main

Schreibe nun die main-Methode fuer das DLA Programm. Benutze dazu folgenden Rumpf, der schon die Grafik-Funktionalitaet und andere Vorgaben enthaellt:

import java.awt.Color;

class DLA {
	public static void main(String[] args) { 		
		//Feld fuer Kollisionsueberpruefung erstellen
		int[][]field = ...

		
		//Grenzen fuer Koordinaten der Partikel aus field berechnen (.length verwenden)
		int maxX = ...
		int maxY = ...

		//Fenster fuer Grafikausgabe vorbereiten und anzeigen
		Pad drawPad = new Pad();
		drawPad.setBackground(Pad.black);
		drawPad.setPadSize(maxX, maxY);
		drawPad.setVisible(true);
		drawPad.setColor(Pad.white);
		

		//"Samen" erzeugen. Also den ersten Partikel in der Mitte des Feldes setzen
		setPixel(...);
		
		//Radius des Partikels der am weitesten vom Zentrum entfernt ist
		int maxR=0;
		
		//Schleifenkopf, solange maxR nicht den Rand des Fensters
		//beruehrt, sollen neue Punkte gezeichnet werden
		while(...) {
			//einen Punkt auf einem Kreis um den Mittelpunkt mit dem Radius
			//maxR+20 erzeugen
			double x = Math.toRadians(Math.random()*360);
			int movingPixelX = limit((int)(Math.cos(x)*(maxR+20))+maxX/2, 0, maxX);
			int movingPixelY = limit((int)(Math.sin(x)*(maxR+20))+maxY/2, 0, maxY);
			
			//Schleife zum bewegen des Partikels
			//while(!isTouching(...)) && inRange(..., ..., maxR+30, ..., ...))
			{
				//Partikelkoordinaten zufaellig bewegen (moveRandom)
				movingPixelX = ...
				movingPixelY = ...
			}
			
			//Schleife zuende, ueberpruefe ob eine Beruehrung vorliegt:
			if(isTouching(...)) {
				//Farbwertberechnung fuer 1337 blau-Effekt
				int k = limit(255-(int)(255*((double)maxR*2)/(double)maxX), 0, 255);
				Color c = new Color(k, k, 255);
				
				//den Partikel setzen und zeichnen
				setPixel(...);
				
				//Radius zum Mittelpunkt berechnen,
				//wenn groesser als altes Maximum, ueberschreiben
				...
			}
		}
		 		
		return;
	}
...
}

Hinweis: Koordinaten im Computer

Am Computer werden Koordination, historisch bedingt, anders behandelt als im rechtwinkligen Koordinatensystem. Koordination im Computer werden von links nach rechts, als X-Achse und von oben nach unten als Y-Achse berechnet. Beachte dies bei der Verwendung von drawPad.drawDot(x,y).

(0,0)-------------------- X
|                  (640,0)
|
|
|
|
|
| (0,480)          (640,480)
Y