Eine Studie der künstlichen Intelligenz für Erstsemester

Während des ersten Semesters bekommen Studenten bei uns ein einfaches grafisches Framework zur Verfügung gestellt, welches eine Ameise auf einer Ebene zeigt. Nach und nach sollen den Ameisen verschiedene Verhaltensmuster beigebracht werden. Wie diese umgesetzt werden, bleibt dabei dem Studenten überlassen. Auf diese Weise können die noch unerfahrenen Programmierer schnell zu Ergebnissen kommen und werden auch dazu motiviert, eigene Features einzubauen. Zu Semesterende durften wir in Teams eine finale Version abgeben. Die beste Version sollte mit einer Urkunde und einem Preisgeld von einem Cent gekürt werden :) Die Version von Clas Rurik und mir gewann den ersten Platz. Hier gibt's einige Bilder dazu (zum Vergrößern bitte klicken)

Das ist also mein erstes Universitätsprojekt. Es ist nicht wirklich interaktiv. Nach dem Starten am besten Zurücklehnen und den Ameisen beim arbeiten zuschauen. Mittels Klick auf die Minimap unten rechts kann man den Bildausschnitt bewegen.

Download & Anleitung

 Zum starten hast du zwei Möglichkeiten:

• Direkter start mittels WebStart: Folge diesem Link.
• Downloade die JAR-Datei und führe sie lokal aus. Hier lang.

Features

Hier eine kleine Liste der von Clas und mir implementierten Features:

• Beliebig große Spielfelder.
• Scroll-und Zoombares Spielfeld mit Minimap.
• Eimersystem zum effektiven Managen der Ameisen.
• Eine einfache Ameisenintelligenz.
• Ein einfaches Ökosystem.
• Neue Ameisenvöler wandern ein, wenn Alte aussterben.
• Käfer jagen Ameisen.
• Ameisen jagen Käfer und Beute, wenn sie zahlreich genug sind.
• Namensgenerator. Wir kenne alle Käfer mit Namen.
• Kampf zwischen Kapitalisten und Kommunisten in der Standardkonfiguration. Keine politische Botschaft :)

Bucketing: Wie man mit vielen Entitäten auf einer großen Fläche umgeht.

Wenn man viele Objekte auf einem weiten Feld hat, wird das überprüfen auf Sichtkontakt für den Prozessor eine echte Rechenleistung. Schauen wir uns folgendes Beispiel an:

In einer naiven Implementierung würde man einfach alle Ameisen in eine Liste packen. Der Käfer (K) kann 4 Ameisen (A) sehen, muss aber über die ganze Liste iterieren und für jede Ameise prüfen, ob er sie auch wirklich sieht. Für die Ameisen ist die Situation noch drastischer: Jede Ameise muss jede andere Ameise auf Sichtkontakt prüfen. Das entspricht einer Komplexität von n² und ist offensichtlich suboptimal. Wie kann man diesen Prozess also verbessern? Die typischen Sichtradii unserer Protagonisten sind für gewöhnlich deutlich kleiner als das Spielfeld selbst. Wir wollen, dass der Algorithmus folgendes tut:

• Er soll die Anzahl der zu prüfenden Ameisen nahe an die Zahl der tatsächlich sichtbaren Ameisen bringen.
• Da die Ameisen sich schnell bewegen, soll die zugrundeliegende Datenstruktur leicht modifizierbar sein.

Eine einfach zu implementierende Lösung ist das sogenannte "Bucketing". Man unterteilt das Spielfeld in gleich große Quadrate und wirft jede Ameise in einen "Eimer" entsprechend dem Quadrat auf dem sie steht. Die Datenstruktur innerhalb eines Eimers kann z.B. wieder eine Liste sein.

K errechnet jetzt die Koordinaten der Eimer, welche von seinem Sichtfeld mindestens berührt werden. Dann überprüft er alle Ameisen in diesen Eimern auf Sichtkontakt. In diesem Beispiel muss der Käfer nur noch 9 Ameisen auf Sichtkontakt überprüfen. Die tatsächliche Komplexitätsreduktion hängt von der Größe des Spielfeldes, der Eimergröße und der Anzahl der Ameisen ab.

Zusätzlich muss die Simulation nun aber auch noch die Eimer verwalten, da die Ameisen sich ja fortbewegen und dabei die Eimer wechseln. Diese Operation ist aber wenig aufwendig, und kann weiter reduziert werden, wenn man die Berechnung "fuzzy" macht, also zum Beispiel nur jeden fünften Schritt ausführt - solche Vereinfachungen sind bei Natursimulationen nicht ungewöhnlich. Gute Ergebnisse haben wir übrigens erreicht, wenn wir die Eimergröße gleich des Sichtradius der Ameisen gesetzt haben.