Gruppenmitglieder: Florian Teßmer, Marvin Münnich, Maren Kretzschmar, Vladimir Fomin, Florian Hellbusch

In diesem Projekt versuchen wir die Simulation sogenannter ‘Boids’ (vom engl. 'bird-oid object'), die sich in der Natur ähnlich zu Schwarzfischen verhalten. Die Agenten sollen nach den drei Prinzipien Ausrichtung, Separation und Kohäsion handeln. Das bedeutet, dass sie sich der Ausrichtung der anderen Agenten angleichen, versuchen in der Nähe anderer Boids zu bleiben, aber auf Abstand zu gehen, wenn sie zu nah an einen anderen Agenten kommen. Dadurch versuchen wir, ähnliche Muster entstehen zu lassen wie bei z.B. Schwärmen von Sardinen.

Wir haben uns zu Beginn des Projektes auf folgende Mindest- und Maximalziele geeinigt.

1. Zuerst wollen wir eine 2D Simulation mit PyGame erstellen, in der sich die Agenten nach den in der Kategorie „Ideen“ beschriebenen Grundprinzipien verhalten.
2. Danach wollen wir eine ‘Fressfeinde’-Funktion einfügen, durch die zufällig ausgewählte Boids zu Fressfeinden werden und sich die übrigen Boids ihnen gegen über anders verhalten. Das implementieren wir hauptsächlich durch die Separation-Funktion.
3. Später planen wir Hindernisse einzubauen, um die die Boids herum navigieren müssen.
4. Im Optimalfall würden wir unsere Simulation mit vPython in 3D übertragen.

In Sachen Arbeitsteilung, um diese Ziele zu erreichen, entschieden wir, dass Marvin das wöchentliche Protokoll führt. Andererseits haben wir auch gesagt, dass wir uns gemeinsam mit einem Ziel beschäftigen und bei einem Durchbruch gemeinsam darüber diskutieren. Diese Struktur ergab sich dadurch, dass die Ziele hauptsächlich in der vorgegebenen Reihenfolge Sinn ergeben.

Hier ist unser Protokoll.

Unser Programm lässt sich in 5 Hauptbestandteile aufteilen:

1. Erzeugung aller Boids. Anzahl an Boids, Fressfeinden und Hindernissen werden zu Beginn festgelegt. Jeder Boid wird als Tupel mit Geschwindigkeit und Position gespeichert.

Jetzt betrachten wir jeden Boid einzeln. Dieser Boid kann als “aktuell” bezeichnet werden.

2. Vom aktuellen Boid innerhalb des Radius sichtbare Boids bestimmen. Der Radius wird beim Start des Programms festgelegt und dient dazu, dass ein jeweiliger Boid nicht vom ganzen Schwarm, sondern nur von den Boids in seiner unmittelbaren Umgebung beeinflusst wird.

3. Kräfteberechnung in Abhängigkeit von Positionen der sichtbaren Boids. Die Kräfteberechung, d.h. die Bestimmung der neuen Bewegungsrichtung jedes Individuums in Schwärmen folgt nach drei Regeln - Separation, Kohäsion und Ausrichtung.

4. Aus berechneten Kräften neue End-Geschwindigkeit zusammensetzen.

5. Positionen aller Boids updaten.

Mithilfe von pygame (2D-Version) bzw. vpython (3D-Version) erfolgt dann die Darstellung der Boids auf dem Bildschirm.

Nachfolgend gezeigte Code-Ausschnitte stammen aus der 2D-Version. Die 3D-Version hat jedoch einen ähnlichen Code.

Für die erste Erzeugung der Boids bei Start werden Anzahl der Boids, Fressfeinde, Hindernisse sowie für spätere Berechnungen, der Radius festgelgt.

    def __init__(self, n, s, r):  # B = Boids([30, 1, 0], [1000, 1000], 100)
        self.n = n
        self.boundry_size = s
        self.radius = r
        self.boid_positions, self.boid_velocities = self.generate_agents(0)
        self.pred_positions, self.pred_velocities = self.generate_agents(1)
        self.obstacle_positions = np.random.rand(self.n[2], 2) * self.boundry_size
 
        self.target_framerate = 60
        self.speed = 60 / self.target_framerate

Eine Liste mit Positionen und Geschwindigkeiten von Boids und Fressfeinden wird zu Beginn durch die Funktion self.generate_agents() erzeugt. Die Fressfeinde bewegen sich schneller als die Boids.

    # typ 0: boids / typ 1: predators
    def generate_agents(self, typ):
        positions = np.random.rand(self.n[typ], 2) * self.boundry_size
        velocities = np.ones([self.n[typ], 2]) * [1, 0]
        angles = np.random.rand(self.n[typ]) * np.pi * 2
 
        for i in range(self.n[typ]):
            velocities[i] = rotate_vector(velocities[i], angles[i])
 
        return (positions, velocities * self.speed * (2 + typ))

