Verkehr, Mobilität und generell die Konzipierung und Erstellung von Verkehrsinfrastruktur sind ein Kernthema in der modernen Stadtplanung. Jedoch ist es in den allerwenigsten Fällen möglich, das Konzept eines Straßensystems effektiv zu testen bevor es wirklich umgesetzt wird. Ein Ersatzmodell für das erdachte Szenario muss her.

Wir haben es uns zum Ziel gesetzt eine realitätsnahe Verkehrssimulation in der Programmiersprache Python (Version 2.7) zu programmieren, die auf veränderlichen Straßensystemen einen Verkehrsfluss simuliert, und anhand dieser Simulation die Effizienz des jeweiligen Straßensystems testet und dessen Schwachstellen aufzeigt. Ohne großen Aufwand, können so verschiedene, sehr individuelle Szenarien verglichen werden, beispielsweise ob an einer bestimmten Stelle einen Ampelkreuzung oder ein Kreisverkehr sinvoller ist. Die Auswertung beruht auf Betrachtungen der Effizienz, der Umweltfreundlichkeit, der Kollisionswahrscheinlichkeit und noch vielen weiteren Faktoren.

Um dieses Ziel zu erreichen, haben wir das Projekt in drei Phasen aufgeteilt:

Grundstruktur: Erstellung einer bedingt realitätsnahen Simulation, die auf einem beliebigen Straßennetz fließenden Verkehr simulieren kann. Die Priorität liegt noch bei der Erweiterbarkeit des Programmes, das heißt es soll eine Modulare Grundstruktur entstehen, die es erleichtert weitere Ideen zu implementieren. Wir wollen uns quasi keine Möglichkeiten „verbauen“.

Realismus:

Auf dieser Grundstruktur aufbauend legen wir wert auf Realitätsnähe. Mithilfe von realen Statistiken versuchen wir das Fahrverhalten der Autofahrer chaotisch, jedoch kontrolliert zu modellieren. Beispielhaft wäre hier der regionsspezifisch variierende Anteil an Fahrern mit Blutalkohol zu berücksichtigen, die Werte hierfür entnehmen wir offiziellen Statistiken. Dieser Alkoholpegel hat natürlich einen Einfluss auf die Fahrweise der jeweiligen Fahrer. Weitere Faktoren, die die Fahrerqualität beeinflussen können sind um einige zu nennen Erfahrung, Alter, Müdigkeit, Aggressivität und Geschlecht. Diese Faktoren haben Einfluss auf die Sichtweite, Reaktionszeit und Regelachtung der Fahrer. Den Zusammenhang zwischen diesen Fahrereigenschaften und der Fahrweise gilt es in dieser Phase zu modellieren und in der Simulation umzusetzen.

Anwendung: Wenn wir der Meinung sind, die Simulation ist realitätsnah genug, können wir unsere Simulation zur Anwendung bringen. Geplant sind u.a. die Implementierung der Simulation in ein eigenes Programm für eine Nutzerfreundliche Anwendung, die Erstellung eines Editors innerhalb dieses Programmes, mit dem einfach und schnell Straßennetze erstellt werden können und natürlich die tatsächliche Nutzung der Simulation in Form der Ausgabe aller nötigen Informationen zu einem vom Nutzer erstellten Verkehrssystem. Was die Simulation an Informationen ausgeben kann ist lediglich durch unsere Kreativität begrenzt.

Im ersten Versuch eine solche Grundstruktur zu erstellen, schufen wir das Straßennetz, die Klasse „Auto“ und eine Wegfindung, die die kürzeste Route zwischen zwei Punkten auf dem Straßennetz ermittelt. Das Konzept ging auf, jedoch verursachte die Wegfindung immer wieder Probleme, die aufwändig zu beheben waren. Das Grundproblem dieser ersten Struktur ließ sich auf einen Konzeptfehler zurückführen:

In unserem ersten Versuch (siehe: linkes Bild) haben wir in einem Straßennetz nur die Kreuzungsmittelpunkte definiert und nicht die „Reaktionspunkte“, an denen die Autos abbiegen, warten oder etwas besonderes beachten müssen. Aus diesen Kreuzungsmittelpunkten hat sich die Wegsuche immer wieder aufs Neue die Reaktionspunkte errechnet. Dadurch konnten wir jedoch auch keine eindeutigen Straßenrichtungen definieren, sodass es nicht wirklich Straßen gab, sondern eher „Straßen-Mittelstriche“, aus denen sich das Auto errechnet hat, wie weit es rechts von dieses fahren muss.

Wir haben uns aufgrund der Fehleranfälligkeit dieses Konzeptes für eine neue Struktur entschieden, in der alle Reaktionspunkte als Unterpunkte der Kreuzungen feststehen (siehe: rechtes Bild). Die Wegsuche läuft seit dem wesentlich besser und wir haben nun auch die Möglichkeit die Reaktionspunkte für verschiedene Kreuzungen definieren können, beispielsweise für eine Kreisverkehr. Da die Reaktionspunkt ähnlich funktionieren ist die Übertragung auf einen Kreisverkehr wesentlich leichter als noch in der ersten Struktur - Modularität wiederhergestellt.

Dieses zweite Konzept behielten wir bei und teilten das Programm der Übersicht und Modularität wegen in acht Unterprogramme auf: Data, Ausführende, Autoklasse, Kürzester Weg, Fahrspur Entwicklung, Autoklasse, Autofahrtklasse, Makecars und Darstellung. Zur Vereinfachung sind die Informationen, die einer Funktion oder einer Klasse jedes Mal gegeben werden von nun an als „Input“ und die Informationen, die eine Funktion oder Klasse ausgibt als „Output“ bezeichnet.

Hier werden alle Daten gespeichert, wie zum Beispiel die Koordinaten der Kreuzungsmittelpunkte und der Reaktionspunkte. Zu Bemerken ist, dass selbstverständlich nicht alle Koordinaten der Reaktionspunkte von Hand eingegeben werden müssen, sondern dass sich das Programm aus den Mittelpunkten diese errechnet. Die Benennung erfolgt gemäß dem Bild oben rechts.

