Softwarepraktikum

Simulation und Visualisierung von Fischschwärmen

Intro und Aufgabestellung

Ziel des Praktikums war es, das Verhalten von Fischschwärmen möglichst realistisch zu simulieren. Die Fische sollten in der Lage sein, sich selbständig zu Schwärmen zu formieren und sie sollten mehrere Arten von Hindernissen erkennen und geschickt ausweichen können.

Beschreibung

Die Fische befinden sich in einem 3-dimensionalen nicht besonders großen Aquarium, doch ihr Vehalten wird nur von lokalen Parametern beeinflusst. Das heißt, jeder Fisch wird in seinem Verhalten nur von seinen Nachbarn und ihm im Weg liegenden Hindernissen beeinflusst. Dieses Modell erscheint realistisch, denn aufgrund der beschränkten Sichtweite usw. kann kein Fisch ein globales Wissen über das ganze Aquarium haben.

Die Fische halten sich am liebsten in einem Schwarm auf und es gibt einen optimalen Abstandsbereich zu den anderen Fischen, den sie einzuhalten versuchen. Wenn ein Fisch am Rand sich zu weit vom Schwarm entfernt, erfährt er eine Kraft zum Mittelpunkt des Schwarms hin. Wenn ein Fisch am Rand etwas den Anschluss verliert, kann es sein, dass er zu einem anderen, in der Nähe befindlichen Schwarm übergeht. Mehrere Schwärme können sich zu einem vereinigen und ein großer Schwarm kann sich in mehrere kleine Schwärme aufteilen (z.B.: beim Ausweichen eines Hindernisses). Wenn sich die Fische zu nahe kommen, erfahren sie eine abstoßende Kraft, die proportional zu 1/r^3 ist, wobei r für den Abstand zum anderen Fisch steht.

Beim Ausweichen von Hindernissen gibt es prinzipiell zwei Modelle. Am einfachsten ist es, ein Potentialfeld um jedes Hindernis zu errichten, so dass jeder Fisch, der in das Potentialfeld eindringt, eine abstoßende Kraft erfährt. Dieses Modell habe ich für die Aquariumswände benutzt, denn die Fische müssen den Wänden ja nicht ausweichen, sondern sich einfach nur davon fernhalten. Die Schwäche dieses Modells besteht darin, dass kein Fisch parallel zum Hindernis oder knapp daran vorbei schwimmen kann, ohne in seiner Bahn beeinflusst zu werden.

Das bessere Modell berücksichtigt die aktuelle Position und Schwimmrichtung des Fisches und greift nur dann ein, wenn es tatsächlich zu einer Kollision kommen würde. Dieses Modell ist etwas komplizierter, denn man muss etwas mehr mit Vektoren rechnen und man braucht außerdem auch noch für jede Art von Hindernis einen neuen Algorithmus, aber nur dieses Modell ermöglicht ein "intelligentes" Ausweichen von Hindernissen. Aus diesem Grund habe ich mich bei den anderen Hindernissen im Aquarium für dieses Modell entschieden. Ich habe zwei Arten von Hindernissen eingebaut: Zylinder und Kugel

Implementierung

Das Programm ist in C++  geschrieben und ich habe Wert auf Objektorientierung gelegt, um einen späteren Ausbau der Simulation so simpel wie möglich zu gestalten. Die Visualisierung wurde mit Hilfe von Open GL Bibliotheken realisiert.

Alle Objekte im Aquarium wurden von einer einzigen Oberklasse "TankObject" abgeleitet. Von dieser Klasse wurde eine Oberklasse "MovedTankObject" für bewegte Objekte abgeleitet. Die Ausweichalgorithmen der Simulation können mit allen konkreten Klassen, die von dieser Oberklasse abgeleitet wurden,  umgehen (z.B.: Fisch). Die konkreten Klassen besitzen Angaben über die relative Größe, Maximalgeschwindigkeit und Maximalbeschleunigung der Objekte, die sie darstellen sollen.