Nun werden alle vom aktuellen Boid innerhalb des Radius sichtbare Boids bestimmt. Nur diese spielen später bei der Kräfteberechnung eine Rolle. Die Funktion get_target_mask() gibt ein Array zurück. Dabei wird die Liste aller Positionen der Boids als Grundlage genommen und geschaut, ob der Boid der jeweiligen Position innerhalb oder außerhalb des Radius ist. Befindet er sich im Radius, wird sein Wert auf True gesetzt. Da die Positionen innerhalb der Liste gleich bleiben, kann jeder Boid später auf eine Position zurückverfolgt werden. Hierbei wird unterschieden, ob es sich beim aktuellen Boid um Boid oder Predator handelt. Handelt es sich um einen Predator wird der betrachtete Radius verdreifacht.

    def get_target_mask(self, current_pos, current_vel = np.zeros(2)):
        boid_mask = np.zeros([self.n[0]], dtype=bool)
...
 
        for i in range(self.n[0]):
            if (self.boid_positions[i] != current_pos).all() and np.dot(current_vel, self.boid_positions[i] - current_pos) >= 0:
                if current_pos in self.pred_positions:
                    boid_mask[i] = np.linalg.norm(self.boid_positions[i] - current_pos) < self.radius * 3
                else:
                    boid_mask[i] = np.linalg.norm(self.boid_positions[i] - current_pos) < self.radius
 ...
 
        return (boid_mask, pred_mask, obstacle_mask)

Nachdem alle Boids erzeugt wurden können wir mit der eigentlichen Simulation des Schwarmverhaltens beginnen. Jedes Individuum eines Schwarms folgt immer drei bestimmten Regeln - Separation, Kohäsion und Ausrichtung. Alle drei Kräfte ermöglichen zusammen das typische Schwarmverhalten. Bei uns sind die Kräfte Vektoren, die die neue Richtung des aktuellen Boids anzeigen.

Separation - Der aktuelle Boid (grün) bewegt sich in eine Richtung mit der eine Häufung von mehreren Boids an einem Ort verhindert werden kann. Wir berechnen diese Kraft (roter Pfeil), indem wir die alle Normvektoren zwischen aktuellen Boid (grün) und jeweiligem blauen Boid nach Nähe zum aktuellen Boid gewichten und addieren.

    def get_separation_force(self, current_pos, target_pos):
        vectors = current_pos - target_pos
        distances = np.reshape(np.linalg.norm(vectors, axis=1), (len(vectors), 1))
        norm_vectors = vectors / distances
        weighted_vectors = norm_vectors * (self.radius - distances)
        force = np.sum(weighted_vectors, 0) / len(vectors)
        return force

Alignment - Der aktuelle Boid bewegt sich ungefähr in die selbe Richtung wie seine Nachbarn. Hierfür gewichten wir die Normvektoren der Geschwindigkeiten der betrachteten Boids nach Abstand zum aktuellen Boid.

    def get_alignment_force(self, current_pos, target_pos, target_vel):
        vectors_pos = current_pos - target_pos
        distances = np.reshape(np.linalg.norm(vectors_pos, axis=1), (len(vectors_pos), 1))
 
        length_vectors_vel = np.reshape(np.linalg.norm(target_vel, axis=1), (len(target_vel), 1))
        norm_vectors_vel = target_vel / length_vectors_vel
        weighted_vectors = norm_vectors_vel * (self.radius - distances)
        force = np.sum(weighted_vectors, 0) / len(weighted_vectors)
        return force

Kohäsion - Der aktuelle Boid bewegt sich zum Mittelpunkt der betrachteten Boids. Für den Mittelpunkt der betrachteten Boids werden alle Position addiert und durch die Anzahl geteilt. Der Vektor ensteht aus Differenz zwischen Mittelpunkt und Position.

    def get_cohesion_force(self, current_pos, target_pos):
        center_position = np.sum(target_pos, 0) / len(target_pos)
        force = center_position - current_pos
        return force

Nachdem die Fressfeinde zusammen mit den Boids erzeugt wurden und durch ein Array unterschieden wird, welche Boids als Predator behandelt werden sollen, bekommen sie in der draw-Funktion eine rote Farbe und handeln nach ausgewählten Kräften. Einerseits nutzen die Fressfeinde die Kohäsionskraft, um sich zu den normalen Boids zu bewegen. Andererseits nutzen diese die Separationskraft in Bezug auf die Fressfeinde, verstärkt um den Faktor 10 für ein verstärktes Fluchtverhalten.