In diesem Programm werden alle Unterprodramme aufgerufen. Alles wird von hier aus initialisiert, beendet und kontrolliert. Mithilfe einer solchen übergeordneten Kontrolle können wir beliebig viele Module hinzufügen, die nicht aufeinander zugreifen, sonder getrennt von hier aus „bedient“ werden können.

Die Funktion „Kürzester Weg“ ist eine Wegfindung, die aus zwei beliebigen Punkten auf dem in Data definierten Raster (Input der Funktion) die kürzester Strecke zwischen diesen beiden Punkte berechnet. Zu bemerken ist, dass dieser Start und Endpunkt nicht total zufällige Punkte auf dem Straßennetz sind, sondern sogenannte vordefinierte „Spawnpunkte“. Diese liegen vorzugsweise außerhalb des betrachteten Gebietes, sodass dort ein bestimmter Verkehrsfluss simuliert werden kann. Der Output der Funktion sind die Straßen, auf denen das Auto bzw. der Fahrer fahren muss um den Zielpunkt zu erreichen. Die bereits beschriebenen Reaktionspunkte werden an dieser Stelle noch nicht berechnet.

In der Funktion „Fahrspur Entwicklung“ werden aus den zu Fahrenden Straßen die Reaktionspunkte berechnet. Input dieser Funktion ist der Output der Funktion Kürzester Weg. Wir haben die beiden Funktionen getrennt, um Fehlerquellen besser erkennen zu können, da die Wegfindung zwar wesentlich weniger fehleranfällig läuft, allerdings weiterhin zu den häufigsten Fehlerquellen gehört.

Die Funktion „Kürzester Weg“ bekommt die Punkte A und B als Argumente gegeben (Bild 1) und gibt die Straßen 1 bis 6 in einer Liste aus (Bild 2). Die Funktion Fahrspur Entwicklung errechnet aus dieser Liste die Reaktionspunkte und gibt dieser in einer Liste aus (Bild 3), sodass aus dem Start- und Endpunkt eine Liste von Punkten errechnet wird, die das Auto abfährt um zum Ziel zu kommen.

Instanzen der Autoklasse sind individualisierbare Autos. Nahezu alles an den hier beschriebenen Autos ist veränderbar. Es kann mit dieser Klasse genauso gut ein kleiner PKW, wie ein großer langsamer LKW erstellt werden. Es kann natürlich sein, dass wir in Zukunft auf Unterklassen dieser Parent-Klasse setzen, aber in unserem momentanen Rahmen funktioniert alles soweit gut mit einer Klasse. In Punkto Realismus (Phase 2) müssen wir natürlich hier am meisten verändern. Bei der Erstellung dieser Klasse lag der Focus darauf, dass alles erweiterbar bleibt.

In der Autofahrtklasse kommen die Funktionen zur Wegsuche und die Autoklasse zusammen. Aus den Spawnpunkten werden zwei zufällige Punkte, die nicht direkt nebeneinander liegen ausgewählt und eine Route zwischen Ihnen wird berechnet. Eine Instanz der Klasse Autoklasse wird erstellt, die der jeweiligen Instanz der Autofahrtklasse zugeordnet wird. Von hier aus wird das Auto dann auch mithilfe der Funktion „pilot()“ gesteuert. Man kann also sagen, dass die Instanzen der Autofahrtklasse die Autos und ihre Aktionen verwalten und kontrollieren.

Die Funktion Makecars haben wir inzwischen gestrichen. Sie hat bis dahin eine fast zufällige Route berechnet und eine Auto erstellt und dieses einer Instanz der Klasse Autofahrt zugeordnet. Da wir dies jedoch nach gänzlicher Fehlerbeseitigung in der Klasse Autofahrt machen, wird die Funktion Makecars nicht mehr gebraucht.

Die Darstellung ist auch immer noch eine Baustelle von uns. Diese machen wir seit dem Projektanfang mit dem Modul Tkinter. Die Syntax dieses Moduls ist einfach und das User Interface sieht sehr gut aus, jedoch müssen wir mit unserer Simulation den sogenannten „Canvas“ benutzen, der bei der Simulation von über 100 Objekten gleichzeitig sehr langsam wird. Der Umstieg auf eine bessere Lösung der Darstellung, wie z.B. mit OpenGL wird eines der Themen sein, mit der wir uns im nächsten Semester beschäftigen.

Mit dieser Struktur lief die Simulation relativ flüssig, sofern man die Anzahl der Elemente gering hielt. Die erstellten Autos fuhren nur auf dem Straßennetz herum, jedoch reagierten sie noch nicht aufeinander. Auch Ampeln gab es noch nicht.

Für die Simulation von Hindernissen, wie Autos und Ampeln, standen mehrere Ideen zur Auswahl. Eines der Konzepte beinhaltete Listen von Hindernissen aller Typen, die von allen Akteuren auf dem Raster komplett kontrolliert wurden auf Hindernisse in der Nähe in der eigenen Sichtrichtung. Jedoch wäre dieses Konzept nicht sehr realitätsnahe gewesen, da die Autos bzw. die Autofahrer nicht wirklich nach Hindernissen „geschaut“ hätten. Wir haben uns jedoch für ein Konzept aus der Linearen Algebra entschieden (eventuell weil wir diese Vorlesung parallel gehört haben).

Hinter der normalen zweidimensionalen Koordinatenebene der Simulation liegt nochmals ein Raster, dass Hindernisse darstellt - quasi eine weitere Dimension. Dieses Raster stellen wir in der von uns so genannten „Hindernismatrix“ dar. Eine Matrix ist einfache eine Art Daten in einem zweidimensionalen Raster zu speichern. Das einfache Konzept dahinter ist, dass in eine Nullmatrix (nur Nullen als Einträge) alle Hindernisse - vereinfacht - als Einsen eingetragen werden.

Zu bemerken ist, dass die von uns verwendete Hindernismatrix wesentlich feiner ist, als in dem hier gezeigten Beispiel. Ein Meter ein der Simulation entspricht fünf Einträgen in der Matrix, also ist die Fahrspurbreite äquivalent zu 15 Datenpunkten. Für unsere aktuellen Zwecke ist eine solche Feinheit ausreichend.

