# Waldbrandsimulation

Dieses Buch steht im Regal Programmierung.
Dieses Wikibook beschäftigt sich mit der softwaretechnischen Simulation von Waldbränden mit der Hilfe von strukturierten Java-Programmen. Zur Modellierung des räumlich diskreten dynamischen Systems wird ein zellulärer Automat implementiert.

## Algorithmus Forest Fire

In der angewandten Mathematik ist das Waldbrandmodell Forest Fire ein dynamisches System, das eine selbstorganisierte Kritikalität aufweisen kann. Dies ist dann der Fall, wenn das System weitgehend unabhängig von der Wahl der Anfangsparameter mit der Zeit von selbst einen kritischen Punkt erreicht. Hierbei entstehen typischerweise spontan und allein aufgrund einer wohldefinierten Interaktion einzelner Systemelemente komplexe Strukturen. In Bezug auf ein Waldgebiet bedeutet dies, dass je nach Baumdichte und Geometrie der Anordnung durch einen einzigen Blitzschlag, der einen einzelnen Baum entzündet, ein mehr oder weniger großer Waldbrand entstehen und sich ausbreiten kann. Ein einziges initiales Ereignis kann auf diese Weise auch mehrere Brandherde verursachen, oder ein ganzer Wald kann komplett niedergebrannt werden.
Frühe Versionen des entsprechenden Algorithmus gehen auf Christopher L. Henley (1989) sowie auf Barbara Drossel und Franz Schwabl (1992) zurück.
→ Siehe auch englischsprachiger Wikipedia-Artikel Forest-fire model.
* Animierte Waldbrandsimulationen der Java-Klasse SimForestModel
* 960 Videoframes in 38,4 Sekunden (25 Frames pro Sekunde).
* 1200 Videoframes in Full HD (1920 x 1080 Bildpunkte). Parameter: Anzahl der initialen Blitzschläge im gesamten Gebiet = 8 Feuerausbreitungswahrscheinlichkeit auf Nachbarbaum = 1,0 Baumlöschwahrscheinlichkeit = 0,2

## Programmbestandteile

Das hier vorgestellte Java-Programm simuliert ein rechteckiges Waldgebiet. Hierzu werden mehrere Java-Klassen verwendet, die im Folgenden beschrieben werden.

### PseudoRandom

Für die Berechnung eine Folge von Pseudozufallszahlen wird ausgehend von einem Startwert $z_{0}>0$ (Englisch auch seed für Samen beziehungsweise Saatgut) mit einem primitiven Polynom eine ganzzahlige positive Zahlenfolge berechnet. Hierfür wird eine primitive Polynomfolge verwendet:
    $z_{i+1}=a\cdot z_{i}{\bmod {m}}$
Für den Divisor $m$ ist eine möglichst große Primzahl zu wählen. Für den Faktor $a$ kann eine teilerfremde ganze Zahl ausgesucht werden, die in der Nähe von ${\frac {\sqrt {m}}{3}}$ liegt. Durch einen positiven ganzzahligen Startwert und die ganzzahligen Modulo-Divisionen wird sichergestellt, dass für die Zahlen der Polynomfolge stets gilt:
    $0<z_{i}<m{\text{ mit }}z_{0}>0{\text{ und }}\forall i:0<i$
Bei der Multiplikation $z_{i+1}=a\cdot z_{i}$ wird die aktuelle Zahl $z_{i}$ also stets mit $a$ multipliziert, und durch die anschließende Modulo-Division durch $m$ ist die nächstfolgende Zahl $z_{i+1}$ stets kleiner als $m$. Durch diesen Umstand wird erreicht, dass bei wiederholter Ausführung der Berechnungen jede Zahl von 1 bis $m-1$ genau einmal erzeugt wird, bevor der Wert $z_{0}$ erneut erreicht wird. Danach wiederholt sich diese Sequenz zyklisch:
    $z_{n\cdot (m-1)}=z_{0}{\text{ mit }}n\in \mathbb {N}$:
