Fast ein Baum im Baum..

Wie versprochen möchte ich immer mal wieder auf interessante Aspekte in Konzeption und Coding der von mir implementierten Features eingehen. Dabei geht es mir nicht so sehr um eine flächendeckende Beschreibung – ich habe nicht vor, die Doku in den Blog zu verlagern ;) – sondern darum, einzelne, aus meiner Sicht schöne oder interessante Stellen zu erläutern. Beginnen möchte ich dabei mit einer Stelle in der Simulation der Umwelt, genauer mit der Auswertungsreihenfolge der Umweltfaktoren.

Die Menge der durch Photosynthese umgewandelte und damit der Pflanze zur Verfügung stehenden Energie hängt von einer Reihe von abiotischen Faktoren ab, die sich gegenseitig beeinflussen (siehe auch Wikipedia). In der realen Welt sind dies Kohlenstoffdioxid, Licht, Wasser und Temperatur. In einer fiktiven Welt können natürlich beliebige Umweltfaktoren wie Magie, Schall oder eine andere Art Licht hinzukommen. Diese Umweltfaktoren beeinflussen sich gegenseitig und beeinflussen die Effektivität der Photosynthese, ein paar Beispiele aus der realen Welt sind: Die Menge an aufnehmbaren Kohlenstoffdioxid kann gedrosselt werden durch die Wassermenge bzw. die Luftfeuchtigkeit, die Temperatur beeinflusst die Photosyntheserate. Wenn man beliebige Kombinationen von beliebig vielen verschiedenen Umweltfaktoren zulassen möchte, stellen sich vor allem zwei Probleme:
1. In welcher Reihenfolge können die Umweltfaktoren ausgewertet werden? Im obigen Beispiel sollte die Wassermenge berechnet werden, bevor die Kohlenstoffdioxidmenge berechnet wird, da dieses Ergebnis von der aufgenommenen Wassermenge abhängt.
2. Wie bildet man alle möglichen Beeinflussungsarten wie “beeinflusst die Photosyntheserate” oder “setzt eine obere Grenze” ab?

Wir beschäftigen uns zunächst (also in diesem Beitrag) mit der ersten Frage. Da theoretisch beliebige Kombinationen von a priori nicht bekannten Umweltfaktoren möglich sein sollen, kann dem Programm keine vorher festgelegte Reihenfolge vorgegeben werden. Wie soll eine solche Reihenfolge also festgelegt werden? Dazu zunächst ein wenig Graphentheorie [1], wirklich nur ein ganz wenig. Ein gerichteter Graph G = (V, E) besteht aus einer Menge von Knoten V und eine Menge von gerichteten Kanten E, wobei jede Kante definiert ist als ein geordnetes Paar von Knoten. Ein solcher gerichteter Graph ist kreisfrei, falls es keinen Weg gibt, der aus einem Knoten heraus und später wieder in ihn hinein führt. Wenn wir unsere Problemstellung nun übersetzen in die neu gelernten Begriffe, so ist jeder Umweltfaktor ein Knoten und immer, wenn ein Umweltfaktor einen anderen Umweltfaktor beeinflusst, zeichnen wir eine Kante vom Knoten des ersten Umweltfaktors zum Knoten des zweiten Umweltfaktors. Wenn in diesem Graph ein Kreis auftritt heißt das, dass sich die Umweltfaktoren ringförmig beeinflussen, also zum Beispiel wäre “Wassermenge beeinflusst Kohlenstoffdioxidmenge beeinflusst Magie beeinflusst Wassermenge” ein Kreis. Diesen Fall wollen wir ausschließen, da man sich in der Berechnung sonst ewig im Kreis drehen könnte. Wir haben nun also einen kreisfreien, gerichteten Graphen vorliegen. Ein solcher Graph ist topologisch sortiert, wenn man eine Reihenfolge der Knoten gefunden hat, in der für jede Kante der Endknoten weiter hinten in der Reihenfolge liegt als der Anfangsknoten. Wenn man eine solche topologische Sortierung der Umweltfaktoren hat und die Umweltfaktoren in dieser Reihenfolge auswertet, dann beeinflusst jeder Umweltfaktor nur Umweltfaktoren, die später ausgewertet werden -> perfekt :)

Ist man erst einmal zu dieser Erkenntnis gelangt, dann ist der Rest kein Hexenwerk mehr – ein Algorithmus zum topologischen Sortieren von Graphen ist schnell gefunden. Man startet mit einer leeren Liste bereits sortierter Knoten und sucht in jeder Iteration im Graphen nach Knoten ohne eingehende Kanten, nimmt diese ans Ende der Liste bereits sortierter Knoten auf und entfernt den Knoten und alle ausgehenden Kanten aus dem Graphen. Am Ende ist der Graph leer und die Knoten sind topologisch sortiert. In der so ermittelten Reihenfolge werden die Umweltfaktoren dann vom Programm ausgewertet. Das obige Beispiel hat als eine mögliche topologische Sortierung Wasser -> Temperatur -> Luftfeuchtigkeit ->Kohlenstoffdioxid -> Licht.

[1] Algorithmische Graphentheorie, Volker Turau, Oldenbourg Verlag, 3. Auflage, 2009

Cookie

Ich bin.. hmm, wie fange ich nun am Besten an? Mit dem Trivialen: Ich bin Cookie :) Und wie drücke ich nun am besten aus, wie ich mich in Science-O-Matics und in !∃2.0 einbringe? Vielleicht kurz zu mir: Ich habe Mathe mit einem Schwerpunkt in der reinen Mathematik studiert, nach meinem Abschluss dann ein Jährchen mal ein wenig Geld verdient in der ABAP Entwicklung, dann bin ich zurück zur Uni, habe mit einem kurzen Exkurs in die mathematische Optimierung mein Wirtschaftsmathe Diplom vollendet und mache gerade meinen Doktor in der quantitativen Forschung der Wirtschaftswissenschaften, also Optimierung auf Wirtschaftsseite, Modelle aufstellen, Algorithmen analysieren, anpassen oder entwickeln, implementieren.. Ist echt cool :D Also im Herzen Mathematikerin. Nein, Informatikerin.. Beides halt ^^ Für !∃2.0 mache ich vor allem Mathemagie und deren Umsetzung, aber auch viele andere Hintergrundmodelle. Sachen, die man in Spielen schon immer mal cool gefunden hätte.. "einfach" mal umgesetzt als eigenständiges Feature. So ist zum Beispiel die Generierung der Umwelt zum größten Teil aus meiner Feder. Hmm.. was schreibt man sonst noch in eine Vorstellung rein? Das Alter? - Vergesst es, nach dem Alter einer Dame fragt man nicht :P Hobbies? Tja, Computerspiele, wie man sich wohl denken kann ^^ Aber auch LARP, Gesellschaftsspiele und Trading Card Games, nähen und Sport würde ich dazu zählen.. Ehrlicherweise auch Shoppen, Schuhe und Klamotten ;) Ach, warum ich Cookie heiße? Das sollte schnell klar werden ohne dass ich es ausführe ;)
Posted in Code-O-Matic, Theory-O-Matic. Tagged with , , .

Hinterlasse eine Antwort

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

Du kannst folgende HTML-Tags benutzen: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>