Hindernisse funktionieren auf dieselbe Weise, nur dass diese durch Stillstehen keine Geschwindigkeitszuweisung benötigen und daher keine Kohäsionskraft anwenden, also nur von den Boids die Separationskraft berechnet wird. Ihnen wurde die Farbe blau zugeordnet.

Zuerst werden aus der Maske alle Positionen der Target boids bestimmt.

    def update_velocity(self, current_pos, current_vel):
 
        boid_target_mask, pred_target_mask, obstacle_target_mask = self.get_target_mask(current_pos, current_vel)
 
        # applying target masks
        # to get the positions and velocities of visible boids and obstacles
        boid_target_pos, boid_target_vel = self.boid_positions[boid_target_mask], self.boid_velocities[boid_target_mask]
        pred_target_pos, pred_target_vel = self.pred_positions[pred_target_mask], self.pred_velocities[pred_target_mask]
        obstacle_target_pos = self.obstacle_positions[obstacle_target_mask]
     ...

Nun werden die Kräfte mithilfe der zuvor bestimmten Funktionen berechnet. Ist im Sichtfeld des aktuellen Boid mind. ein Feind, wird die zehnfache Separation-Kraft angewendet - schließlich will der Boid schneller vom Predator wegschwimmen, sobald er ihn sieht.

Letztendlich werden die neuen Geschwindigkeiten zu den Positionen hinzuaddiert.

Der Modus lässt sich durch die Home-Taste (Pos1) starten. Durch das Eingeben einer Zahl von 1-5 wird ein bestimmter Modus ausgewählt. Der interaktive Modus ist dazu da die wirkenden Kräfte auch sehen zu können.

Bei Modus 1-4 wird der Mauszeiger als weiterer Boid behandelt. Mit dem anfangs festgelegten Radius wird ein Kreis um den Mauszeiger dargestellt. Alle weiteren Boids bewegen sich nicht. Für den Mauszeiger-Boid wird/werden je nach ausgewählten Modus

1. die Kohäsionskraft als blaue Linie angezeigt.
2. die Alignment-Kraft als blaue Linie angezeigt.
3. die Separationskraft als blaue Linie angezeigt.
4. alle einzelnen Kräfte (grau) und die insgesamt wirkende Kraft (grün) angezeigt.

Modus 3: Separation Modus 4: alle Kräfte

In Modus 5 werden die Kräfte wie in Modus 4 dargestellt. Nur diesmal beziehen sie sich nicht auf den Mauszeiger, sondern auf einen Boid. Die Boids bewegen sich in diesem Modus wieder.

2D 3D

Umsetzung der Ziele: Prinzipiell haben wir alle unserer Ziele erreicht. Nur in Sachen Hindernisse haben wir uns entschieden, auf Flächenhindernisse zu verzichten, weil es das Programm unnötig verkompliziert hätte.

Probleme und Entscheidungen: Von kleineren Bugs abgesehen, haben wir wenige Umsetzungsprobleme gehabt. Unsere erste große Entscheidung war es, auf mehrere Klassen zu verzichten. Sowohl die Boids als auch die Hindernisse und Fressfeinde waren sich einfach zu ähnlich, dass man verschiedene Datencontainer gebraucht hätte. Zudem haben wir uns gegen das Feature entschieden, die Sicht nach hinten einzuschränken, weil der Code sehr kompliziert war und das Ergebnis nur geringfügig veränderte. In Sachen Kräfteabstimmung brauchte es etwas Feinabstimmung, einerseits da die Division durch 0 oft vorkam, andererseits weil die Drehung der Boids meist sehr abrupt war. Das Zurechtfinden mit vpython war herausfordernd, aber machbar.

Auswertung des Endergebnis: Im Allgemeinen sind wir mit unserem Ergebnis zufrieden. Wir haben festgestellt, dass Python als Programiersprache nicht die beste Wahl für unser Vorhaben gewesen ist, weil sich die Bewegung der Boids bei größerer Anzahl merklich verlangsamt. Aber da wir alle den Crashkurs absolviert haben und es für Anfänger leicht zu verstehen ist, haben wir das Beste daraus gemacht. Für die Zukunft gibt es wahrscheinlich noch Ausbaumöglichkeiten, um die Simulation an echte Fische anzupassen, wie das Fressen von Fischen, Fortpflanzung und weitere Umgebungsdetails, aber unsere Simulation konzentrierte sich eher auf die Bewegung besagter Fische. Dieses Ziel haben wir erreicht.

Code&Python-Pakete Protokoll GitHub Pygame Vpython Boids-Wkipedia(Bilder) Boid Video