Ein gewaltiger Vorteil dieses Ansatzes ist, dass jeder Datenpunkt natürlich nicht eindimensional sein muss, sondern wiederum eine Liste von Einträgen haben kann. So können Hindernisse sehr genau beschrieben werden. An der Differenzierung von Hindernissen arbeiten wir gerade, da dies neben der Fahrermodellierung eine große Rolle in punkto Realismus spielt.

Ideen für Hindernisargumente, die schon teilweise implementiert sind:

• Hindernisse können nur aus bestimmten Richtungen gesehen werden, wie z.B. Ampeln
• Hindernisse gelten nur für bestimmte Fahrzeuge, wie z.B. Eine zu niedrige Durchfahrtshöhe für LKWs
• Schilder: (für bestimmte oder für alle Autos)
  • Temposchilder
  • Stopschilder
  • Straßensperrung
  • Gebote/Verbote, wie z.B. Überholverbot, Spielstraße, besondere Vorfahrtregeln

Wir haben noch viele Ideen, wie wir die Simulation an diesem Punkt erweitern können. Mit diesem Konzept haben wir ein - unserer Meinung und Beobachtung nach zu urteilen - sehr realistisches Sichtmodell für die Autos, bzw. Autofahrer in unserer Simulation geschaffen, welches gut mit unserem Anspruch an die Modularität der Simulation harmoniert.

Auf dem Konzept der Hindernismatrix können wir leicht aufbauen. Das Sichtfeld des Autos kann mit einem Feld, oder vereinfacht mit Vektoren (hier zur Veranschaulichung verwendet) dargestellt werden. Dieser Vektor kann vereinfacht werden, indem man ihn nicht als Vektor sieht, sondern als einzelne Koordinatenpunkte in einer Reihe bzw. einer Liste, geordnet nach der Entfernung. Eine kleine Visualisierung macht diese Methode verständlicher.

Das Rote Auto will nach links abbiegen und schaut deswegen natürlich nicht nur geradeaus, sondern seinen Fahrweg entlang nach Hindernissen.

Der Sichtvektor wird zu Sichtpunkten vereinfacht.

Diese Sichtpunkte können der Reihe nach mit der Hindernismatrix abgeglichen werden und mit sehr wenig Rechenaufwand erhält das Auto die Entfernung zu seinem nächsten Hindernis und dessen genaue Beschreibung (gemeint ist seine Art; siehe „Hindernismatrix“).

In der Folgenden Animation wird das Konzept dieser Methode deutlich. Hinweise hierzu:

• Hier war die Simulation noch auf einem Stand, wo das Auto nur geradeaus gesehen hat und nicht in die Kurve
• Es wird nur jeder zehnte Punkt des Sichtvektors gezeigt
• Die Punkte werden grün angezeigt falls kein Hindernis in Sicht ist und rot, wenn eines in Sicht ist
• Der rot-schwarze Punkt ist der gewünschte Anhaltepunkt, an dem das Auto anhalten soll
• Da dies noch eine Version der Phase 1 ist, ist Realismus nicht unbedingt gewünscht, wichtig ist die Funktionalität.

Wichtig ist, dass mit dieser Methode natürlich die nächsten beliebig vielen Hindernisse identifiziert werden können und dass es natürlich mehrere Sichtvektoren geben kann, wie z.B. ein kurzes Sichtfeld nach hinten. Dies gehört neben der Hindernismatrix an sich und den Fahrermodellen zu den wichtigsten Gebieten der zweiten Phase.

Die Simulation ist in der Programmiersprache Python 2.7 geschrieben. In unserer aktuellsten Version benutzen wir Folgende Module:

• future
• math
• random
• Tkinter
• numpy
• time
• OpenGL
• PyGame

Die neueste bugfreie Version beinhaltet 1.269 Zeilen Code. Die Software befindet sich in der Alpha Version 3.01 und steht nur autorisierten Personen zur Verfügung.

Dieses Semester begannen wir mit einer funktionierenden Simulation, die allerdings einige Schwachstellen aufweist.

Die Simulation läuft relativ flüssig, wenn nur ein Auto simuliert wird. Jedoch ruckelte das Bild bereits bei mehr als zwei Autos so sehr, dass die Autos bei jedem Frame von Punkt zu Punkt springen und sich nicht in cm/dm pro Frame, sondern fast in Meter pro Frame fortbewegen. Dies hatte zur Folge, dass die Autos an den Reaktionspunkten (Siehe: Dokumentation von Mathesis 1) nicht erkennen dass ein neuer Streckenabschnitt beginnt und dann z.B. statt in eine Linkskurve einzubiegen geradeaus weiter fahren.

Die Darstellung mit Tkinter ist weiterhin nicht optimal, da Tkinter nicht mit GPU Beschleunigung, sondern nur auf der CPU rechnet. Jedoch reicht dies für die weitere Entwicklung aus, da hier nicht der Bottleneck der Simulation liegt. Allerdings ist die maximale Bildrate einer sich permanent erneuernden Grafik in einem Tkinter Canvas bei etwa 60 bis 70 Frames pro Sekunde. Der Nachteil daran ist, dass die Performance der Simulation nicht auf Anhieb einsehbar ist, da eine halb so rechenaufwendige Version nicht doppelt so viele Frames simulieren kann. Um den Fortschritt schnell zu sehen simulieren wir dazu ausreichend Fahrzeuge, sodass der Bottleneck wieder die Simulation und nicht die Darstellung ist.

Daher verwenden wir den bisherigen Initialisierungs-Code weiter. Die Klasse ModifiedCanvas wird im Folgenden noch näher erläutert.

self.main = Tk()	
self.cv = ModifiedCanvas(self.main, width = Variables.TKIWidth, height = Variables.TKIHeight)
self.cv.pack(expand = YES, fill = BOTH)
self.cv.setDimensions(Variables.TKIWidth, Variables.TKIHeight, Variables.TKIScale)
self.cv.activateZoom()
self.contin = True
self.cv.bind("<Button-1>", self.pause_)