Das Programm ist keine Echtzeitsimulation, denn ich musste die Simulationsschritte sehr klein machen, um sicher zu gehen, dass sich die Fische nicht durchdringen und nicht durch die Wände schwimmen. Aus diesem Grund besteht das Programm aus zwei Teilen. Der erste Teil ist die Simulation und der zweite Teil ist die Visualisierung.

Die Simulation berechnet in sehr kleinen Zeitintervallen die neuen Positions- und Geschwindigkeitsvektoren der Fische. Nach jedem zehnten Zeitintervall werden diese Vektoren in einer Datei "position.txt" ausgegeben. Die relevanten Daten der Hindernisse werden ebenfalls in Dateien ausgegeben. Damit sich die Fische auf einer stetig differenzierbaren Bahn bewegen, verändern die einzelnen Methoden der Simulation immer nur den Beschleunigungsvektor. Mit Hilfe des Beschleunigungsvektors wird die neue Geschwindigkeit und die neue Position berechnet. Sowohl die Beschleunigung als auch die Geschwindigkeit haben einen Maximalwert, der aber für jede konkrete Klasse unterschiedlich sein kann.

Die Datei "position.txt" enthält auch Angaben über die Größe des Aquariums und Anzahl der Fische. Diese Angaben werden für die Visualisierung benötigt.

Für die Visualisierung werden die von der Simulation erzeugten Dateien eingelesen und in einer Instanz der Klasse "myanimation" gespeichert. Die Positions- und Geschwindigkeitsvektoren der Fische werden in einer Liste von frames verwaltet. Ein einzelnes frame enthält die Positionen und Geschwindigkeiten aller Fische zu einem bestimmten Zeitpunkt. Es stellt sozusagen ein einzelnes Bild in der Filmrolle dar. Die Klasse "myanimation" enthält unter Anderem auch ein Pointer auf die einzelnen frames der Liste und eine Methode "incframe", die diesen Pointer jeweils ein frame weiter setzt. Am Ende der Liste wird dieser Pointer wieder auf den Anfang gesetzt. Die Methode "mydisplay" ruft die Methode für die Darstellung der Fische mit den Werten des aktuellen frames auf. Sie ruft ebenfalls die Methoden für die Darstellung der Hindernisse auf. Die Fische werden als gestreckte Tetraeder dargestellt. Orientierung: siehe Kommentare im Quellcode.

Das eigentliche Herz der Open GL Visualisierung befindet sich in der Datei "aquarium.cc". Hier werden alle nötigen Parameter initialisiert, Kameraposition bestimmt und der Film zum Laufen gebracht. Die "glutTimerFunc" ruft die Funktion "myanimation::incframe" auf und anschließend ruft sie sich selber in 20ms wieder auf. Die "DisplayFunc" wird auf "myanimation::mydisplay" gesetzt. Das Programm bietet die Möglichkeit, die Größe der Fische zu verändern, während die Animation läuft (einfach Taste "f" drücken). Für Screenshots oder Ähnliches kann man die Animation mit der Taste "s" anhalten und auch wieder starten.

Für mehr Details siehe Kommentare im Quellcode.

Bemerkungen (für die, die mit dem Code experimentieren wollen)

Wenn die Hindernisse zu eng zusammenstehen, kann es vorkommen, dass die Fische durch ein Hinderniss durchschwimmen.

Das Programm besteht aus folgenden Dateien:

Download

Die Quellcodes befinden sich in einem .tar Archiv und ein makefile ist auch dabei. Das makefile kompiliert das Ganze (falls alle nötigen Bibs vorhanden sind) und erzeugt dabei die program files "sim" und "aquarium". Anschließend werden diese files in richtiger Reihenfolge aufgerufen (erst "sim" dann "aquarium").

Download: Fischsim.tar

Kontakt

Bei Fragen, Anregungen ... Roland Cerna