Javakurs/Übungsaufgaben/DiffusionLimitedAggregation

Einleitung

Als [Diffusion Limited Aggregation, kurz DLA, bezeichnet man physikalische Vorgaenge bei denen sich Teilchen durch | Brownsche Bewegung zufällig bewegen und bei Kontakt mit anderen Teilchen anlagern. Diese Vorgänge können leicht am Computer simuliert werden und erzeugen sehr schöne Gebilde. In dieser Aufgabe soll es darum gehen, eine solche DLA-Simulation zu programmieren.

Eine solches Programm könnte z.B. so aussehen:

Die Theorie

Um ein möglichst gleichmäßiges Wachstum des DLA-Fraktals zu erreichen, setzt man in der Mitte des Bildschirms einen Keim und lässt auf einer Kreisbahn (grün) um das Zentrum einen neuen Partikel erscheinen. Diesen Partikel bewegt man zufällig über 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 Größe des DLA-Fraktals wachsen. Dazu überprüft man bei jeder Anlagerung eines Partikels, ob sich das Fraktal vergrößert hat und ändert gegebenenfalls den Radius. Ein Partikel hat außer seiner Existenz keine weiteren besonderen Eigenschaften.

Vorueberlegungen

Soweit so gut. Nun bist du ein wenig gefragt!
Lies dir die folgenden Fragestellungen durch, und denke darüber 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 würde man überprüfen, ob ein Partikel einen anderen berührt?
3. Wie kann man einen Partikel über die Fläche 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. Wenn dir die Struktur des Programms schon klar ist, dann kannst du gern allein Versuchen das Problem zu loesen. Hier sei noch ein Code-Fragment zum Berechnen von Koordinaten auf einem Kreis gegeben:

//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);

Falls dir noch nicht ganz klar ist, wie alles zusammen wirken soll, benutze 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

Kommentare

Wenn du Anmerkungen zur Aufgabe hast oder Lob und Kritik loswerden möchtest ist hier die richtige Stelle dafür. Klicke einfach ganz rechts auf "bearbeiten" und schreibe deinen Kommentar direkt ins Wiki. Keine Scheu, es geht nichts kaputt ;)