Um einen Frame der Simulation zu simulieren, rufen wir die Funktion “draw“ auf. Am Ende dieser Funktion (innerhalb) wird mit dem folgenden Befehl die Funktion wieder aufgerufen. Der Vorteil daran ist, das sie auf diese Weise nicht unendlich rekursiv ist.

self.main.after(time, draw)

Die Anzeige wird jedes Mal erneuert, aber die Simulation läuft nur weiter, wenn die Variable “self.contin“ wahr ist.

Eine weitere große Schwachstelle ist, dass wir zuvor nicht besonders objektorientiert programmiert haben und sehr viele Variablen und Objekte „hard-coded“ sind (Objekte werden nicht anonym und automatisch im Programmfluss erzeugt, sondern manuell und je nach Szenario erzeugt und wirklich benannt). Das ganze Raster ist keine Instanz einer Klasse, sondern alles basiert auf handgetippten Variablen auf.

Da unser Team das regelmäßige Programmieren erst mit dem MINTgrün Studium begonnen hat, hatten wir am Anfang noch nicht die Erfahrung und Routine um diese Fehler zu vermeiden.

Mit dem Pyton-Profiler cProfile analysieren wir die Simulation:

import cProfile
cProfile.run(“Simulation()“)

Dadurch müssen wir feststellen, dass wir ein eindeutiges Bottleneck haben: Die Hindernismatrix. Die 6 rechenaufwendigsten Prozesse der Simulation sind Teil der Hindernismatrix.

Profiler-Protokoll

Wir programmieren die gesamte Simulation neu und strukturieren die Klassen und die Interaktionen neu. Dabei achten wir darauf, dass die Simulation stets erweiterbar und klar aufgeteilt bleibt. Die neue Struktur:

Dabei lassen wir zunächst die Sicht weg. Wir implementieren des weiteren das Konzept der bedingten Hindernisse - zunächst nur als bedingte Ampeln. Diese verhalten sich wie Ampeln, jedoch haben sie keine Zeitschaltung. Sie besitzen einen oder mehrere bestimmte Bereiche, die bei Abfrage des Ampelstatus nach Objekten kontrolliert werden und „rot“ sind, wenn sich ein Objekt in dem/den Kontrollbereich/-en befinden. Ein Beispiel für eine Anwendung sind Linksabbieger, die solange warten bis kein Gegenverkehr mehr kommt.

Dieses Konzept kann man beliebig erweitern indem man z.B. beim Linksabbiegen alle Autos die an einer roten Ampel warten ignoriert. Dazu braucht es lediglich eine Unterscheidung zwischen den beiden Kontrollbereichen und eine Abfrage der Ampel.

Eine weitere Anwendung hierfür ist der Kreisverkehr, in dem alle Autos die sich in dem Kreisverkehr befinden Vorfahrt haben und alle einfahrenden Autos zu warten haben.

Sichtmodelle in Simulation zu konzipieren ist ein komplexes Gebiet, da in geometrischen Simulationen alle Teile/Objekte aufeinander reagieren. Wir haben uns zu Anfang für dieses Modell entschieden, da es weitestgehend der Realität entspricht.

Die simpelste Methode einer Kollisionserkennung: Jedes Fahrzeug kontrolliert zu jedem Hindernis auf dem gesamten Stadtplan , ob dieses in seinem Sichtbereich (± °) liegt und welche Distanz es entfernt ist. Jedoch wird hierbei viel mehr als nötig gerechnet.

Ein Ansatz um den Rechenaufwand zu reduzieren ist, den Straßenplan in Abschnitte eines Rasters einzuteilen. Durch die Sichtrichtung und die Sichtdistanz werden die Rasterabschnitte der Spitze des Sichtvektors (Abschnitt 8) und der aktuellen Position (Abschnitt 1) bestimmt. Es werden dann nur alle Rasterabschnitte kontrolliert, die in dem Rechteck liegen, dass von der beiden Abschnitten (1 und 8) aufgespannt wird (Abschnitte 1, 2, 3, 6, 7 und 8).

Ein Nachteil an dieser Methode bleibt jedoch noch, setzt man die Abweichung des Sichtbereiches auf einen festen Wert wie z.B 1°, dann kann es bei einer hohen Sichtweite vorkommen, dass Autos auf der entgegenkommenden Spur als Hindernisse wahrgenommen werden. Setzt man die Abweichung auf einen zu kleinen Wert wie z.B. 0,1°, dann kann es durch Rundungsfehler sein das Hindernisse übersehen werden.

Um diese beiden Szenarien zu verhindern muss die Abweichung des Sichtvektors abhängig von der Distanz sein: Zunächst wird die Distanz bestimmt; die Spurbreite ist bekannt. Dann gilt:

Abweichung = math.arctan(Spurbreite/(2 * Distanz))

Das Raster ist in der Klasse “ObstacleGrid“ ein 3 dimensionales Numpy array “self.chunks“, das in jeder Liste alle Elemente als Integer-Zahlen enthält. Jeder Integer steht für ein Objekt, dessen Referenz in dem Dictionary „self.obstacles“ gespeichert wird. Dieses Referenz weist jedoch nicht direkt auf das Objekt, sondern auf ein Hilfsobjekt, das die für die Sicht notwendigen Variablen enthält. Ohne dieses Zwischenobjekt könnten Autofahrer nicht wissen, welche Seite einer Ampel sie sehen und würden eine Ampel theoretisch von hinten sehen. Dies würde beim Abbiegen oft zu abruptem Abbremsen führen. Bei Autos braucht es dieses Zwischenobjekt nicht, jedoch haben wir es aus Gründen der Einheitlichkeit auch implementiert.

Um einen Pool an möglichen Integer Kennung zu haben, aber nicht immer neue erzeugen zu müssen regelt die Raster-Klasse das mit zwei Listen für freie und benutzte IDs:

self.freeIDs = range(255)
self.usedIDs = []

