Baumverteilung für Forstbetrieb

Hintergrund

Als Vorbereitung auf die Abschussprüfung haben wir alte Prüfungsaufgaben durchgearbeitet. Diese Dokumentation beschreibt die Aufgabe, ein Programm zu schreiben, die einem Forstbetrieb hilft, einen Wald mit möglichst hoher Artenvielfalt zu pflanzen.

Aufgabe

Ein bisher in Monokultur bewirtschafteter und durch Schädlinge wie den Borkenkäfer vernichteter Wald soll wiederaufgeforstet werden. Um diesen und anderen Schädlingen zu begegnen, soll die Monokultur einem abwechslungsreichen Bestand weichen. Ihre Aufgabe als Softwareentwickler/-in der MATSE Grün AG ist nun die Bestimmung einer möglichst abwechslungsreichen Bepflanzung des neu entstehenden Mischwaldes. Jede unterschiedliche Baumart i benötigt zum guten Wachstum einen individuellen Radius riin dem sich kein anderer Baum mitsamt seinem individuellen Radius befinden darf.

Zur Bestimmung der optimalen Verteilung und Vielfalt wird eine Formel benutzt die einen Wert zwischen 0 und 1 zurückliefert. Je näher der Wert an 1 liegt desto besser ist das Ergebnis. Zur Berechnung des Wertes wurde folgende Formel angegeben:

D=1-sum_{i=1}^{m}(frac{n_i}{f})^{2}

B=D*frac{sum_{k=1}^{m}n_i*pi * r_i^{2}}{b*l}

Wobei:
m = Anzahl der Baumarten
n = Anzahl aller Bäume
ni = Anzahl der Bäume des Art i
B = Endgültiges Ergebnis

Umsetzung

Umgesetzt wurde das Projekt web-basiert mithilfe von HTML und Javascript, deshalb kann es rein Clientseitig funktionieren. Zur Darstellung wird ein HTML-5 Canvas benutzt der die Bäume direkt nach dessen Berechnung anzeigt. Zusätzlich können einige Parameter der Algorithmus in der über Eingabefelder und Schieberegler frei eingestellt werden. Zum Starten des Algorithmus gibt es drei verschiedene Methoden:

  • Schleife: Die Berechnung erfolgt ohne Verzögerung und wird sofort angezeigt
  • Intervall: Die Berechnung wird Schritt für Schritt mit kurzer Pause ausgeführt
  • Random: Es wird versucht Zufällig 1 Millionen Bäume einzufügen

 

Algorithmus

Der Algorithmus versucht zuerst 2 zufällig gewählte Bäume direkt nebeneinander einzufügen. Zwischen diesen beiden Bäumen wird nun im Hintergrund eine Verbindung hergestellt. Bei jedem weiteren Schritt wird nun versucht bei allen Verbindungen auf der linken und rechten Seite jeweils Bäume einzufügen, sodass diese direkt aneinander liegen. War dies Erfolgreich wird zwischen dem neuen Baum und den alten 2 Bäumen jeweils eine Verbindung erstellt. Konnte keiner der verfügbaren Bäume eingefügt werden wird diese Seite der Verbindung verworfen. Wurde eine Verbindung komplett abgearbeitet wird sie gelöscht, die Bäume bleiben jedoch bestehen. Dieser Vorgang wird nun solange wiederholt bis kein neuer Baum mehr eingefügt werden kann.

Benutzeranleitung

Zum Starten des Algorithmus kann einer der drei Methoden ausgewählt werden, für jede Methode gibt es einen Button: “Run (loop)”, “Run (interval)” und “Run (rand)”. Desweiteren können noch andere Einstellungen vorgenommen werden, hier eine Liste aller Parameter:

  • Width: Breite des Waldes
  • Height: Höhe des Waldes
  • Interval speed: Zeit die gewartet wird bevor der nächste Schritt ausgeführt wird
  • Show numbers: Zeigt die Nummern der Bäume an oder nicht
  • Start points: Anzahl der Start-Bäume bzw. Verbindungen
  • Tree-(A/B/C) size: Größe der jeweiligen Bäume

Bei einigen Werten muss der Algorithmus erst neugestartet werden, um dies zu tun kann einfach einer Buttons erneut gedrückt werden, auch wenn der Algorithmus noch läuft. Um das Ergebnis auszuwerten kann der “Tree-Index” Wert betrachtet werden, je näher dieser an 1 liegt desto besser war das Ergebnis.

 

Sourcecode:

 

Dokumentation: Max Bebök