Mathesis Wiki

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
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 <bzfmakks@zib.de>
Date:   Thu May 18 19:56:45 2017 +0200

    initalized project and constructed first files

Author: stefan <bzfmakks@zib.de>
Date:   Thu Jun 1 17:59:38 2017 +0200

    started a very simple GUI
    

Author: stefan <bzfmakks@zib.de>
Date:   Fri Jun 2 14:29:57 2017 +0200

    now people can fall :-)

    
Author: Caspar <caspar.meister@hotmail.de>
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 <nomis.r@web.de>
Date:   Thu Jun 8 16:50:51 2017 +0200

    Szenario Deklariert


Author: stefan <bzfmakks@zib.de>
Date:   Thu Jun 8 16:45:36 2017 +0200

    Karte-conflict deleted


Author: Simon <nomis.r@web.de>
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 <nomis.r@web.de>
Date:   Wed Jun 21 17:55:15 2017 +0200

    Personengenerierung Implementiert (siehe Bsp. im Tests-Verzeichnis)

Author: Simon <nomis.r@web.de>
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 <bzfmakks@zib.de>
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 <bzfmakks@zib.de>
Date:   Thu Jun 22 08:24:34 2017 +0200

    main.py tests new obstacles

Author: stefan <bzfmakks@zib.de>
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 <nomis.r@web.de>
Date:   Thu Jul 6 18:00:49 2017 +0200

    Personen werden in den Exit aufgenommen und aus der Simulation genommen

Author: stefan <bzfmakks@zib.de>
Date:   Thu Jul 6 19:03:56 2017 +0200

    implemented Map.pointIsAvailable

Author: stefan <bzfmakks@zib.de>
Date:   Thu Jul 6 18:27:00 2017 +0200

    personen laufen jetzt mit etwas abstand um die ecken

Author: stefan <bzfmakks@zib.de>
Date:   Fri Jul 7 15:34:17 2017 +0200

    wenn dijkstra probleme macht, renn er einfach direkt richtung ziel

Author: Simon <nomis.r@web.de>
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 <caspar.meister@hotmail.de>
Date:   Thu Jul 13 17:53:42 2017 +0200

    Bewegungsklasse ueberarbeitet
Author: stefan <bzfmakks@zib.de>
Date:   Thu Jul 13 16:39:35 2017 +0200

    simulation constructor skeleton added

Author: Simon <nomis.r@web.de>
Date:   Thu Jul 13 16:19:04 2017 +0200

    cleaned Bewegungsverhalten 2.0


Author: Caspar <caspar.meister@hotmail.de>
Date:   Thu Jul 13 15:25:29 2017 +0200

    Saemtliche Klassen mit Kommentaren ausgestattet

Author: Anntares93 <ajmg@hotmail.de>
Date:   Thu Jul 13 15:20:18 2017 +0200

    GUI editor added

Author: stefan <bzfmakks@zib.de>
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:
<code python> 
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
</code>

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. <code python>from Dijkstra import getShortestPath </code>

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.
Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Seiten-Werkzeuge