In der Klasse wird natürlich auch festgehalten, welche ID zu welchem Objekt gehört und - zum schnellen Löschen - auch andersherum.

self.obstacles = {}
self.IDs = {}

Wir verwenden nun keinen normalen Tkinter Canvas mehr, sondern unseren Canvas-Wrapper „ModifiedCanvas“, der eine Abstraktion des Tkinter Canvas für unseren Gebrauch ist. Der herkömmliche Tkinter Canvas beinhaltet einige Dinge, die etwas ungewohnt und unpraktisch sind. Ein Problem war, das mit folgenden Befehlen

draw():
    Canvas.delete(“all“)
 
    Canvas.create_ …
    Canvas.create_ …
    Canvas.create_ …
 
    Window.after(1, draw)

der Zoom jedes mal auf den Faktor 1 zurückgesetzt wird. Sodass man zwar zoomen kann, jedoch nach einigen Millisekunden wieder das ursprüngliche Bild hat. Auch wenn man die Funktion in einer “while-Schleife“ unendlich wieder aufrufen würde ist dies ein Problem. Vermutlich wird der Zoom nicht auf danach gezeichnete Objekte sondern nur auf bestehende Objekte angewandt. Das würde bedeuten, dass alle später gezeichneten Elemente eine andere Geometrie besitzen als die vorherigen Elemente.

Das bringt uns zu der zweiten Eigenheit des Standard-Canvas: Der Ursprung des kartesischen Koordinatensystems befindet sich in der oberen linken Ecke und nicht links unten, dies ist bei GUI-Applikationen zwar sehr häufig so und in den meisten Betriebssystemen etabliert, jedoch haben wir die Simulation bis jetzt mit einer Koordinatenrichtung von unten nach oben und von links nach rechts - Also mit dem Koordinatenursprung in der unteren linken Ecke - programmiert.

Aus diesen Gründen haben wir den Canvas-Wrapper „ModifiedCanvas“ erstellt. Dieser besitzt eine eigene Geometrie und akzeptiert sowohl HEX- als auch RGB-Farben. Der Standard-Canvas akzeptiert nur HEX-Farben oder bestimmte Farbnamen. Keine Canvas-Funktionen wurden überschrieben, sondern es wurden auf diesen aufbauende Funktionen hinzugefügt.

Am Beispiel der Funktion “createLine()“ kann man sehen, wie alle Farbcodes in HEX-Farben umgewandelt werden:

def createLine(self, *args, **kwargs):
	if "fill" in kwargs:
		if type(kwargs["fill"]) == type([1,2,3]):
			kwargs["fill"] = self.RGBtoHEX(kwargs["fill"])

Eine Übersicht der Klassenfunktionen der Klasse ModifiedCanvas:

#  -*- coding: utf-8 -*-
 
from Tkinter import *
import numpy as np
import math
 
class ModifiedCanvas(Canvas):
 
        def RGBtoHEX(self, rgb):
 
	def toINT(self, integer):
 
	def setDimensions(self, width, height, scale):
 
	def createLine(self, *args, **kwargs):
 
	def createPolygon(self, *args, **kwargs):
 
	def createOval(self, *args, **kwargs):
 
	def createRectangle(self, *args, **kwargs):
 
	def createDot(self, *args, **kwargs):
 
	def createMultiplePolygons(self, ps, **kwargs):
 
	def createMultipleLines(self, ps, **kwargs):
 
	def createMultiple(self, ps, **kwargs):
 
	def createFromArray(self, ps, **kwargs):
 
	def createCar(self, x, y, direction, width, length, color = [0,0,0], **kwargs):
 
	def processKoords(self, Koords):
 
	def processKoord(self, Koord):
 
	def activateZoom(self):
 
	def zoom(self, event):
 
	def drawTargets(self,*args):
 

Den modifizierten Canvas zu initialisieren ist kaum aufwendiger als beim herkömmlichen Canvas:

#  -*- coding: utf-8 -*-
 
from Tkinter import *
from mod import ModifiedTkinter #Um den Wrapper zu importieren
 
main = Tk()
 
canvas = ModifiedCanvas(self.main, width = Variables.TKIWidth, height = Variables.TKIHeight)
canvas.pack(expand = YES, fill = BOTH)
 
canvas.setDimensions(Variables.TKIWidth, Variables.TKIHeight, Variables.TKIScale)
canvas.activateZoom()
 
'''Folgendes wird in der Manager-Klasse benutzt um die Simulation anzuhalten,
   den Canvas jedoch weiter zu updaten (inkl. Zoom etc.)'''
 
self.contin = True
canvas.bind("<Button-1>", self.pause_)

Den Nutzen dieses „ModifiedCanvas“ kann man anhand einer Funktion beispielhaft zeigen. Die Funktion ModifiedCanvas.createFromArray nimmt als Argument einen Array in dem jedes Element ein zu zeichnendes Objekt ist. Dieses Objekt ist in dem Array ebenfalls ein Array mit zwei Elementen: Das erste Element sind die Koordinatenpunkte in Form von x-y-Arrays und das zweite Element ist die Farbe in RGB Form. Des weiteren kann diese Funktion beliebig viele Keyword-Argumente annehmen, die auf jedes Element angewendet werden. In dem Array können Punkte, Kreise und Polygone gemischt enthalten sein.

def createFromArray(self, ps, **kwargs):
 
    for p in ps:
 
        if len(p[0]) == 2:
	    if "width" not in kwargs:
                #Ampelstriche sollen bei jeder Zoomstufe gleich dick sind
		kwargs["width"] = Variables.TLStripWidth
	    self.createLine(p[0], fill = p[1], **kwargs)
 
	elif len(p[0]) > 2:
	    self.createPolygon(p[0], fill = p[1], **kwargs)
 
	elif len(p[0]) == 1:
	    self.createDot(p[0], fill = p[1], **kwargs)

Die nächste Baustelle in dieser Klasse ist der Zoom. Die Elemente werden bis jetzt nur von der Linken unteren Ecke aus vergrößert, Ziel ist es das man wie bei einer Karte - z.B. Google Maps - in bestimmte Punkte reinzoomen kann und auch die Pfeiltasten zum navigieren verwendet werden können.

