Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

--- ss20:plagen-simulation [2020/08/26 14:59]
egerlach [2. Implementierung von Schwarmverhalten]
+++ ss20:plagen-simulation [2020/09/08 17:00] (aktuell)
valentingiogoli [2.1 Performance Optimierung]
@@ Zeile 1: / Zeile 1: @@
-====== Plagenbekämpfung ======
+[[projekte_im_sommersemester_2020|← Zurück zur Projektauswahl]]
+====== Simulation von Heuschreckenschwärmen ======
-==== Projektziel ====
-Wir wollen die Verbreitung von Heuschreckenschwärmen abhängig von unterschiedlichen Parameter simulieren und in einem Spiel - ähnlich wie \\ [[https://www.ndemiccreations.com/en/22-plague-inc | Plague Inc.]] - visualisieren. Dabei wollen wir möglichst realitätsnah bleiben und aktuelle Erkenntnisse mit einbeziehen.
 ==== Teilnehmer*innen ====
@@ Zeile 22: / Zeile 22: @@
 **Was ist das Ziel unseres Projekts?**
-Wir wollen inspiriert von der aktuellen Heuschreckenplage in Ostafrika Heuschreckenplagen simulieren und visualisieren. Dabei betrachten wir das Schwarmverhalten der Heuschrecken und äußere Einflussfaktoren wie Futterquellen und Bekämpfung (z.B. durch Pestizide). Dabei wollen wir möglichst realitätsnah bleiben und aktuelle Erkenntnisse mit einbeziehen.
+Wir wollen inspiriert von der aktuellen Heuschreckenplage in Ostafrika Heuschreckenplagen simulieren und visualisieren. Dabei betrachten wir das Schwarmverhalten der Heuschrecken und äußere Einflussfaktoren wie Futterquellen und Bekämpfung (z.B. durch Pestizide). Wir wollen hierbei möglichst realitätsnah bleiben und aktuelle Erkenntnisse mit einbeziehen.
 **Was ist Schwarmverhalten?**
-Schwarmverhalten bezeichnet den Zusammenschluss von Tiere zu Aggregationen, dabei bewegen sich die Individuen in eine gemeinsame Richtung.Daraus ergeben sich Vorteile bei der Nahrungssuche und erhöhter Schutz vor Fressfeinden. Typische Schwarmtiere sind Fische, Vögel und Insekten wie die Wander- und Wüstenheuschrecken.
+Schwarmverhalten bezeichnet den Zusammenschluss von Tiere zu Aggregationen, dabei bewegen sich die Individuen in eine gemeinsame Richtung. Daraus ergeben sich Vorteile bei der Nahrungssuche und erhöhter Schutz vor Fressfeinden. Typische Schwarmtiere sind Fische, Vögel und Insekten wie die Wander- und Wüstenheuschrecken.
 **Wie funktioniert die Schwarmbildung bei Heuschrecken?**
@@ Zeile 49: / Zeile 48: @@
 Grafik aus [[http://coffeepoweredmachine.com/wp-content/uploads/2013/08/boidsThreeRules.png]]
-Im Folgenden eingige GIFs zu unserer eigenen Implementierung dieser Regeln, zunächst alle kombiniert und dann die drei Regeln im Einzelnen.
+Im Folgenden einige GIFs zu unserer eigenen Implementierung dieser Regeln, zunächst alle kombiniert und dann die drei Regeln im Einzelnen.
 {{:ss20:all-together.gif?direct|}}
@@ Zeile 55: / Zeile 54: @@
-==== Separation ====
-{{:ss20:seperation.gif?direct|}}
 ==== Alignment ====
+<code>
+def alignment(self,boid,ind):
+        avg = Vector(0,0)
+        count = 0
+        for i in ind[0]: #Für alle Elemente in Ind (Nachbarn innerhalb bestimmtem Radius/ Die k nähesten Nachbarn) wird gecheckt ob ihre Position der Eigenen entspricht(nur bei sich sebst der Fall)
+            if boid[i].position != self.position:
+                avg += boid[i].velocity #Alle Geschwindigkeitsvektoren der Nachbarn werden zusammenaddiert
+                count += 1 #Anzahl der Nachbarn wird gezählt
+        if count > 0: #Bei mehr als Null Nachbarn wird der Durchschnittsvektor berechnet, normiert und mit der maximal Geschwindigkeit multipliziert. Anschließend wird der eigene Geschwindigkeitsvektor subtrahiert und der Vektor wird ein weiteres mal Normiert und mit der maximal Kraft multipliziert.
+            avg /= count
+            avg = (avg /np.linalg.norm(avg)) * self.max_speed
+            avg -= self.velocity
+            avg = (avg /np.linalg.norm(avg)) * self.max_force
+        self.acceleration += avg #Ergebniss wird zu dem Beschleunigungsvektor addiert
+</code>
 {{:ss20:alignment.gif?direct|}}
 ==== Cohesion ====
+<code>
+    def cohesion(self,boid,ind): #gleich dem allignment, bloß mit der positon
+        center = Vector(0,0)
+        count = 0
+        for i in ind[0]:
+            if boid[i].position != self.position:
+                center += boid[i].position
+                count += 1
+        if count > 0:
+            center /= count
+            center -= self.position
+            center = (center /np.linalg.norm(center)) * self.max_speed
+            center -= self.velocity
+            center = (center /np.linalg.norm(center)) * self.max_force
+        self.acceleration += center
+</code>
 {{:ss20:cohesion.gif?direct|}}
+==== Separation ====
+<code>
+    def seperation(self,boid,ind): #gleich dem allignment, bloß mit der der differenz dem normierten Abstand(differenz der Positionen)
+        dist = Vector(0,0)
+        count = 0
+        for i in ind[0]:
+            if boid[i].position != self.position:
+                dist += (self.position - boid[i].position)/np.linalg.norm(boid[i].position - self.position)
+                count += 1
+        if count > 0 :
+            dist /= count
+            dist = (dist /np.linalg.norm(dist)) * self.max_speed
+            dist -= self.velocity
+            dist = (dist /np.linalg.norm(dist)) * self.max_force
+        self.acceleration += dist
+</code>
+{{:ss20:seperation.gif?direct|}}
+===== 2.1 Performance Optimierung =====
+In der grundlegenden Implementierung des Algorithmus prüft jeder Boid alle anderen Boids aus der flock Liste, um zu berechnen, ob sie sich innerhalb eines vorgegebenen Radius befinden und somit als Nachbarn gelten.
+Hierbei werden in jedem Schritt viele vermeidbare Berechnungen ausgeführt, weshalb der Code bei n > 50 Boids sehr langsam wird. Ohne weitere Bearbeitung wäre der Algorithmus sehr ineffizient mit einer Komplexität von O(n^2).
+Um dem Entgegen zu wirken haben wir uns entscheiden KD-Trees zu verwenden. KD-Trees sind Suchbäume um Punkte in einem k dimensionalen zu organisieren. In unserem Projekt ist k = 2. KD-Trees sind besonders praktisch für die Suche nach den nähsten Nachbarn oder der Suche innerhalb eines bestimmten Abstands.
+In unserem Code haben wir sklearn library verwendet. Durch die Implementierung des KDTree aus sklearn.neighbors werden nur noch die Nachbarn eines Boids innerhalb eines Radius r = 50 betrachtet.
+Hierdurch konnten wir, je nach verfügbarer Rechenleistung, Schwärme mit bis zu n = 500 Boids simulieren.
+[[https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html#sklearn.neighbors.KDTree| weitere Einzelheiten zu den KD-Trees von scikit-learn]]
+===== 3. Fazit =====
+Wir hatten uns mehr vorgenommen, als wir schlussendlich erreicht haben. Ursprünglich wir wollten eine interaktive Visualisierung von Heuschreckenplagen realisieren. Im Laufe der Zeit haben wir den interaktiven Aspekt etwas vernachlässigt und uns dafür auf die Simulation des Schwarmverhalten fokussiert. Dabei haben wir einiges über Schwärme und objektorientierte Programmierung in Phyton gelernt.

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge