Mathesis Wiki

Stefan, Simon, Robin, Caspar und Ata

„Evacuation simulator“

TODO: Struktur-erklährung: Dijkstra, Kräfte-Zusammenwirkung, Gas-Modell, verwendete Software(python-pakete)

Code: 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:

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

• 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:

• 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:
• 
• 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:

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.