Mögliche Weiterentwicklungen wären auch:

• Eine 'eingebaute' Framerate Messung
• Eigene Scrollbars schon ab Initialisierung
• Blockierter Maximalzoom (sowohl raus als auch rein)
• Zoom ab bestimmter xy Position
• tags und Objektlistung, in eigenem Speicher, vllt. eine Klasse CanvasObject(object)?

Wir haben ebenfalls mit Cython programmiert, die Dateien dafür befinden sich im Build 5.07 in dem Ordner „Hindernissicht“. Jedoch benutzen wir die Dateien noch nicht, die Funktionen PYdistance und PYdirection in V07_Helper_Functions.py sind die gleichen Funktionen, nur vollständig in Python geschrieben. Wir haben aktuell keine Geschwindigkeitsprobleme, sodass wir auch die Python Funktionen benutzen können. Es wäre jedoch kein Aufwand einige Funktionen in Cython zu benutzen.

Mit einer nun sehr flüssig laufenden Simulation können wir uns ganz dem Thema Realismus widmen.

Der erste Schritt ist die Simulation unabhängig von der Bildrate zu machen. Bis jetzt lief die Simulation so, dass jedes Zeitintervall einen festen Zeitschritt bekommt. Und unabhängig von der eigentlichen Framerate simuliert wird. Also vergeht die Zeit in der Simulation schneller, wenn mehr Frames als erwartet simuliert werden, und vergeht in Zeitlupe, wenn die Framerate einbricht. Ab dem jetzigen Zeitpunkt messen wir nach jeden Zeitschritt die vergangene Zeit und die Simulation läuft in Echtzeit. Es ist ebenfalls möglich das ganze im Zeitraffer ablaufen zu lassen.

Um die Fahreigenschaften zu optimieren, trennen wir die Klassen Car und Driver. Der Fahrer bekommt bei der Initialisierung einige Variablen, wie Alter, Fähigkeit, Aggressivität und Geschlecht. In dieser Klasse wird nun alles berechnet, was von Fahrer zu Fahrer unterschiedlich ist, z.B. wie er auf eine Gelbe Ampel bei einer bestimmten Distanz und Geschwindigkeit reagiert.

Die Sichtweite ist bislang fest gesetzt. Diese sollte sowohl abhängig von der Fähigkeit und des Alters des Fahrers, wie von der Geschwindigkeit sein. Um diese zu bestimmen gibt die jeweilige Instanz der Autoklasse ihre Geschwindigkeit an ihren Fahrer weiter und dieser berechnet daraus die Sichtweite. Dies ist das gleiche Prinzip bei der Berechnung der gesamten Sicht.

Eine Liste mit den gesehenen Objekten und den jeweiligen Distanzen wird an die Fahrerklasse weitergegeben. Anhand dieser Information und der statischen (Bremskraft, etc.) und dynamischen (aktuelle Geschwindigkeit, etc.) Daten des eigenen Fahrzeugs bestimmt der Fahrer die Geschwindigkeitsänderung in Prozent der maximalen Beschleunigung bzw. der maximalen Bremskraft. Dieses Modell ist sehr realitätsnah, da der Fahrer zunächst alle Informationen erhält - nicht relevante Hindernisse werden vorher entfernt (nicht in Sichtvektor) - und gibt zurück, was in der Realität ein „aufs Gaspedal bzw. Bremspedal treten“ wäre. In die Beschleunigungsberechnung fließen Autos, Ampeln, bedingte Ampeln und Änderungen des Tempolimits mit ein. Noch nicht implementiert ist das die Fahrer vor dem Abbiegen auf eine Kurven- und Autoabhängige Geschwindigkeit abbremsen.

Gelenkt wird in der Autoklasse, da die Autos nach wie vor wie auf “Schienen“ fahren. Wir sind dabei geblieben, da wir sonst ein neues Spursystem einführen müssten und die Simulation wesentlich komplexer werden würde. Dieser Schritt ist auch nicht geplant.

Leider haben wir bis jetzt noch nicht implementiert, dass Fahrer mehr als nur geradeaus sehen können. Optimal wäre es, wenn die Fahrer an ihrer geplanten Fahrspur entlang „sehen“ und diese kontrollieren, als wäre es eine gerade. Um dies zu erreichen müsste das Auto seine Route und seine Position und Sichtweite an die Klasse “ObstacleGrid“ weitergeben und diese Klasse errechnet daraus die Hindernisse. Daran ist zu sehen, dass erweiterte Konzepte einer Verkehrssimulation in der jetzigen Struktur sehr einfach zu implementieren wären. Mit dem Objekt-Orientierten Design wird alles an der Stelle berechnet, wo es hingehört und alles bleibt getrennt, erweiterbar und austauschbar.

Mit der Struktur und der Realitätsnähe der Simulation haben wir jetzt die Möglichkeiten die Simulation für wirkliche Szenarien zu benutzen.

Die Initialisierung unseres herkömmlichen Straßennetzes mit Ampelkreuzungen haben wir so weit wie möglich abstrahiert. Dafür sind nur nötig:

die Ampeltaktungen die Mittelpunkte der Ampelkreuzungen die Mittelpunkte der Spawnkreuzungen

