# 2-D-Baum Generierung



## protectedzone (10. Okt 2013)

Hallo

Ich habe einen rekursiven und zufälligen Algorithmus erzeugt, der zweidimensionale Bäume generieren kann.

Ich meine mit "Bäumen" Bäume aus (virtuellem) Holz und keine abstrakten Graphen oder so. 

Der Algorithmus wird später vielleicht mal Bestandteil eines kleineren 2-d Spiels...

Hier könnt ihr den Algorithmus downloaden:

protectedzone.de

Lest die description durch und testet mal das Programm und berichtet von möglichen Bugs!
Gebt in der Konsole beispielsweise command1 oder command2 ein und schaut, was passiert.

protectedzone


----------



## jonas.r (10. Okt 2013)

Das ist ziemlich cool!


----------



## protectedzone (11. Okt 2013)

Danke Jonas
Wie gesagt: Bug-report und konstruktive Kritik willkommen


----------



## Phaesty (15. Okt 2013)

Ich finde, dass das schon mal sehr gut aussieht, aber ich finde es merkwürdig das die Äste immer wieder dicker werden. Wenn sie sich verzweigen, müssten sie nicht dünner werden ?


----------



## protectedzone (16. Okt 2013)

Phaesty hat gesagt.:


> Ich finde, dass das schon mal sehr gut aussieht, aber ich finde es merkwürdig das die Äste immer wieder dicker werden. Wenn sie sich verzweigen, müssten sie nicht dünner werden ?



Es kommt auf die Einstellungen drauf an.
Falls du in der Konsole b600, c250, d600 eingibst, sieht es schon anders aus. Diese Zahlen müssen in einer bestimmten Relation zueinander stehen, so muss zum Beispiel c < b sein.

Aber mit diesen Einstellungen kann sich der Baum nicht "entwickeln", da die Äste schnell kleiner werden und kleine Äste nicht mehr wirklich in das Bildschirmkoordinatensystem passen.


----------



## jonas.r (18. Okt 2013)

Hast du Lust zu erklären, wie der Algorithmus funktioniert und wie genau sich die Parameter a, b, c und d auf diesen auswirken?
Würde mich interessieren.

Liebe Grüße,
Jonas

P.s.: Achja, noch ein bisschen konstruktive Kritik: 
Ich finde die generierten Bäume haben bis jetzt sehr wenig Fülle. Die Äste werden immer sehr gleichmäßig kleiner. Bei einem Baum hat auch manchmal ein großer Ast einen kleine Zweig dran. Du kannst ja mal schauen, ob du an einem Ast des 3. Levels auch mal einen Ast eines 5. oder 6. Levels ranhängst.


----------



## protectedzone (19. Okt 2013)

Ok. Ich habe gerade nochmal nachgeschaut, da ich immer so schnell vergesse, was ich überhaupt programmiert habe.

Also wie ich schon geschrieben habe, rechnet der Algorithmus rekursiv. 
Starten tut der Algorithmus mit einem vorgegebenen Hauptstamm, der nicht zufällig gegeriert wird.
Egal wie die Einstellungen sind, der erste Stamm bleibt immer gleich.

Die Klasse dieses Stammes besitzt eine Methode addChildren.
Mit dieser Methode werden genau zwei Kindstämme hinzugefügt, falls der Stamm noch keine Kinder besitzt. 
Anderfalls, also wenn der Stamm, den man mit der besagten Methode aufruft, schon Kinder besitzt, wird einfach addChildren von den Kindern aufgerufen. Und falls diese schon Kinder besitzen, leiten sie den Befehl an die Kindeskinder weiter, usw.

Ich rufe diese Methode in einer Schleife auf:
Eine Iteration: 1 Hauptstamm + 2 Kinder
Zwei Iterationen: 1 Hauptstamm + 2 Kinder + 4 Kindeskinder
Drei Iterationen: 1 + 2 + 4 + 8
n Iterationen: 1 + 2 + … + 2^n Stämme

Zudem wird bei jedem Hinzufügen geschaut, ob der Platz nicht schon von anderen Ästen aufgebraucht wurde.

Der Befehl axx gibt vor, wie häufig die besagte Schleife aufgerufen wird. Theoretisch sind 99 Aufrufe möglich, aber ich behaupte mal, dass hier der Speicher nicht mehr ausreicht: 1+2+4+…+2^99 Objekte…
Beispiel a2 = 1 + 2 + 4 = 7 Äste/Stämme

Der Befehl bxxx gibt an, wie gross die Ansatzfläche für den Kindesstamm ist. Wenn bxxx sehr klein ist, ist die Fläche für die Kindsstämme sehr gross. Wenn bxxx sehr gross ist, ist die Ansatzfläche für den nächsten Stamm sehr klein.

Der Befehl cxxx gibt an, wie lang die Stämme sind. Je grösse c, desto länger, und je kleiner, desto kürzer.
Wichtig hierbei ist, dass cxxx bxxx beeinflusst. Also je länger ein Stamm ist, desto grösser auch die Ansatzfläche. 

Deswegen müssen cxxx und bxxx beim Verstellen immer gemeinsam betrachtet werden.

Und zuzletzt dxxx: Das ist auch ein komischer Parameter. Dieser bestimmt wie bxxx auch die Ansatzfläche (also der Bereich, wo ein neuer Stamm anknüpfen soll). Er besagt, wie das gleichschenklige Dreieck mit Höhe h aussieht, an dessen beiden Seiten, die die gleiche länge haben, die Kinder anknüpfen. Genauer: Je grösser dxxx, desto kleiner h, und je kleiner dxxx, desto grösser h.
Weiss Gott, warum ich das wieder umgekehrt proportional definiert habe 
Man kann also sagen bxxx bestimmt die Breite und dxxx die Höhe des gleichschenkligen Dreiecks, an dessen gleichlangen Seiten die neuen Kinder dranwachsen. (Diese Erkenntnis kam mir auch grad während des Schreibens)

Noch zwei wichtige Sachen: All diese Befehle beeinflussen den ersten Stamm nicht! 
Probier die Befehle bei kleinem axx aus, a4 ist zum Beispiel eine gute Einstellung zum ausprobieren.

Und was vielleicht noch nicht so deutlich war: Wenn die Kindesäste keinen Platz mehr finden, weil sie schon vorhandene Äste schneiden würden, so werden sie nicht generiert. Deswegen kann es vorkommen, dass bei gewissen Einstellungen manchmal fast keine Äste entstehen…

Deswegen wächst der Baum nicht immer so exponentiell.

Ok und zu deiner letzten Anmerkung: Ja das kann man durchaus machen. Jedoch muss man solche Schritte meistens schon von Anfang an mit einberechnen. Und bei mir war es halt so, dass ich genau definiert habe: Jeder Ast hat genau zwei Kinder oder gar keine! Aber sicherlich und näher an der Realität könnte man auch sagen: Jeder Ast hat zwischen 0 und 10 Kindern. 
Und auch könnte man Blätter dranhängen, das wäre sicher auch noch schön. Aber ich habe gedacht: Mein Programm passt so besser zum Herbst 

Protected Zone


----------

