Schwarm II
Simulation des Schwarmverhaltens
Schwarmbildung - Schwarmverhalten
Version 2.02
Frank Vollbrecht, Büttgen,
2015
Bildung von Schwärmen
Vorwort
zu Version 2
In
Version 2 werden erweiterte Steuerungsmöglichkeiten und Variablen in einem Applet über die
Bedienoberfläche zugänglich gemacht, mit denen die Schwarmbildung verändert
werden kann. Bereits in Version 1 konnte man die Größe des Schwarms festlegen
(zwischen 100 und 2000 Individuen) und auf Basis einer festen
Nachbarschaftsbeziehung mit bis zu 7 Nachbarn die Schwarmbildung verfolgen.
Einstellbar war bereits auch die Berücksichtigung der Bewegungsrichtung der
Nachbarschaftsgruppe.
Bei
Version 2 kann das in Version 1 noch beschränkte Gesichtsfeld der
Individuen von 90 Grad auf eine Rundumsicht von 360 Grad erweitert werden.
Hiermit wird eine Annäherung an einige Tiere vorgenommen, die ebenfalls ein
sehr großes Sichtfeld besitzen (z.B. Fische oder Antilopen). Für die
Schwarmbildung kann auch die in Version 1 fest voreingestellte Zahl von 7
Nachbarn zur Bildung einer Nachbarschaftsgruppe variiert werden. Durch diese in
der Bedienoberfläche einstellbaren variablen Größen können die
unterschiedlichen Formen der Schwarmbildung und des Schwarmverhaltens in einer
Simulation aufgezeigt werden.
Schwarm II - Simulation des Schwarmverhaltens
1. Einstellen
der Schwarmoptionen
2. Fähigkeiten
der Schwarmindividuen
6. Allgemeine
Angaben und Beobachtungen
7. Schlussfolgerungen,
Ziele, Seiteneffekte
Kurzfassung
Beschrieben wird das Schwarmverhalten durch eine Softwaresimulation auf der Basis einfacher gesetzter Regeln. Hierbei kann die Bildung von Schwärmen verschiedener Größen simuliert und beobachtet werden. Es werden virtuelle Kleinstlebewesen durch kleine rote Striche mit 2 Pixeln dargestellt, die sich auf dem Bildschirmausschnitt auf dem dort durch die Bildpunkte vorgegebenen Rasteruntergrund auf der 2-dimensionalen Ebene bewegen. Die Kleinstlebewesen besitzen einen optischen Sinn, über den sie ihre Artgenossen wahrnehmen können. Im gewissen Sinne handelt es sich um 1-dimensionale Lebewesen in einer 2-dimensionalen Welt. Über verschiedene Steuerungen können die Schwarmgröße und andere Beeinflussungen verändert werden. Zur Darstellung des Schwarmes können verschiedene Darstellungsarten gewählt werden, die das Schwarmverhalten besser sichtbar machen als die reinen Bewegungen der virtuellen Kleinstlebewesen, z.B. durch Darstellung der von den Kleinstlebewesen gezogenen Spuren/Pfade. Die Größe der Individuen mit nur 2 Pixeln erlaubt es, ein möglichst großflächiges Schwarmverhalten mit vielen Individuen zu simulieren.
Inbetriebnahme
Die Software ist Bestandteil der Website Opartandmore.de. Sie kann unter folgendem Link im Webbrowser aktiviert werden:
http://www.opartandmore.de/interferenzen/dfschwarm.htm
Voraussetzung für die Inbetriebnahme der Software ist die einmalige vollständige Aktivierung von JAVA-Applets in den Browser-Einstellungen sowie von JavaScript. Für die Aktivierung von JAVA muss von Oracle das JAVA-Plugin in den Browser geladen werden. Als Folge der Sicherheitsrisiken bei der Verwendung von JAVA-Applets im Browser besteht dann die Notwendigkeit, über das JAVA-Control-Panel in der Windows-Systemsteuerung, den Zugang zu der Website http://www.opartandmore.de zuzulassen:
Abbildung 1 JAVA-Control-Panel Einstellungen
Für dieses JAVA-Applet besteht kein Sicherheitszertifikat, weswegen die oben gezeigten einmaligen Einstellungen erforderlich werden. Nach Vornahme dieser Einstellungen lässt sich das JAVA-Applet im Browser aktivieren. Der Internet-Explorer verlangt nach der Aktivierung allerdings weitere Bestätigungen, dass man die „Ausführung geblockter Inhalte“ zulassen möge und verlangt wie auch Chrome und Firefox die Quittierung unsignierter Anwendungen:
Abbildung 2 Nachfrage des Internet Explorers
Nach Betätigen des „Ausführen“-Buttons wird dann der Start des JAVA-Applets vom Browser zugelassen:
Abbildung 3 JAVA-Applet Schwarm: Darstellung inkl. Bedienfeld (rechts)
In den folgenden Abschnitten 1 – 4 werden die Einstellungsoptionen des Applets und deren Auswirkungen sowie Bildbeispiele als Folge der wählbaren Darstellungsvarianten beschrieben. Abschnitt 5 zeigt die hier gewählten und über die Software auch modifizierbaren Schwarmregeln, durch die das hier gezeigte Schwarmverhalten entsteht. In Abschnitt 6 werden Beispiele und Bildfolgen des Schwarmverhaltens dargestellt, im Abschnitt 7 werden Hinweise zu offenen Fragestellungen aufgezeigt, die sich auch durch spätere Untersuchungen durch entsprechende Softwareerweiterungen klären ließen.
Für weitergehende Detailuntersuchungen eines einzelnen Schwarmindividuums kann im JAVA-Applet auch eine TRACE-Funktion aktiviert werden, die später erläutert wird. Hierzu empfiehlt es sich, zusätzlich für den Browser die JAVA-Konsole über das JAVA-Control-Panel in der Systemsteuerung dort unter „erweitert“ zu aktivieren sowie auch die Status-Zeile des Browsers einzuschalten.
1. Einstellen der Schwarmoptionen
Als Menüpunkt ist die Zahl der Schwarmindividuen über eine Auswahlbox (siehe Abb. 3) einstellbar. Minimal sind 100 Individuen, maximal 2000 Individuen einstellbar. Nach Auswahl werden die Individuen über Zufallszahlen auf dem Bildschirmfenster platziert.
Über Auswahlfelder können verschiedene Optionen eingestellt werden:
Speed: Vorgabe zum Geschwindigkeitsvermögen der Individuen. Die vom Individuum gewählte Geschwindigkeit hängt dann von der Nachbarschaftsumgebung ab (siehe unten bei Schwarmregeln). Sofern Speed nicht angekreuzt wurde, wird bei jedem Verarbeitungsschritt 1 Bewegungsschritt (Step) von 1 Pixel durchgeführt (siehe auch Abb. 4).
Gradient: Vorgabe zur Bewegungsrichtung der Individuen im Vergleich zu Nachbarindividuen. Bei Auswahl dieser Option Gradient wird zur Entscheidung der nächsten Bewegungsrichtung und ggf. auch der Geschwindigkeit die Bewegung von Nachbarindividuen herangezogen. Ohne Auswahl dieser Option wird lediglich ein gemeinsamer Schwerpunkt von Nachbarindividuen beim nächsten Bewegungsschritt berücksichtigt.
Rand: Berücksichtigung des Bildschirmfensters als Grenze. Ohne diese Beschränkung können Individuen das Fenster verlassen. Bei Überschreitung der Begrenzung erfolgt eine Spiegelung des Individuums an der gegenüberliegenden Fensterkante, so dass der Schwarm immer dieselbe Größe aufweist.
Die Bewegungsabläufe werden nacheinander schrittweise (hier Step genannt) durchgeführt. Die Zahl abgelaufener Steps (Zeitschritte) wird in der Status-Zeile des Browsers angezeigt, sofern diese Option in den Einstellungen des Browsers aktiviert wurde. Hiermit lässt sich das Zeitverhalten des Schwarms messen.
Über die Auswahlbox Nachbarn (siehe Abb. 3) kann die maximale Größe der Nachbarschaftsgruppe vorgegeben werden, die das jeweilige Individuum nutzt, um seine eigene Bewegungsrichtung einzustellen. Bei einem Wert von beispielsweise 30 wird von bis zu 30 Nachbarn der Schwerpunkt oder bei Einstellung des Gradienten eine gemittelte Bewegungsrichtung als Vorgabe für das eigene Bewegungsziel des Individuums verwendet. Als Voreinstellung sind 7 Nachbarn eingestellt, die aus Sicht des Individuums eine Nachbarschaftsgruppe bilden, an der sich die eigene Bewegung orientieren soll. Als Extremfall kann als Wert auch 1 angegeben werden, woraus sich ergibt, dass die eigene Bewegungsrichtung dann nur von einem einzigen Nachbarn abhängt. Bisweilen führt das dazu, dass sich zwei Nachbarn eine Zeitlang gegenseitig umkreisen.
Als weitere Auswahl kann man das Sichtfeld der Individuen festlegen (siehe Abb. 3). Die Voreinstellung ist 90 Grad, was bedeutet, dass das Individuum zur Bildung von Nachbarschaftsgruppen nur die Nachbarn heranzieht, die sich vor dem Individuum in Bewegungsrichtung in einem Sichtfeld von 90 Grad aufhalten (siehe auch Blickfeld in Abb. 4). Bei einer Einstellung von 360 Grad erfährt das Individuum eine Rundumsicht, was auch dazu führen kann, dass der Schwerpunkt der Nachbarschaftsgruppe sich in Bewegungsrichtung hinter dem Individuum befindet.
2. Fähigkeiten der Schwarmindividuen
Jedes virtuelle Lebewesen besitzt folgende Eigenschaften:
· Blickrichtung nur nach vorn mit einer Blickwinkelweite von 45 Grad nach rechts und links bzw. nach vorn und alternativ eine Rundumsicht von 360 Grad in Abhängigkeit durch die gewählte Einstellung im Bedienfeld (siehe Abb. 3). In diesem Kontext wird keine Unterscheidung zwischen Gesichtsfeld und Blickfeld sowie Blickwinkel oder Sichtfeld vorgenommen. Die Begriffe werden hier synonym verwendet, da die Physiologie der Augen hier keine Bedeutung hat.
· Blickweite 200 Rasterlinien nach vorne. Das Gesamtfenster besitzt eine Ausdehnung von 550x550 Rasterlinien (Bildpunkten).
· Zielpunkte bei der Abschätzung der Bewegungsrichtung einer Gruppe von Nachbarindividuen werden bei Auswahl der Option Gradient auf 50 Bildpunkte extrapoliert (siehe auch Gradientenregeln)
· Bewegungsrichtungen pro Rasterlinie bzw. pro Step: 45 Grad links, 0 Grad vorwärts, 45 Grad rechts
· Bewegungsgeschwindigkeit 1 Rasterlinie pro Step (Ausnahmen bei aktivierter Option Speed werden unten erläutert )
Abbildung 4 Schrittweise Bewegungen (steps)
Das
Bild zeigt in stark vergrößerter Darstellung die Bewegungsmöglichkeiten eines
Individuums in mehreren Steps auf der 2-dimensionalen
Rasterfläche. Für den 1. und 2. Step sind alle
Bewegungsmöglichkeiten angegeben. Step 3 und 4 werden
aus Gründen der Übersichtlichkeit jeweils ausgehend von nur einem
Vorgängerpunkt dargestellt. Mit 4 Steps kann ein
Individuum eine Kehrtwendung vollführen. Für Step 1
ist auch das nach vorn gerichtete Blickfeld angedeutet, das sich aus den zwei
45 Gradwinkeln zusammensetzt. Bei Aktivierung von Speed (siehe unten) können Step 1 und 2 zu einem Step
verknüpft werden. Eine Kehrtwendung kann dann in 2 Steps
vollzogen werden.
3. Steuerungsfunktionen
Zur besseren Verfolgung des Geschehens kann über die Steuerungs-Buttons im Bedienfeld (siehe Abb. 3) auf den Ablauf und die Darstellung eingegriffen werden:
Stop: Der Ablauf wird angehalten. Statisches Bild.
Step: Es wird lediglich der nächste Step durchgeführt, anschließend wird der Ablauf wieder angehalten.
Restart: Der Standardablauf wird reaktiviert.
Trace: Von einem Individuum wird der Wahrnehmungsraum dargestellt:
Hierbei werden die in Blickweite und im Blickwinkel gefundenen nächsten Nachbarn, hier Nachbarschaftsgruppe genannt, durch schwarze Verbindungslinien markiert.
Bei Auswahl der Option „Gradient“ werden auch die Bewegungsrichtungen der einzelnen Mitglieder der Nachbarschaftsgruppe durch graue Linienstücke angezeigt.
Der Schwerpunkt der Nachbarschaftsgruppe wird durch ein grün gefülltes Quadrat angezeigt.
Die Richtung des Geschwindigkeitsgradienten der Nachbarschaftsgruppe wird durch eine grüne Linie ausgehend vom Schwerpunkt der Nachbarschaftsgruppe dargestellt.
Ein schwarzes Quadrat um das überwachte Individuum zeigt an, dass derzeit keine Nachbarschaftsgruppe erkannt wird.
Der cyan/blaue Richtungsanzeiger gibt die für einen Step eingeschlagene Bewegungsrichtung wieder.
Die Vergangenheitsspur des Individuums wird durch eine cyan-farbene Linie angezeigt.
Das große rote Quadrat zeigt den Schwerpunkt des gesamten Schwarms an.
Das kleine rote Quadrat zeigt den Bildmittelpunkt an.
Kleine grün ausgefüllte, unbewegliche Quadrate zeigen Kollisionsstellen an, bei denen der Mindestabstand zwischen Individuen unterschritten wurde.
Die Auswahl von „Trace“ zur Verfolgung der Wahrnehmung eines Individuums ist bei einer großen Individuenzahl schwieriger, da die grafischen Informationen schnell überschrieben werden. Hier empfiehlt es sich, die Schwarmgröße möglichst klein zu halten. In der Java-Console werden weitere Angaben zur Wahrnehmung und Entscheidungsfindung des ausgewählten Individuums ausgegeben.
Reset: Entfernen aller Trace-Anzeigen und Kollisionsorte, Wiederherstellung der Standarddarstellung.
Abbildung 5 Trace-Darstellung für 1 ausgewähltes Individuum (Ausschnitt)
4. Darstellungsarten
Im Auswahlfeld Darstellung (siehe Abb. 3) können 5 verschiedene Sichten auf den Schwarm eingestellt werden, mit denen das Schwarmverhalten unterschiedlich dargestellt wird. Da die Website Opartandmore Kunst als einen Schwerpunkt zum Thema hat, berücksichtigen die Darstellungen auch den optisch künstlerischen Eindruck.
In der Standardeinstellung werden die virtuellen Kleinstlebewesen durch 2 rote Pixel dargestellt. Durch die Bewegungsabfolgen und auch die Aufzeichnung der zurückgelegten Pfade ist trotz dieser Kleinheit erkennbar, wo das Vorderteil und Hinterteil dieser Lebewesen liegen. Zurückgelegte Pfade werden durch gelbe, langsam verblassende Strichspuren sichtbar gemacht.
Abbildung 6 Standarddarstellung
mit 500 Individuen nach ca. 250 Steps
(ohne Gradient) und 90 Grad Sichtfeld
Nach Auswahl der Darstellung „Pfade“ wird der historische Pfadverlauf der Individuen intensiver hervorgehoben wird, so dass sich die Schwarmbewegung als Ganzes besser verfolgen lässt. Dunkle Pfadlinien sind bei dieser Darstellungsart älter. Aus Gebieten mit vielen dunklen Liniensignaturen zieht sich der Schwarm zum Betrachtungszeitpunkt überwiegend zurück. Nach jeweils ca. 250 Steps werden die dunklen Pfadlinien entfernt.
Abbildung 7 Darstellung mit hervorgehobenen Pfaden
500 Individuen nach ca. 400 Steps (ohne Gradient), Sichtwinkel 90 Grad
Diese Darstellungsart zeigt also einen Blick in die Vergangenheit der Schwarmbewegung (vergleiche die dunklen Strukturen hier im Bild nach 400 Steps mit den hellen Strukturen bei dem Darstellungsbeispiel oben in Abb. 6 nach 250 Steps, dort mit den hellen Strukturen) und gleichzeitig den aktuellen Schwarmzustand.
Bei der Auswahl der Darstellung „Richtungen“ wird zusätzlich die aktuelle Bewegungsrichtung der Lebewesen hervorgehoben. Hierbei werden die rot dargestellten virtuellen Lebewesen in Längsrichtung überproportional groß symbolisiert.
Abbildung 8 Anzeige der Bewegungsrichtungen
Hervorgehobener Anzeige der Bewegungsrichtungen, wie
vorher bei Abb. 7 aber nach ca. 600 Steps
Die oben gezeigte Folge der 3 Bilder mit verschiedenen Darstellungsarten auf Basis eines Schwarmes mit einer einheitlichen Größe von 500 Individuen und einer Zeitfolge von 250, 400 sowie 600 Steps zeigt auch deutlich die Veränderungsprozesse bei der Strukturbildung im Schwarm.
Bei der Darstellungsart „nur Pfade“ werden ausschließlich die Pfade ohne Individuen dargestellt.
Abbildung 9 Reine Pfaddarstellung ohne Individuen
Reine Darstellung der Pfade, wie vorher in Abb. 8 aber
nach ca. 1.000 Steps
Bei der Darstellungsart „Beziehungen“ werden die Sichten zwischen allen Individuen gleichzeitig dargestellt. Insbesondere bei kleinen Schwärmen und kleiner Zahl von Nachbarn kann man das Beziehungsgeflecht zwischen den Individuen ablesen. Die Individuen werden jetzt als Quadrate dargestellt, wobei die Größe bläulicher Quadrate die Größe der Nachbarschaftsgruppe widerspiegelt. Kleine rote punktförmige Quadrate stellen Individuen dar, die momentan keine Nachbarn für ihre Eigenbewegung verwenden können (z.B. wenn sich alle Nachbarn außerhalb des Sichtfelds aufhalten). Die Querbeziehungen zwischen den Individuen werden außerdem durch Verbindungslinien angezeigt.
Abbildung 10 Nachbarschaftsbeziehungen
mit 100 Individuen, 90 Grad Sichtfeld und max. 7
Nachbarn in einer Nachbarschaftsgruppe
Unterschiedliche Einstellungen bei der Zahl der Nachbarn in einer Nachbarschaftsgruppe oder auch die Änderung des Sichtfeldes führen auch zu sehr unterschiedlichen Nachbarschaftsbeziehungen. Bei dieser Darstellung lässt sich beispielsweise erkennen, welche Individuen frei davon sind, dem Schwarm zu folgen und eigene Wege einschlagen können, aber auch welche Schwarmindividuen diesen Ausreißern folgen, wodurch neue Schwarmstrukturen gebildet werden können.
Die beiden letzten Darstellungsarten lassen auch eine künstlerische Ansicht zu. Durch Schieben des Mauszeigers in das Bild werden Hintergrundfarben und –effekte generiert, die das Aussehen in künstlerischer Form verändern, aber gleichzeitig auch durch Schummerung den historischen Ablauf der letzten Steps in einer animierten Grafik hervorheben (siehe Abb. 11).
Abbildung 11 Künstlerische Darstellung von Abb. 10
5. Schwarmregeln
Die virtuellen Lebewesen müssen folgende Regeln einhalten, die auf den von Craig Reynolds aufgestellten Schwarmregeln (Separation, Köhäsion und Alignment) basieren. Die weiteren hier eingeführten Regeln wie Stillstandsregel, Begrenzungsregel oder Geschwindigkeitsregel, aber auch die Vorgabe der Extrapolation der Bewegung benachbarter Schwarmindividuen bei Auswahl der Option Gradient sind hier willkürlich gesetzt:
- Stillstandsregel: Stillstand ist nicht erlaubt.
- Begrenzungsregel: Meide Begrenzungen (Fensterkante; sie kann durch Weglassen der Rand-Option ausgeschaltet werden (siehe Abb. 3))
- Separation: Vermeide Kollisionen (eine Kollision wird im Bild durch ein grünes Feld angezeigt)
- Nachbarschaftsregel: Nehme Nachbarschaftsgruppe (max. 7 Individuen) im Blickfeld wahr
- Kohäsion und Alignment:
Ø folge dem arithmetischen Schwerpunkt der Nachbarschaftsgruppe
oder alternativ
Ø folge der Bewegungsrichtung des Nachbarschaftsgruppe (bei Einstellung der Option Gradient):
Gradientenregel: bei der Auswahl der Option Gradient (siehe Abb. 3) werden als fest eingestelltes Entfernungsmaß 50 Rasterlinien in Richtung des Gradienten vorgegeben, was ca. ¼ der Sichtweite der virtuellen Lebewesen entspricht
- Beharrungsregel: Falls keine der obigen Regeln greift, gehe geradeaus in Blickrichtung weiter und verharre bei dieser Bewegung
Sofern „Speed“ aktiviert ist, ergeben sich folgende Zusatzregeln für die Individuen, wobei die Erhöhung der Geschwindigkeit pro Step verdoppelt wird.
·
Geschwindigkeitsregeln:
Ø Erhöhung der Geschwindigkeit bei Kollisionsgefahr
Ø Erhöhung der Geschwindigkeit bei freier Sicht
Ø Erhöhung der Geschwindigkeit, falls Nachbarschaftsgruppe sich schnell bewegt
Die hier wiedergegebene Reihenfolge der Regeln gibt auch gleichzeitig die Stärke der Regeln wieder. Die oberen Regeln sind stärker als Untere.
Die Separationsregel wird in einem Algorithmus umgesetzt, bei dem in einem Rasterfeld von 10 x 10 Rastern (Pixeln) um das Individuum herum geprüft wird, ob sich ein oder mehrere andere Individuen innerhalb dieses Feldes befinden. Gegenüber dem Nachbarindividuum mit der dichtesten Annäherung wird eine Richtung eingeschlagen, die am weitesten von diesem wegführt. Dabei wird auch die Bewegungsrichtung des Nachbarindividuums berücksichtigt. Bei Entscheidungsvarianten, die mehr als 1 gleichwertige Bewegungsrichtung zulassen, erfolgt eine Zufallsentscheidung für die neu einzuschlagende Richtung. Sofern die Option Speed aktiviert ist, wird bei einem Pixelabstand von weniger als 3 Rasterelementen die Geschwindigkeit des Individuum erhöht, d.h. es wird in einem 2. Step erneut versucht, einen größeren Abstand vom Nachbarindividuum zu erzielen. Wenn als beste Lösung nur noch ein Rasterabstand von <= 1 ermittelt wird, kommt das einem Stillstand gleich, d.h. dann wird die Stillstandsregel verletzt. Verletzungen der Stillstandsregel werden durch eine grüne Marke im Bild symbolisiert.
6. Allgemeine Angaben und Beobachtungen
Die Idee zu diesem Applet entstand als Anregung durch die TV-Sendung von 3SAT vom 1.9.2011 „Scobel – Schwärme, über kollektive Intelligenz“. In dieser Sendung diskutierte Gert Scobel mit seinen Gästen Jens Krause, Constanze Kurz und NielsWerber über Schwarmintelligenz. Dabei beschrieb Prof. Jens Krause die grundsätzlichen Eigenschaften kollektiver Intelligenz. Das dort von ihm erläuterte Regelwerk wurde in der oben genannten Form adaptiert und auf die oben definierte künstliche 2-dimensionale Welt der virtuellen Kleinstlebewesen angewandt.
Die folgenden Bilder zeigen Beispiele der Schwarmbildung bei Verwendung verschiedener Optionen.
Im ersten Beispiel Abb. 12 wird das Bild mit kleiner Individuenzahl (100) und nur max. 1 Nachbarn in der Nachbarschaftsgruppe gezeigt. Bei einem Sichtwinkel von 90 Grad und ohne Gradientenbildung kommt es kaum zu Schwarmverhalten, auch wenn sich einige Gruppen bilden, die aber nur lose zusammenhängen und sich schnell umbilden. Zwischen den einzelnen Individuen bestehen geringe Verbindungen.
Abbildung 12 a) Geringe Schwarmbildung und b) Nachbarschaftsbeziehungen
Auch bei einem Blickfeld von 360 Grad (Abb. 13) ergeben sich im Hinblick auf den optischen Eindruck der Spuren nur wenige Unterschiede. Die Beziehungen der Individuen untereinander sind aber andersartig, da sich hier jetzt Kleingruppen aus 2-4 Individuen bilden. Dieser Effekt verstärkt sich, wenn die Zahl der Nachbarn auf 2 gesetzt wird:
Abbildung 13 a) Nachbarschaftsbeziehungen mit 1 bzw. b) 2 Nachbarn (100 Individuen mit 360 Grad Blickfeld, ohne Gradientenbildung)
Aber bereits bei 2 Nachbarn bilden sich bei größeren Individuenzahlen großräumige Strukturen, wobei bei einem 90 Grad Sichtfeld größere Kreisstrukturen entstehen, die untereinander in Verbindung stehen, während sich bei einem 360 Grad Sichtfeld viele kleine Einzelschwärme bilden, bei denen nur ein geringer Austausch zwischen den Einzelschwärmen stattfindet. Allerdings entstehen hierbei bisweilen auch linienförmige Strukturen, die an Formationen beim Vogelflug erinnern (z.B. im rechten Teilbild in der linken oberen Ecke in Abb. 14b):
Abbildung 14 a) Vergleich zwischen 90 (links) und b) 360 (rechts) Grad Sichtfeld bei 1000 Individuen ohne Gradienten nach 200 Steps
Bei einer 3-dimensionalen Darstellung wäre zu vermuten, dass die Kreisstrukturen bei Abb. 14a sich zu kugelförmigen Gebilden ähnlich wie Blasen oder Globulen strukturieren würden. Bei einer Nachbarschaftsgruppe mit bis zu 30 Nachbarn und 1000 Individuen ergeben sich andere oder auch größere Strukturen:
Abbildung 15 a) Vergleich Nachbarschaftsgruppen zwischen 90 (links) und b) 360 (rechts) Grad Blickfeld bei jeweils 30 Nachbarn
Ein großer Unterschied besteht in der Geschwindigkeit der Strukturbildung bei großen Nachbarschaftsgruppen. Bei Abb. 15a links waren bei nur 90 Grad Blickwinkel 1000 Steps notwendig für die Ausbildung der großen kreisförmigen Strukturen mit dem zentralen Haufen, während sich die Strukturen rechts im Bild mit einem Blickwinkel von 360 Grad bereits nach 200 Steps bilden. Im Vergleich hierzu in Abb. 16 die Schwarmbildung mit nur 7 Nachbarn in einer Nachbarschaftsgruppe nach 200 Steps, die zeigt, wie schnell sich einzelne und relativ stabile Teilschwärme bilden (durch die dunklen Linien werden ausgehend vor einer Zufallsverteilung beim Start die Vergangenheitsspuren dargestellt):
Abbildung 16 Schwarmbildungen bei 360 Grad Blickfeld und 7 Nachbarn in einer Nachbarschaftsgruppe mit 1000 Individuen
Ein gänzlich unterschiedliches Schwarmverhalten stellt sich bei Anwendung der Alignmentregel (Gradientenbildung) dar Abb. 17). Erstaunlicherweise sind die Unterschiede zwischen dem Gesichtsfeld von 90 Grad und 360 Grad relativ gering. Ausgehend von einer Zufallsverteilung beim Start zeigt sich sehr schnell die Ausbildung gerichteter Schwarmstrukturen mit gemeinschaftlichen Richtungen einzelner Teilschwärme:
Abbildung 17 a) Alignmentregel (Gradient) links, b) Schwarmbeziehungen rechts
(100 Individuen bei 360 Grad Sichtweite und 270 Steps sowie 7 Nachbarn als Nachbarschaftsgruppe)
Abb. 17 zeigt den Verlauf der letzten 250 Bewegungsänderungen von insgesamt nur 280 Steps, wobei hier auch die Ausrichtung der Individuen hervorgehoben ist, die sich als sehr parallel in den einzelnen Teilschwärmen zeigt. Das rechte Teilbild (Abb. 17b)zeigt die zughörigen Beziehungen der Nachbarschaftsgruppen in den Teilschwärmen. Die Teilschwärme II und III haben sich kurz vorher getrennt. Der Teilschwarm III erhielt Zulauf durch Mitglieder von Teilschwarm II. Die Teilschwärme I und II sind weitgehend getrennt ebenso wie III und IV, auch wenn der Eindruck der Einsgerichtetheit im linken Teil der Abbildung vorherrscht.
Die Abb. 18. zeigt erstaunlicherweise ein ähnliches Schwarmverhalten auch bei 90 Grad Blickwinkel, wobei aber aus dem Beziehungsgeflecht im rechten Bild (Abb 18b) hervorgeht, dass wegen des eingeschränkten Gesichtsfeldes die Nachbarschaftsbeziehungen über erheblich größere Distanzen aufgebaut werden müssen:
Abbildung 18 a) Alignmentregel (Gradient) links und b) Schwarmbeziehungen (links) bei 90 Grad Blickwinkel
Die mit roten Pfeilen im rechten Teil von Abb. 18 markierten Individuen haben selbst keine Nachbarn mehr für die eigene Richtungswahl, da das Sichtfeld mit 90 Grad sehr eingeschränkt ist. Die Pfeile am linken Rand zeigen damit diejenigen Individuen an, die den Schwarm in eine bestimmte Richtung führen, ohne aber dass diese Richtung untereinander abgestimmt ist. Die Richtung der Individuen erfolgt dann durch die Beharrungsregel, die dazu führt, dass Teile des Schwarms diesen Individuen folgen.
Das Individuum „i“ (weiter oben im rechten Teil von Abb. 18b) zeigt, dass es nicht mehr vollständig zum Schwarm zugehörig ist, sondern selbst keine Nachbarn in seinem Blickfeld vorfindet. Das Individuum ist also gerade dabei, aus dem Schwarm auszubrechen. 30 Steps später ist die Trennung dann vollzogen, auch am linken Bildrand (rote Punkte) lösen sich weitere Individuen vom Schwarm (siehe Abb.19):
Abbildung 19 Ablösung von Individuen vom Schwarm
Das Verhalten von Ablösungen aus dem Schwarm mangels Nachbarn im Blickfeld findet bei einer Rundumsicht von 360 Grad nicht statt, da jedes Individuum auch seine rückwärtigen Nachbarn im Blickfeld hat. In Abb. 19 wurden die Schwarmbeziehungen aus Abb. 18 in eine 360 Grad Rundumsicht gewandelt, die zeigen, dass der Schwarm hierbei vollständig verbunden ist, wobei aber auf der linken Seite eine Aufspaltung des Schwarms in 2 Teilschwärme stattfindet (oben und unten). Die 3 roten Pfeile zeigen, dass die vorher bei 90 Grad Blickwinkel isolierten Individuen hier dagegen fest mit dem Schwarm verbunden sind:
Abbildung 20 Schwarmbeziehungen bei 360 Grad Blickwinkel als Gegenüberstellung zu Abb. 19
Das 360 Grad Blickfeld verhindert aber nicht, dass sich Teilschwärme bilden, die sich ablösen, wie Abb. 17 oder 20 zeigen.
Bei der Anwendung der Alignmentregel (Gradient) in Verbindung mit einem 360 Grad Blickfeld erfolgt die Schwarmbildung sehr schnell. Die Abb. 21 zeigt bei 1000 Individuen die Bildung mehrerer Teilschwärme bei weniger als 40 Steps (links):
Abbildung 21 a) Bildung von Teilschwärmen nach nur 36 Steps (links) und b) nach 450 Steps (rechts)
Das rechte Teilbild (Abb. 21b) zeigt auch die Neuorganisation der Richtungen der Schwarmindividuen, wenn Randberührungen stattfinden bzw. wenn sich 2 Teilschwärme treffen. Bei einem 360 Grad Blickwinkel erfolgen dann signifikant schnellere Neuausrichtungen der Teilschwärme gegenüber dem 90 Grad Blickwinkel. Die Abb. 22 zeigt die Neuausrichtung der Individuen bei 90 Grad Blickwinkel nach 180 Steps sowie den Verlauf der bisherigen Bewegungen beim Zusammentreffen von Teilschwärmen:
Abbildung 22 Langsamere Neuausrichtung bei 90 Grad Blickwinkel
7. Schlussfolgerungen, Ziele, Seiteneffekte
Wenn man die Alignmentregel nicht aktiviert (ohne Gradient), dann entsteht aber dennoch ein Schwarmverhalten, das sich durch weniger Dynamik aber durch andere Strukturen auszeichnet wie beispielsweise in Abb. 6. Da das Schwarmverhalten sich stark verändert, wenn man zusätzlich zur der Kohäsionsregel mit der Richtung auf den Mittelpunkt der Nachbarschaftsgruppe die Zielrichtung der Nachbarn verwendet (Alignment), kann man vermuten, dass in der Natur bei der Alignmentregel viele Varianten bestehen, die die Bewegungsentscheidungen des Individuums und damit des gesamten Schwarms beeinflussen. Die Alignmentregel hat offensichtlich gegenüber der Kohäsionsregel einen erheblichen Einfluss auf die Struktur von Schwärmen.
Bei der Alignmentregel (mit Gradientenbildung) bliebe zu untersuchen, welchen Einfluss die Extrapolation des Zielpunkts auf die Schwarmbildung und –bewegung hat. Die Unterschiede zwischen den hier voreingestellten 50 Bildpunkten (mit Gradient) und 0 Bildpunkten (ohne Gradient) sind derart massiv, dass man hier untersuchen könnte, welchen Einfluss dieser Extrapolationspunkt auf die Schwarmbildung und -bewegung sowie die zeitliche Abfolge hierzu (Zahl der Steps) hat. In einer späteren Softwareversion wird daher ggf. dieser Wert variabel einstellbar gemacht.
Insgesamt wäre weiter im Sinne virtueller Feldversuche zu untersuchen, welche funktionalen Abhängigkeiten sich bei der Schwarmbildung durch Verwendung verschiedener Parameter ergeben und ob es hierzu Entsprechungen bei natürlichen Schwärmen gibt. Vermutlich bestehen bei der Softwaresimulation mehrdimensionale Abhängigkeiten bei der Schwarmbildung zwischen der Zahl der Individuen, des Maßes des Gradienten, der Zahl der Steps und der Sichtweite. Zu untersuchen wäre auch, ob bei einem Gradienten von 0 die Sichtweite einen Einfluss auf den Durchmesser der entstehenden ringförmigen Gebilde (z.B. Abb. 6) hat. Zu untersuchen wäre auch, ob die funktionalen Abhängigkeiten linear verlaufen oder einer anderen mathematischen Funktion genügen und ggf. auf Schwellenwerten basieren. Dann wäre zu prüfen, ob sich die hier auf einer eingeschränkten 2-dimensionalen Ebene ablaufenden Prozesse zur Schwarmbildung auch in der 3-dimensionalen Realität im Tierreich finden lassen.
Als Besonderheit der Programmierung ist noch die Randbegrenzung zu beachten. Die Wahrnehmung der Individuen ist bezüglich der Randbegrenzungen ebenfalls begrenzt. Auch bei der Aufhebung der Randbegrenzung wird die Wahrnehmung auf die durch das Bildschirmfenster begrenzte Fläche eingegrenzt, d.h. die Individuen nehmen keine Individuen außerhalb des Bildschirmfensters wahr. Dies gilt auch, wenn die Randbegrenzung im Bedienfeld Rand (siehe Abb. 3) abgestellt ist und der Rand keine Grenze für die Bewegung der Individuen mehr darstellt. Diese Vorgehensweise wurde wegen des geringeren Programmieraufwands gewählt. Hierdurch treten vermutlich Seiteneffekte auf, die bei natürlichem Schwarmverhalten anders ablaufen können.
Als weitere Besonderheit resultieren Bewegungen und Distanzen der Individuen aus der gewählten Form der Rasterverarbeitung, was sich durch gestreckte Form und höhere Geschwindigkeit bei Diagonalbewegungen gegenüber Horizontal- und Vertikalbewegungen zeigt sowie auch durch ungenaue Sichtweiten bei diagonalen Richtungen. Diese Form der Berechnung wurde dennoch gewählt, um den Rechenaufwand gegenüber genauen Distanzberechnungen zu minimieren.
Als Hauptregel wurde das Verbot des Stillstands für Individuen als willkürliche Schwarmregel vorgegeben. Eine derartige Regel ist auf einer 2-dimensionalen Oberfläche nicht zwingend. In der Natur bei ist bei Schwärmen auf Oberflächen diese Regel im Allgemeinen ausgesetzt. Wie man bei Ameisen leicht beobachten kann, können die Individuen bei hoher Schwarmdichte zu einem Stillstand kommen, wenn beispielsweise eine Futterquelle erreicht wurde. Hier kommt es zu Kollisionen, bei denen nach eigenen Beobachtungen die Ameisen sich aus der scheinbaren 2. Dimension auch in die Dritte begeben und sich dann auch übereinander bewegen und auch positionieren, wenn die Individuendichte zu hoch wird (siehe auch Karl Gößwald, Organisation und Leben der Ameisen, Wissenschaftliche Verlagsgesellschaft, Stuttgart, 1985, Abb. 133). Um bei den hier dargestellten Individuen Kollisionen besser erkennen zu können, ist das Stillstandsverbot als Regel vorgegeben. Kollisionen bzw. zu nahe Kontakte werden dann als kleine gefüllte grüne Quadrate wiedergegeben. Es ist zu vermuten, dass eine Stillstandsvermeidung auch bei einigen natürlichen Schwärmen angestrebt wird (z.B. beim Flug von Vögeln oder Bienen, um Kollisionen und Abstürze zu vermeiden, oder bei belebten Ameisenstraßen, um den Bewegungsfluss nicht zu unterbrechen).
Das gesamte Applet mit seinen Algorithmen zur Umsetzung der Schwarmregeln ist relativ umfangreich. Es kann daher nicht ausgeschlossen werden, dass durch die Programmierung auch Seiteneffekte oder auch Fehler im Algorithmus entstanden sind, die dazu führen, dass neben den oben beschriebenen Schwarmregeln weitere versteckte Effekte bestehen.
Seiteneffekte entstehen sicherlich auch durch die hier gewählte Verarbeitung der Separationsregel. Bei der oben beschriebenen Umsetzung der Separationsregel wird nicht berücksichtigt, dass das Blickfeld des Individuums ggf. nur 90 Grad beträgt, d.h. alle Nachbarindividuen im Umfeld von 5 Pixeln werden auf Annäherungen untersucht. Da in der Natur im Nahbereich neben dem Sehsinn häufig aber auch noch andere Sinne aktiv sind (z.B. Elektrosensorik bei einigen Fischarten oder Exterozeption, wo es zu einer Körperoberflächenwahrnehmung bei Annäherung kommen kann), gibt der hier gewählte Ansatz vermutlich die Realität besser wieder als die Beschränkung auf den reinen Sehsinn im Nahbereich. Denkbar ist aber, dass unterschiedliche Umsetzungen der Separationsregel zu unterschiedlicher Schwarmbildung führen.
Ein weiterer Seiteneffekt entsteht vermutlich durch die Umsetzung der Beharrungsregel auf ein gleichförmiges Rasterfeld, bei der ein Individuum sich geradeaus weiterbewegt. Wenn sich mehrere Individuen ohne Sichtkontakt untereinander gleichförmig in dieselbe Richtung bewegen, entsteht der Eindruck einer gleichförmigen Gruppenbewegung. Diese Gruppenbewegung existiert aber nur scheinbar, da die Individuen keinen weiteren Sichtkontakt untereinander haben und nur zufällig dieselbe Richtung eingeschlagen haben (siehe hierzu auch weiter unten im Abschnitt Richtungsvektoren).
Aus Gründen des Laufzeitverhaltens wurde für Bewegungen eine modifizierte Rastermetrik (auch Manhattanmetrik genannt) gewählt, bei der neben horizontalen und vertikalen Bewegungen auch diagonale Bewegungen im Raster zugelassen werden. Dies führt sicherlich ebenfalls zu Seiteneffekten, da als Folge des Satzes von Pythagoras bei diagonalen Bewegungen kürzere Strecken als bei Achsenbewegungen entlang der Horizontalen und Vertikalen zurückgelegt werden. Im Algorithmus der Version 2 werden daher Diagonalbewegungen nur dann zugelassen, wenn der Betrag der Steigung < |2| ist, wodurch die Auswirkungen dieses Seiteneffekts reduziert werden; in allen anderen Fällen werden die Regeln der Manhattanmetrik angewandt. Eine weitere Erläuterung zu diesem Seiteneffekt findet man im Abschnitt Richtungsvektoren. Durch die hier abgewandelte Form der Metrik entsteht ein höherer Bewegungsspielraum der Individuen, insbesondere wenn Bewegungsänderungen von nur 45 Grad durchgeführt werden sollen, was bei einer reinen Manhattanmetrik in einem Step unzulässig wäre.
Anhang - Angaben zur Software
Kernaufbau
Das Applet Schwarm nutzt neben Standard-Java Klassen, die aus Standard-Packages (z.B. lang.Math oder util.Random oder awt.Graphics) zugeladen werden, ein weiteres eigenes Package „de.opartandmore.www.oppack“, das insbesondere Klassen und Hilfsfunktionen für die grafische Verarbeitung und die Ausgabe von Grafiken für die eigenen Java-Klassen der Website opartandmore.de bereitstellt. Hierbei werden 2 Images in Verbindung mit je 1 MemoryImageSource für die Aufbereitung der grafischen Ausgabe („gB“) des nächsten Steps und für die aktuelle Ausgabe der grafischen Inhalte auf dem Bildschirm („g“) des jeweils aktuellen Steps verarbeitet.
Für die Kommunikation mit dem Benutzer werden die einfachen Standard-Java-Klassen aus lang.Object verwendet; SWING kommt hierbei nicht zum Einsatz. Die Kommunikation mit dem Benutzer erfolgt neben erweiterten Standard-Listenern für die Maus-Interaktion, die über die Klasse „Applet“ implementiert werden, über mehrere selbst erstellte Listener, mit denen die Eingaben aus dem Bedienfeld übernommen werden.
Für den prozessgesteuerten Ablauf werden die Standard-Java-Prozeduren (init(), start(), stop(), run(), update() und paint()) verwendet, die aber mit ergänzenden Eigenschaften gegenüber dem Java-Standard überschrieben werden. Mit start, run, update und paint wird der Prozess der Ausgabe von grafischen Informationen auf dem Bildschirm inkl. der erforderlichen Rechenoperationen für jeden einzelnen Step (s.o.) durchgeführt.
Das Java-Applet Schwarm wird in einem eigenen Package mit der Bezeichnung „Interferenzen“ geführt:
package interferenzen;
import java.applet.Applet;
import java.awt.*;
import java.lang.*;
import java.lang.Math;
import java.util.Random;
import java.util.Date;
import java.awt.Graphics;
import java.awt.Color;
import java.awt.image.*;
import java.awt.Font;
import java.awt.Cursor;
import java.awt.event.*;
import de.opartandmore.www.oppack.*;
public class
Schwarm extends Applet implements
MouseListener, MouseMotionListener,
ComponentListener, Runnable { … }
Hiermit ist der Kernaufbau des Applets Schwarm gesetzt. Die Entwicklung von JAVA-Applets in der Website opartandmore.de begann bereits in den 90er Jahren als hier noch kein eigener JAVA-Style-Guide bekannt war. Aus dieser Zeit haben sich in den Quellprogrammen bis heute Abweichungen vom heute gültigen Style-Guide erhalten, so dass das Lesen der Quellprogramme bisweilen erschwert wird.
Die Quellprogramme der Version 2 erhalten auch einige Erweiterungen, die sich für eine Folgeversion nutzen lassen, wenn die Auswirkungen von Schwarmmanipulationen untersucht werden sollen. Allerdings sind diese Programmteile nur unvollständig umgesetzt und bisher auch deaktiviert.
Klassenkonzept
Die Version 2 nutzt derzeit lediglich eine einzige selbst erstellte Klasse mit der Bezeichnung „SchwarmIndividuum“ für einige wenige Angaben, durch die ein Schwarmindividuum definiert wird. Diese Klasse wird für die einzelnen Schwarmmitglieder jeweils separat erzeugt, so dass bei maximaler Schwarmgröße 2000 einzelne Instanzen dieser Klasse erzeugt werden. Diese Klasse enthält ebenfalls bereits Code für die Erweiterung der Software mit Schwarmmanipulationen:
class SchwarmIndividuum
{
int xs,ys;
// aktuelle Position
int nextx,nexty; // nächste Position
int richtungx, richtungy; // eingeschlagene Richtung
int
memory=0; // >0 : es gab einen Raptor in der Nähe.
//Versuche gefundene Richtung beizubehalten
boolean braptor=false;
// t-> raptorgedächtnis ist aktiv
boolean bmanipulator=false;
// t-> Das Individuum ist ein Manipulator,
// der vorgegebene Wege läuft #V2.01
SchwarmIndividuum(int xs, int
ys, int richtungx,
int richtungy) {
this.xs=xs;
this.ys=ys;
this.richtungx=richtungx;
this.richtungy=richtungy;
}
void set_memory(int m) {
memory=m;
braptor=true;
}
void set_manipulation(boolean bmanipulator) {
this.bmanipulator=bmanipulator;
}
boolean check_manipulator() {
return bmanipulator;
}
boolean remember() {
if(memory>0)
{
memory--;
}
else braptor=false;
return braptor;
}
}
Die Instanzen werden in Version 2 von anderen Schwarmindividuen bei Zugehörigkeit zu einer Nachbarschaftsgruppe im Hinblick auf den Ort und die eingeschlagene Richtung geprüft, um den Schwerpunkt oder Gradienten der Nachbarschaftsgruppe zu ermitteln, wodurch das eigene Verhalten beeinflusst wird. Die oben eingebauten Funktionen zu Raptoren und Manipulatoren sind derzeit deaktiv geschaltet.
Matrizen
Die Pixeloberfläche des Applet-Windows stellt den 2-dimensionalen Bewegungsraum der Individuen und auch weiterer grafischer Komponenten dar, die über Java-Funktionen mit Vektorgrafik aus awt.Graphics auf den imageBuffer „gB“ abgebildet werden. Für Berechnungen werden aber 2 separate Matrizen verwendet, die genau diesen Bewegungsraum mit 550 x 550 Punkten abdecken.
Die int-Matrix „xweg“ enthält für jeden Pixel die Aufzeichnung der Spuren aus der Vergangenheit und ggf. auch die Anwesenheit eines Individuums. Durch den int-Wert jedes Matrixelements wird angezeigt, wann hier ein Indviduum war bzw. ob sich hier gerade ein Individuum aufhält. Der Wert 255 wird dabei als aktueller Aufenthaltsort eines Individuums definiert. Werte < 255 stellen das abnehmende Alter eines Pfads an dieser Stelle dar. Die Matrix wird bei jedem Step fortgeschrieben, wobei das Alter von Pfaden jeweils um 1 gegenüber dem Vorgängerwert reduziert wird. Mit diesem Vorgehen kann der Alterungsprozess der Pfadverläufe sowie der aktuelle Aufenthaltsort von Individuen angezeigt werden. Nach ca. 250 Reduzierungen (Steps) wird das Pixel wieder weiß im Sinne von leer dargestellt.
Mit der 2. int-Matrix „whois“ werden die Individuen auf der 2-dimensionalen Bildfläche über einen Verweis auf die zugehörige Klasseninstanz „SchwarmIndividuum“ identifiziert. Die Identifikation ist erforderlich, um bei Nachbarn einer Nachbarschaftsgruppe mit einer Gradientenberechnung die Richtung der gesamten Nachbarschaftsgruppe zu ermitteln, woraus sich für das abfragende Individuum eine Entscheidung für das eigene Verhalten (Richtungswahl und ggf. Änderung der Geschwindigkeit) entwickelt.
Richtungsvektoren
Die Bewegung eines Individuums wird durch 2-dimensionale Richtungsvektoren mit x in horizontaler Richtung und y in vertikaler Richtung beschrieben, die sich jeweils relativ auf den aktuellen Standort des Individuums beziehen. Ausgehend von Abb. 4, wo die Bewegung eines Individuums auf dem Raster für einzelne Steps grafisch aufgetragen sind, ergeben sich bei den zugelassenen Richtungsänderungen von 0 auf -45 oder +45 Grad ausgehend von einem Koordinatenpunkt 3 verschiedene Richtungsvarianten, die ein Individuum im nächsten Step gehen könnte. Damit Richtungsänderungen von 45 Grad möglich werden, ohne 2 Steps vollführen zu müssen, sind hier auch diagonale Richtungen zugelassen, wodurch die reine Form einer Metrik mit Manhattangeometrie durchbrochen wird. Hierdurch ergeben sich eine höhere Vielfalt an Bewegungsentscheidungen und auch gleichförmigere Bewegungen der Individuen als Vorteile, da die häufigen Richtungsänderungen der Manhattanmetrik reduziert werden können.
Diese hier gewählte Kombination aus Manhattanmetrik und Diagonalmetrik führt aber auch zu Nachteilen. Einheitskreise, d.h. kleinstmögliche Kreiswege um einen Mittelpunkt werden bei der Manhattanmetrik durch Quadrate und bei der Diagonalmetrik durch diagonal gedrehte Quadrate erzielt (siehe Abb. 23), die durch die jeweils 4 Freiheitsgrade der Bewegungsrichtungen entstehen. Größere Kreise können bei Anwendung reiner Manhattanmetrik durch regelmäßige Vielecke approximiert werden. Bei der hier vorgenommenen Kombination von Manhattanmetrik und Diagonalmetrik ergeben sich insgesamt 8 Freiheitsgrade. Die Abb. 24 zeigt mit den blauen Linien die Auswirkung dieser Kombinationsmetrik, wenn man die Individuen dazu zwingt, einem anderen Individuum zu folgen, das sich auf einer approximierten Kreislinie mittels eine Vielecks bewegt (im Beispiel unten wurde ein Hunderteck benutzt). Das Ergebnis der Kombinationsmetrik ist ein Bewegungsablauf, der dann einem Achteck als Approximation eines Kreises entspricht.
Abbildung 23 Einheitskreise bei Manhattanmetrik und Diagonalmetrik
Abbildung 24 Kreisapproximation bei kombinierten Metriken
Als Konsequenz der 8 Bewegungsrichtungen ergeben sich Einschränkungen, die insbesondere bei der Darstellung von Gradienten durch maximal 8 verschiedene Parallelrichtungen der Individuen sichtbar werden.
Als weitere Konsequenz können bei einem Sichtfeld von 90 Grad auch scheinbare Schwarmbewegungen entstehen, die sich aus den insgesamt nur 8 Freiheitsgraden der Bewegungsrichtungen ergeben. Bei der Darstellung der Beziehungen zwischen den Schwarmindividuen werden derartige Scheinschwärme durch Gruppen von Individuen, die mit rotem Punkt dargestellt sind, sichtbar. Bei diesen rot dargestellten Individuen handelt es sich bei dieser Darstellungsart um Individuen, die keine eigene Nachbarschaftsgruppe besitzen. Beim Ausschnitt in Abb. 25 wird durch die dargestellte Schummerung in rot und blau gezeigt, wie die aktuelle Bewegungsrichtung der Individuen auf diesem Ausschnitt aussieht. Bei den 2 rot dargestellten Individuen mit paralleler Bewegungsrichtung in Richtung der roten Pfeile besteht keine direkte Schwarmbeziehung. Diese 2 roten Individuen werden von 3 blau gefärbten Individuen (in Richtung der blauen Pfeile nach links oben) verfolgt und bilden somit einen scheinbaren Schwarm, der aus 5 Individuen besteht. Es bleibt zu klären, ob das hier dargestellte simulierte Verhalten auch in der Natur vorkommt:
Abbildung 25 Bildung von Scheinschwärmen
(Die
Farbe sowie die Größe der blauen Symbole spiegelt die Zahl der erkannten
Nachbarn wieder. Rot bedeutet: es werden in Bewegungsrichtung keine Nachbarn
erkannt. Die grauen Verbindungslinien zeigen ungerichtete
Nachbarschaftsbeziehungen im Zeitverlauf mehrerer Steps.
Als Folge der optischen Überlagerung mehrerer Steps
sind einige der Farbinformationen nur verschwommen bzw. als Schummerung zu
erkennen. Die Pfeile wurden nachträglich in die Grafik projiziert. Der hier
mittels Schummerung gezeigte Zeitverlauf kann als animierte Grafik über die
Darstellung „Beziehungen“ im Bedienfeld aktiviert werden, indem der Mauszeiger
anschließend in das Bild geführt wird.)
Die 3 möglichen Richtungsvarianten eines Individuums werden temporär in zwei 3-elementigen Vektorfeldern „xdi“ und „ydi“ für die horizontale und vertikale Komponente gespeichert. Zugelassen werden für jede Komponente ausschließlich die 3 Werte -1, 0 und +1 als Änderungswerte ausgehend von der aktuellen Position, aus denen sich der Richtungsvektor zusammensetzt. Auf diese Weise kann erzwungen werden, dass pro Step auch nur eine Bewegungsänderung von einem Pixel entsprechend Abb. 4 erfolgt. Wegen der oben vorgenommenen Definition der Stillstandsregel ist der Richtungsvektor (0,0) nicht zugelassen. Mindestens eine Komponente muss von 0 verschieden sein.
Abgesehen von den 3 möglichen Richtungsänderungen ausgehend von einer Position des Individuums ergeben sich aber aus der Geometrie des Rasters insgesamt 8 verschiedene Richtungen (rechts, links, hoch, runter sowie 4 diagonale Richtungen). Von diesen 8 Richtungen müssen die erlaubten Richtungen, die ein Individuum gemäß Abb. 4 einschlagen darf, als Entscheidungsgrundlage für die nächste Bewegung des Individuums identifiziert werden. Hierzu werden alle möglichen Transitionen der Geometrie geprüft:
// Suche die möglichen
alternativen Richtungen zur aktuellen Bewegungsrichtung (xri,yri)
//
(xri,yri)
//
( 0,-1) --> (-1,-1) oder ( 1,-1)
//
( 1,-1) --> ( 0,-1) oder ( 1, 0)
//
( 1, 0) --> ( 1,-1) oder ( 1, 1)
//
( 1, 1) --> ( 1, 0) oder ( 0, 1)
//
( 0, 1) --> ( 1, 1) oder (-1, 1)
//
(-1, 1) --> ( 0, 1) oder (-1, 0)
//
(-1, 0) --> (-1, 1) oder (-1,-1)
//
(-1,-1) --> (-1, 0) oder ( 0,-1)
//
// Speichere die 3
zugelassenen Richtungen in (xdi,ydi)
Als Grundlage für die Bildung von Richtungsvektoren wird das Standard-Koordinatensystem von JAVA verwendet, bei dem die linke obere Ecke als (0,0) und die rechte untere Ecke als (549,549) bezogen auf die hier vorgegebene Bildfläche definiert sind.
Nachbarschaftsgruppe
Bei der Suche einer Nachbarschaftsgruppe wird ausgehend von dem Ort des suchenden Individuums bei einem Blickwinkel von 90 Grad das in Abb. 4 gezeigte Blickfeld in Richtung der Bewegungsrichtung des Individuums nach anderen Individuen durchsucht. Die Suche wird abgebrochen, wenn die vorgegebene Zahl von Nachbarn (siehe Bedienfeld in Abb. 3), die eine Nachbarschaftsgruppe ausmachen sollen, erreicht wurde. Die Suche wird auch dann abgebrochen, wenn die maximale Sichtweite des Individuums, die in dieser Version fest auf 200 Rasterlinien eingestellt ist, ohne ausreichende Anzahl gefundener Nachbarn erreicht wurde.
Bei einer Rundumsicht mit einem Blickwinkel von 360 Grad werden zur Vereinfachung der Verarbeitung Quadrate um den Ort des suchenden Individuums gelegt, auf deren Kanten nach Nachbarn gesucht wird. Die Kantenlänge wird nacheinander soweit erhöht, bis eine ausreichende Anzahl von Nachbarn gefunden wurde oder aber die maximale Sichtweite erreicht wurde. Die Abstände zu den Nachbarn im Nahbereich werden über eine Manhattanmetrik ermittelt, d.h. Diagonalen werden hier nicht berücksichtigt.
Zentrale Abstandsfunktionen
Zur Entscheidung der nächsten Bewegung des Individuums wird der minimale Abstand nach den 3 möglichen Richtungsänderung (xdi[],ydi[]) berechnet. Der kürzeste Abstand wird als Basis für die Endentscheidung verwendet. Für die Berechnung werden die Einschränkungen der Manhattan-Metrik bei Steigungen < |2| durch diagonale Abstände ersetzt, wodurch relativ gute Ergebnisse bei der Ermittlung minimaler Abstände erzielt werden:
int minAbstand(int xp, int yp,
int mx, int
my, boolean check) {
//--------------------------
// (xp,yp) : aktuelle Koordinate des Individuums
// (mx,my) : Ermittelter Schwerpunkt oder Gradient der
Nachbarschaftsgruppe
int index;
// Ergebnisindex der neuen Bewegungsrichtung (xdi,ydi)
int
amin=999999; // Zwischenwert zur
Ermittlung eines minimalen Abstands
int xpneu,ypneu; // Koordinaten als Zwischenwerte
möglicher Richtungsvektoren
int
dxyneu=999999; // Minimal
ermittelter Abstand
boolean bdia,bx,by; // t-> dichtester Abstand zur
Richtung Diagonale (bdia),
// x-achse (bx), y-achse
(by)
// Diagonalen
wirken stärker,
// daher Optimierung der
Bewegungsrichtung erforderlich
int rx,ry; // Zwischenwert zur Ermittlung
des Abstands (xp,yp)-(mx,my)
int dx,dy,dxy; // Verhältnis der Abstände bezogen
auf Abzisse und Ordinate
boolean
bprotokoll=Debug1 & check;
bdia=true; // #v2.01b
bx=false;
by=false;
rx=mx-xp;
ry=my-yp;
dx=Math.abs(rx);
dy=Math.abs(ry);
if(dx>0
& dy>0) {
// Verhältnis zwischen x- und y-Achse, um eine
Vorzugsrichtung zu finden
if(dx>dy) dxy=(dx)/(dy);
else dxy=(dy)/(dx);
if(dxy>=2 ) { //
Manhattan Geometrie kann direkt angewandt werden
bdia=false;
if(dx>dy) bx=true; // Ergebnis: in x-richtung
laufem
else by=true; // Ergebnis: in y-richtung
laufen
}
}
else if(dx==0) bx=true;
else if(dy==0) by=true;
index=-1;
for(int i=0;i<3;i++) {
// alle möglichen 3
Bewegungsrichtungen prüfen
if(xdi[i]>-10) {
xpneu=xp+xdi[i];
ypneu=yp+ydi[i];
if(bx & xdi[i]!=0
& ydi[i]==0) { // Manhattan-Metrik in x-Richtung
anwenden
// wenn Abstände nicht größer werden
if((xp<mx & xdi[i]>0) | (xp>mx & xdi[i]<0)) {
index=i; // #v2.01
}
else
{ bdia=true; }
}
else
if(by & ydi[i]!=0 & xdi[i]==0) { //
Manhattan-Metrik in y-Richtung anwenden
// wenn Abstände nicht größer werden
if((yp<my & ydi[i]>0) | (yp>my & ydi[i]<0))
{
index=i; // #v2.01
}
else
{ bdia=true;
}
}
}
}
if(bprotokoll) System.out.println("Index nach 1. Test: "+index);
if
(index<0) { //
Sofern noch kein Ergebnis vorliegt, erfolgt eine Diagonalbetrachtung
for
(int i=0;i<3;i++) {
if(xdi[i]>-10) {
xpneu=xp+xdi[i];
ypneu=yp+ydi[i];
// Ermittlung des
minimalen diagonalen Abstands
dxyneu=(xpneu-mx)*(xpneu-mx)+(ypneu-my)*(ypneu-my);
if(dxyneu<amin) {
amin=dxyneu;
index=i;
}
}
}
}
if(bprotokoll) {
System.out.println("Ergebnis="+index);
}
return index;
}
Im Nachgang zur Berechnung des neu einzuschlagenden Wegs erfolgt die Umsetzung der vorrangigen Separationsregel, mit der Unterschreitungen von Abständen bzw. Kollisionen von Individuen verhindert werden sollen. Hierbei wird um den Mittelpunkt des Individuums ein Quadrat mit einer Seitenlänge von 11 Pixeln gespannt und geprüft, ob sich in diesem Quadrat Nachbarn befinden. Sofern Nachbarn in diesem Quadrat gefunden werden, wird die Bewegungsrichtung des nächsten Nachbars ermittelt und die eigene Bewegungsrichtung von diesem Nachbarn weggeführt, indem von den oben gezeigten 3 möglichen Richtungsvektoren derjenige ausgewählt wird, der vom Nachbarn am besten wegführt. Bei mehr als einem gleichwertigen Ergebnis wird eine Zufallsentscheidung getroffen.
Diese Vorgehensweise führt im Allgemeinen zu guten Resultaten. Als Kollision wird hier definiert, wenn alle Richtungsvektoren zu einem Abstand <= 1 zwischen den Köpfen zweier Individuen führen. Kollisionen werden in der Grafik als kleines grünes Quadratsymbol angezeigt. Bei großen und stark verdichteten Schwärmen treten bisweilen Kollisionen auf, wobei dann das Stillstandsverbot für die Dauer der Kollision verletzt wird, bis wieder neue Richtungen ohne Kollisionen eingeschlagen werden können. Kollisionen werden in der int-Matrix „xweg“ als besonderes Pfadereignis gespeichert; sie werden so lang als grünes Quadrat angezeigt, bis ein neuer und jüngerer Pfad über den Kollisionspunkt gelegt wird.
Prozeduraler Ansatz
Das Applet Schwarm nutzt abgesehen von Standard-Java-Klassen nur wenige eigene Objektstrukturen. Es wird stattdessen vielmehr ein prozeduraler Ansatz verfolgt, wobei ausgehend vom Prozessablauf bei jedem einzelnen Step Abläufe, Prozeduren, Funktionen und Hilfsroutinen zur der Erzeugung von Bilddaten und zur Berechnung der Schwarmindividuen sowie aller weiteren grafischen Informationen führen. Von den im Kernaufbau beschriebenen Standard-Java-Prozeduren gehen von den 2 Prozeduren init() und paint() die entscheidenden Verarbeitungsschritte aus.
init() dient der Initialisierung aller Datenstrukturen, dem Aufbau der Bedienoberfläche inkl. der Listenernutzung und der Kommunikation mit dem Benutzer. Ausgehend von init() werden folgende weiteren eigenen Prozeduren aufgerufen:
- initschwarm() : erzeuge und initialisiere einen Schwarm mit der vorgegebenen Zahl von Individuen nach einem Zufallsprinzip.
- changeschwarm() : verändere den Schwarm bei Änderung der Angabe der Schwarmgröße durch den Benutzer.
paint() ist die zentrale und bei jedem Step zyklisch aufgerufene Prozedur, bei der sämtliche Berechnungen erfolgen und die Bildschirmausgabe angestoßen wird. In paint() werden nacheinander folgende weiteren Prozeduren und Funktionen verschachtelt aufgerufen, wobei hier Hilfsroutinen und der Zugang zu den Objektinstanzen der Individuen („SchwarmIndividuum“) zur besseren Übersicht nicht aufgeführt werden:
- moveschwarm() : die Aufgabe der Prozedur besteht in der Berechnung des nächsten Steps für alle Individuen, wobei innerhalb der Prozedur eine Schleife über alle Individuen durchlaufen wird. Hierbei erfolgen auch die Randkontrolle, wenn Individuen den Rand berühren, sowie die Geschwindigkeitskontrolle der Individuen. Bei Nutzung der Speed-Option (siehe Abb. 3) wird der Ablauf dieser Prozedur und aller darin verschachtelten Prozeduren im Bedarfsfall verdoppelt, so dass innerhalb eines Steps die Berechnung von 2 Steps erfolgt, wodurch bei Einhaltung der in Abschnitt 5 genannten Geschwindigkeitsregeln eine Verdoppelung der Geschwindigkeit erreicht werden kann. In dieser Prozedur erfolgt auch die Fortschreibung der Matrizen „xweg“ und „whois“
o richtungen() : für jedes Individuum werden die möglichen Richtungsvektoren (xdi[],ydi[]) ermittelt.
o suchenachbarn() : bildet für ein einzelnes Individuum die zugehörige Nachbarschaftsgruppe inkl. Schwerpunkt- und Gradientenberechnung unter Verwendung der zentralen Abstandsfunktion minAbstand(). In dieser Prozedur erfolgen auch die meisten Sonderplotausgaben der Trace-Funktion (siehe Abschnitt 3), wo bei einem speziellen Individuum die in Abb. 5 gezeigten grafischen Informationen zur Entscheidungsfindung des Individuums erzeugt werden. Für die Darstellung dieses Individuums wird auch eine Hilfsroutine plotindivn() verwendet.
o checknachbarn() : Überwachung der Einhaltung der Kollisionsregeln (Separation) für ein einzelnes Individuum inkl. der Optimierung des nächsten Steps im Nahbereich.
- plotschwarm() : erzeugt aus den vorliegenden Informationen der Matrix „xweg“ die Vektorgrafiken mit den Individuen und Pfaden der Individuen.
Das Applet Schwarm enthält einige weitere Routinen sowie auch Vorbereitungen für eine Folgeversion, bei der Schwarmmanipulationen geplant sind, die hier aber nicht beschrieben werden, zumal sie nicht getestet sind und daher deaktiviert sind.
Bei Bedarf kann das Applet Schwarm auch von fremden Servern oder auf lokalen PCs betrieben werden. Hierzu müssen besondere Zugangscodes beim Aufruf der Software gesetzt werden.
Copyright
Frank Vollbrecht