class Manager(object):
 
    def __init__(self):
 
        ...
 
	self.grid = Grid("The Grid", Variables.SIMWidth, Variables.SIMHeight)
 
        #Die Ampeltaktungen können, aber müssen nicht angegeben
        #werden, da sonst Standardwerte verwendet werdn
 
	TrafficLight("TLAA", self.grid, 200, 200) 
	TrafficLight("TLBB", self.grid, 300, 200)
	TrafficLight("TLCC", self.grid, 200, 100)
	TrafficLight("TLDD", self.grid, 300, 100)
 
	self.grid.addIntersection("AA", 200, 200, TrafficLight.instanceList[0])
	self.grid.addIntersection("BB", 300, 200, TrafficLight.instanceList[1])
	self.grid.addIntersection("CC", 200, 100, TrafficLight.instanceList[2])
	self.grid.addIntersection("DD", 300, 100, TrafficLight.instanceList[3])
 
	self.grid.addSpawnIntersection("S1", 100, 200)
	self.grid.addSpawnIntersection("S2", 400, 200)
	self.grid.addSpawnIntersection("S3", 100, 100)
	self.grid.addSpawnIntersection("S4", 400, 100)
 
	self.grid.addIntersectionLink("AA","BB")
	self.grid.addIntersectionLink("AA","CC")
	self.grid.addIntersectionLink("DD","BB")
	self.grid.addIntersectionLink("DD","CC")
	self.grid.addIntersectionLink("AA","S1")
	self.grid.addIntersectionLink("BB","S2")
	self.grid.addIntersectionLink("CC","S3")
	self.grid.addIntersectionLink("DD","S4")
 
	self.grid.confirmIntersections()
 
	self.grid.addCar("Anton", speed = 10, speedLimit = 10)
 
	self.draw()

Die Klasse Grid errechnet sich selbst, welche Kreuzungsseiten mit anderen verbunden werden und entfernt die übrigen offenen Seiten. Bei den Spawnkreuzungen werden von selbst Spawn- und Despawn-Punkte getrennt.

Diese automatische Verbindung haben wir in diesem Stück Code, das in der Klasse Grid beinhaltet ist eingefügt. Der Code funktioniert und wir haben noch nie eine falsche Verlinkung der Kreuzungen gesehen, jedoch ist der Code sehr schwer zu durchblicken und wir werden die Klasse Grid als einen der nächsten Schritte ordnen und besser organisieren.

An unserem Build eines Kreisverkehrs ist gut zu sehen, dass wir die einzelnen Bestandteile der Initialisierung schon sehr gut abstrahiert haben, wir sie jedoch für die spezielleren Anwendungsfälle noch nicht vereinfacht haben.

Die Reaktionspunkte sehen wie folgt aus, bei großen Kreisverkehren sind die Einfahrten jedoch dementsprechend groß, sobald wir die Erstellung der Kreisverkehr vereinfacht haben, werden wir uns diesem Punkt widmen.

Bei diesem Kreisverkehr muss jeder Bestandteil, wie z.B. die Routen, die die einzelnen Reaktionspunkte verbinden oder die bedingten Ampeln manuell getippt werden. Jedoch muss in dieser Version nur die Variable „rad“ verändert werden, dann baut alles daruaf auf. man könnte also diesen Code schon fast in eine Funktion von „Grid“ implementieren und die Kreuzung in ein ganzes System integrieren.

