Schwärme

Schwarmintelligenz ist ein sehr interessantes Phänomen. Man kann es in verschiedenen Bereichen der Natur beobachten. Zum Beispiel finden die Ameisen ihre Wege anhand der Spuren ihrer Vorgänger. Dadurch organisiert sich die Nahrungsfindung von selbst. Es gibt keine Ameise, die die Strecken kennt und die anderen Koordiniert. Genauso bei den Bienen und Termiten.

Ich habe ein kleines Testprogramm geschrieben, welches für jedes Objekt ein paar einfache Regeln bereithält. Es bilden sich dann automatisch Schwärme. Die Regeln sind:

• Suche die Nähe deiner Artgenossen
• Laufe in die selbe Richtung wie deine Artgenossen
• Versuche einen Mindestabstand zu deinen Artgenossen einzuhalten

Das Programm kann man sich hier herunterladen. Es läuft komplett von allein und ist nur ca. 600 KB groß:



Dabei kommt dann sowas raus:

Ich werde später noch mehr über dieses Programm schreiben. Es läuft auch noch nicht ganz optimal.

--- update ---
So, nun habe ich das Programm verbessert. Die Einheiten laufen nun immer in Grüppchen über das Feld. Man kann auch einzelne Einheiten mit der Maus steuern und die anderen Einheiten werden davon beeinflusst. Auf folgendem Screenshot sieht man die Einheiten (Weißer Kreis) und Ihren Sichtradius (Blauer Kreis) und den Mindestabstand zu anderen Einheiten (Roter Kreis).

Mal in Bewegung auf youtube.com zu sehen:


Ich habe nun noch weitere Objekte und Mechanismen hinzugefügt:

• Essen: Blaue Kästen symbolisieren das Essen, je Größer der Kasten, desto mehr Nahrung
• Bewegung der Einheiten kostet Energie, Einheiten können sterben
• Einheiten werden nun zusätzlich von Essen angezogen
• Je größer und ausgefüllter der Kreis, desto älter ist die Einheit
• Die Gesundheit der Einheit ist an der Farbe abzulesen: Grün ist gesund, Rot ist schwach

Auch davon habe ich wieder einen Screenshot und ein Video gemacht:

Youtube:

Genaueres Tutorial

Ich werde in diesem Tutorial nur über die KI sprechen, wie genau man diese Dinge in einer Programmiersprache vollbringt und wie man Sachen visualisiert ist nicht Inhalt dieser Beschreibung. Dafür gibt es viele andere gute Quellen.

Schritt 1: Erstellen der Basis
Wir brauchen einen Bereich, in welchem die Agenten sich bewegen. Als muss festgelegt werden, was die maximale und was die minimale Position sein kann. (2D)
Dann brauchen wir für jede Einheit gewisse Variablen. Für den Anfang reicht wohl die Position und die Geschwindigkeit und die Richtung. Dann brauch jede Einheit die Möglichkeit, die Richtung zu wechseln. Die Klasse, die den algorithmus ausführt muss auf eine Sammlung aller Einheiten zugreifen können. (Könnte man in C++ mittels eines Vektors von Einheiten-Objekten machen). Die Mainloop die auch die Bilder zeichnet ruft auch die Methoden auf, welche die Schwarm-Regeln anwenden und die Einheiten bewegen. Wie oft man diese Sachen aufruft ist jedem selbst überlassen.

Schritt 2: Die Regeln erstellen
Regel 1: Suche deine Nachbarn
Jede Einheit hat einen Sichtbereich. Das kann für den Anfang einfach ein Kreis sein, ein Kreis von 200 Grad wäre aber besser. Als nächstes wird für jede Einheit geschaut, welche Einheiten sie sehen kann. Als nächstes werden die Positionen von allen sichtbaren Einheiten gemittelt. Ein Vektor der zu diesem Punkt zeigt wird gespeichert.
Regel 2: Gehe in diesselbe Richtung wie deine Nachbarn
Es wird diesselbe Funktion für die Sichtbarkeit angewandt, wie bei Regel 1. Anstelle der Positionen werden alle Richtungen der Nachbareinheiten gespeichert und ein gemittelter Vektor aus diesen Daten wird abgespeichert.
Regel 3: Vermeide eine Kollision mit deinen Nachbarn Diese Regel ist ähnlich wie die erste Regel. Mit 2 Veränderungen: 1. Die Sichtweite ist geringer was den Radius betrifft. 2. Der Vektor zum Mittelpunkt der Nachbarn braucht nur um 180 Grad gedreht werden.

Schritt 3: Zusammenfügen der Regeln und die Anwendung
Nun haben wir 3 Vektoren. Diese gewichten wir und addieren wir anschließend. Dann muss dieser Vektor noch normalisiert werden und schon haben wir unsere neue Richtung. Ich habe die 3. Regel am stärksten gewichtet, denn die Einheiten sollten keinesfalls ineinanderlaufen. Direkt danach habe ich die 2. Regel gewichtet, damit der Schwarm auch gemeinsam die Richtung wechselt und sich nicht einfach nur ein Haufen bildet. Am geringsten ist die erste Regel gewichtet. Das reicht aber aus, damit sich ein Schwarm bildet.

Schritt 4: Bewegung
Der errechnete Vektor muss nun der Einheit mitgeteilt werden, damit sie die Richtung wechselt. Dann muss jede Einheit bewegt werden, damit sich auch was tut ;-)

Und schon sind wir fertig :-)

Hunter & Prey

Ich habe nun noch einen weiteren Schwarm hinzugefügt. Dieser jagd nun den Ersten, da es sich um 'Fleischfresser' handelt. Daraus ergeben sich interessante Effekte: Manchmal werden alle 'Pflanzenfresser' aufgefressen. Dann haben die 'Fleischfresser' keine Nahrung mehr und sterben ebenso. Ein anderes Mal können die 'Pflanzenfresser' erfolgrech fliehen und die 'Fleischfresser' verhungern. Dann kommt es zu einer Bevölkerungsexplosion.

Eine ausgewogene, stabile Population ist mir noch nicht gelungen :-)

Auch von diesem Arbeitsschritt gibt es wieder ein Bild und ein Video.


Video auf Youtube.com: