Stefan, Simon, Robin, Caspar und Ata "**Evacuation simulator**" TODO: Struktur-erklährung: Dijkstra, Kräfte-Zusammenwirkung, Gas-Modell, verwendete Software(python-pakete) __**Code:**__ {{:ss17:evacuation.zip|}} Runterladen, entpacken und README.txt für Anleitung lesen __**Idee:**__ Wir wollen ein Programm schreiben, dass die Evakuierung einer Menschenmasse aus einem Gebäude simuliert. Die Personen sollen in einer GUI durch Punkte dargestellt werden und sich realistisch verhalten: * Richtung Ausgang laufen * Sich gegenseitig abstoßen * Bei Gedränge sich gegenseitig verlangsamen * beschränkte Beschleunigung haben und eine maximale Geschwindigkeit * Schildern folgen Einem Nutzer des Programms soll die Aufgabe gestellt werden, durch geschickte Anordnung von "Ausgang -->"-Schildern den Personen-Strom so zu lenken, dass möglichst schnelle Evakuierung erfolgt. Umsetzung: Wir entscheiden und dafür, das Gebäude durch undurchlässige Polygonzüge darzustellen, anstatt ein diskretes Gitter zu verwenden. Die Personen können sich so an jedem erreichbaren Punkt befinden und wir glauben, Laggs und Blockaden zu vermeiden. Zuerst erstellen wir ein UML-Diagramm, indem die grobe Klassenstruktur festgelegt wird. __**Arbeits-Protokoll:**__ Zu jeder Woche sind jeweils die Einträge vom git-log angegeben Author: stefan Date: Thu May 18 19:56:45 2017 +0200 initalized project and constructed first files Author: stefan Date: Thu Jun 1 17:59:38 2017 +0200 started a very simple GUI Author: stefan Date: Fri Jun 2 14:29:57 2017 +0200 now people can fall :-) Author: Caspar Date: Mon Jun 5 17:20:17 2017 +0200 caspars klassenentwuerfe 08.06.2017 (Simon) * git bei großer mehrheit zum Laufen gebracht * Folgende Klassen Implementiert: {{:ss17:diagram.png?200|}} Author: Simon Date: Thu Jun 8 16:50:51 2017 +0200 Szenario Deklariert Author: stefan Date: Thu Jun 8 16:45:36 2017 +0200 Karte-conflict deleted Author: Simon Date: Thu Jun 8 15:31:35 2017 +0200 Karte und Szenario hinzugefügt 15.06.2017 (Caspar + Caspar) * Über die beziehungen zwischen einzelnen Klassen geredet * Url Diagramm überarbeitet {{:ss17:ueberarbeitet.jpeg?200|}} * Simon und Caspar haben angefangen sich mit expliziten Klassen zu beschäftigen * Ata und Robin haben ihre Pygame und Klassenkenntnisse Erweitert. * Stefan fängt an, einfache Szenarien zu basteln Author: Simon Date: Wed Jun 21 17:55:15 2017 +0200 Personengenerierung Implementiert (siehe Bsp. im Tests-Verzeichnis) Author: Simon Date: Wed Jun 21 17:52:45 2017 +0200 Personengenerierung Implementiert (siehe Bsp. im Tests-Verzeichnis) 22.06.2017 (Caspar) * Atas Bakterien können sich nun bewegen bevor sie sterben, GUI macht fortschritte * Robin lernt weiter Pygame für die GUI * Simon hat den Entwurf eines Personen/Karteneditors entwickelt *edit: (Simon) .. kurz vor Ende des Labors abgeschlossen; nutzbarer (Prototyp) Editor fertig * Stefan hat die Polygonklasse implementiert und beginnt nun mit dem Dijkstra Algorithmus * Caspar arbeitet an der Bewegungsverhaltenklasse an einer möglichst realen abstoßungsregel Author: stefan Date: Thu Jun 22 08:28:39 2017 +0200 took over the gits version of person.py, and my version of main.py Author: stefan Date: Thu Jun 22 08:24:34 2017 +0200 main.py tests new obstacles Author: stefan Date: Thu Jun 22 08:23:23 2017 +0200 Obstacle.py is done and can be tested. but tests are not done yet, so it compiles but does not work under guaranty 29.06.2017 (Stefan+Caspar) * Einfache Szenarien funktionieren: Eine Punkt der nur Beschleinigung nach unten erfährt kann jetzt durch ein Labyrinth aus Polygonen fallen. * Simon implementiert Laden und Speichern mit pickle * Simon erstellt Exit-Points und Caspars PersonenBewegung läuft jetzt in Richtung Exit * Die Simulations-Geschwindigkeit und die Simulationsrate wurden entkoppelt und können angepasst werden * Ata lernt die Grundlagen Objektorientierter Programmierung * Robin versucht PyGame zu verstehen 06.07.2017 (Stefan) * Stefan bringt Dijkstra zum Laufen und die Personen finden nun den kürzesten Weg zum nächsten Exit-Point durch ein Labyrinth aus Polygonen: {{:ss17:selection_019.png?250|}} * Robin vertieft (von zu Hause) seine PyGame-Kenntnisse * Simon ist nicht da * Caspar bastelt (zu Hause) weiter an der Struktur PeronenBewegung. Die verschiedenen Ziele gehen jetzt gewichtet in die Bewegungsrichtung ein. Alles wird in ins Hauptprogramm gemerged. * Ata plant die neue GUI Author: Simon Date: Thu Jul 6 18:00:49 2017 +0200 Personen werden in den Exit aufgenommen und aus der Simulation genommen Author: stefan Date: Thu Jul 6 19:03:56 2017 +0200 implemented Map.pointIsAvailable Author: stefan Date: Thu Jul 6 18:27:00 2017 +0200 personen laufen jetzt mit etwas abstand um die ecken Author: stefan Date: Fri Jul 7 15:34:17 2017 +0200 wenn dijkstra probleme macht, renn er einfach direkt richtung ziel Author: Simon Date: Fri Jul 7 15:32:58 2017 +0200 ziel wird gezeichnet Personen werden auf freie Positionen gesetzt 13.07.2017 (Stefan+Caspar) * Robin steigt aus dem Projekt aus. * Wir geben die neue GUI auf, weil keine Aussicht besteht, sie noch rechtzeitig fertig zu programmieren * Caspar arbeitet am Mearching auf git bezueglich der Bewegungsklasse von ihm und der von Simon * Jetzt stoßen sich Personen gegeseitig ab, wie gewünscht * Stefan uebernimmt die Aufgaben von Robin und Ata und übernimmt seine erste rudimentaere GUI als Haupt-GUI * Ata entwirft eine Button klasse die leider nicht mehr implementiert wird * Der MapGenerator von Simon funktioniert nun und wir erstellen erste Instanzen mit nehreren Gängen und Räumen. Mit interessanten Personnezahlen(30-50) läuft die Simulation aber noch nicht flüssig. Author: Caspar Date: Thu Jul 13 17:53:42 2017 +0200 Bewegungsklasse ueberarbeitet Author: stefan Date: Thu Jul 13 16:39:35 2017 +0200 simulation constructor skeleton added Author: Simon Date: Thu Jul 13 16:19:04 2017 +0200 cleaned Bewegungsverhalten 2.0 Author: Caspar Date: Thu Jul 13 15:25:29 2017 +0200 Saemtliche Klassen mit Kommentaren ausgestattet Author: Anntares93 Date: Thu Jul 13 15:20:18 2017 +0200 GUI editor added Author: stefan Date: Wed Jul 19 15:47:56 2017 +0200 dijkstra even faster 20.07.2017 (Stefan+Caspar) * Der Dijkstra Algorithmus laeuft nun schneller. Jetzt können die aufwendigereren Instanzen mit bis zu 30 Personen halbwegs flüssig. * Stefan bastelt alles zusammen um eine Abgabe fuer das Projekt presentieren zu koennen. * Laufendes Programm: * {{:ss17:evacuation_advanced.png?200|}} * Caspar erweitert die Personenbewegungsklasse: Sie berücksichtigen jetzt die Ecken korrekt und können verschiedene Gewichtungen der Stöße, Geschwindigkeiten und Volumina haben. __**Ergebnis:**__ Der Nutzer kann mithilfe eines simplen Editors komfortabel eigene Instanzen/Gebäude samt Ausgängen erstellen und mit Personen füllen und abspeichern. Das Hauptprogramm kann die gespeicherten Instanzen (Pfad ist noch hard-coded) laden und lässt die Simulation laufen. Die Personen errechnen den kürzesten Weg zum nächsten Ausgang und folgen ihm mit realistischer Beschleunigung und Geschwindigkeit. Wir hatten keine Zeit mehr, das Anbringen von Schildern zu implementieren und die Personen behindern sich noch nicht in gewünschtem Maße. Das Gerüst für verschiedene Arten von Menschen ist gebaut, aber wir hatten keine Zeit, mehrere Typen zu implementieren. Bevor die Simulation losgeht, wird erst ein Kürzeste-Wege-Baum mit Dijkstra/A* errechnet. Dies kann einige Zeit dauern, erlaubt uns aber, Simulationen mit bis zu 50 Menschen flüssig laufen zu lassen. __**Programmstruktur:**__ Die Simulation der Evakuierung läuft Zeitdiskretisiert (derzeit 100 steps/second) ab. Das heißt, jede Person muss eine Geschwindigkeit haben, die auch in jedem Zeitschritt aktualisiert wird. Die Steuerung der Simulation (entfernen von Personen, Zeitsteuerung, Start/Ende usw.) übernimmt die "Simulation"-Klasse. Dazu modellieren wir die Personen ähnlich wie Gas-Moleküle im Raum, auf die verschiedene Kräfte wirken: * Wände stoßen Personen ab, wenn sie zu nah dran sind, wie Elektronen von negativ geladenen Platten. * Personen stoßen sich ab, wie gleich geladene Teilchen. * Personen werden mit konstanter Kraft in Richtung des kürzesten Weges zum nächsten Ausgang gezogen. * Personen bremsen alle Personen ihrer Umgebung. Dies Simuliert gegenseitige Behinderung bei Gedränge. Allerding haben unsere Menschen eine maximale Geschwindigkeit und maximale Beschleunigung (ist realistischer). Alle Kräfte werden in jedem Zeitschritt addiert und die Summe wird wie im Molekülmodell multipliziert mit der Zeitintervalllänge auf die Geschwindigkeit addiert. Kräfteaddition:{{:ss17:kraftaddition.gif?100|}} Code: def getMovement(person, timestep, nearbyPeople, _map): %berechnet den bewegungsvektor anhand von den anderen funktionen d = array([0.0, 0.0]) d += person.last_move if(len(_map.getExits())>0): d += simpleFall(person, timestep, _map, _map.getExits()[0]) d += impactHindernisse(person, _map) d += impactPersonen(person, nearbyPeople) speed = LA.norm(d) / timestep factor = min(speed, person.maxSpeed) / speed return d * factor Die Berechnung des kürzesten Weges zum nächsten Ausgang für jede Person in jedem Zeitschritt dauert zu lange. Deshalb werden mit dem Dijkstra-Algorithmus zu Beginn der Simulation vorberechnet und in Form vom abzulaufenden Punkten gespeichert. Wir benutzen dafür das Python-Paket. from Dijkstra import getShortestPath Außerdem verwenden wir die Pakete "pickle" und "pygame" für den Gebäudeeditor zum Erstellen und Speichern/Laden von Instanzen. Das Pjojekt war anfangs größer angelegt, als es geworden ist. Deshalb hatten wir von Anfang an die Klassenstrukturen so gebaut, dass sie leicht erweiterbar sind. Derzeit läuft die Simulation noch ohne, dass der Nutzer Einfluss darauf nehmen kann. Die Struktur der Klassen ist aber darauf ausgelegt, dass der Nutzer interaktiv verschiedene Instanzen der Klasse "Map" laden kann und die Simulation wie in einem Video-Player vorwärts/rückwärts/schneller/langsamer laufen lassen kann. Zusätzlich könnte man außer Ausgängen noch andere Unterklassen von "PoI" (point of interest), wie z.b. Schilder implementieren, die der Nutzer einfügen kann, um die Personen zu lenken.