class Manager(object):
 
	def __init__(self):
 
                ...
 
                self.grid = Grid("The Grid", Variables.SIMWidth, Variables.SIMHeight)
 
		SpawnNodes = ["S14","S15","S26","S27","S38","S31","S42","S43"]
		RANodes = ["RA1","RA2","RA3","RA4","RA5","RA6","RA7","RA8","RA_1","RA_2","RA_3","RA_4"]
 
		for n in SpawnNodes + RANodes:
			self.grid.dijkstra.addNode(n,0)
 
		rad = 10			       #Radius der Spur des Kreisverkehres
		sb  = 1.5			       #Spurbreite
		vb  = rad * math.cos(math.pi * 0.25)   #x/y-Abstand der Zwischenpunkte
		vc  = rad + 0.5
 
		vr1 = (vb - 1.5)/(0.29289322)	       #Radius beim Reinfahren
		vr2 = vr1	  		       #Radius beim Rausfahren
		va  = vb + math.sqrt(vr1**2/2.0) .     #x-Abstand der Ein- und Ausfahrt-Punkte
 
		vd1 = 0.25 * math.pi * vr1
		vd2 = vd1
		vrb = 0.5 * math.pi * 6.5
 
		ve  = math.cos(0.75 * 0.5 * math.pi) * vr1
		vf  = (1 - math.cos(0.25 * 0.5 * math.pi)) * vr1
 
		self.grid.Spawns =   ["S15", "S27", "S31", "S43"]
		self.grid.Despawns = ["S14", "S26", "S38", "S42"]
 
		self.grid.Sub["S14"] = [ 201.5 , 292.0 ]
		self.grid.Sub["S15"] = [ 198.5 , 292.0 ]
		self.grid.Sub["S26"] = [ 292.0 , 198.5 ]
		self.grid.Sub["S27"] = [ 292.0 , 201.5 ]
		self.grid.Sub["S38"] = [ 198.5 , 108.0 ]
		self.grid.Sub["S31"] = [ 201.5 , 108.0 ]
		self.grid.Sub["S42"] = [ 108.0 , 201.5 ]
		self.grid.Sub["S43"] = [ 108.0 , 198.5 ]
 
		self.grid.Sub["RA1"] = [ 200.0 +  1.5 , 200.0 +  va  ]
		self.grid.Sub["RA2"] = [ 200.0 +  va  , 200.0 +  1.5 ]
		self.grid.Sub["RA3"] = [ 200.0 +  va  , 200.0 -  1.5 ]
		self.grid.Sub["RA4"] = [ 200.0 +  1.5 , 200.0 -  va  ]
		self.grid.Sub["RA5"] = [ 200.0 -  1.5 , 200.0 -  va  ]
		self.grid.Sub["RA6"] = [ 200.0 -  va  , 200.0 -  1.5 ]
		self.grid.Sub["RA7"] = [ 200.0 -  va  , 200.0 +  1.5 ]
		self.grid.Sub["RA8"] = [ 200.0 -  1.5 , 200.0 +  va  ]
 
		self.grid.Sub["RA_1"] = [ 200.0 + vb , 200.0 + vb ]
		self.grid.Sub["RA_2"] = [ 200.0 + vb , 200.0 - vb ]
		self.grid.Sub["RA_3"] = [ 200.0 - vb , 200.0 - vb ]
		self.grid.Sub["RA_4"] = [ 200.0 - vb , 200.0 + vb ]
 
		self.grid.addSimpleLink("S15", "RA8", 90, 180, 180,   0,   0)
		self.grid.addSimpleLink("S27", "RA2", 90, 270, 270,   0,   0)
		self.grid.addSimpleLink("S31", "RA4", 90,   0,   0,   0,   0)
		self.grid.addSimpleLink("S43", "RA6", 90,  90,  90,   0,   0)
 
		self.grid.addSimpleLink("RA1", "S14", 90,   0,   0,   0,   0)
		self.grid.addSimpleLink("RA3", "S26", 90,  90,  90,   0,   0)
		self.grid.addSimpleLink("RA5", "S38", 90, 180, 180,   0,   0)
		self.grid.addSimpleLink("RA7", "S42", 90, 270, 270,   0,   0)
 
		self.grid.addSimpleLink("RA8", "RA_4", vd1, 180, 225, 1, vr1)
		self.grid.addSimpleLink("RA2", "RA_1", vd1, 270, 315, 1, vr1)
		self.grid.addSimpleLink("RA4", "RA_2", vd1,   0,  45, 1, vr1)
		self.grid.addSimpleLink("RA6", "RA_3", vd1,  90, 135, 1, vr1)
 
		self.grid.addSimpleLink("RA_1", "RA1", vd2, 315,   0, 1, vr2)
		self.grid.addSimpleLink("RA_2", "RA3", vd2,  45,  90, 1, vr2)
		self.grid.addSimpleLink("RA_3", "RA5", vd2, 135, 180, 1, vr2)
		self.grid.addSimpleLink("RA_4", "RA7", vd2, 225, 270, 1, vr2)
 
		self.grid.addSimpleLink("RA_1", "RA_4", vrb, 315, 225, -1, rad)
		self.grid.addSimpleLink("RA_4", "RA_3", vrb, 225, 135, -1, rad)
		self.grid.addSimpleLink("RA_3", "RA_2", vrb, 135,  45, -1, rad)
		self.grid.addSimpleLink("RA_2", "RA_1", vrb,  45, 315, -1, rad)
 
		RAObstacle(self.grid.OBSGrid, 200 - sb , 200 + va , [200 + vb, 200 + vb, 200 + vc, 200], 	[200, 200 + vc, 200 + vb, 200 + vb], 		135, 225)
		RAObstacle(self.grid.OBSGrid, 200 + va , 200 + sb , [200, 200 - vb, 200 + vb, 200 - vc],   	[200 + vb, 200, 200 + vc, 200 - vb], 		225, 315)
		RAObstacle(self.grid.OBSGrid, 200 + vb , 200 - va , [200 - vc, 200, 200 - vc + vb,200 - vb],[200 - vc + vb, 200 - vb, 200, 200 - va], 	315, 45)
		RAObstacle(self.grid.OBSGrid, 200 - va , 200 - sb , [200 - vb, 200 + vc, 200, 200 + vb], 	[200 - vc, 200 + vb, 200 - vb, 200], 		45, 135)
 
		sb += vf
		va -= ve
 
		RAObstacle(self.grid.OBSGrid, 200 - sb , 200 + va , [200 + vb, 200 + vb, 200 + vc, 200], 	[200, 200 + vc, 200 + vb, 200 + vb], 		135, 225)
		RAObstacle(self.grid.OBSGrid, 200 + va , 200 + sb , [200, 200 - vb, 200 + vb, 200 - vc],   	[200 + vb, 200, 200 + vc, 200 - vb], 		225, 315)
		RAObstacle(self.grid.OBSGrid, 200 + vb , 200 - va , [200 - vc, 200, 200 - vc + vb,200 - vb],[200 - vc + vb, 200 - vb, 200, 200 - va], 	315, 45)
		RAObstacle(self.grid.OBSGrid, 200 - va , 200 - sb , [200 - vb, 200 + vc, 200, 200 + vb], 	[200 - vc, 200 + vb, 200 - vb, 200], 		45, 135) 
		#self.grid.addCar("Anton", speed = 5, speedLimit = 5)
 
		self.rad = rad
		self.scale = Variables.TKIScale
 
		self.draw()

Unser Ziel ist es, für jeden Kreuzungstyp schon ein vorgefertigtes Geometrieschema zu haben, sodass diese reibungslos miteinander funktionieren. Es wäre auch aktzeptabel, wenn wir die einzelnen Kreuzungen manuell miteinander verbinden müssten. Dann wäre die Unübersichtlichkeit ist der Funktion Grid.adIntersectionLink(self, …) beseitigt.

Eine Rechts-Vor-Links-Kreuzung lässt sich mit den gegebenen Bestandteilen ebenfalls sehr einfach erstellen. Die Rechts-Vor-Links-Regel lässt sich, wie beim Kreisverkehr mit bedingten Ampel realisieren. Für den Fall das von jeder Seite ein Auto kommt, könnte man bei einer der Seiten ein Ausnahmeregel einbetten.

Es ist statistisch erwiesen, dass beim Linksabbiegen mit Gegenverkehr die meisten Unfälle an Kreuzungen passieren. Beim Linksabbiegen bei Mehrspurigen Straßen ist dies ein noch größeres Problem, da der Verkehr dort noch unübersichtlicher ist. Die „Diverging Diamond Intersection“ versucht dieses Problem für große Zubringerstraßen zu Autobahnen zu lösen, indem die Fahrbahnseiten kurz die Seiten wechseln und dadurch kein Abbiegen nötig ist.

Jede einzelne Klasse zu erklären und jedes Problem, dass wir hatten aufzuführen würde den Rahmen dieser Dokumentation sprengen. Jedoch könnte ihr euch den Code selbst anschauen und verändern. Wir haben den Code so hilfreich wie möglich auskommentiert.

Hinweise zur Benutzung:

Um die Größe des Simulationsfensters zu verändern muss man in V07_Variables.py die Variable Variables.TKIPix verändern.

Um die Simulation zu pausieren muss man ein Mal mit der linken Maustaste auf den Canvas klicken, während das Tkinter-Fester im Fokus liegt.

Links

Normales Straßennetz mit Ampelkreuzungen

Kreisverkehr