Embed Size (px)
Citation preview
Georg-Simon-Ohm-Hochschule Nürnberg
Fakultät Elektrotechnik Feinwerktechnik Informationstechnik
Studiengang Media Engineering
Bachelor-Arbeit von
Benjamin K u c k u k
Interaktive Simulation von Schwarmverhalten
SS 2013
Abgabedatum: 27.05.2013
Betreuer: Prof. Dr. Stefan Röttger
Schlagworte: Schwarmverhalten, Craig Reynolds, OpenSceneGraph, Binning
Inhaltsverzeichnis1 Einleitung....................................................................................................................4
2 Geschichte und Motivation für Simulationen von Schwarmverhalten........................5
3 Begriffserklärung........................................................................................................7
4 Kinematic- und Steering-Klassen...............................................................................8
5 Steering Behaviors...................................................................................................13
6 Steering Behaviors eines Boids...............................................................................16
6.1 Biologische Grundlage......................................................................................17
6.2 Cohesion...........................................................................................................17
6.3 Separation.........................................................................................................19
6.4 Alignment..........................................................................................................22
6.5 Kombination der Steering Behaviors................................................................24
6.5.1 Kombination nach Wichtigkeit....................................................................25
6.5.2 Kombination mit Gewichtung.....................................................................27
6.6 Berechnung der Orientierung............................................................................28
7 Nachbarschaften......................................................................................................30
7.1 Anzahl und Parameter der Nachbarschaften....................................................31
7.2 Ermitteln der Nachbarschaften.........................................................................35
7.2.1 Brute Force Methode.................................................................................35
7.2.2 Binning Methode........................................................................................38
7.2.3 Vergleich der Laufzeitabhängigkeiten.......................................................41
8 Implementierung der Simulation...............................................................................51
8.1 Verwendete Software........................................................................................51
8.2 Ablauf der Implementierung..............................................................................53
8.3 Funktionalitäten der Simulation.........................................................................56
9 Zusammenfassung...................................................................................................60
10 Ausblick..................................................................................................................62
Literaturverzeichnis....................................................................................................65
3 von 65
1 Einleitung
Die vorliegende Arbeit wird sich mit der Erstellung einer Simulation von Schwarmver-
halten befassen. Dafür werden zuerst die theoretischen Grundlagen erläutert wer-
den, die größtenteils auf den Arbeiten von Craig Reynolds basieren. Diese beinhal-
ten das Prinzip der Steering Behaviors und die drei Steering Behaviors eines Boids:
Cohesion, Alignment und Separation.
Des Weiteren beinhalten die theoretischen Grundlagen das Prinzip der Nachbar-
schaften, die von den Steering Behaviors benötigt werden. Die Suche nach Nach-
barn wird sich als algorithmische Herausforderung erweisen, weswegen auf sie ge-
sondert eingegangen werden wird. Dazu wird eine effizientere Berechnungsmethode
präsentiert und auf ihre Laufzeitabhängigkeit hin untersucht werden. Über den ge-
samten Abschnitt der theoretischen Grundlagen werden Parameterwerte vorgestellt
werden, die von den von Craig Reynolds vorgeschlagenen Werten abweichen. Es
wird untersucht werden, ob diese Variationen eine Alternative bieten und ein ähnlich
gutes Ergebnis liefern können.
Im Anschluss wird auf die implementierte Simulation eingegangen werden. Dabei
wird der Schwerpunkt auf denjenigen Funktionalitäten liegen, die eine Interaktion mit
den Programm ermöglichen. Zusätzlich wird die verwendete Bibliothek
OpenSceneGraph präsentiert werden, zusammen mit dem groben Ablauf der Erstel-
lung der Simulation.
4 von 65
2 Geschichte und Motivation für Simulationen von
Schwarmverhalten
1987 veröffentlichte Craig Reynolds seiner Abhandlung Flocks, Herds, and Schools:
A Distributed Behavioral Model[1]. Er beschrieb darin die Grundlagen eines Algorith-
mus, mit dessen Hilfe man natürlich aussehende Bewegungen von Herden und
Schwarm bildenden Tieren simulieren kann. Er nannte das Programm, für das er die-
sen Algorithmus entwickelt hatte, genauso wie die Individuen eines simulierten
Schwarms: Boids.
Die Entwicklung dieses Programms wurde von der Filmindustrie angestoßen. 1992
kam Tim Burton's Batman Returns in die Kinos der USA. Batman kämpft in diesem
Film gegen den Bösewicht Penguin, der mit einer Armee aus bewaffneten Pinguinen
die Kontrolle über Gotham City übernehmen möchte (s. Abbildung 11). Die Filmema-
cher mussten folglich für zwei Tierarten Schwärme simulieren, nämlich Pinguine und
Fledermäuse. Batman Returns war der erste Film, in dem der Algorithmus von Craig
Reynolds verwendet wurde[2].
1 Quelle Abbildung 1: http://90srocks.blogspot.de/2011/06/its-human-nature-to-fear-unusual.html
5 von 65
Abbildung 1: Die Armee aus bewaffneten Pinguinen aus dem Film Batman Returns
Die bis dahin übliche und auch heute noch verwendete Vorgehensweise ist, die Be-
wegung von jedem einzelnen Tier zu animieren. Da dies eine sehr mühselige und
zeitaufwändige Arbeit ist, waren sowohl die Animatoren als auch die Produzenten
froh, eine einfachere, schnellere und damit auch kostengünstigere Alternative gefun-
den zu haben. Die Filmemacher mussten sich dann lediglich um die allgemeinen Be-
wegungsabläufe der Schwärme kümmern, wie z.B. „die Fledermäuse kommen aus
der Höhle, fliegen dreimal um Batman herum und attackieren seinen Gegner.“ Um
die Details der Bewegungen kümmerte sich danach der Algorithmus.
Seltsamerweise wurde dieser Algorithmus seit seiner Entwicklung vor über 25 Jahren
nicht großartig verändert. Zudem wurden keine nennenswerten Alternativen entwi-
ckelt, die vergleichbare oder sogar bessere Ergebnisse liefern als die Arbeit von
Craig Reynolds. Es wurden lediglich ein paar Variationen vorgeschlagen, von denen
einige in dieser Arbeit vorgestellt werden. Der Algorithmus von Craig Reynolds ist da-
mit seit jeher der Standard, wenn es um die Simulation von Schwarm- und Herden-
bewegungen geht.
6 von 65
3 Begriffserklärung
Für die folgenden Abschnitte wird neben dem Begriff „Schwarmbewegung“ zusätzlich
auch „Schwarmverhalten“ verwendet. Dieser wird streng genommen nicht korrekt
eingesetzt, da es in dieser Arbeit nicht um das Verhalten von Schwarmtieren geht
(Jagd, Fortpflanzung, etc.), sonder ausschließlich um deren Bewegungen. Jedoch
kann man durch die Bewegung eines Schwarms Informationen über seinen „Gemüts-
zustand“ erhalten. Man würde z.B. von einem nervösen, aggressiven oder gelasse-
nen Verhalten sprechen. Deswegen werden die Begriffe „Schwarmverhalten“ und
„Schwarmbewegung“ mit identischer Bedeutung verwendet, obwohl es aus rein bio-
logischer Sicht falsch ist.
Zudem wird in den folgenden Abschnitten meistens nur von Schwarmverhalten ge-
sprochen, nicht aber von Herdenverhalten. Der Grund dafür ist, dass das Herdenver-
halten lediglich eine zweidimensionale Variante des dreidimensionalen Schwarmver-
haltens ist. Aus der Sicht des Algorithmus gibt es folglich keinen Unterschied zwi-
schen Schwärmen und Herden. Um allerdings die Lesbarkeit dieses Textes zu erhö-
hen, und da das Programm zu dieser Arbeit drei Dimensionen verwendet, wird aus-
schließlich der Begriff „Schwarmverhalten“ benutzt.
Des Weiteren tauchen in dieser Arbeit mehrere englische Begriffe und englischer
Pseudo-Code auf. Diese wurden größtenteils eins zu eins aus der Fachliteratur über-
nommen. Ein Grund dafür ist, dass es keine wirklich treffenden Übersetzungen für
die meisten Begriffe gibt. Ein anderer ist, dass sich ein Leser, der an einer Weiterbil-
dung interessiert ist, so schneller in der Fachliteratur zurechtfinden wird.
In dem nächsten Abschnitt werden einige physikalische Gleichungen als Grundlage
verwendet. Die machen jedoch nur bedingt Sinn, da es in der „digitalen Welt“ keine
Einheiten wie Meter oder Kilogramm gibt. Um dieses Problem zu umgehen, wird in
der gesamten Arbeit von Boid-Längen und Boid-Massen gesprochen. Logischerwei-
se besitzt ein Boid die Länge von einer Boid-Länge und die Masse von einer Boid-
Masse.
7 von 65
4 Kinematic- und Steering-Klassen
Bevor man den Algorithmus von Craig Reynolds verstehen kann, benötigt man zu-
erst drei theoretische Grundlagen. Zwei dieser Grundlagen werden in diesem Ab-
schnitt vorgestellt, nämlich die Kinematic- und die Steering-Klasse. Dabei soll mit al-
ler Wichtigkeit gesagt werden, dass diese Klassen nur zur besseren Verdeutlichung
der Steering Behaviors benötigt werden, die im nächsten Abschnitt präsentiert wer-
den. Auch die in den Klassen enthaltenen Variablen, deren Datentypen und die Me-
thoden unterliegen ausschließlich diesem einen Zweck. Wie genau die Implementie-
rung der Steering Behaviors und der dazugehörigen Funktionalitäten aussieht, soll
und kann in dieser Arbeit nicht vorgeschrieben werden.
Die Steering Behaviors wurden allgemein für sich bewegende Einheiten entwickelt.
Eine Einheit kann dabei ein Boid, ein Fisch, ein Auto, ein UFO oder anderes sein.
Unabhängig von der visuellen Darstellung lässt sich eine Einheit durch ihre Position
und ihre Blickrichtung beschreiben. Ihre Bewegung hingegen wird von ihrer Ge-
schwindigkeit und ihrer Rotation repräsentiert. Alle vier Parameter lassen sich in ei-
ner Kinematic-Klasse zusammenfassen, wobei man zwischen zwei- und dreidimen-
sionalen Anwendungen unterscheiden muss. Die zweidimensionale Variante der
Kinematic-Klasse sieht wie folgt aus ([4], S. 46):
class Kinematic: # 2D
Vector2D position
Vector2D velocity
float orientation
float rotation
end class
Die Position und die Geschwindigkeit sind einfache zweidimensionale Vektoren.
orientation ist eine reelle Zahl zwischen −π und π und beschreibt die Abwei-
chung von der frei wählbaren „Null-Orientierung“. rotation ist die Winkelgeschwin-
8 von 65
1
2
3
4
5
6
digkeit und damit eine beliebige reelle Zahl. In Anlehnung an [4], S. 178ff sieht die
dreidimensionale Variante wie folgt aus:
class Kinematic: # 3D
Vector3D position
Vector3D velocity
Quaternion orientation
Vector3D rotation
end class
position und velocity wurden einfach um eine Dimension erweitert. rotation
hingegen wurde in einen Rotationsvektor und orientation in eine Quaternion um-
gewandelt. Statt einer Quaternion kann man genauso gut eine 3x3-Matrix oder drei
Euler'sche Winkel wählen. Allerdings haben Quaternionen den Vorteil, dass sie Ma-
trix Drift vermeiden und ein einfacheres Interpolieren zwischen zwei Orientierungen
erlauben[5]. Auch in der Simulation zu dieser Arbeit wurden Quaternionen verwen-
det.
Wenn man nun eine Einheit bewegen möchte, sollte man ausschließlich der Ge-
schwindigkeit und der Rotation direkt Werte zuweisen. Die Position und die Orientie-
rung hingegen sollte man anhand der beiden anderen Variablen aktualisieren. Der
Grund dafür ist, dass Einheiten in den meisten Fällen eine nachvollziehbare und im
weitesten Sinne real wirkende Bewegung haben sollen, weswegen sich die Position
und die Orientierung nicht plötzlich verändern sollte. Die Kinematic-Klasse könnte für
diese Aktualisierung eine update()-Methode bekommen, die z.B. in jedem Frame
aufgerufen wird:
9 von 65
1
2
3
4
5
6
class Kinematic: # 2D
... # Member data as before
function update(elapsedTime):
position += velocity * elapsedTime
orientation += rotation * elapsedTime
end function
end class
Dabei ist elapsedTime die seit dem letzten update()-Aufruf verstrichene Zeit. Für
den dreidimensionalen Fall lässt sich die Position genauso aktualisieren. Lediglich
die Orientierung muss entsprechend des gewählten Datentyps anders aktualisiert
werden.
Craig Reynolds setzte an dieser update()-Methode an und erweiterte das in ihr
enthaltene Konzept. Die Geschwindigkeit und die Rotation werden nun ebenfalls
nicht mehr direkt verändert, sondern mit einer linearen Beschleunigung und einer
Winkelbeschleunigungen aktualisiert. Diese lassen sich ähnlich wie bei der Kinematic-
Klasse in einer Steering-Klasse zusammenfassen ([4], S. 46), was für den zweidi-
mensionalen Fall
class Steering: # 2D
Vector2D linear
float angular
end class
und für den dreidimensionalen Fall
class Steering: # 3D
Vector3D linear
Vector3D angular
end class
ergibt. linear und angular haben jeweils denselben Datentyp wie velocity und
10 von 65
1
2
3
4
5
6
7
8
1
2
3
4
1
2
3
4
rotation, da sie im physikalischen Zusammenhang Ableitungen von diesen Para-
metern sind.
Die update()-Methode der Kinematic-Klasse sieht dann wie folgt aus ([4], S. 47):
class Kinematic: # 2D
... # Member data as before
function update(steering, elapsedTime):
position += velocity * elapsedTime +
0.5 * steering.linear * elapsedTime^2
orientation += rotation * elapsedTime +
0.5 * steering.angular * elapsedTime^2
velocity += steering.linear * elapsedTime
rotation += steering.angular * elapsedTime
end function
end class
Diese Gleichungen sind bekannt aus dem Physik-Unterricht, werden in der Praxis al-
lerdings kaum verwendet ([4], S. 47). Das kann anhand der Simulation zu dieser Ar-
beit beispielhaft begründet werden. Die Geschwindigkeit und die linearen Beschleu-
nigung haben dort in etwa den gleichen Wert. Bei einer typischen Bildfrequenz von
60 Hz beträgt elapsedTime 1/60 s. Dadurch ist der zweite Summand in Zeile 6
120-mal kleiner als der erste Summand in Zeile 5 und trägt somit nur einen kleinen
Teil zur Positions-Aktualisierung bei. Analog dazu verhält es sich mit der Aktualisie-
rung der Orientierung. Wenn man also jeweils den zweiten Summanden weg lässt,
spart man sich einige Berechnungen ohne dabei allzu viel Genauigkeit zu verlieren.
Es bleibt also
...
position += velocity * elapsedTime
orientation += rotation * elapsedTime
...
11 von 65
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
3
4
übrig, wobei sich die restlichen Zeilen nicht verändern. Für den dreidimensionalen
Fall gilt, das sich fast alle Parameter genauso aktualisieren lassen. Die einzige Aus-
nahme bildet wieder die Aktualisierung der Orientierung.
Mit der Einführung der Steering-Klasse hat sich die Anzahl der Berechnungen in der
update()-Methode verdoppelt. Das kann im Endeffekt große Auswirkungen auf die
Laufzeit des Programms haben, da die update()-Methode für jede Einheit sehr
häufig aufgerufen werden muss. Andernfalls würde sie keine flüssige Bewegung be-
schreiben. Der Grund, diese Verdopplung an Berechnungen einzugehen, ist die we-
sentlich natürlicher und realistischer aussehenden Bewegung, die diese Methode mit
sich bringt. Dies ist leicht nachzuvollziehen, da in der Realität ausschließlich Kräfte
wirken und nicht plötzlich Werte für Geschwindigkeiten und Rotationen „auftauchen“.
Jedoch beinhaltet die Steering-Klasse keine Kräfte, sondern nur Beschleunigungen.
Den Zusammenhang zwischen diesen beiden physikalischen Größen beschreibt die
Gleichung F=a⋅m , wobei a die Beschleunigung, F die Kraft und m die Masse
der Einheit ist, auf die die Kraft F einwirkt. Für die Implementierung der zu dieser
Arbeit gehörenden Simulation musste die Masse deswegen nicht weiter beachtet
werden, da ein Boid die Masse von einer Boid-Masse hat und somit F=a gilt. Für
eine evtl. Weiterentwicklung der Simulation wäre es jedoch interessant, wenn die
Boids unterschiedliche Massen und somit die Beschleunigungen unterschiedliche
Beträge hätten. Die schwereren Boids würden dann träger reagieren als die leich-
teren Boids, was womöglich interessante Auswirkungen auf das Schwarmverhalten
hätte.
12 von 65
5 Steering Behaviors
Aus dem letzten Abschnitt wurde ersichtlich, wie Position, Orientierung, Geschwin-
digkeit und Rotation anhand eines Steering-Objektes aktualisiert werden. Die Be-
rechnung solcher Steering-Objekte übernehmen die Steering Behaviors. Diese sind
eine Gruppe von Algorithmen, die ebenfalls von Craig Reynolds entwickelt wur-
den[3]. In dieser Arbeit werden sie als Grundlage für das Verständnis des Algorith-
mus für Schwarmverhalten behandelt. Allerdings werden sie auch unabhängig von
diesem rege in der Videospiele-Industrie verwendet.
Ein Steering Behavior wird stets durch eine Aufgabe beschrieben, die das Behavior
zum Ziel hat. Beispiele sind Verfolgen, Fliehen oder Ausweichen. Dies ist eine se-
mantische Beschreibung, die einen Eindruck über das resultierende Bewegungsver-
halten gibt. Daneben gibt es noch eine algorithmische Beschreibung, die definiert,
wie die resultierenden Beschleunigungen berechnet werden.
Als detailliertes Beispiel wird das Seek Behavior betrachtet. Es lässt eine Einheit eine
bestimmte Position anstreben, wie z.B. die Position einer anderen Einheit (semanti-
sche Beschreibung). Die resultierende lineare Beschleunigung ist maximal und eine
Winkelbeschleunigung wird nicht berechnet (algorithmische Beschreibung). Der
Pseudo-Code für das Seek Behavior sieht wie folgt aus ([4], S. 57f):
13 von 65
class Seek:
characterPosition
targetPosition
maxLinearAcceleration
function calculateSteering():
steering = new Steering()
steering.linear = characterPosition – targetPosition
steering.linear.normalize()
steering.linear *= maxLinearAcceleration
steering.angular = 0
return steering
end function
end class
Man sieht, dass die Berechnungen eines Steering Behaviors nicht sehr kompliziert
sein müssen. Und obwohl hier ein recht einfaches Beispiel gewählt wurde, sind die
anderen Steering Behaviors nicht sehr viel schwieriger zu verstehen. Eine komplette
Erklärung aller entwickelten Steering Behaviors findet man in [4], S. 55ff, welche
auch als Grundlage für die Implementierung der zu dieser Arbeit gehörenden Simula-
tion verwendet wurde.
Der Reiz der Steering Behaviors befindet sich in der einfachen Kombinierbarkeit. Als
Beispiel wird die Bewegung eines Flugzeug in einem Videospiel betrachtet. Diese
lässt sich mit mehreren Steering Behaviors beeinflussen, wie z.B. Wind, Gravitation,
die Steuerung durch einen Spieler und das automatische Ausweichen anderer Flug-
zeuge. Jedes der verwendeten Steering Behaviors berechnet für das Flugzeug je-
weils ein Steering-Objekt. Die darin enthaltenen Beschleunigungen können anschlie-
ßend zusammenaddiert und die Kinematic-Variablen des Flugzeugs anhand der
Summe aktualisiert werden. Es gibt noch weitere Methoden, die Steering Behaviors
14 von 65
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
miteinander zu kombinieren, von denen zwei gängige im Abschnitt 6.5 Kombination
der Steering Behaviors erklärt werden.
In den meisten Fällen möchte der Programmierer die Beschleunigungen in einem
Steering-Objekt nach oben hin beschränken. Es würde sich anbieten, diese Be-
schränkung nicht auf alle Steering-Objekte anzuwenden, sondern nur auf das Ergeb-
nis der Kombination. Auf diese Weise könnte man sich mehrere Berechnung erspa-
ren. Jedoch benötigen einige Steering Behaviors die Schranken bereits beim Berech-
nen der Beschleunigungen. Ein Beispiel ist wieder das Seek Behavior, dass eine li-
neare Beschleunigung mit maximalem Betrag zurückgeben soll. Des Weiteren gibt
es einige Steering Behaviors, deren berechneten Beschleunigungen von Natur aus
einen sehr großen Betrag haben. Bei der Kombination mit anderen Behaviors wür-
den sie deswegen ohne vorherige Beschränkung einen zu großen Einfluss ausüben.
Neben mehr Arbeit, die die Schranken mit sich bringen, bekommt der Programmierer
allerdings auch größeren Einfluss auf das Bewegungsverhalten. Beispielsweise wirkt
eine Einheit bei einem Richtungswechsel träger, wenn eine kleinere Schranke für die
lineare Beschleunigung gewählt wurde. Ein anderes Beispiel ist eine niedrige
Schranke für die Winkelbeschleunigung, durch die der Spieler eines Videospiels kei -
ne schnellen Orientierungs-Wechsel mehr durchführen kann und so eine zusätzliche
Herausforderung gestellt bekommt. Zusätzlich lassen sich noch Schranken für die
Geschwindigkeit und die Rotation einer Einheit aufstellen, deren Einfluss vergleich-
bar mit der Beschränkung der Beschleunigungen ist.
15 von 65
6 Steering Behaviors eines Boids
Craig Reynolds entwickelte für seinen Algorithmus für Schwarmverhalten drei spezi-
elle Steering Behaviors. Dabei handelt es sich teilweise um einfache Ableitungen be-
reits existierender Steering Behaviors. Sie lauten Cohesion, Separation und Align-
ment ([4], S. 98f) und sind nicht wesentlich komplizierter als andere Steering Behav-
iors. Abbildung 2 zeigt die drei Steering Behaviors zusammen mit dem allgemeinen
Ablauf des Algorithmus.
Zunächst wird für jedes Boid eine oder mehrere Nachbarschaften berechnet, d.h. die
jeweiligen Nachbar-Boids (s. Abschnitt 7 Nachbarschaften). Anhand dieser Nachbar-
schaften berechnen die drei speziellen Steering Behaviors jeweils ein Steering-
16 von 65
Abbildung 2: Der Ablauf des Algorithmus für Schwarmverhalten
Objekt, die anschließend miteinander kombiniert werden. Mit diesem kombinierten
Steering-Objekt werden anschließend die Kinematic-Variablen des Boids aktualisiert.
Besonders hervorzuheben ist dabei die Tatsache, dass es aus der Sicht des Algorith-
mus eigentlich gar keinen Schwarm gibt. Die Beschleunigungen werden für jedes
Boid einzeln berechnet, wobei ausschließlich die naheliegenden Boids aus der Nach-
barschaft berücksichtigt werden. Und dennoch entsteht am Ende ein Boid-Schwarm,
deren Verhalten man durch die verschiedenen Parameter der Steering Behaviors be-
einflussen kann.
Bevor auf die einzelnen Bausteine des Algorithmus eingegangen wird, muss noch
kurz auf das „biologische Original“ zurückgegriffen werden. Dadurch lässt sich die
Entwicklung der speziellen Schwarm bildenden Steering Behaviors anschließend
besser nachvollziehen.
6.1 Biologische Grundlage
Die Bewegungen in einem Schwarm lassen sich durch zwei einfach Motivationen
wiedergeben[1]:
1) Bleibe im Schwarm
2) Kollidiere nicht mit anderen
Hinzu kommt wenn nötig „Punkt 0)“, nach dem sich ein Tier einem Schwarm an-
schließen soll, wenn es dies bisher noch nicht getan hat. Diese einfachen Regeln rei-
chen aus, die nun folgenden Steering Behaviors zu begründen.
6.2 Cohesion
Die Aufgabe, die Cohesion im Wesentlichen übernimmt, ist das Folgen von anderen
Boids. Dementsprechend ist es eine Ableitung des bereits vorgestelltem Seek Be-
17 von 65
haviors. Durch das Cohesion Behavior schließt sich ein Boid einem Schwarm an und
bleibt in diesem. Abbildung 3 illustriert seine Funktionsweise:
Es berechnet zunächst die durchschnittliche Position aller Boids (orange), die sich in
der Nachbarschaft (grau) eines Boids befinden. Anschließend wird diese Position an-
gestrebt, indem vom Seek Behavior eine maximale lineare Beschleunigung in diese
Richtung berechnet wird (grün) ([8], S. 309). Als Pseudo-Code sieht das wie folgt
aus:
class Cohesion extends Seek:
... # Member data from Seek
neighborhood # Contains all neighbor boids
function calculateSteering():
targetPosition = neighborhood.getMeanPosition()
return Seek.calculateSteering()
end function
end class
Alternativ kann man auch die durchschnittliche Position aller Boids verwenden. Aller-
dings würde es dadurch ziemlich schwierig werden, ein „schönes“ Schwarmverhalten
18 von 65
Abbildung 3: Die Funktionsweise des Cohesion Behaviors
1
2
3
4
5
6
7
8
9
zu simulieren. Zusätzlich kann man das Cohesion Behavior anstatt vom Seek Behav-
ior vom Arrive Behavior ableiten ([4], S. 99). Dieses gibt nicht wie das Seek Behavior
immer eine maximale lineare Beschleunigung in die Richtung des Ziels zurück, wo-
durch die Einheit immer wieder über das Ziel hinausschießt, wieder zurück kommt,
darüber hinausschießt, usw. Stattdessen sorgt es dafür, dass die Einheit auf der Ziel-
Position stehen bleibt. Auf diese Weise kann das Arrive Behavior einige Probleme
beseitigen, die bei bestimmten Nachbarschafts-Einstellungen mit dem Seek Behavior
auftreten (s. Abschnitt 7.1 Anzahl und Parameter der Nachbarschaften).
6.3 Separation
Separation sorgt dafür, dass ein Boid nicht mit einem anderen Boid kollidiert. Es gibt
mehrere Versionen, dieses Verhalten zu implementieren. Beispielsweise kann man
wie beim Cohesion Behavior die durchschnittliche Position aller Nachbarn berech-
nen, um vor dieser dann zu fliehen2. Dafür würde das Flee Behavior nahe liegen, das
genauso funktioniert wie das Seek Behavior. Der einzige Unterschied ist, dass die li-
neare Beschleunigung in die genau entgegengesetzte Richtung zeigt.
[4], S. 82 schlägt hingegen vor, für jedes Boid in der Nachbarschaft eine lineare Be-
schleunigung zu berechnen, die von dem jeweiligen Boid fort weist (s. Abbildung 4a
auf S. 21). Diese Beschleunigungen werden zusammenaddiert und die Summe wenn
nötig auf maxLinearAcceleration beschränkt. Als Peudo-Code sieht das wie
folgt aus ([4], S. 82f):
2 Quelle: Quellcodes verschiedener Schwarm-Simulationen, die während der Recherche zu dieser Arbeit gefunden wurden
19 von 65
class Separation:
characterPosition
neighbors
threshold
maxLinearAcceleration
function calculateSteering():
steering = new Steering()
steering.linear = 0
for each neighbor in neighbors:
direction = neighbor.position – characterPosition
distance = direction.length()
if distance < threshold:
strength = getStrengthFromDistance(distance)
direction.normalize()
steering.linear += strength * direction
end if
end for
steering.linear.clampLengthTo(maxLinearAcceleration)
steering.angular = 0
return steering
end function
end class
threshold beschreibt hier eine Distanz-Grenze, die üblicherweise kleiner oder
gleichgroß ist wie der normale Nachbarschafts-Radius. clampLengthTo() be-
schränkt den Betrag der linearen Beschleunigung auf maxLinearAccleration,
wenn er diesen Wert überschreitet. Die zu der Separation-Klasse gehörenden Me-
thode getStrengthFromDistance() berechnet die Stärke bzw. den Betrag der li-
20 von 65
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
nearen Beschleunigung, abhängig von der Distanz zu dem jeweiligen Nachbar-Boid.
Dies könnte z.B. linear geschehen ([4], S. 82):
function getStrengthFromDistance(distance): # Linear
strength = maxLinearAcceleration *
(threshold – distance) / threshold
return strength
end function
Angelehnt an ein logisches, natürliches Verhalten würde allerdings die Angst vor ei-
ner Kollision mit immer kleiner werdender Distanz immer schneller größer werden,
und damit auch die ausweichende Beschleunigung. Diese Verhalten wäre dann kei-
ne lineare, sondern eine invers-quadratische Abhängigkeit ([4], S. 82). Der Unter-
schied wird durch Abbildung 4 verdeutlicht:
In den beiden Abbildungen a) und b) werden nur die beiden Nachbar-Boids (dunkel-
blau, lila) berücksichtigt, deren jeweiliger Abstand zum Boid unterhalb von
threshold liegt (dunkelgrau). Durch das Einsetzen der invers-quadratischen Me-
thode sieht man, dass das nähere Nachbar-Boid ein wesentlich größeren Einfluss
ausübt als das andere Nachbar-Boid, dessen Einfluss sich sogar verringert hat. Hin-
zu kommt, dass die Beschleunigung stärker als bei der linearen Methode ist, was al-
21 von 65
Abbildung 4: Zwei verschiedene Methoden zur Berechnung des Separation Steering-Objektes
a) Lineare Abhängigkeit b) Invers-quadratische Abhängigkeit
1
2
3
4
5
lerdings von den gewählten Parameter abhängt. In Pseudo-Code sieht die invers-
quadratische Berechnungs-Methode wie folgt aus ([4], S. 82):
function getStrengthFromDistance(distance): # Inverse square
strength = min(decayCoefficient / distance^2,
maxLinearAcceleration)
return strength
end function
decayCoefficient ist eine beliebige positive Konstante, die beschreibt, wie
schnell der Betrag der Beschleunigung mit zunehmender Distanz abnimmt. Das be-
deutet, dass für einen kleinen decayCoefficient das Separation Behavior eine
recht „schwache“ Wirkung hat. Die Distanz zwischen den Boids befindet sich meis-
tens unterhalb von threshold. Für einen großen decayCoefficient hingegen
wird threshold nicht unterschritten. Allerdings hat dieses strenge Einhalten der
Grenze ein recht starr wirkendes Verhalten als Nachteil, welches bei echten Schwär-
men nicht beobachtet werden kann. Für die Simulation zu dieser Arbeit wurde
decayCoefficient auf 30 eingestellt. Die daraus resultierende ausweichende Re-
aktion der Boids wirkt dynamisch und nicht starr, und threshold wird meistens ein-
gehalten. Natürlich ist der „optimale“ Wert des decayCoefficient von threshold
und maxLinearAcceleration abhängig, die in der Simulation Werte von 8 Boid-
Längen und 15 Boid-Längen pro s² haben.
6.4 Alignment
Das Cohesion und Separation Behavior haben bereits alle Punkt der biologischen
Grundlagen abgedeckt. Jedoch ergeben diese beiden Steering Behaviors noch kein
natürlich aussehendes Schwarmverhalten, sondern ein eher unkoordiniert wirkender
„Boid-Pulk“, der sich mit etwas Glück in eine Richtung bewegt. Was noch fehlt, ist
eine Art Grundeinstellung der Boids, nämlich in die gleiche Richtung zu fliegen wie
die Nachbarn.
22 von 65
1
2
3
4
5
Diese Aufgabe übernimmt das Alignment Behavior. Von Craig Reynolds selbst gibt
es dafür zwei Varianten. Nach [2] und [3] soll ein Boid die durchschnittlichen Orien-
tierung seiner Nachbarn annehmen. Nach [1] hingegen soll sich ein Boid der durch-
schnittlichen Geschwindigkeit seiner Nachbarn anpassen, was die erste Variante mit
einschließt. In der Simulation zu dieser Arbeit wurde die zweite Variante aus [1] aus-
gewählt, da diese auch in [4] verwendet wird. Um diese Variante klar von der ersten
abzugrenzen, wird sie im Folgenden Velocity Match Behavior genannt. Abbildung 5
zeigt die Funktionsweise dieses Behaviors:
Aus allen Geschwindigkeiten (dunkelgrau) der Nachbar-Boids wird zunächst die
durchschnittliche Geschwindigkeit (orange) berechnet. Anschließend wird unter Be-
rücksichtigung der momentane Geschwindigkeit des Boids eine lineare Beschleuni-
gung (grün) berechnet, mit der das Boid die angestrebte Durchschnitts-Geschwindig-
keit in einer bestimmten Zeit erreichen wird. In Pseudo-Code lässt sich dieser Algo-
rithmus wie folgt darstellen ([4], S. 66):
23 von 65
Abbildung 5: Die Funktionsweise des Velocity Match Behaviors
class VelocityMatch:
characterVelocity
neighbors
maxLinearAcceleration
timeToTargetVelocity
function calculateSteering():
steering = new Steering()
targetVelocity = neighbors.getMeanVelocity()
steering.linear = targetVelocity – characterVelocity
steering.linear /= timeToTargetVelocity
steering.linear.clampLengthTo(maxLinearAcceleration)
steering.angular = 0
return steering
end function
end class
Das Velocity Match Behavior erfüllt sowohl den ersten als auch den zweiten Punkt
der biologischen Grundlagen. Da sich alle Boids mit der in etwa gleichen Geschwin-
digkeit in dieselbe Richtung bewegen, kann es zu keiner Kollision kommen und der
Schwarm bleibt zusammen.
6.5 Kombination der Steering Behaviors
Wie bei den einzeln vorgestellten Steering Behaviors eines Boids gibt es auch bei
der Kombination ebendieser verschiedene Ansätze. Zwei der gängigsten sind die
Kombination nach Wichtigkeit und die Kombination mit Gewichtung. Allgemein las-
sen sich diese Kombinations-Methoden immer anwenden, wenn verschiedene Steer-
ing Behavior miteinander kombiniert werden sollen. In diesem Abschnitt werden sie
24 von 65
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
allerdings anhand von Cohesion, Separation und Alignment erklärt, da es in dieser
Arbeit vorwiegend um die Simulation von Schwarmverhalten geht.
6.5.1 Kombination nach Wichtigkeit
Die Kombination nach Wichtigkeit ([4], S. 103ff) priorisiert die drei Steering Behaviors
eines Boids nach ihrer logischen Wichtigkeit. Das bedeutet, dass Separation am
wichtigsten ist, da sich ein Boid bei einer Kollision „verletzen“ könnte und es deswe-
gen unten allen Umständen eine Kollision vermeiden möchte. Die beiden anderen
Behaviors können nach Belieben priorisiert werden, je nachdem welches resultieren-
de Verhalten dem Entwickler besser gefällt.
Um verschiedene Steering Behaviors miteinander zu kombinieren, wird zunächst das
Behavior mit der höchsten Priorisierung angesprochen. Dieses berechnet wie üblich
ein Steering Objekt und gibt es zurück. Wenn der Betrag von einer der beiden zu-
rückgegebenen Beschleunigungen größer als ein bestimmter und meist sehr kleiner
Schwellwert ist, wird dieses Steering-Objekt zum Aktualisieren der Kinematic-Para-
meter des Boids verwendet. Wenn allerdings keiner der beiden Beträge größer als
der Schwellwert ist, wird das nächste Verhalten angesprochen. Dieser Algorithmus
wird solange durchgeführt, bis er zum letzten Behavior gelangt. In diesem Fall wird
das vom letzten Behavior berechnete Steering-Objekt zur Aktualisierung verwendet.
In Pseudo-Code sieht das wie folgt aus ([4], S. 104):
25 von 65
class PrioritySteering:
steeringBehaviors # Arranged in order of priority
epsilon # Very small number
function calculateSteering():
for each behavior in steeringBehaviors:
steering = behavior.calculateSteering()
if steering.linear.length() > epsilon or
steering.angular.length() > epsilon:
return steering
end if
end for
return steering
end function
end class
Dabei handelt es sich um eine dreidimensionale Variante, da in Zeile 10 die Winkel-
beschleunigung als Vektor behandelt wird. Für zweidimensionale Anwendungen wür-
de der Vergleich durch abs(steering.angular) > epsilon ersetzt werden.
Anhand des Namens der calculateSteering()-Methode kann man erkennen,
dass die Kombination von Steering Behaviors ebenfalls als Steering Behavior ge-
handhabt werden kann. Dadurch können mehrere Behaviors in einer Kombinations-
Klasse zusammengefasst und diese wiederum wie ein einzelnes Steering Behavior
behandelt werden.
Für die Simulation zu dieser Arbeit wurde die Kombination nach Wichtigkeit auspro-
biert. Allerdings lieferte sie kein „schönes“ Schwarmverhalten, das sich zusätzlich
sehr schlecht beeinflussen und kontrollieren ließ. Deswegen wurde die Kombination
mit Gewichtung ausprobiert, die wesentlich bessere Ergebnisse lieferte und deswe-
gen für die Simulation ausgewählt wurde.
26 von 65
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
6.5.2 Kombination mit Gewichtung
In der Kombination mit Gewichtung ([4], S. 96ff) werden in jedem Fall alle drei Steer-
ing Behaviors angesprochen. Dazu erhalten sie jeweils ein Gewicht, das wieder ab-
hängig von ihrer logischen Wichtigkeit sein kann. Nach [4], S. 99 ist in diesem Fall
Separation wichtiger als Cohesion und Cohesion wichtiger als Velocity Match. Aller-
dings kann man sie auch nach anderen Kritierien priorisieren. Für die Simulation zu
dieser Arbeit wurden folgende Gewichte gewählt:
Dabei ist zu beachten, dass die Wirkung der Gewichtung stark mit den Parametern
der Nachbarschaften zusammenhängt. Diese Werte sind also nur in Verbindung mit
den Werten aus Abschnitt 7.1 Anzahl und Parameter der Nachbarschaften sinnvoll
und wurden durch viel Ausprobieren gefunden.
Die Beschleunigungen in den berechneten Steering-Objekte aller drei Steering Be-
haviors werden nun mit ihren jeweiligen Gewichten multipliziert und die Produkte an-
schließend zusammenaddiert. Im Gegensatz zu der Kombination nach Wichtigkeit
muss die Summe überprüft und wenn nötig beschränkt werden. Der dazugehörige
Pseudo-Code sieht wie folgt aus ([4], S. 97f):
27 von 65
Tabelle 1: Gewichtungen der Steering Behaviors eines Boids
Gewichtung
1,0
Separation 1,0
0,5
Steering Behavior
Cohesion
Velocity Match
class WeightedSteering:
steeringBehaviors
maxLinearAcceleration
maxAngularAcceleration
function calculateSteering():
steering = new Steering()
for each behavior in steeringBehaviors:
steering += behavior.weight *
behavior.calculateSteering()
end for
steering.linear.clampToLength(maxLinearAcceleration)
steering.angular.clampToLength(maxAngularAcceleration)
return steering
end function
end class
Zeile 14 kann dabei übersprungen werden, wenn z.B. nur die drei Steering Behaviors
eines Boids verwendet werden, da diese ausschließlich lineare Beschleunigungen
berechnen.
6.6 Berechnung der Orientierung
In den Pseudo-Codes der drei Steering Behaviors wird ersichtlich, dass sie aus-
schließlich lineare Beschleunigungen berechnen. Die Boids bewegen sich so zwar im
Raum, aber drehen sich nicht und blicken deshalb immer in die gleiche Richtung. Da
dieses Verhalten sehr realitätsfremd erscheinen würde, muss die Orientierung an
Richtungsänderungen angepasst werden. Zusätzlich würden ohne die Aktualisierung
der Blickrichtung die Nachbarschaften falsch berechnet werden und der gesamte Al-
gorithmus zur Schwarm-Simulation würde nicht funktionieren.
28 von 65
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Eine Variante, diese Funktionalität zu implementieren, ist das Look Where You Go
Behavior. Dieses berechnet ausschließlich eine Winkelbeschleunigung, die die Ori-
entierung eines Boids an seine momentane Bewegungsrichtung anpasst. Durch den
Weg über eine Beschleunigung entsteht ein verzögertes Anpassen an einen Rich-
tungswechsel, was einen sehr interessanten Effekt erzeugt.
Diese Variante wurde in der Simulation zu dieser Arbeit ausprobiert. Allerdings war
sie zu fehleranfällig und zu schwer zu kontrollieren. Deswegen hat man sich für eine
weit einfachere Methode entschieden, die vollkommen ausreichend ist. Anstatt den
Umweg über ein Steering Behavior zu nehmen, wird die Orientierung einfach anhand
der momentanen Bewegungsrichtung festgelegt. Diese Variante ist wesentlich einfa-
cher zu implementieren, robuster und benötigt weniger Berechnungen. Aus diesen
Gründen wird sie in der finalen Version der Simulation verwendet.
29 von 65
7 Nachbarschaften
Der Begriff „Nachbarschaft“ wurde in dieser Arbeit bereits mehrfach verwendet, wo-
bei er immer zwei Bedeutungen beinhaltete. Zum Einen bezeichnet er eine bestimm-
te Menge an Boids, die sich in der Nähe eines Boids befinden. Diese Nachbar-Boids
werden von den einzelnen Steering Behavior des Boids verwendet, um ihre Steering-
Objekte zu berechnen. Zum Anderen beschreibt „Nachbarschaft“, wie diese Menge
an Nachbar-Boids festgelegt wird. Vögel z.B. orientieren sich jeweils an ihren sieben
nächsten Artgenossen[6]. In den meisten Fällen wird jedoch eine Art Sichtfeld be-
nutzt. Wenn sich ein anderes Boid in diesem Sichtfeld befindet, gehört es zur Nach-
barschaft. Ein Vogel hat z.B. ein Sichtfeld von ca. 300°, das sich aus den Sichtfel -
dern beider Augen zusammensetzt[1]. Neben einem Winkel wird ein Nachbarschafts-
Sichtfeld aber noch durch einen Radius beschrieben, wie die nachfolgende Abbil-
dung 6 zeigt:
Der Grund für eine radiale Beschränkung ist wieder das biologische Vorbild. Bei-
spielsweise wird die Sicht eines Herden-Tiers in den meisten Fällen durch seine Art-
genossen behindert. Ein Sichtfeld mit unendlicher Ausdehnung würde demnach kei-
nen Sinn machen, da sich die Boids an Nachbarn orientieren würden, die sie in der
30 von 65
Abbildung 6: Sichtfeld eines Boids
Realität gar nicht sehen könnten. Zusätzlich würde solch ein unendliches Sichtfeld
die Laufzeit des Algorithmus stark vergrößern.
7.1 Anzahl und Parameter der Nachbarschaften
Craig Reynolds schlägt in [1] vor, den Steering Behaviors eines Boids zwei Nachbar-
schaften zu geben. Alignment und Separation sollen das weite 300° Sichtfeld eines
Vogels bekommen. Der Radius soll relativ klein sein, da sich diese Steering Behav-
iors nur an den nächsten Boids orientieren müssen. Cohesion hingegen ist für das
Folgen von anderen Boids zuständig, weswegen es einen größeren Radius bekom-
men soll. Zudem benötigen echte Vögel eine Tiefenwahrnehmung für das Verfolgen
von Artgenossen. Diese ist bei Vögeln nur in einem Sichtfeld von ca. 10° bis 15°
vorhanden, da sich dort die Sichtfelder beider Augen überlappen[1].
Diese Variante der Nachbarschaften ist sehr nah am biologischen Vorbild. Allerdings
ist ein Programmierer nicht an die Realität gebunden. In den meisten Implementie-
rungen, die während der Recherche zu dieser Arbeit gefunden wurden, wurde aus-
schließlich eine einzige Nachbarschaft verwendet. Diese hatte einen Winkel von
360° - es handelte sich also um einen Sicht-Kreis bzw. eine Sicht-Kugel. Dies ist die
am einfachsten zu implementierende Variante, die durchaus sehr gute Ergebnisse
liefern kann. Zudem hat sie einen geringeren Rechenaufwand als mehrere Nachbar-
schaften. In anderen Simulationen wurde diese Variante mit einem Sichtfeld-Winkel
ergänzt. Beide Varianten wurden auch für die Implementierung zu dieser Arbeit aus-
probiert. Allerdings hat sich gezeigt, dass es im Rahmen einer „feineren“ Simulation
mehr Sinn macht, wie von Craig Reynolds vorgeschlagen für die einzelnen Steering
Behaviors auch verschiedene Nachbarschaften zu definieren. Jedoch haben andere
als die von ihm vorgeschlagenen Parameter ein weit besseres Verhalten mit weniger
Rechenaufwand gebracht.
Dabei stehen die Ergebnisse und Einsichten, die im Folgenden beschrieben werden,
auf einer rein subjektiver Basis. Es wurden viele Nachbarschafts-Einstellung auspro-
biert, bis letztendlich ein zufriedenstellendes Ergebnis erreicht wurde. Allerdings
31 von 65
muss jeder Entwickler selber für sich entscheiden, was für ihn zufriedenstellend ist
bzw. welches Schwarmverhalten er haben möchte. Für diese Arbeit wurde ein dyna-
misches, aber dennoch nicht „quirliges“ Verhalten angestrebt. Es ist schwer in Wor-
ten zu beschreiben, weshalb an dieser Stelle auf die Simulation verwiesen werden
muss. Diese hat die als optimal empfundenen Parameter bereits voreingestellt, die
am Ende dieses Abschnitts kurz zusammengefasst werden.
Cohesion hat wie von Craig Reynolds vorgeschlagen ein Sichtfeld mit einem enge-
rem Winkel als die beiden anderen Steering Behaviors bekommen. Wenn der Winkel
zu groß gewählt wird (d.h. zwischen 180° und 360°), kann die durchschnittliche Po-
sition der Nachbarn „in“ einem Boid oder sogar dahinter liegen. Dadurch würde das
Boid Gefahr laufen, ins Stocken zu geraten und keine flüssige Vorwärtsbewegung
mehr zu beschreiben (s. Abbildung 7).
32 von 65
Abbildung 7: Boids, die aufgrund eines 360° Radius der Cohesion-Nachbarschaft ins Stocken geraten sind und sich nicht mehr vorwärts bewegen
Der von Craig Reynolds vorgeschlagene Winkel von 10°-15° hatte hingegen eine zu
„scheuklappenähnliche“ Wirkung, da die Boids auf den Großteil ihrer Nachbarn nicht
mehr reagiert haben. Deswegen wurde er auf ~60° vergrößert, was ein weit dynami-
scheres Verhalten erbrachte. Für den Radius schlägt Craig Reynolds einen großen
Wert vor. Allerdings hat sich gezeigt, dass ein wesentlich größerer Radius gar nicht
nötig ist. Im Prinzip könnte er auch genauso groß wie die anderen Radii sein, für die
Simulation wurde aber ein Faktor von ca. 2 gewählt. Zusätzlich nimmt mit kleiner
werdenden Radius auch die Laufzeit des Programms ab (s. Abschnitt 7.2.2 Binning
Methode). Zusätzlich schlägt Craig Reynolds vor, den Radius der Cohesion-Nach-
barschaft dynamisch anzupassen, je nachdem wie viele Nachbarn sich gerade in ihr
befinden. Diese Variante wurde probeweise implementiert, aber aufgrund der nahezu
verschwindenden Wirkung auf das Schwarmverhalten wieder gelöscht.
Velocity Match ist relativ flexibel in Bezug auf den Winkel des dazugehörigen Sicht-
feldes. Der einzige Unterschied zwischen einem großen, evtl. 360° Winkel und ei-
nem kleinen Winkel ist, dass der große Winkel eine harmonischere Schwarmbewe-
gung zur Folge hat. Das ist leicht nachzuvollziehen, da sich die Boids mit einem
großen Winkel an mehr Nachbarn orientieren. Für die Simulation wurde ein Winkel
von 360° gewählt, man könnte aber auch genauso gut die von Craig Reynolds vor-
geschlagenen 300° verwenden.
Separation hingegen sollte auf jeden Fall einen Sichtwinkel von 360° bekommen,
und nicht 300°. Das liegt daran, dass Cohesion alleine die Boids nicht zuverlässig
„antreiben“ kann. Separation hilft dabei, indem es ein Boid vor den Nachbarn in sei-
nem „Rücken“ fliehen lässt. Dafür wird ein Sichtfeldwinkel von 360° benötigt.
Der schlimmste Fall für Separation ist, wenn im gesamtem „vollen“ Sichtfeld die
Nachbarn etwa gleichmäßig verteilt wären. Dies hätte zur Folge, dass ein Boid auf
der Stelle hin und her zittern würde. Allerdings muss man sich um dieses Problem
keine Sorgen machen, da das Cohesion Behavior in diesem Fall eingreifen und die
flüssige Bewegung so nicht unterbrochen werden würde – vorausgesetzt, das Cohe-
sion-Sichtfeld hat keinen allzu großen Winkel.
33 von 65
In der Simulation teilen sich Alignment und Separation ein Sichtfeld mit 360° und da-
mit auch die Nachbarn. Da Separation aber einen threshold-Wert besitzt, der an-
gibt, ab welcher Distanz zu anderen Boids das Behavior zu wirken beginnt, kann
man so auf einfache Weise eine kleinere Separation-Nachbarschaft erhalten. In den
als optimal empfundenen Werten wurde Separation allerdings auf den Nachbar-
schafts-Radius eingestellt, sodass threshold keine „Unter-Nachbarschaft“ erzeugt.
Die Werte aller Nachbarschaften sollen noch einmal kurz zusammengefasst und gra-
fisch dargestellt werde:
34 von 65
Tabelle 2: Die als optimal empfundenen Werte der Nachbarschafts-Parameter
15 1 8
8 2π
Steering Behavior
Radius[Boid-Längen]
Winkel [rad]
Separation threshold [Boid-Längen]
Cohesion
Separation, Velocity Match
Abbildung 8: Die in Tabelle 2 festgehaltenen Werte maßstabsgetreu dargestellt
7.2 Ermitteln der Nachbarschaften
7.2.1 Brute Force Methode
Für das Berechnen der Nachbarschaften, d.h. welche Boids Nachbarn von welchen
Boids sind, wurde zu Beginn die sehr einfache Brute Force Methode implementiert.
Diese überprüft für jedes Boid alle andere Boids auf eine mögliche Nachbarschaft:
class BruteForce:
function findNeighborhoods(boids):
for each boid in boids:
for each possibleNeighbor in boids:
if possibleNeighbor == boid
continue
else if boid.sees(possibleNeighbor)
boid.neighbors.append(possibleNeighbor)
end if
end for
end for
end function
end class
Die Methode sees() in Zeile 7 gibt dabei true zurück, wenn possibleNeighbor
im Sichtfeld von boid liegt.
Es hat sich sehr früh herausgestellt, dass die Leistungsfähigkeit der gesamten Simu-
lation im Wesentlichen durch die Brute Force Methode bestimmt wird. Sie hat eine
Laufzeitabhängigkeit von O(n2) , wobei n die Anzahl an Boids ist. Diese Tatsache
ist an sich nicht schlimm, da am Ende nur die Laufzeit des gesamten Algorithmus
zählt. Um aber einen Eindruck über den Einfluss der Brute Force Methode zu bekom-
men, wurden einige Versuche durchgeführt. Dabei wurden die Nachbarschaften mit
denjenigen Werten eingestellt, die am Ende des Abschnitts 7.1 Anzahl und Parame-
ter der Nachbarschaften als empfundenes Optimum vorgestellt wurden. Die einzel-
35 von 65
1
2
3
4
5
6
7
8
9
10
11
12
13
nen Parameter der Steering Behaviors (decayCoefficient, Gewichtungen) beka-
men ebenfalls diejenigen Werte, die in ihren Abschnitten vorgestellt wurden. Als
Test-Computer diente derjenige PC, auf dem die Simulation implementiert wurde. Da
es nur auf den Verlauf der Linien in den nachfolgenden Diagrammen ankommt, und
nicht auf die gemessenen Zeiten, wird auf eine Auflistung der im Test-Computer ein-
gebauten Hardware verzichtet.
Die Messergebnisse des ersten Versuchs wurden in Diagramm 1 eingetragen. Es
wurden die Laufzeiten von zwei Teilen des Algorithmus in Abhängigkeit zu der An-
zahl an Boids gemessen. Die grüne Linie zeigt die benötigte Zeit für das Berechnen
aller Steering-Objekte, das Aktualisieren der Kinematic-Parameter u.ä. Die rote Linie
gibt Aufschluss darüber, wie lange die Suche der Nachbarschaften mit der Brute
Force Methode gedauert hat. Die blaue Linie zeigt, wie lange die Dauer eines
Frames ist. In dieser Information befindet sich die erreichte Frame Rate (Frame Rate
= 1 / Frame-Dauer), die aufgrund ihrer Wichtigkeit zusätzlich als gestrichelte blaue Li-
nie eingefügt wurde.
36 von 65
Diagramm 1: Die Berechnungszeiten der beiden Algorithmus-Teile mit der Brute Force Methode und die daraus resultierende Frame Rate
0 50 100 150 200 250 300 350 400 450 5000
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
Suche der Nachbarschaften Dauer eines Frames
Aktualisierung der Boids Frame Rate
Anzahl an Boids
Be
rech
nu
ng
sze
it [m
s]
Bild
fre
qu
en
z [H
z]
Man sieht, dass die Linie der Frame-Dauer ab 200 Boids parallel zu der Linie der
Nachbarschafts-Berechnung liegt. Davor befindet sich die Frame-Dauer bei ca.
17 ms, was der „flüssigen“ Frame Rate von 60 Hz entspricht. Der Grund dafür liegt in
der verwendeten OpenSceneGraph-Bibliothek, die so programmiert wurde, dass die
Frame Rate nie über 60 Hz hinausgeht. Man kann also erkennen, dass die Leis-
tungsfähigkeit der Simulation direkt von der Brute Force Methode bestimmt wird und
eine flüssige Bildfrequenz nur bis 200 Boids möglich ist.
Das nachfolgende Diagramm 2 zeigt den Anteil der Nachbarschafts-Berechnung an
der Laufzeit des gesamten Algorithmus. Dieser setzt sich zusammen aus der Suche
der Nachbarschaften (rote Linie) und der Aktualisierung der Boids (grüne Linie). Da-
bei wird ersichtlich, dass bereits für geringe Boid-Anzahlen der Anteil oberhalb von
80 % liegt und sich relativ schnell 100 % annähert:
Diese beiden Testreihen zeigen, dass eine effizientere Berechnung der Nachbar-
schaften dringend benötigt wird, wenn man die Laufzeit des gesamten Algorithmus
37 von 65
Diagramm 2: Der Anteil der Nachbarschafts-Suche an der Laufzeit des gesamten Algorithmus
0 50 100 150 200 250 300 350 400 450 5000
10
20
30
40
50
60
70
80
90
100
Anteil der Nachbarschafts-Suche
Anzahl an Boids
An
teil
an
de
r g
esa
mte
m L
au
fze
it [%
]
verringern möchte. Es wurden mehrere Möglichkeiten in Betracht gezogen, dieses
Ziel zu erreichen, wobei man sich zunächst für die Binning Methode entschieden hat.
7.2.2 Binning Methode
Der Begriff „Binning“ beschreibt eine Raumaufteilung in eine beliebige Anzahl an
gleichgroße Zellen. Für jede Zelle wird gespeichert, welche Boids sich gerade in ihr
befinden. Diese Information wird jeden Frame aktualisiert. Wenn man nun die Nach-
barschaft für ein Boid berechnen möchte, muss man nicht mehr alle Boids überprü-
fen. Stattdessen ermittelt man diejenigen Zellen, die vom Sichtfeld des Boids ge-
schnitten werden, und überprüft die in ihnen enthaltenen Zellen. Der gesamte Algo-
rithmus zur Berechnung der Nachbarschaft sieht dann wie folgt aus:
class Binning:
function findNeighborhoods(boids):
for each boid in boids:
cells = getCellsFromFieldOfView(boid.fieldOfView)
for each cell in cells:
for each possibleNeighbor in cell:
if possibleNeighbor == boid
continue
else if boid.sees(possibleNeighbor)
boid.neighbors.append(possibleNeighbor)
end if
end for
end for
end for
end function
end class
38 von 65
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
getCellsFromFieldOfView() gibt dabei die vom Sichtfeld geschnittenen Zellen
zurück. Während der Implementierung der Binning Methode stellte diese Funktion
die größte Herausforderung dar, da eine Überlappung zwischen einem Kugelaus-
schnitt (Sichtfeld) und Quadern (Zellen) nicht einfach zu bestimmen ist. Eine einfa-
chere Variante beschreibt deswegen das Sichtfeld durch eine Axis Aligned Bounding
Box (AABB). Anschließend wird berechnet, welche Zellen von der AABB geschnitten
werden werden, wodurch man nur noch Überlappungen zwischen einem Quader und
Quadern ermitteln muss. Die Variante ist wesentlich einfacher zu implementieren, hat
jedoch eine Schwachstelle, die von Abbildung 9 illustriert wird:
In diesem Fall werden alle neun Zellen von der Methode zurückgegeben, da sie von
der AABB des Sichtfeldes (weiß gestrichelt) geschnitten werden. Dabei werden in
Wirklichkeit nur die grünen Zellen vom Sichtfeld geschnitten und die orangefarbenen
Zellen sind irrelevant. In diesem Fall würde die ermittelte Zellen-Menge fast zur Hälf-
te aus unwichtigen Zellen bestehen. Allgemein tritt dieses Problem bei engen Sicht-
feldern mit großen Radii auf. Um es zu lösen, kann man das Sichtfeld durch mehrere
39 von 65
Abbildung 9: Das Ermitteln der Zellen, die von dem Sichtfeld geschnitten werden, mittels einer
AABB
kleine AABBs beschreiben3. Zu diesem Zweck wird das Sichtfeld zuerst durch meh-
rere gleichgroße Kugeln approximiert und anschließend deren AABBs verwendet.
Abbildung 10 veranschaulicht diesen Vorgang:
Diesmal gibt die Methode zwei Zellen (grau) weniger zurück. Dadurch sinkt der Anteil
an unwichtigen Zellen in der ermittelten Zellen-Menge. Da aber das Überprüfen meh-
rere AABBs auch mehr Berechnungszeit benötigt, sollte man diese Methode nur
dann anwenden, wenn man sie wirklich braucht. Deswegen wurde für die Simulation
zu dieser Arbeit eine Fallunterscheidung implementiert:
• Für einen Sichtfeld-Winkel α≤30 ° wird das Sichtfeld durch mehrere AABBs
beschrieben. Die Anzahl der AABBs hängt vom Radius des Sichtfeldes ab.
• Für 30 °<α≤180 ° wird die kleinst möglichste umschreibende Kugel des Sicht-
feldes berechnet und ihre AABB verwendet.
3 Quelle: Persönliches Gespräch mit Prof. Dr. Röttger
40 von 65
Abbildung 10: Das Ermitteln der Zellen, die von dem Sichtfeld geschnitten werden, mittels
mehrerer AABBs
• Für 180°<α wird α=360 ° angenommen und es wird die AABB der Kugel mit
dem Sichtfeld-Radius verwendet.
An dieser Stelle ist noch sehr viel Platz für Optimierungen, da immer noch einige irre-
levant Zellen zurückgegeben werden. Allerdings hat diese Methode ausgereicht, um
den Anteil an unwichtigen Zellen genügend zu verringern.
7.2.3 Vergleich der Laufzeitabhängigkeiten
Wie bereits im Abschnitt 7.2.1 Brute Force Methode erwähnt, besitzt die dort be-
schrieben Methode eine Laufzeitabhängigkeit von O(n2) . Die Laufzeitabhängigkeit
der Binning Methode hingegen ist bis jetzt noch unbekannt. Um einen ersten Ein-
druck über die Verbesserung zu gewinnen, die die Binning Methode mit sich bringt,
wurde mit beiden Methoden die Berechnungszeit der Nachbarschafts-Ermittlung in
Abhängigkeit zu der Anzahl an Boids gemessen. Wie bei den beiden Versuchen aus
Abschnitt 7.2.1 Brute Force Methode wurden die als optimal empfundene Werte für
die Nachbarschaften und die Steering Behaviors eingestellt. Wichtig sind für die
nachfolgenden Versuche zudem noch die Werte folgender Parameter:
Die gemessenen Berechnungszeiten von beiden Methoden wurden in ein gemeinsa-
mes Diagramm eingetragen:
41 von 65
Tabelle 3: Werte der für die Versuche wichtigen Parameter
Parameter Wert
80
Anzahl der Zellen 20³ = 8000
15
13
Kantenlänge des Raumwürfels[Boid-Längen]
Maximale lineare Beschleunigung[Boid-Längen / s²]
Maximale Geschwindigkeit[Boid-Längen / s]
Wie erwartet zeigt die Laufzeitabhängigkeit der Brute Force Methode den bereits
mehrfach erwähnten quadratischen Anstieg. Die Binning Methode hingegen steigt im
Vergleich kaum an. Der Versuch musste bei 2000 Boids beendet werden, da sich bei
der Brute Force Methode bereits ab 1500 Boids kein Schwarmverhalten mehr bilde-
te. Das liegt daran, dass die update()-Methode der Kinematic-Klasse (s. S. 11) die
seit dem letzten Funktions-Aufruf verstrichene Zeit berücksichtigt. Bei größeren
„Zeitsprüngen“ verändern sich deswegen die Positionen der Boids und damit auch
die Nachbarschaften zu plötzlich. Dadurch ist kein „gleichmäßiges“ Folgen mehr
möglich. Abbildung 11 zeigt die Wirkung dieser Schwelle:
42 von 65
Diagramm 3: Die Abhängigkeit der Laufzeit zur Anzahl an Boids für die Berechnung der Nachbarschaften
0 200 400 600 800 1000 1200 1400 1600 1800 20000
100
200
300
400
500
600
700
800
900
Brute Force Binning
Anzahl an Boids
Be
rech
nu
ng
sze
it [m
s]
Nichtsdestotrotz hat der Versuch deutlich die geringere Laufzeit der Binning Methode
und die damit einhergehende Verbesserung gegenüber der Brute Force Methode ge-
zeigt. Jedoch ist aus den Messergebnissen keine eindeutige Laufzeitabhängigkeit zu
erkennen. Diagramm 4 zeigt dieselben Messwerte der Binning Methode wie in Dia-
gramm 3, diesmal allerdings mit einer anderen Skalierung der y-Achse.
43 von 65
Abbildung 11: Das resultierende Schwarmverhalten mit der Brute Force Methode bei zwei unterschiedlichen Anzahlen an Boids
a) 700 Boids b) 1700 Boids
Diagramm 4: Dieselben Messwerte, die auch in Diagramm 3 zu finden sind, mit einer anderen y-Achsenskalierung
0 200 400 600 800 1000 1200 1400 1600 1800 20000
10
20
30
40
50
Binning
Anzahl an Boids
Be
rech
nu
ng
sze
it [m
s]
Es scheint, dass die Kurve einen „leicht quadratischen“ Anstieg beschreibt. Es könn-
te sich aber genauso gut um Schwankungen in den Messwerten handeln und die
Laufzeitabhängigkeit ist eigentlich linear. Hinzu kommt, dass keine Messwerte ober-
halb von 2000 Boids vorliegen. Um die Laufzeitabhängigkeit der Binning Methode zu
bestimmen, sind deswegen noch weitere Maßnahmen nötig. Als erstes wurde über-
legt, von welchen Parametern die Laufzeit abhängt:
• Die Anzahl an Boids n und die Anzahl an Nachbarschaften s ergeben
eine Art „Grundabhängigkeit“ O(s⋅n) , da auf jeden Fall für jede Nachbar-
schaft alle Boids einmal überprüft werden müssen. Falls in jeder Zelle sich je-
weils nur ein Boid befindet und die Sichtfelder aller Boids keine anderen Zel-
len schneiden, bleibt es bei dieser Abhängigkeit.
• Die Größe von Radius und Winkel einer Nachbarschaft im Verhältnis zu der
Größe der Zellen bestimmt, wie viele Zellen für ein Boid auf Nachbarn über-
prüft werden müssen. Die Größe der Zellen wird wiederum von der Raumgrö-
ße und der Anzahl der Zellen bestimmt.
• Zusammen mit der Gleichmäßigkeit der Boid-Verteilung bzw. -Dichte verän-
dert sich die Laufzeit ebenfalls. Abbildung 12 auf der nächsten Seite zeigt
zwei Fälle, in denen der zweidimensionale Raum in vier Zellen aufgeteilt wur-
de. Insgesamt befinden sich 8 Boids innerhalb des Raumes, die in a) un-
gleichmäßig und im Vergleich dazu in b) gleichmäßiger verteilt sind. Im Fall
von a) würde sich die Laufzeitabhängigkeit O(s⋅n2) annähern, im Fall von b)
O(s⋅n2/c) , wobei c die Anzahl an Zellen ist. O(s⋅n2/c) würde sie dabei nur
erreichen, wenn die Sichtfelder aller Boids keine anderen Zellen schneiden
würden, als diejenige, in der sich das jeweilige Boid gerade befindet.
44 von 65
Bei der Entwicklung hat sich gerade der dritte Punkt als Stolperstein herausgestellt,
der zu Beginn nicht beachtet wurde. „Schöne“ Schwarmsimulationen lassen den
Schwarm in einem Raum herum fliegen. Das bedeutet aber gleichzeitig auch, dass
die Boids niemals gleichmäßig im Raum verteilt sind. An dieser Stelle könnte man
ansetzen, und die Binning Methode hinsichtlich dieser Eigenschaft verbessern. Es
kann aber auch sein, dass ein ganz anderer Algorithmus besser geeignet ist. Da die
Binning Methode aber genug Verringerung der Laufzeit gebracht hat, wurde sie wei-
terhin beibehalten.
Da die Laufzeitabhängigkeit aufgrund der dritten Abhängigkeit stark schwanken
kann, ist es schwer, sie mathematisch genau zu bestimmen. Stattdessen wurde der
Versuch, sie experimentell zu bestimmen, fortgeführt. Diagramm 5 zeigt die Mess-
werte einer weiteren Testreihe, in der der Algorithmus zunächst in drei Teile aufge-
teilt wurde: Die Ermittlung der Nachbar-Boids in der ersten Nachbarschaft, die glei-
che Berechnung in der zweiten Nachbarschaft und die Aktualisierung der internen
Datenstruktur. Anschließend wurde die Berechnungszeit für alle drei Teile in Abhän-
gigkeit zu der Boid-Anzahl gemessen. Um auf die möglichen Schwankung in der
45 von 65
Abbildung 12: Zwei Beispiele an unterschiedliche Boid-Verteilungen
a) b)
Laufzeit einzugehen, wurden für jeden Algorithmus-Teil jeweils die minimalen und
maximalen Werte festgehalten:
Wie man sieht, hat die Aktualisierung der Datenstruktur den geringsten Einfluss auf
die gesamte Laufzeit und bleibt auch bei hohen Boid-Anzahlen stets unter 10 ms.
Währenddessen zeigen die beiden Nachbarschafts-Suchen einen im weitesten Sinne
quadratischen Anstieg. Dabei bleiben die Minimal-Werte beider Suchen diesem Ver-
halten nahezu treu, während die Maximal-Werte zwischen 3000 und 6500 Boids
46 von 65
Diagramm 5: Die Abhängigkeit zwischen Laufzeit und Boid-Anzahl für alle drei Algorithmus-Teile der Binning Methode
0 1000 2000 3000 4000 5000 6000 7000 80000
50
100
150
200
250
Erste Nachbarschaft Max. Zweite Nachbarschaft Max. Aktualisierung Max.Erste Nachbarschaft Min. Zweite Nachbarschaft Min. Aktualisierung Min.
Anzahl an Boids
Be
rech
nu
ng
sze
it [m
s]
nach oben hin stark ausbrechen. Zusätzlich wurde beobachtet, dass bei 3000 Boids
– also zeitgleich mit dem starken Anstieg der Maximal-Werte – der Raum „voll“ er-
schien. Diese Beobachtung wird dadurch unterstrichen, dass sich bei 3500 Boids an-
fingen Staus zu bilden, wie man in Abbildung 13 sehen kann. Dies geschieht nur,
wenn es nicht genügend Platz zum Ausweichen gibt. Bei spätestens 5000 Boids wur-
de die Bildfrequenz dann so gering, dass sich wie bei der Brute Force Methode bei
1500 Boids kein Schwarmverhalten mehr bilden konnte.
Was an den Kurven zusätzlich auffällt ist ihre Deckungsgleichheit, die trotz verschie-
dener Parameter der Nachbarschaften besteht. Ein Grund dafür könnte sein, dass
die AABBs beider Nachbarschaften in etwa dieselben Abmessungen haben. Auf der
anderen Seite könnte diese Deckungsgleichheit aber auch bedeuten, dass kleinere
Unterschiede in den Parameterwerten der Nachbarschaften keine große Auswirkung
haben. Ergänzend dazu lässt sich aus der Erfahrung heraus berichten, dass sich für
große Unterschiede die Berechnungszeiten hingegen stark unterscheiden.
Nachdem die Laufzeit in Abhängigkeit zu der Boid-Anzahl gemessen wurde, wurde
sie in einem weiteren Versuch in Abhängigkeit zu der Zellen-Anzahl gemessen. Da-
bei wurden die Messungen mit denselben Parametern wie bei dem vorherigen Ver-
47 von 65
Abbildung 13: Das Bilden eines Staus bei 4000 Boids in einer Raumecke
such durchgeführt, die oben in Tabelle 3 aufgelistet wurden. Die Boid-Anzahl wurde
auf 800 eingestellt. Die gemessenen Minimal- und Maximal-Werte der drei Algorith-
mus-Teile wurden wieder in ein Diagramm eingetragen, deren y-Achse für eine bes-
sere Veranschaulichungen der Ergebnisse logarithmisch skaliert ist:
Diesmal zeigt die Berechnungszeit für die Aktualisierung der internen Datenstruktur
ebenfalls einen Anstieg bei steigender Zellen-Anzahl. Diese Verhalten ist allerdings
stark von der Implementierung abhängig, weshalb ihm nicht allzu viel Bedeutung bei-
gemessen werden kann. Um nun die optimale Zellen-Anzahl herauszufinden, wurden
48 von 65
Diagramm 6: Die Abhängigkeit zwischen Laufzeit und Zellen-Anzahl für alle drei Algorithmus-Teile der Binning Methode
0 5 10 15 20 25 30 35 40 450
1
10
100
Erste Nachbarschaft Max. Zweite Nachbarschaft Max. Aktualisierung Max.
Erste Nachbarschaft Min. Zweite Nachbarschaft Min. Aktualisierung Min.
Anzahl an Zellen
Be
rech
nu
ng
sze
it [m
s]
die Minimal- und Maximal-Werte aller drei Algorithmus-Teile zusammenaddiert und in
Diagramm 7 eingetragen:
Man erkennt, dass beide Kurven bei 13 Zellen ein Minimum haben. Diese Zellenan-
zahl wäre also für die oben genannten Parameter das Optimum. Allerdings ver-
schiebt sich diese Zahl der Erfahrung nach mit der Veränderung von Parametern,
weshalb diesem Ergebnis ebenfalls nicht allzu viel Bedeutung beigemessen werden
kann.
Um eine verlässliche Aussage über den Zusammenhang zwischen Laufzeit und Zel-
len-Anzahl machen zu können, hätte man deswegen mehrmals denselben Versuch
mit jeweils anderen Parametern durchführen müssen. Dieses Vorgehensweise wäre
allerdings recht zeitaufwändig geworden, weshalb sie nicht mehr Bestand dieser Ar-
beit sein konnte. Hinzu kommt, dass der dritte Parameter der Laufzeitabhängigkeit,
49 von 65
Diagramm 7: Die Abhängigkeit zwischen Laufzeit und Zellen-Anzahl für die gesamte Binning Methode
0 5 10 15 20 25 30 35 40 451
10
100
1000
Binning Methode Max.Binning Methode Min.
Anzahl an Zellen
Be
nö
tigte
Be
rech
nu
ng
sze
it [m
s]
die Gleichmäßigkeit der Boid-Verteilung, nur schwer kontrollierbar ist. Man hätte des-
halb einen komplexeren Versuchsaufbau benötigt, wenn man verlässliche Informatio-
nen über den Einfluss dieses Parameters auf die Laufzeit erlangen wollte. Auch dies
konnte aus Zeit-Gründen nicht mehr im Rahmen dieser Arbeit durchgeführt werden.
Hinzu kommt, dass die Ermittlung der Laufzeitabhängigkeit nicht zum Schwerpunkt
dieser Arbeit gehört. Deswegen wurde der Versuch, die Laufzeitabhängigkeit experi-
mentell zu ermitteln, an dieser Stelle abgebrochen.
Nichtsdestotrotz konnte das Programm dank der Binning Methode für wesentlich
mehr Boids Schwarmverhalten simulieren, als mit der Brute Force Methode möglich
war. Es standen noch weitere Methoden im Raum wie z.B. die Verwendung von Bäu-
men oder die Sweep And Prune Methode. Allerdings hat die Binning Methode bereits
genügend Verbesserung gebracht, weswegen auf die Implementierung der anderen
Methoden verzichtet wurde.
50 von 65
8 Implementierung der Simulation
Der Titel dieser Bachelor-Arbeit lautet „Interaktive Simulation von
Schwarmverhalten“. Gemeint ist damit nicht nur eine theoretische Auseinanderset-
zung, sondern auch das Implementieren einer eben solchen interaktiven Simulation.
Dieser Abschnitt stellt den zweiten Teil der Arbeit dar, der die Aufgabe hat, die Er-
stellung ebendieser Simulation zu erklären. Dabei geht es um die verwendete Soft-
ware, die Vorgehensweise zum Implementieren und eine Präsentation der fertigen
Simulation. Ziel ist es allerdings nicht, den Simulations-Quellcode zu erläutern. Für
diesen Zweck wurde mittels Doxygen eine HTML-Dokumentation erstellt, auf die an
dieser Stelle verwiesen wird.
8.1 Verwendete Software
Zu Beginn der Bachelor-Arbeit stand schnell fest, dass die Simulation in C++ imple-
mentiert werden soll. Der Grund dafür lag in der bereits vorhandenen Erfahrung mit
dieser Programmiersprache. Es standen allerdings auch andere Varianten im Raum,
wie z.B. eine Implementierung als Web-Applikation in HTML5 und JavaScript. Mit
diesen Sprachen war man allerdings nicht sehr vertraut, weswegen man wohl einen
Großteil der Arbeit mit dem Erlernen dieser Sprachen zugebracht hätte. Mit C++ als
Programmiersprache konnte man sich stattdessen auf den Inhalt der Simulation fo-
kussieren.
In den meisten Software-Projekten ist es erwünscht, nicht alles von Hand selber pro-
grammieren zu müssen. Stattdessen möchte man soviele Aufgaben wie möglich an
Bibliotheken abgeben, damit man die „Kernfunktionalitäten“ seiner Applikation
schneller implementieren kann. Für die Simulation zu dieser Arbeit wurde entschie-
den, eine Bibliothek zu suchen, die Funktionen für das Rendering, Audio u.ä. zur
Verfügung stellt. Dafür hatte man sich verschiedene C++ Game Engines angesehen,
wie z.B. Ogre3D und PLIB. Zusätzlich hat man sich verschiedene Scene Graph Bi-
51 von 65
bliotheken angesehen, wie z.B. OpenSceneGraph und NVidia SceniX, da das Ren-
dering die wohl wichtigste Aufgabe war, die die Bibliothek übernehmen sollte.
Die Entscheidung fiel letztendlich auf OpenSceneGraph (OSG), da diese Bibliothek
wesentliche Vorteile bietet:
• OSG bietet zwar viele Funktionalitäten, ist aber dennoch überschaubar und
man schafft einen schnellen Einstieg. Es gibt es viele Tutorials und Dokumen-
tation, ein Forum, Mailing Lists und Buch für Einsteiger[7]
• OSG ist auf einfache Weise erweiterbar. Es gibt bereits eine Vielzahl an sog.
NodeKits, die solche Erweiterung implementieren und dadurch weitere Funk-
tionalitäten zur Verfügung stellen
• Die OSG- und NodeKits-Entwickler helfen bei Problemen in dem bereits ge-
nannten Forum und den Mailing Lists, wodurch man sehr kompetente Hilfe be-
kommt
• OSG ist sehr effizient bzgl. des Renderings
• OSG ist plattformübergreifend
Diese Vorteile sind teils subjektiv, teils basieren sie auf Fakten von der offiziellen
OSG Homepage www.openscenegraph.org. Natürlich gibt es auch einige Nachteile,
wie z.B. die fehlende Audio-Unterstützung. Allerdings waren diese für die Simulation
nicht so wichtig wie das Rendering, weshalb man sie ohne Weiteres in Kauf nehmen
konnte.
Die Simulation wurde auf einem PC mit Ubuntu als Betriebssystem entwickelt. Man
hat auf eine spezielle IDE verzichtet, da diese vom Entwickler als unnötig kompliziert
empfunden werden und die meisten Funktionalitäten nicht gebraucht werden. Statt-
dessen wurden einfache Editoren (Emacs, Geany), CMake und damit generierte
52 von 65
Makefiles verwendet. Die Verwendung von CMake unterstützt zusätzlich die
Plattformunabhängigkeit.
8.2 Ablauf der Implementierung
Für die Entwicklung der Simulation wurde kein besonderes Projektmanagement an-
gewandt. Zu Beginn hatte man sich Gedanken über verschiedene Funktionalitäten
gemacht, die die Simulation am Ende der Entwicklung aufweisen sollte. Im Wesentli-
chen war aber der Titel der Bachelor-Arbeit die einzige Spezifikation, an die man sich
gehalten hat. So wurden einige geplante Funktionalitäten im Laufe des Implementie-
rens wieder verworfen, während immer wieder neue Richtungen eingeschlagen wur-
de. Aus diesem Grund geschah das Programmieren im weitesten Sinne iterativ. Zu-
nächst wurde der Algorithmus für Schwarmverhalten so einfach und schnell wie mög-
lich in Processing implementiert, damit man bereits frühzeitig einen Prototyp zur Ver-
fügung hatte. Da man aber schneller als geplant damit anfing, die Simulation mit
OSG zu implementieren, gibt es es keine voll funktionsfähigen Processing-Sketches.
Zu der Simulation wurden nach und nach immer weitere Funktionalitäten hinzuge-
fügt. Dabei hat man sich mit der bis dahin unbekannten OSG-Bibliothek vertraut ge-
macht, indem man mehrere der bereits erwähnten Tutorials absolvierte und Fachlite-
ratur las[7]. Im Verlauf des Implementierens geschah zwei mal eine Überarbeitung
der gesamten Software-Architektur, die jeweils mehrere Tage in Anspruch nahm. Al-
lerdings konnte nur so auf die sich ständig verändernden Funktionalitäten reagiert
werden und ein gute Balance zwischen Effizienz und Eleganz der Architektur gefun-
den werden. Als Stichtag wurde der 1. März 2013 angepeilt, der auf den Tag genau
eingehalten wurde. An diesem Tag war die Simulation voll funktionsfähig und die ge-
planten Funktionalitäten fertig implementiert. Was noch fehlte, war die Dokumentati-
on des Quellcodes und die Feineinstellung der Parameter. Zusätzlich fehlten noch ei-
nige Buttons des Head-Up-Displays (HUD), deren Implementierung allerdings reine
Schreibarbeit war, da ihre Klasse bereits fertiggestellt wurde.
53 von 65
Der Quellcode der finalen Simulation besteht aus insgesamt 29 Klassen. Abbildung
14 zeigt alle Klassen in einem UML ähnlichen Diagramm aufgelistet:
54 von 65
Abbildung 14: Die Klassen der finalen Simulation, geordnet nach Aufgabengebieten
Nachdem diese Klassen implementiert waren, nahm das Einstellen der Parameter
überraschend viel Zeit ein. Es gelang zunächst nicht, das gewünschte Schwarmver-
halten zuverlässig zu generieren. Deswegen hatte man sich andere Implementierun-
gen und deren Parameter angesehen und in der eigenen Simulation ausprobiert –
leider ohne Erfolg. Schlussendlich gelang es nach einer Vielzahl an Versuchen den-
noch, ein „schönes“ Schwarmverhalten zu erzeugen. Die dazugehörigen Parameter
wurden in den vorhergehenden Abschnitten bereits aufgelistet.
Während diesem Prozess des Ausprobierens wurden zwei Dinge ersichtlich:
1) Zwei Sets an komplett verschiedenen Parametern können das selbe Ergebnis
erzeugen.
2) Zwei Sets mit scheinbar gleichen Parametern können komplett unterschiedli-
che Ergebnisse erzeugen.
Diese beiden, scheinbar kontroversen Einsichten sind einfach zu begründen. Bei-
spielsweise lässt sich sowohl über den threshold-Parameter als auch über den
decayCoefficient-Parameter beeinflussen, welche Distanz zwischen den Boids
von dem Separation Behavior erzeugt wird. Auf der anderen Seite ist der eingehalte-
ne Abstand nicht nur von diesen beiden Werte abhängig, sonder z.B. auch von dem
Winkel der dazugehörigen Nachbarschaft und der Beschränkung der linearen Be-
schleunigungen. Wenn man diese beiden Parameter nicht berücksichtigt, können
gleichbleibende Werte von threshold und decayCoefficient in verschiedenen
Fällen unterschiedliches Verhalten hervorrufen.
Zusammengefasst lässt sich sagen, dass es keine „Patent-Rezepte“ für bestimmte
Verhalten gibt. Neben allen Parametern muss man auch die Implementierung be-
rücksichtigen, da diese entscheidet, wie die einzelnen Parameter gegenseitig Ein-
fluss aufeinander ausüben. Erfahrungsgemäß macht es demnach am meisten Sinn,
mit den verschiedenen Parametern einfach „herum zu spielen“, bis man das er-
wünschte Schwarmverhalten eingestellt hat.
55 von 65
8.3 Funktionalitäten der Simulation
Beim Starten der Simulation erscheint eine bestimmte Anzahl an Boids an zufälligen
Positionen im Raum. Diese haben unterschiedliche Orientierungen und Geschwin-
digkeiten, weshalb man zu Beginn kein Schwarm, sondern nur eine chaotische Boid-
Menge sieht. Nach einer relativ kurzen Zeit, wenn sich die Boids ein wenig bewegt
haben, kann man die ersten kleinen Schwärme sehen, die sich nach und nach zu ei-
nem großen Schwarm zusammenfügen. Abbildung 15 beinhaltet einige Screenshots
der Simulation, die nacheinander mit einigen Sekunden Zeitunterschied aufgenom-
men wurden. a) zeigt die Boids direkt nach dem Starten der Simulation und d) den
Status nach ca. einer halben Minute.
56 von 65
Abbildung 15: Die verschiedenen Stadien der Schwarmbildung nach dem Starten der Simulation
a) b)
c) d)
Die Simulation läuft innerhalb eines Würfel förmigen Raumes ab, welcher zusammen
mit einem Koordinatensystem durch einfache Linien dargestellt wird. Zu Beginn der
Implementierung erschienen Boids, die den Würfel durch eine Seite verließen, auf
der genau gegenüberliegenden Seite. Dadurch entstand allerdings neben einem un-
endlichen Raum auch oft eine monotone Bewegung des Schwarms in nur eine Rich-
tung. Eine bessere Variante ist das Einfügen eines weiteren Steering Behaviors, das
die Boids zurück in den Würfel treibt, sobald sie diesen verlassen. Dadurch ergibt
sich wesentlich mehr Dynamik in der Schwarm-Bewegung. Abbildung 16 zeigt beide
Fälle.
Der Title dieser Arbeit verspricht eine Simulation von Schwarmverhalten, die interak-
tiv sein soll. Noch vor dem Implementieren stand fest, dass eine Interaktionsmöglich-
keit ein Head-Up-Display (HUD) sein soll, mit dem man die verschiedenen Parameter
des Algorithmus verändern kann. Das HUD wurde zusätzlich in zwei Teile unterteilt.
Rechts befinden sich alle Buttons und Eingabefelder, mit denen sich die Parameter
einstellen lassen und links befinden sich die Anzeigen verschiedener Stoppuhren, die
die Dauer bestimmter Berechnungen messen. Diese Stoppuhren wurde eingeführt,
um die verschiedenen Versuche, die im Abschnitt 7.2 Ermitteln der Nachbarschaften
57 von 65
Abbildung 16: Zwei verschiedene Möglichkeiten, mit "Raumwänden" umzugehen
a) Unendlicher Raum b) Steering Behavior
dargestellt wurden, durchzuführen. Das HUD wurde mit dem OSG NodeKit
osgWidget implementiert.
Für eine weitere Interaktionsmöglichkeit erschien das Steuern eines bestimmten
Boids als interessant. Für diesen Zweck benötigte man zunächst die Möglichkeit, ein
bestimmtes Boid anzuklicken und dadurch auszuwählen. Man erkennt, dass ein Boid
ausgewählt ist, daran, dass die Nachbarschaften dargestellt und die dazugehörigen
Nachbarn markiert werden (s. Abbildung 17). Diese Funktion hat zusätzlich den Vor-
teil, dass man während des Implementierens eine visuelle Rückmeldung bekommt,
wenn man verschiedene Versuche mit den Nachbarschaften durchführt.
Nachdem man ein Boid ausgewählt hat, soll man es wie bereits erwähnt auch steu-
ern können. Dafür wurde in frühen Simulationsversionen ein weiteres Steering Be-
havior eingefügt, das das Boid entsprechend der gedrückten Pfeil-Tasten bewegen
lässt. Leider erwies sich diese Variante als schwer steuerbar, was auch mit der
schlechten Tiefenwahrnehmung bei dem Betrachten der Simulation zusammenhing.
Aus diesem Grund wurde das Steering Behavior wieder entfernt und eine andere
58 von 65
Abbildung 17: Visualisierung der Nachbarschaften und Markierung der in ihnen enthaltenen Nachbarn
Steuerungs-Methode in Betracht gezogen. Diese konnte aus Zeitgründen nicht mehr
implementiert werden, weswegen man im Abschnitt 10 Ausblick nähere Information
zu ihr findet.
Neben dem Beeinflussen des Schwarmverhaltens oder einzelner Boids kann der Be-
nutzer der Simulation auch die Visualisierung beeinflussen. Per Tastendruck kann
man die Sichtbarkeit des HUDs, des Raumes und des Koordinatensystems an- und
ausschalten. Zusätzlich lässt sich – wie es bei allen OSG Applikation standardmäßig
der Fall ist – der Raumwürfel mittels der Maus drehen, vergrößern und verkleinern.
Da es wie bereits erwähnt schwer ersichtlich ist, in welcher Tiefe sich die Boids befin-
den, wurde außerdem die Möglichkeit implementiert, in eine anaglyphische 3D-Dar-
stellung umzuschalten.
59 von 65
9 Zusammenfassung
In dieser Arbeit wurde gezeigt, wie man eine interaktive Simulation von Schwarmver-
halten entwickeln kann. Es wurden die dazu nötigen theoretischen Grundlagen er-
klärt, wozu die Steering Behaviors und das Prinzip der Nachbarschaften gehören.
Die von Craig Reynolds vorgeschlagenen Parameter wurden untersucht und entspre-
chend verändert, da sie nicht das gewünschte Ergebnis brachten. Es hat sich ge-
zeigt, dass es keine „Patent-Rezepte“ für bestimmte Schwarmverhalten gibt, sondern
dass in jeder Simulation die optimalen Parameter neu bestimmt werden müssen.
Zusammen mit den Nachbarschaften wurde auch die Suche bzw. die Berechnung
ebendieser eingehender betrachtet. Es wurde gezeigt, dass diese Berechnung aus-
schlaggebend für die Leistungsfähigkeit der gesamten Simulation ist. Da die einfache
Brute Force Methode nur für relativ wenig Boids ausreicht, wurde eine zweite Metho-
de vorgestellt, nämlich die Binning Methode. Ihre Laufzeitabhängigkeit wurde näher
betrachtet und es wurde versucht, sie experimentell zu bestimmen. Jedoch ist dieses
Vorhaben nach mehreren Versuchen nicht gelungen, weswegen es aus mangelnder
Zeit aufgegeben wurde. Unabhängig davon hat es die Binning Methode ermöglicht,
die Simulation mit weit mehr Boids laufen zu lassen als mit der Brute Force Methode.
Im Anschluss wurde erläutert, wie die Simulation implementiert wurde. Das beinhal-
tete u.a. die verwendete Bibliothek OpenSceneGraph und die zum Implementieren
verwendete Vorgehensweise. Es wurde betont, dass neben dem eigentlichen Imple-
mentieren das Einstellen der Parameter überraschend viel Zeit einnahm. Anschlie-
ßend wurde die Simulation mit ihren einzelnen Funktionalitäten vorgestellt, wobei der
Fokus auf den Interaktionsmöglichkeiten lag.
Zusammengefasst hat sich gezeigt, dass sich die zunächst recht einfache Aufgaben-
stellung, einen bereits bestehenden Algorithmus zu implementieren, im Nachhinein
als sehr zeitaufwändig erwies. Es stand noch eine Vielzahl an weiteren Funktionalitä-
ten zum Implementieren bereit, die aus Zeitmangel nicht mehr in die finale Simulation
mit aufgenommen werden konnten und deswegen im nächsten Abschnitt 10 Ausblick
60 von 65
beschrieben werden. Nichtsdestotrotz konnte die Aufgabe, eine interaktive Simulati-
on von Schwarmverhalten zu entwickeln, in der vorgeschriebenen Zeit bewältigt wer-
den.
61 von 65
10 Ausblick
Für die Entwicklung der Simulation stand leider nur begrenzt Zeit zur Verfügung.
Während der Implementierung und größtenteils danach sind einige interessante Ide-
en aufgekommen, die Teile der Simulation verändert oder womöglich gar verbessert
hätten. Diejenigen Ideen, die es aus Zeitgründen nicht mehr die finale Simulation ge-
schafft haben und noch nicht in den obigen Abschnitten erwähnt wurden, werden hier
absatzweise aufgelistet.
Eine Funktionalität der Simulation ist das mögliche Umschalten auf den
anaglyphischen 3D-Modus. Dieser wurde wie bereits erwähnt deswegen eingeführt,
weil man bei der normaler Darstellung sehr schwer feststellen kann, in welcher „Tie-
fe“ sich die Boids befinden. Passend dazu könnte man auch die Steuerung „dreidi-
mensional“ machen, indem man z.B. mittels einer Tiefenkamera wie die Microsoft
Kinect Handgesten im Raum erfasst. Anhand dieser Gesten könnte sich der
Schwarm jeweils anders bewegen, z.B. der Hand folgen. Eine komplexere Gestener-
kennung könnte es ermöglichen, verschiedene Parameter wie z.B. die maximale Ge-
schwindigkeit mit der Hand zu steuern.
Des Weiteren wäre es interessant, eine State Machine zu implementieren, die ver-
schiedene „Gemütszustände“ des Schwarms verkörpert. Damit diese Zustände für
den Betrachter sichtbar sind, sollte sich das Schwarmverhalten diesen Zuständen
anpassen. Das bedeutet, dass die Zustände durch verschiedene Werte der einzel-
nen Parameter wie Gewichtungen, maximale Beschleunigung u.ä. beschrieben wer-
den. Durch die verschiedenen Werte ergeben sich verschiedene Verhalten, die vom
Entwickler mit Worten wie „ängstlich“ oder „gelassen“ betitelt werden können.
Neben dieser Vergrößerung der Verhaltens-Vielfalt könnte man auch die Anzahl an
Schwärmen vergrößern. Diese könnten miteinander interagieren, sodass z.B. drei
Schwärme eine Nahrungskette bilden, wobei ein Glied immer das nächste verfolgt
und frisst. Dementsprechend würde dieses Glied vor dem vorherigen fliehen. Das
62 von 65
letzte könnte sich von den „kompostierten Überresten“ toter Tiere ernähren. Mit die-
sen Regeln hätte man auf einfache Weise ein rudimentäres Ökosystem erschaffen.
Gerade bei einer Simulation von Tieren, die real wirken soll, muss man auch andere
Kräfte als die Steering Behaviors für Boids beachten. Bei Vögeln z.B. wirkt die Gravi-
tation und der Wind. Dabei kann man auch den Flügelschlag mit einbeziehen. Bei
kleinen Vögeln steigt der Vogel abrupt auf, wenn er mit den Flügeln schlägt, und
sinkt genau so schnell ab, wenn er damit aufhört. Daraus resultiert eine Bewegung
ähnlich der eines hüpfenden Balls. Diese ließe sich hervorragend durch zusätzliche
Steering Behaviors implementieren. Zudem neigen sich Vögel, wenn sie eine Kurve
fliegen. Eine Implementierung dieser Neigung wäre für eine realistischere Simulation
unerlässlich.
Im Zusammenhang mit den komplexeren Kräften, die ein realistischeres Verhalten
ergeben würden, könnte man einem Tier auch ein realistischeres Aussehen geben.
Dazu sind aufwändigere Modelle nötig, mit entsprechender Textur und dazugehöri-
gen Animationen, wie z.B. dem Flügelschlag.
Neben einer aufwändigeren Darstellung der Tiere würde die Simulation ebenfalls an-
sprechender aussehen, wenn die GUI aufwändiger gestaltet wäre. Zusätzlich zu vie-
len grafischen Details wären auch einige weitere Funktionalitäten von Vorteil. Bei-
spielsweise könnte man die GUI derartig erweitern, dass man die verschiedenen Pa-
rameter eines angeklickten Boids einsehen und verändern kann. Für Testreihen wäre
es außerdem sinnvoll, die GUI noch weiter von den Kernfunktionalitäten zu trennen.
Erst dann könnte man z.B. mit entsprechenden Skripten Testreihen automatisieren.
In diesem Zusammenhang könnte man dann auch Sets von Parametern speichern
und laden, was für das Einstellen eines gewünschten Schwarmverhaltens sehr vor-
teilhaft wäre.
Während der Ausführungen über das Laufzeitverhalten der Binning Methode wurde
erläutert, dass für große Boid-Anzahlen die Berechnung der Nachbarschaften den
Großteil der gesamten Berechnungszeit benötigt. Die Aktualisierung der internen Da-
63 von 65
tenstruktur hingegen benötigt eine vergleichsweise verschwindende Berechnungs-
zeit. Dementsprechend könnte man die Suche der Nachbar-Boids z.B. nur alle fünf
Frames durchführen, während die Aktualisierung jeden Frame durchgeführt wird. In
diesem Fall würde der Schwarm in fünf gleichgroße Gruppen unterteilt werden und
die Nachbarschaften der Boids aus der ersten Gruppe werden im ersten Frame ak-
tualisiert, die der zweiten Gruppe im zweiten Frame, usw. Dadurch würde sich wahr-
scheinlich ein nahezu identisches Schwarmverhalten ergeben, jedoch nur mit einem
Fünftel der Berechnungszeit. Diese Annahme basiert auf der Beobachtung, dass sich
die Nachbarn über relativ lange Zeitspannen kaum verändern, sobald sich der
Schwarm in seinem Verhalten „eingefunden“ hat. Zusätzlich lassen sich Teile des Al-
gorithmus noch auf die GPU verlagern, wodurch man noch mehr Boids in die Simula-
tion mit einbinden könnte.
64 von 65
Literaturverzeichnis[1]: Reynolds, C.W., Flocks, Herds, and Schools: A Distributed Behavioral Model,
1987
[2]: Reynolds, C.W., Boids - Background and Update, Stand 21.3.2013, http://www.red3d.com/cwr/boids/
[3]: Reynolds, C.W., Steering Behaviors For Autonomous Characters, 1999
[4]: Millington, Ian; Funge, John, Artificial Intelligence for Games, 2009
[5]: Bobic, Nick, Rotating Objects Using Quaternions, Stand 4.4.2013, http://www.gamasutra.com/view/feature/131686/rotating_objects_
using_quaternions.php
[6]: Mattioli, Sandro, Die unbekannten Flugobjekte , Stand 10.4.2013, http://www.sandromattioli.de/component/content/article/35-
journalismus-kategorie/142-die-unbekannten-flugobjekte-artikel
[7]: Wang, Rui; Qian, Xuelei, OpenSceneGraph 3.0, 2010
[8]: Shiffman, Daniel, The Nature Of Code - Simulating Natural Systems With
Processing, 2012
65 von 65