Zur Veranschaulichung ist im Folgenden die sehr kurze Polynomfolge mit der Primzahl $m=37$ und dem Koeffizienten $a=2$ sowie dem Startwert $z_{0}=1$ angegeben, die aus einer Sequenz mit nur $m-1=36$ verschiedenen Zahlen besteht:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 |
| $z_{i}$ | 1 | 2 | 4 | 8 | 16 | 32 | 27 | 17 | 34 | 31 | 25 | 13 | 26 | 15 | 30 | 23 | 9 | 18 | 36 | 35 | 33 | 29 | 21 | 5 | 10 | 20 | 3 | 6 | 12 | 24 | 11 | 22 | 7 | 14 | 28 | 19 | 1 |
Im praktischen Fall mit einer erheblich größeren Länge der Sequenz können zum Beispiel die beiden Konstanten 2.147.483.647 und 15.015 eingesetzt werden:
$m=2^{31}-1=2.147.483.647$
$a=3\cdot 5\cdot 7\cdot 11\cdot 13=15.015$ mit $a\approx {\frac {\sqrt {m}}{3}}\approx 15.447$
In dieser Polynomfolge wird für die Primzahl $m$ die achte Mersenne-Primzahl $M_{31}$ zur Basis Zwei verwendet. Der Koeffizient des Polynoms $a$ wird hier als Produkt aus den fünf ersten ungeraden Primzahlen 3, 5, 7, 11 und 13 zusammengesetzt, die in ihrer Eigenschaften als Primzahlen untereinander und zu $m$ teilerfremd sind.
Zur Berechnung einer neuen Zahl sind lediglich eine ganzzahlige Multiplikation und eine ganzzahlige Modulo-Division erforderlich, so dass sich ein sehr geringer Rechenaufwand und somit - insbesondere bei Simulationen mit zahlreichen pseudozufälligen Entscheidungen - eine kurze Laufzeit des Programms ergibt. Bei der erforderlichen Multiplikation wird maximal die ganze Zahl $a\cdot m=32.244.466.959.705$ erreicht, die kleiner als $2^{45}$ ist, und deswegen mit 64-Bit-Computersystemen sehr effizient und schnell berechnet werden kann.
Wenn noch mehr verschiedene Pseudozufallszahlen innerhalb einer Sequenz erwünscht sind, können die beiden Konstanten vergrößert werden. Der ganzzahlige Datentyp mit Vorzeichen erlaubt in 64-Bit-Computersystemen in der Regel die Darstellung der größten ganzen Zahl $2^{63}-1=9.223.372.036.854.775.807$, also gut drei Trillionen. Wenn der Zahlenraum für positive ganze Zahlen besser ausgenutzt werden soll, um noch mehr verschiedene Pseudozufallszahlen in einer Sequenz zu erhalten, können alternativ beispielsweise die beiden Konstanten m' = 9.095.665.192.937 als eine sehr große Primzahl sowie a' = 969.969 als das zu m' teilerfremde Produkt kleiner Primzahlen verwendet werden, deren Produkt $a'\cdot m'=8.822.513.271.527.908.953<2^{63}$ mit einem Zahlenwert von knapp drei Trillionen immernoch kleiner als die größte in 64-Bit-Computersystemen effizient zu verarbeitende ganze Zahl ist:
    $m'=9.095.665.192.937\approx 2^{43}$
    $a'=3\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19=969.969<2^{20}$ mit $a'\approx {\frac {\sqrt {m'}}{3}}\approx 1.005.300$

#### Java-Programm

Die Java-Klasse PseudoRandom erzeugt pseudozufällige Zahlenfolgen, um die scheinbar zufällige Ausbreitung von Bäumen und Flammen simulieren zu können.
Mit dem Aufruf der Methode setStartValue (long startwert) kann ein beliebiger ganzzahliger Startwert $z_{0}>0$ gesetzt werden, von welchem ausgehend eine definierte Pseudozufallszahlenfolge generiert wird. Falls eine scheinbar zufällige Zahlenfolge gewünscht ist, kann der Startwert mit Hilfe der parameterlosen Methode setStartValueToSystemTime auf die aktuelle Systemzeit in Millisekunden gesetzt werden, die vom 1. Januar 1970 an gemessen wird.
Die Methode long nextInteger (long max) gibt eine ganze Zahl z mit der Eigenschaft $0<z<max$ zurück. Die ganzen Zahlen der Folge können mit Hilfe der kleinsten nicht auftretenden ganzen Zahl $m$ als Gleitkommazahl $g$ auf das Intervall zwischen Null und Eins normiert werden, so dass $0<g<1$ gilt:
$g={\frac {z}{m}}$
Eine solche reelle Zahl wird durch die Methode double nextProbability zurückgegeben.
Mit dem folgenden Java-Programm mit der Java-Klasse PseudoRandom können entsprechende Pseudozufallszahlen erzeugt werden:
→ Java-Programm "PseudoRandom"

### SimForestModel

Die Java-Klasse SimForestModel dient der Implementierung eines Modells für die Umsetzung einer Simulation von Waldbränden in einer rechteckigen Fläche.
Die Erdoberfläche in einem rechteckigen Waldgebiet aus $x$ mal $y$ Zellen kann aus vier verschiedenen Elementen zusammengesetzt werden:
* Unbewachsener Waldboden (SimForestModel.SOIL)
* Baum (SimForestModel.TREE)
* Wasser (SimForestModel.WATER)
* Brennender Baum (SimForestModel.FIRE)
Die entsprechenden öffentlichen Konstanten für diese Aufzählung sind in der Java-Klasse "SimForestModel" definiert:
Das Modell verwendet zwei zweidimensionale Datenfelder (Arrays), um aus einem bestehenden Waldgebiet, das in der Instanzvariablen SimForestModel.currentGround gespeichert ist, ein nächstes, simuliertes Waldgebiet zu berechnen, das in der Instanzvariable SimForestModel.nextGround zwischengespeichert wird. Jedes Waldelement enthält einen Zahlenwert des Datentyps "long", in dem die vier oben genannten und aufgezählten Werte gespeichert werden können. Mit dem Konstruktor SimForestModel (int x, int y) der Klasse werden die Breite x und die Höhe h des rechteckigen Waldgebiets festgelegt, und die beiden zweidimensionalen Datenfelder SimForestModel.currentGround und SimForestModel.nextGround werden erzeugt:
Für das hier implementierte Modell gelten die folgenden Regeln:
* Auf unbewachsenem Waldboden wächst mit der Wahrscheinlichkeit $p_{Baum}$ ein neuer Baum.
* Ein Baum entzündet sich mit der Wahrscheinlichkeit $p_{Blitz}={\frac {h_{Blitz}}{n_{Baum}}}$ durch einen Blitzschlag, weil auf dem Waldgebiet mit $n_{Baum}$ Bäumen in jedem Jahr $h_{Blitz}$ Blitze an zufälligen Orten einschlagen.
* Ein Baum fängt mit der Wahrscheinlichkeit $p_{Feuer}$ Feuer, wenn ein Nachbarbaum brennt.
* Nach dem Erlöschen ist in einer Zelle unbewachsener Waldboden vorhanden.
* Eine Wasserzelle kann nicht mit Bäumen bewachsen sein.
Ablauf einer Simulation mit einer ständig variierenden Anzahl von $n_{Baum}$ Bäumen :
* In der im Zeitraffer ablaufenden Simulation wird für jedes unbewachsene Feld Waldboden anhand der Wahrscheinlichkeit für den jährlichen Baumbewuchs $0\leq p_{Baum}\leq 1$, ob auf einem Stück unbewachsenen Waldboden im neuen Jahr ein neuer Baum wächst. Dieser Wert wird mit dem Methodenaufruf model.setTreeGrowthIndex (pBaum) festlegt.
* Anhand der jährlichen Häufigkeit $h_{Blitz}\geq 0$ wird für das gesamte Gebiet simuliert, dass auf zufälligen Punkten des Gebiets insgesamt $h_{Blitz}$ Gewitterblitze einschlagen. Dieser Wert wird mit dem Methodenaufruf model.setAnnualNumberOfLightnings (hBlitz) festgelegt.
* Wenn ein Blitz einen Baum trifft, dann fängt dieser Feuer (rot = SimForestModel.FIRE) und überträgt die Flammen anhand der Ausbreitungswahrscheinlichkeit $0\leq p_{Feuer}\leq 1$, auf benachbarten Bäume, die dann ebenfalls abbrennen. Dieser Wert wird mit dem Methodenaufruf model.setProbabilitySpreadOfForestFire (pFeuer) festgelegt. Abgebrannte Bäume hinterlassen unbewachsenen Waldboden.
* Die Wahrscheinlichkeit $0\leq p_{Loesch}\leq 1$ bestimmt, wie lange ein brennender Baum im Mittel noch in Flammen steht, nachdem er Feuer gefangen hat. Dieser Wert wird mit dem Methodenaufruf model.setFireExtinctionIndex (pLoesch) festgelegt. Erst nachdem alle Flammen eines Jahres erloschen sind und somit nicht mehr auf andere Bäume übertragen werden können, wird die jährliche Simulation für den neuen Baumbewuchs fortgesetzt (siehe oben, erster Punkt).
Der Baumwuchs in einem Jahr wird mit der Methode boolean simulateYear simuliert:
Die Bäume, die innerhalb eines Jahres auf unbewachsenem Waldboden (SOIL) neu wachsen, werden mit dem Methodenaufruf simulateTreeGrowth simuliert:
Das Wachstum eines Baumes (TREE) in einer bestimmten Zelle (x, y) des Waldgebiets wird mit dem Methodenaufruf newTree (int x, int y) simuliert:
Die Blitzschläge, die innerhalb eines Jahres erfolgen, werden mit dem Methodenaufruf boolean simulateLightnings simuliert:
Ein einzelner Blitzschlag wird mit dem Methodenaufruf boolean simulateLightning simuliert:
Die Simulation eines Waldbrands während eines Jahres erfolgt mit der Methode long simulateBurning:
Hierbei wird mit der Methode boolean fireNextToTree (int x, int y) für jeden Baum in einer bestimmten Zelle (x, y) des Waldgebiets untersucht, ob einer der benachbarten acht Bäume brennt und seine Flammen mit der Wahrscheinlichkeit probabilitySpreadOfForestFire auf den untersuchten Baum überträgt. Diese Wahrscheinlichkeit gilt unmittelbar für die direkt benachbarten vier Waldelemente (oben, rechts, unten und links). Für die um den Faktor ${\sqrt {2}}$ weiter entfernten diagonal benachbarten Waldelemente wird diese Wahrscheinlichkeit um diesen Faktor reduziert:
Mit dem folgenden Java-Programm mit der Java-Klasse SimForestModel können Modelle zur Simulation von Waldbränden erzeugt und verwaltet werden:
→ Java-Programm "SimForestModel"

### SimForestFrame

Die Java-Klasse SimForestFrame realisiert als Erweiterung der Java-Standardklasse javax.swing.JFrame (Basisklasse ist java.awt.Component, und der Name des Software-Pakets "awt" steht für "advanced windows toolkit", was ungefähr als "fortgeschrittener Fenster-Werkzeugsatz" übersetzt werden kann) eine stetig aktualisierte graphische Ausgabe von Inhalten der Klasse SimForestModel:
* java.awt.Component
** java.awt.Container
*** java.awt.Window
**** java.awt.Frame
***** javax.swing.JFrame
****** SimForestFrame
Für die graphische Ausgabe werden Instanzen der Java-Klassen java.awt.image.BufferedImage und java.awt.image.WritableRaster verwendet. Eine Instanz der Klasse SimForestFrame wird mit der überschriebenen parameterlosen Java-Standardmethode init initialisiert und mit der überschriebenen, öffentlichen und typengebundenen Java-Standardmethode paint ausgegeben. Die Methode paint benötigt dafür als Parameter eine Instanz der Java-Klasse java.awt.Graphics.
Zur Synchronisation der graphischen Ausgabe wird eine Instanz der Java-Standardklasse java.awt.event.ActionListener implementiert. Hierbei handelt es sich um ein Java-Interface, das Ereignisse der Klasse java.awt.event.ActionEvent empfängt: Ereignisse zur aktualisierten graphischen Ausgabe werden mit Hilfe einer Instanz der Java-Klasse javax.swing.Timer ausgelöst. Dieser Zeitgeber wird durch den Aufruf seines Konstruktors javax.swing.Timer (1, this) mit einem Verzögerungsparameter (hier eine Millisekunde) als ActionListener erstellt, und die Instanz der Klasse javax.swing.JFrame wird von diesem Zeitgeber durch den Aufruf seiner Methode addActionListener automatisch intern registriert. Der Verzögerungsparameter wird verwendet, um die Verzögerung der Ereignisse in Millisekunden festlegen zu können.
Der Konstruktor SimForestFrame (int x, int y, long count) zur Initialisierung der Ausgabe der Simulation ist folgendermaßen gestaltet, um ein Waldgebiet mit der Breite x und der Höhe y für count Jahre zu erzeugen:
Die Simulation wird mit dem Aufruf der Methode init gestartet. Bevor innerhalb der Methode init die graphische Ausgabe mit dem Aufruf der Methode paint zum ersten Mal erfolgt, wird der bereits registrierte javax.swing.Timer durch den Aufruf seiner Methode start gestartet:
Sobald der Zeitgeber mit der gebundenen Methode start aus der Klasse javax.swing.Timer in der Methode init der Klasse SimForestFrame gestartet wurde, wartet dieser jeweils, bevor ein Ereignis der Klasse java.awt.event.ActionEvent an den registrierten java.awt.event.ActionListener auslöst werden kann. Wenn das Ereignis ausgelöst wurde, wird die Methode actionPerformed (java.awt.event.ActionEvent event) des Objekts mit einem Parameter event der Klasse java.awt.event.ActionEvent aufgerufen, die schließlich wiederum die Java-Standardmethode java.awt.Component.repaint aufruft, die intern dann wiederum die Standard-Methode paint aufruft. Am Ende der Simulation wird der Zeitgeber durch den Aufruf der gebundenen Methode stop aus der Klasse javax.swing.Timer angehalten. Die aus der Basisklasse java.awt.event.ActionListener überschriebene Standardmethode actionPerformed (java.awt.event.ActionEvent event) für die synchronisierte Aktualisierung einer Instanz der Klasse SimForestFrame sieht folgendermaßen aus:
In der privaten Instanzvariable forestIsBurning wird der boolesche Wert "true" gespeichert, wenn es noch mindestens einen brennenden Baum im Waldgebiet gibt. Falls dies der Fall ist, wird das entsprechende Jahr so lange simuliert, bis kein Baum mehr brennt. Ansonsten wird mit der Laufvariable SimForestFrame.currentYear das aktuelle Jahr bis zur Anzahl der gewünschten zu simulierenden Jahre SimForestFrame.numberOfYears hochgezählt.
Mit dem Aufruf der Methode java.awt.Toolkit.getDefaultToolkit.sync am Ende der Standardmethode paint (java.awt.Graphics graphics) zur graphischen Darstellung der Instanz graphics wird sichergestellt, dass die graphische Anzeige vollständig aktualisiert ist, bevor durch den Zeitgeber ein neues Ereignis (java.awt.event.ActionEvent) ausgelöst wird:
Mit dem folgenden Java-Programm mit der Java-Klasse SimForestFrame kann die Bildschirmanzeige von Waldbrandsimulationen realisiert werden:
→ Java-Programm "SimForestFrame"

### Aufruf des Programms

Mit dem Aufruf der folgenden öffentlichen Hauptmethode main (java.lang.String arguments) kann eine 50-jährige Simulation mit 800 Waldbodenfeldern in der Breite und 600 Waldbodenfeldern in der Höhe berechnet und graphisch dargestellt werden. Der Aufruf des Konstruktors SimForestFrame (int x, int y, long count) erzeugt eine entsprechende Instanz frame der Klasse SimForestFrame, wobei dieser automatisch den Konstruktor SimForestModel (int x, int y) der Java-Klasse SimForestModel aufruft und somit eine Instanz model dieser Klasse erzeugt. Mit dem Unterprogramm init (SimForestModel model) kann die Instanz model von SimForestModel initialisiert werden.
Mit den beiden gebundenen Methoden getWidth und getHeight können die Abmessungen des simulierten rechteckigen Waldgebiets abgerufen werden. Von der Methode model.getGroundState (x, y) wird der Zustand des Waldbodenelements an der Stelle (x, y) zurückgegeben, und mit dem Aufruf der Methode model.setGroundState (x, y, status) wird der gewünschte ganzzahlige Zustand status des Waldbodenelements an der Stelle (x, y) gesetzt. Die vier gültigen Zustände sind in den Konstanten SOIL, TREE, WATER und FIRE der Klasse SimForestModel definiert.

## Nachwort

Die hier angegebenen strukturierten Programmbeispiele können ohne große Umstände in jede andere strukturierte Programmiersprache übertragen werden. Durch die Modifikation und Ergänzung der angegebenen Algorithmen können ohne große Umstände anders gestaltete Erdoberflächen berechnet werden.
Es wäre erfreulich, wenn dieses Wikibook zu einem besseren und tieferen Verständnis der strukturierten Programmierung und als Einstieg in die Technik der Programmierung von Simulationsrechnungen mit zellulären Automaten beitragen kann.
Die folgende Bildergalerie zeigt einige mit dem hier vorgestellten Algorithmus erzeugte Waldbrände:
* Wandbrandsimulationen

## Danksagung

Der Hauptautor dankt seinem ehemaligen Kollegen und Nutzer eines Gepard-Computers Dr.-Ing. Thomas Wittich, der ihm 1988 die Programmiersprache Modula-2 vorgestellt und nähergebracht hat. Dies hat dazu geführt, dass der Hauptautor auch den Nachfolger Oberon und das damit programmierte multitasking-fähige Betriebssystem Oberon System mit graphischer Oberfläche kennengelernt hat, mit welchem er Anfang der 1990er Jahre nicht nur seine Dissertation erstellt, sondern für das er auch die Simulation "ForestFire" als Demonstrationsprojekt für Hintergrundprozesse programmiert hatte.

## Literatur

* Lars Dingeldein: A Cellular Automata Based Forest-Fire Model, Universität Frankfurt, 2020
* Richard D. Zinck, Volker Grimm, Benjamin M. Bolker, Donald L. DeAngelis: Unifying Wildfire Models from Ecology and Statistical Physics, Helmholtz Centre for Environmental Research–UFZ, Department of Ecological Modelling, in: The American Naturalist, Volume 174, Number 5, University of Chicago, 2009
* Barbara Drossel, Franz Schwabl: "Self-organized critical forest-fire model". Physical Review Letters. American Physical Society (APS). 69 (11): 1629–1632, 1992
* Christopher L. Henley: Self-organized percolation: a simpler model, Bulletin of the American Physical Society, 34, 838, 1989

## Einzelnachweise

* ↑ Derrick Henry Lehmer, Mathematical Methods in Large-scale Computing Units, in: Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, 14. September 1949, Seiten 141 bis 146, Harvard University Press, Cambridge, Massachusetts, 1951
* ↑ Donald Ervin Knuth: 3.2.1. The Linear Congruential Method, in: The Art of Computer Programming, 3. Auflage, Volume 2, Seminumerical Algorithms, Addison-Wesley, 1997, ISBN 0-201-89684-2
* ↑ C.5 Specifications for integer and floating point datatypes and operations, in: ISO/IEC 10967-1 Information technology — Language independent arithmetic — Part 1: Integer and floating point arithmetic, second edition, 2012-07-15
* ↑ Chris K. Caldwell: 9095665192937, Prime Curios!, 2023, abgerufen am 11. November 2023

## Siehe auch

* Strukturierte Programmierung
* Rekursive Labyrinthe
* Das Apfelmännchen

## Zusammenfassung des Projekts

„Waldbrandsimulation“ ist nach Einschätzung seiner Autoren zu 100 % fertig
* Zielgruppe: Informatiker, Mathematiker
* Lernziele: Simulation von Waldbränden mit einem Java-Programm.
* Buchpatenschaft/Ansprechperson: Benutzer:Bautsch
* Sind Co-Autoren gegenwärtig erwünscht? Ja, sehr gerne. Korrekturen von offensichtlichen Fehlern direkt im Text; Inhaltliches bitte per Diskussion.
* Richtlinien für Co-Autoren: Wikimedia-like.