Inhaltsverzeichnis


1. Übersicht

1.1.                   Wie das Projekt entstanden ist

 

Im Rahmen der Vorlesung Objektorientierte Programmierung (OOP) bei Herrn Prof. Jürgen Sauer im WS 2000/2001 entstand die erste Version des Projekts “Steering Behaviors”. Ziel der Vorlesung war es, ein für die Vorlesung angemessenes Java-Applet zu entwickeln. Das Projekt “Steering Behaviors” stütze sich dabei auf die in der  Siggraph 2000 veröffentlichte Arbeit von Robin Green. Diese erste Version stellte dabei ein System mit Beispielen für einfache Verhaltenskombinationen dar. Für eine benutzerdefinierte Szenenbeschreibung wurde eine selbst definierte Skriptsprache verwendet, die als Parameter an das Applet übergeben wurde.

Anfang 2001 entstand dann die Idee das Projekt zu einer Diplomarbeit zu erweitern. Dabei sollten nun alle in der Arbeit von Reynold beschriebenen Verhalten implementiert werden. Die Intelligenz der Simulation wird dabei mit Hilfe einer Verhaltenssteuerung erweitert. Dadurch kann die Intelligenz an die Szenenbeschaffenheit angepaßt werden können.

Es enstand die Idee, anstatt der Skriptsprache für die Beschreibung der Szenen die Metasprache XML zu verwenden. Dabei verwendet man eine moderne standardisierte und plattformunabhängige Sprache. Für die Erstellung der Szene wurde ein leistungsfähiger Editor programmiert, der jede Form von Szenen erstellen kann. Dieser erlaubt es, XML-Dateien zu lesen und zu schreiben.

Eine weitere,  sehr bereichernde Idee für die Arbeit war die Implementierung eines eigenen Renderers. Dieser kann sowohl in der Simulationsdarstellung als auch im Editor verwendet werden.

Das Projekt “Steering Behaviors” stellt aufgrund der Vollständigkeit und individuellen Szenenerstellung eine gute Referenz zu den Arbeiten von Craig Reynolds dar.

1.2.                   Was sind Steering Behaviors

Steering Behaviors sind die logische Weiterentwicklung des Boids Modells von Craig Reynolds aus dem Jahre 1986. Das als “Boids” bezeichnete Computer basierte Modell ist eine Möglichkeit zum simulieren von koordinierten Bewegungen wie sie in Fisch- oder Vogelschwärmen zu sehen ist. Der Name „Boids“ bezeichnet hierbei die einzelnen simulierten Kreaturen. Das ursprüngliche Schwarmmodell basiert auf drei einzelnen Verhalten. Hierbei dient „Separation“ zum Abwenden von Situationen in denen sich die Mitglieder des Schwarms zu dicht aufeinander befinden. „Alignment“ wird benutzt um alle Elemente des Schwarms in die selbe Richtung zu lenken. Das dritte Verhalten, „Cohesion“, dient zum steuern eines einzelnen „Boids“ zur durchschnittlichen Position seiner nächsten Nachbarn. Durch eine geschickte Kombination dieser drei einfachen Verhalten konnte Reynolds eine glaubhafte Simulation des Verhaltens von Schwärmen auf dem Rechner simulieren. Ein erstes Beispiel für eine Animation unter Verwendung dieses Modells stellt der Kurzfilm „Stanley and Stella in: Breaking the Ice“ dar. Er entstand in einer Kooperation der Symbolics Graphics Division mit Whitney / Demos Production im Jahr 1987 und wurde im Electronic Theater der SIGGRAPH 1987 uraufgeführt.

Abbildung 1: Szene aus Stanley and Stella in: Breaking the Ice (1987)

Die in dieser Produktion verwendeten und evaluierten Algorithmen zur Vermeidung von Hindernissen bei der Steuerung der einzelnen „Boids“ präsentierte Reynolds in seiner im Jahre 1988 erschienen Arbeit unter dem Titel „Not Bumping Into Things“. Hier beschreibt er mehrere Möglichkeiten für Algorithmen und Regeln zum Ausweichen von Hindernissen. Es wird hierbei nicht auf komplexe Planungsstrategien und Pfadfindealgorithmen eingegangen, sondern rein auf Strategien basierend auf lokalen Informationen, d.h. im unmittelbaren Umkreis des Fahrzeuges.

Reynolds Arbeit über Steering Behaviors, die im Jahr 1999 auf der Games Developer Conference erschienen ist, erweitert die schon im „Boids“ Modell vorgestellten Verhalten. Es werden weitere Bausteine für komplexe, autonome Systeme vorgestellt. Jedes einzelne dieser Verhalten definiert nur eine bestimmte Reaktion auf die simulierte Umgebung des allgemein als Fahrzeug bezeichneten autonomen Agenten. Man erhält dadurch einen einfachen Baukasten für komplexe Systeme. Je nach dem welche Verhalten man einem Fahrzeug zuweist, desto komplexere Situationen kann dieses Fahrzeug meistern. Die unter dem Begriff „Steering Behaviors“ zusammengefaßten Verhalten sind dabei nur die unterste Steuerungsebene für ein autonomes System. Wie diese kombiniert werden können, wird anhand von mehreren Beispielen dargestellt.

Robin Green stellte auf der SIGGRAPH 2000 eine als „Steering Behaviours“ bezeichnete Arbeit vor. In dieser Arbeit greift er die von Reynolds entwickelten Verhalten auf und präsentiert Beispiele für eine Implementation der einzelnen Verhalten unter Verwendung der Sprache C++. Auch werden weitere mögliche Probleme und Lösungen für diese aufgezeigt. Diese Arbeit entstand als Teil der Entwicklung des Computerspiels „Dungeon Keeper 2“ von Bullfrog Productions Ltd.

Abbildung 2: Screenshot aus Dungeon Keeper 2, Bullfrog Productions Ltd.

Dieses Spiel kann als gelungenes Beispiel für die Verwendung der Steering Behaviors angesehen werden. Die im Spiel auftretenden autonomen Charaktere werden unter Verwendung von einzelnen einfachen Verhalten gesteuert und zeigen auf, was für einen Grad an Realismus man durch eine geschickte Kombination dieser Verhalten erreichen kann.

2.   Theorie

2.1.                   Fahrzeugmodel

Sowohl Craig Reynold als auch Robin Greene verwenden in ihren Arbeiten ein vereinfachtes Fahrzeugmodell. Es basiert auf der Verwendung einer Punkt - Masse zur Definition des Fahrzeuges. Ein Fahrzeug besteht aus einer Position und einer Geschwindigkeit. Zur weiteren Vereinfachung wird die Masse auf eins festgelegt und taucht deswegen bei weiteren Berechnungen nicht mehr auf. Die Ausrichtung des Fahrzeuges wird mit Hilfe der Vektoren m_localx und m_localy beschrieben. Diese beiden Vektoren bilden das lokale Koordinatensystem des Fahrzeuges und werden verwendet um zwischen Weltkoordinaten und Fahrzeugkoordinaten umzurechnen. Um die Position eines Fahrzeuges zu aktualisieren wird in jedem Frame der Animation die Geschwindigkeit mit dem erzeugten Kraftvektor addiert und das Ergebnis zur aktuellen Position addiert. Diese als Euler Integration bezeichnete Methode ist einfach zu implementieren und in diesem Fall vollkommend ausreichend um die Ergebnisse zu berechnen. Sie kann jederzeit durch stabilere Integrationsmethoden ersetzt werden, ohne etwas an der Simulation zu ändern. Das lokale Koordinatensystem wird für jedes Frame an den Geschwindigkeitsvektor angepaßt, wobei hier der Durchschnitt über die letzten drei Vektoren verwendet wird. Dies dient zum Vermeiden von möglichem „zittern“ des Fahrzeuges bei entgegengesetzt steuernden Verhalten und führt auch zu sanfteren Richtungswechseln.

 

 

 

 

 

2.2.                   Behaviors

2.2.1.Seek and Flee Behaviors

Anwendung

Die Seek und Flee Verhalten implementieren komplementäre Verhaltensmuster. Die verwendete Logik ist für beide gleich. Der Unterschied liegt nur im erzeugten Steuerungsvektor. Seek wird dazu verwendet, ein Fahrzeug auf ein bestimmtes Ziel hin zu steuern. Ein Beispiel hierfür wäre ein Fisch der sich direkt auf seine Nahrung zubewegt. Das Ziel kann einerseits ein fester Punkt im Raum sein, oder auch ein anderes Fahrzeug und sich in Bewegung befinden. Dagegen wird Flee benutzt, um ein einfaches Ausweichverhalten zu simulieren. Hierbei kann ebenfalls ein festes oder bewegtes Ziel vorliegen dem ausgewichen werden soll.

Implementierung

Die Berechnung des Steuerungsvektors ergibt sich aus den Werten für die  aktuelle Geschwindigkeit des Fahrzeuges und der Position des gewünschten Ziels. Zuerst wird die Position des Ziels ausgedrückt als Vektor zwischen dem Ziel und dem Fahrzeug. Dies ist die gewünschte Geschwindigkeit. Die resultierende Kraft ergibt sich aus der Differenz zwischen diesem Vektor und dem aktuellen Geschwindigkeitsvektor.

 

Abbildung 3: Kraftvektor beim Seek Verhalten

Beim Seek Verhalten subtrahiert man die aktuelle Geschwindigkeit des Fahrzeuges von der gewünschten Geschwindigkeit. Um den Kraftvektor des Flee Verhaltens auszurechnen, wird statt dessen der gewünschte Geschwindigkeitsvektor von der aktuellen  Geschwindigkeit abgezogen. Durch diese einfache Berechnung kann das Fahrzeug entweder in Richtung des Ziels gesteuert werden, oder vom Ziel weg gesteuert werden. Zu beachten ist wie bei allen Verhalten, das der resultierende Kraftvektor die maximale Kraft des Fahrzeuges nicht überschreiten darf.

Problematik

Da das Seek Verhalten kontinuierlich seinen Kraftvektor erzeugt, kann sich ein in den meisten Fällen unerwünschter Effekt ergeben. Falls das Ziel statisch ist, oder sich langsamer als das Fahrzeug bewegt,  führt die zum Ziel gerichtete Steuerungskraft zwar zuerst zu einem Erreichen des Ziels, steuert aber dann noch weiter über das Ziel hinaus. Nun wird wiederum ein Kraftvektor in die entgegengesetzte Richtung erzeugt und das Fahrzeug steuert wieder zurück. Die entstehende Bewegung ähnelt einer Motte, die um eine Lichtquelle fliegt.

2.2.2.Arrive Behavior

Anwendung

Das Arrive Verhalten ist eine Erweiterung des Seek Verhaltens. Es dient, ebenso wie Seek, zum Steuern des Fahrzeuges zu einem bestimmten Punkt hin. Der wichtigste Unterschied liegt in der Art des Ankommens beim Ziel. Bei Seek wird der Zielpunkt normalerweise mit maximaler Geschwindigkeit erreicht, und das Fahrzeug fährt mit der aktuellen Geschwindigkeit in die aktuelle Richtung weiter, erkennt daß es nicht mehr am Ziel ist und steuert wieder in die andere Richtung. Das Ergebnis erinnert an eine Motte, die um eine Lichtquelle kreist. Im Normalfall ist das nicht das Ergebnis das man sich erhofft hat. Das Arrive Verhalten bremst das Fahrzeug anhand von Vorgaben kontrolliert ab und stoppt es an der gewünschten Stelle.

Implementierung

Die eigentliche Berechnung des Steuerungsvektors geschieht zunächst genauso wie beim Seek Verhalten. Der Vektor ergibt sich aus der Differenz von der gewünschten Geschwindigkeit und der aktuellen Geschwindigkeit.

 

Abbildung 4: Kraftvektor beim Arrive Verhalten

Soweit sind die beiden Verhalten in der Berechnung noch identisch. Falls das Fahrzeug sich nicht innerhalb des als m_activeDistance bezeichneten Aktivierungsbereichs befindet, wird keine Steuerungskraft erzeugt. Innerhalb des Bereichs berechnet sich die Kraft aus der Distanz zum Ziel geteilt durch die Anzahl an Schritten zum Ziel. Dadurch wird das Fahrzeug um so langsamer, je näher es zu seinem Ziel kommt. Schlußendlich bleibt es am gewünschten Punkt stehen.

Problematik

Es ergibt sich bei diesem Verfahren ein Problem. Durch die Verwendung von Distanz geteilt durch die Anzahl an Schritten, nähert sich das Fahrzeug dem Ziel nur asymptotisch an. Es wird im Normalfall nie vollständig exakt auf dem Zielpunkt zum Stehen kommen. Von der Sicht des Benutzers her ist hier kein Unterschied festzustellen. Probleme können sich ergeben, falls die Ausrichtung des Fahrzeuges weiterhin aktualisiert wird. Ab einem Punkt kann es zu plötzlichen Richtungsänderungen kommen, obwohl das Fahrzeug schon seit einer gewissen Zeit stillzustehen scheint. Eine mögliche Lösung ist das Verhindern des Aktualisieren des Richtungsvektors, falls die Steuerungskraft eine gewisse Stärke unterschreitet. Eine zweite Möglichkeit, die auch hier verwendet wurde, besteht im verwenden der letzten drei Richtungsvektoren beim bestimmen des aktuellen Richtungsvektors. Dadurch werden zu schnelle Änderungen und ein gewisses „Zittern“ des Fahrzeugs bei bestimmten Verhaltenskombinationen automatisch ausgeglichen.

2.2.3.Wander

Anwendung

 

Fahrzeugen soll durch das Wander-Verhalten die Möglichkeit gegeben werden, sich selbstständig und ohne vordefiniertes Ziel durch die Szenerie bewegen zu können. Dies ist in etwa vergleichbar mit Ameisen, die auf dem Weg sind, Nahrung zu suchen. Die meisten Lebewesen die auf der Suche nach etwas sind, klappern die Umgebung in der Regel nicht systematisch ab, sondern bewegen sich zufällig und auf undefinierten Bahnen.

Durch Kombination mit anderen Verhalten (z.B. Seek, Arrive) können die sonst geradlinigen Bahnen durch das Wander Vehalten etwas gestört werden, das sich in der Realität beispielsweise durch äußere Einflüsse, wie Wind oder Bodenunebenheiten bemerkbar macht.

 

Abbildung 5: Beispiel für eine Fahrstrecke mit dem Wander-Verhalten

Implementierung

 

Im Grunde genommen wird das Wander Verhalten durch zufällige Steuerungänderungen realisiert. Dazu gibt es mehrere Möglichkeiten. Die einfachste Möglichkeit scheint natürlich die, dem Geschwindigkeitsvektor jeder Iteration einen zufälligen Vektor zu addieren. Dadurch entsteht jedoch ein sehr unnatürliches Fahrverhalten, da sehr abrupte Richtungswechsel entstehen können. Daher wird im Folgenden ein Verfahren verwendet, das dies verhindert. Wie bei den anderen Verhalten auch, muß das Wander-Verhalten einen Steuerungsvektor zurückliefern. Jedoch gibt man dem Steuerungverktor nur eingeschränkten Freiraum, indem man nur zuläßt, daß sich deren Spitze auf einem vor dem Fahrzeug platzierten Kreis befindet. Dieser Vektor wird in Weltkoordinaten umgerechnet und als Steuerungsvektor des Wander-Verhaltens zurückgegeben.

Abbildung 6: Steuerungsvektor, deren Spitze sich auf dem Kreis befindet

 

Bei jeder Iteration addiert man zu dem aktuellen Steuerungsvektor einen Zufallsvektor, dessen Länge maximal m_rate betragen darf. Durch m_rate kann somit die maximale Steuerungsänderung festgelegt werden. Der neue Vektor wird anschließend auf den Kreis zurückprojeziert.

 

Abbildung 7: Berechnung des neuen Steuerungsvektors

 

Das Verhalten lässt sich durch Variation des Kreisradius m_radius, der Kreisposition m_pos und der maximalen Richtungsänderung m_rate der gewünschten Situation anpassen. Wird der Kreis näher an dem Fahrzeug platziert, dann wird das Fahrzeug schnelle Richtungswechsel durchführen, während bei einer größeren Distanz eine viel geradlinigere Bahn beschrieben wird. Auch ein rechts- bzw. linksdrall kann durch Platzierung über oder unter der lokalen x-Achse des Fahrzeugs erreicht werden.

Abbildung 8: Verschiedene Einstellungen der Attribute

2.2.4.Separation

Anwendung

 

Das Separation Verhalten wird verwendet, um zu anderen Fahrzeugen einen gewissen Abstand zu halten. Dadurch werden Kollisionen unter den Fahrzeugen vermieden. Der Mensch macht das in der Realität automatisch. Bewegt er sich beispielsweise durch eine belebte Fußgängerzone, weicht er anderen Menschen instinktiv aus. Auch die anderen Menschen werden ihm ausweichen aus Angst, mit ihm zusammenzustoßen. Dabei interessieren natürlich nur die Menschen in unmittelbarer Nähe, weiter entfernte sind für den Ausweich-Instinkt unwichtig. Meist werden auch nur Menschen die sich in seiner Bewegungsbahn befinden beachtet, die hinter ihm gehenden interessieren weniger, es sei denn er will ihnen nicht zu Nahe kommen.

Implementierung

 

Das Separation-Verhalten funktioniert, ähnlich wie bei elektrisch geladenen Teilchen, durch gegenseitiges Abstoßen voneinander. Zunächst müssen alle Fahrzeuge, die sich innerhalb eines bestimmten Abstands vom betreffendem Fahrzeug befinden, ermittelt werden. Dazu wird das Simulations-Object Neighborhood verwendet. Die Neighborhood-Methode

 

getNearVehicles(v, m_nearAreaRadius)

 

liefert einen Iterator über eine Fahrzeugliste, deren Fahrzeuge sich maximal m_nearAreaRadius vom Fahrzeug  entfernt befinden. Für jedes benachbarte Objekt wird ein abstossender Vektor  ermittelt. Dieser wird durch Differenz der Position des Fahrzeugs   und dem benachbartem Fahrzeug  berechnet:

Dieser Vektor wird durch normalisieren und skalieren auf die Länge  gebracht, wobei r die Entfernung zwischen den beiden Fahrzeugen beschreibt.

 

Abbildung 9: Berechnung des Steuerungsvektors bei Separation

 

Dadurch wird die abstossende Kraft bei geringer Entfernung verstärkt, während bei grösseren Entfernungen eine leichtere  Kraft entsteht. Diese Kraftvektoren werden zu einem einzigen Steuerungsvektor addiert und als Rückgabewert der calculate()-Methode verwendet:

 

Da durch die Neighborhood-Methode getNearVehicles() auch die hinteren Fahrzeuge beachtet werden, ergibt sich in einigen Anwendungen ein eher unrealistisches Fahrverhalten. Der Mensch beachtet beim Autofahren hauptsächlich die vor ihm fahrenden Fahrzeuge. Um dies zu simulieren, wird je nach Wert des Attributs lookaheadonly die Methode getNearVehiclesFront() aufgerufen, die nur die vor ihm befindlichen Fahrzeuge zurückliefert. Dadurch bremst nur das hintere Fahrzeug ab, falls es einem anderen zu nahe kommen sollte. Für einen Simulationsaufbau, der das Quequing vor einer schmalen Durchfahrt darstellt, ist es unerlässlich, lookaheadonly auf true zu setzen.

2.2.5.Alignment

Anwendung

 

Fahrzeuge mit dem Alignment-Verhalten versuchen sich einer Gruppe von Fahrzeugen anzuschliessen. Die Aufgabe des Verhaltens ist das Angleichen des Richtungsvektors an die durchschnittlichen Bewegungsrichtung der umgebenden Fahrzeuge. Eine Gruppe von Fahrzeugen mit diesem Verhalten wird zuerst ihre Bewegungsrichtung aneinander anpassen und dann Richtungsänderungen als eine Einheit vollziehen. Anwendung findet dieses Verhalten beispielsweise in der Kombination mit weiteren Verhalten in Flocking-Verhalten.

Implementierung

 

Um die Bewegungsrichtung des Fahrzeuges an seine Nachbarn anzugleichen, steuert das Verhalten in die durchschnittliche Fahrtrichtung der benachbarten Fahrzeuge. Dafür wird wieder ein Iterator über alle benachbarten Fahrzeuge innerhalb m_nearAreaRadius erstellt. Die Geschwindigkeitsvektoren dieser Fahrzeuge werden in einer Schleife ermittelt und summiert. Anschliessend wird durch die Anzahl der Fahrzeuge geteilt um die durchschnittliche Fahrtrichtung zu berechnen.

 

Abbildung 10: Berechnung des Steuerungsvektors bei Alignment

 

Der Kraftvektor ist die Differenz zwischen dem berechneten durchschnittlichen  Geschwindigkeitsvektor der Nachbarn und der eigenen Geschwindigkeitsvektors. Diese Kraft darf natürlich die maximale Kraft des Fahrzeuges nicht überschreiten. Der endgültige Steuerungsvektor wird durch Multiplikation mit dem Einflussfaktor m_influence ermittelt.

2.2.6.Cohesion

Anwendung

 

Das Cohesion-Verhalten ist für den Zusammenhalt einer Gruppe von Fahrzeugen zuständig. Dabei wird auf die durchschnittliche Position der benachbarten Fahrzeuge zugesteuert. Das Cohesions-Verhalten ist ein wichtiger Bestandteil des Flocking-Verhaltens. Es sollte nur in Verbindung mit dem Separation Verhalten eingesetzt werden. Ohne dieses Verhalten, steuern alle Fahrzeuge mit Cohesion auf einen gemeinsamen Punkt zu und überlappen sich.

Implementierung

 

Zunächst wird ein Iterator aller naheliegenden Fahrzeuge durch die Neighborhod-Methode getNearVehicles(…) ermittelt. Anschließend werden die Ortsvektoren der Fahrzeuge summiert und durch die Anzahl der Fahrzeuge im vorgegebenen Bereich geteilt. Auf diese dadurch ermittelte Position wird das Fahrzeug hingesteuert.

 

Abbildung 11: Berechnung des Steuerungsvektors bei Cohesion

2.2.7.Flocking

Anwendung

 

Flocking weist den Fahrzeugen ein Verhalten zu, das ihnen die Möglichkeit gibt, sich einer Gruppe anzuschließen. In der Natur ist das beispielsweise bei Vogelschwärmen zu beobachten. Oft sind hunderte von Vögel sehr eng nebeneinander, aber trotzdem kollidieren sie nicht. Sie passen ihre Geschwindigkeit und ihre Flugrichtung den anderen Vögel an und versuchen außerdem noch, Zusammenstösse zu vermeiden. Reynolds beschreibt dieses Verhalten aus einer Kombination der Verhalten Separation, Alignment und Cohesion.

 

D.h. während das Separation-Verhalten Kollisionen unter den Fahrzeugen verhindert, stellt das Cohesion-Verhalten eine gewisse Anziehung untereinander sicher. Fahrzeuge die sich also einem „Schwarm“ nähern, werden von ihm eingefangen und mitgezogen. Durch das Alignment-Verhalten wird in die durchschnittliche Richtung der benachbarten Fahrzeuge gesteuert.

Implementierung

 

Der Steuerungsvektor errechnet sich aus der Summe der Kraftvektoren von Alignment, Cohesion und Separation. Dafür wird ein Vector der Länge 0 erstellt, zu dem die Kraftvektoren der drei verwendeten Behaviors addiert werden. Es werden drei weitere Einflußwerte für die drei einzelnen Verhalten vorgegeben. Mit Hilfe der Attribute „Alignment“, „Cohesion“ und „Separation“ kann man die Verteilung der Kräfte innerhalb des Flocking-Verhaltens noch genauer definieren. Dadurch kann man erreichen, daß die Schwärme dichter oder lockerer sind, oder auch die Bewegungen am Rand nicht mehr so genau nachvollzogen werden.

 

2.2.8.Obstacle Avoidance

Anwendung

Um ein Fahrzeug in einer realistischen Weise durch eine vordefinierte Landschaft zu steuern, ist es notwendig das Fahrzeug so zu bewegen, wie es ein Betrachter erwarten würde. Dazu ist es notwendig ein Verhalten zu definieren, das es erlaubt mit Hindernissen umzugehen. Im täglichen Leben ist für Tiere und Menschen das Ausweichen von Hindernissen ein natürliches Verhalten. Wenn man das Verlangen nach einem kühlen Bier verspürt, bewegt man sich nicht auf einer geraden Linie auf den Kühlschrank zu. Unbewußt wählt man einen Weg, der einem um Hindernisse in der Welt wie Tische, Stühle und andere Dinge, die den direkten Weg versperren, herumführt ohne das man sein primäres Ziel aufgeben muß um seinen gebrochenen Zeh zu behandeln. Dieses unbewußte Ausweichen um vorgegebene Hindernisse versucht das ObstacleAvoidance Verhalten zu realisieren.

Implementierung

Bei der Implementierung des Obstacle Avoidance Verhalten muß zuerst definiert werden, was in der virtuellen Welt ein Hindernis darstellt. Da diese Simulation innerhalb einer zweidimensionalen Welt stattfindet, liegt es nahe, einfache geometrische Figuren als Platzhalter für komplexere Hindernisse zu verwenden. Die einfachste wählbare Form eines Hindernisses stellt der Kreis dar. Dabei ist festzulegen, daß das Hindernis vollständig innerhalb des Kreises Platz finden muß. Wobei man hier auch darauf achten sollte, nicht zuviel unnötigen Platz für die Repräsentation zu verschwenden. Für langgezogene Hindernisse wie z.B. Mauern kann ein Kreis eine äußerst schlechte Annäherung sein. Der Vorteil in der Verwendung eines Kreises liegt in den äußerst einfachen Formeln zur Berechnung von Schnittpunkten mit anderen geometrischen Körpern wie sie bei diesem Verhalten benötigt werden. Als nachteilig erweist sich die meist schlechte Annäherung an das Hindernis durch den Kreis.

Abbildung 12: Beispiel für gute und schlechte Annäherung durch einen Kreis

Da die Nachteile für die Verwendung von Kreisen als Platzhalter für Hindernisse die Vorteile überwiegen, wurden statt dessen Polygone verwendet. Diese bieten den Vorteil, das ein bestimmtes Hindernis aus der realen Welt, wie z.B. ein Tisch oder Stuhl, dadurch beliebig genau angenähert werden kann. Die im zweidimensionalen Raum erzielten Ergebnisse lassen sich auch ohne weiteres in den dreidimensionalen Raum übertragen.

Das Obstacle Avoidance Verhalten muß im ersten Schritt herausfinden, welche Hindernisse sich in der nächsten Umgebung befinden. Dazu bedient es sich des Neighborhood Objektes, das diese Informationen bereitstellt. Diese Eingrenzung der zu überprüfenden Hindernisse ist notwendig, da sich dadurch der Zeitaufwand für die weiteren Tests schon im voraus verringern läßt. Bei großen und komplexen Szenerien mit vielen Hindernissen ist der Aufwand der Vorauswahl im Vergleich zu den eigentlichen Überschneidungstests des Verhaltens als gering anzusehen.

 

Ermitteln des Schnittwinkels und der Entfernung

 

Die Methode getCollisionDetails(…) liefert den Schnittwinkel und die Entfernung zum Hinderniss zurück.  Anhand dieser Werte wird der Gegensteuerungsvektor berechnet.

Dazu wird der Testvektor um die Schnittentfernung verlängert, und anschliesend senkrecht auf die Kante des Hindernisses projeziert. Diser Vektor wird nun für die Gegensteuerung verwendet.

 

Abbildung 13: Steuerungsvektor zum Ausweichen eines Hindernisses

Optimierung durch „Exclusion-Tests“

 

Wenn Hindernisse in der Nähe des Fahrzeuges liegen, muß das nicht unbedingt heißen, daß der Testvektor das Hindernis auch schneidet. Das ist beispielsweise dann der Fall, wenn es neben dem Fahrzeug liegt.

Da Containment meist von vielen Fahrzeugen verwendet wird, und die Berechnung des Steuerungsvektors relativ rechenintensiv ist, kann durch sogenannte “Exclusion-Tests” herausgefunden werden, ob der Testvektor wirklich das Hindernis schneidet. Solche Test bestehen ausschließlich aus if-Abfragen und sind dadurch recht schnell in der Abarbeitung. Sie müssen für jede einzelne Kante des Hindernisses durchgeführt werden.

 

Test 1:

Als erstes wird ein Testpunkt P generiert, der der an der Spitze des Testvektors liegt. Es können nun alle Kanten ausgeschlossen werden, deren Eckpunkte, je nach Richtung des Testvektors, beide außerhalb eines abgegrenzten Bereichs liegen (siehe Bild).

Abbildung 14: Beispiele für Kanten, die im 1. Test verworfen werden

 

Test 2:

 

Erst nachdem die Kante den ersten Test bestanden hat, werden die Eckpunkte in die lokalen Koordinaten des Fahrzeugs umgewandelt. Der Testvektor liegt somit auf der x-Achse.

Wenn nun beide Eckpunkte über bzw. unter der x-Achse liegen, schneidet die Kante nicht den Testvektor. Solche Kanten können verworfen werden.

 

Abbildung 15: Beispiele für Kanten, die im 2. Test verworfen werden

 

 

 

Test 3:

 

Der 3. Test  überprüft, ob die Kante evtl. von der Rückseite getroffen wird. Das ist beispielsweise bei kleinen Hindernissen oft der Fall. Diese Kanten müssen natürlich nicht beachtet werden. Die Punkte der Polygone werden gegen den Uhrzeigersinn definiert. Dadurch kann man solche Kanten ausschließen, deren Punkt 1 unter, und Punkt 2 über der x-Achse liegt.

 

Abbildung 16: Beispiele für eine Rückkante, die verworfen werden kann

Test 4:

 

Test 4 überprüft, ob beide Kantenpunkte größere x-Werte aufweisen, als die Testvektorlänge. Außerdem können auch Kanten verworfen werden, deren Kantenpunkte links von der y-Achse liegen. Denn in diesem Fall ist das Hindernis hinter dem Fahrzeug.

Abbildung 17: Ausschlusskanten des 4. Tests

 

Nach diesen 4 Tests wurden die meisten Kanten verworfen und damit ist auch Rechenzeit gespart worden. Von den verbleibenden Kanten muß nun der Winkel und die Entfernung zum Schnittpunkt berechnet werden.

Als Grundlage für diese Berechnung dient die Formel:

Wobei x1 und y1 die Koordinaten des ersten Kantenpunkts beschreiben. Die Steigung a wird durch  berechnet. Setzt man dieses in die erste Formel ein, löst auf x auf und setzt y auf 0, erhält man die Formel:

Das Ergebnis x ist die gewünschte Entfernung zum Schnittpunkt des Testvektors mit dem Hindernis.

 

Der Schnittwinkel wird mit der Arcustangens-Funktion berechnet.

 

Anmerkung:

Da es auch möglich ist, daß sich Hindernisse überlagern, werden natürlich alle Kanten dieser Hindernisse zum Test herangezogen. Zum Ausweichen muß darum die Kante mit der kleinsten Schnittpunktentfernung verwendet werden. Die Gegensteuerung erfolgt damit durch das naheste Hindernis.

2.2.9.Containment

Anwendung

 

Das Containment-Verhalten ist eine Erweiterung von ObstacleAvoidance. Im Gegensatz zum ObstaceAvoidance verwendet Containment insgesamt drei Testvektoren für eine Kollisionsabfrage: Einen vorne und jeweils einen links und rechts.

Abbildung 18: Testvektoren beim Containment Verhalten

Diese Vektoren werden mit den Parametern sidex, sidey und frontdistance festgelegt (siehe Bild). Für jeden dieser drei Vektoren wird getestet, ob er ein Hinderniss schneidet. Ist das der Fall, wird der Schnittwinkel und die Entfernung zum Schnittpunkt berechnet. Anhand dieser Werte wird ein Steuerungsvektor berechnet, der vom Hindernis wegsteuert.

Implementierung

 

Wie bereits erwähnt muß für jeden der Testvektoren der Schnittwinkel und die Entfernung des Schnittpunkts berechnet werden. Zu diesem Zweck wird die Methode getCollisionDetails(…) verwendet. Durch Angabe des Fahrzeug, des zu testenden Hindernisses und dem Testvektor werden neben Schnittentfernung und –winkel noch die beiden Punkte der entsprechenden Schnittkante des Hindernisses zurückgeliefert. Um nicht bei jedem Hindernis diese Methode aufrufen zu müssen, wird das Neighborhood-Objekt nach Hindernissen in der Entfernung der Testvektorlänge befragt.

Der Vorteil bei der Verwendung von drei Testvektoren, anstelle nur eines einzelnen, liegt in der besseren Behandlung von Situationen in denen das Fahrzeug knapp an Hindernissen entlang fahren muß. Bei ObstacleAvoidance kann es passieren, daß das Fahrzeug sich schon innerhalb des Hindernisses befindet, bevor der Testvektor eine Kollision feststellt. Die zwei zur Seite gerichteten Vektoren bei Containment testen genau den Bereich der von Obstacle Avoidance vernachlässigt wird und erlaubt dadurch eine bessere Behandlung von komplexen Situationen.

2.2.10.                 Containment durch Fuzzy-Logik

 

Im Gegensatz zum einfachen Containment-Verhalten (Kapitel 2.2.8) wird in der Fuzzy-Variante der Steuerungsvektor mit Hilfe von Fuzzy-Logik berechnet. Als Eingangsgrößen wird der Auftreffwinkel und die Schnittentfernung zum Hindernis verwendet. Zum ermitteln dieser Werte kann die Methode getCollisionDetails(...) genutzt werden, die genau diese Größen berechnet.

Die Fuzzy-Sets

 

Fuzzy-Systeme kodieren Regeln in numerischer Form. Die Fuzzy-Set-Theorie geht von der Annahme aus, daß alle Dinge nur zu einem gewissen Grad zutreffen.

Aus diesem Grund wird die Entfernung zum Hindernis in 3 Teile aufgeteilt:

kleine Entfernung (PS)

mittlere Entfernung (PM)

große Entfernung (PB)

 

Die unscharfen Grenzen dieser 3 Entfernungsklassen lassen sich mit folgendem Diagramm darstellen:

 

Abbildung 19: Unscharfe Grenzen der Entfernung

 

Es lässt sich beispielsweise direkt ablesen, daß ein Abstand von 50% der Testvektorlänge als mittlere Entfernung empfunden wird, während bei einer Entfernung von 75% sich eine halb mittel und eine halb große Entfernung ergibt. Je näher das Hindernis gekommen ist, desto stärker soll natürlich ausgewichen werden.

Aber auch der Auftreffwinkel ist ein wichtiger Faktor, wie stark das Fahrzeug ausweichen soll. Ein Autofahrer der leicht von der Spur abgekommen ist, wird nur eine leichte Fahrtrichtungskorrektur machen, während er bei einem frontalen Hindernis sofort stark auszuweichen beginnt.

 

Der Auftreffwinkel wird in 5 Teile zerlegt:

negativ mittel (NM)

negativ klein (NS)

senkrecht, bzw. null (ZE)

positiv klein (PS)

positiv mittel (PM)

 

Abbildung 20: Unscharfen Grenzen des Winkels

Die Regeltabelle

 

Um entsprechend der Eingangsgrößen handeln zu können, wird eine Regeltabelle benötigt. Diese Regeltabelle legt fest, bei welcher Kombination aus Entfernungs- und Winkelgrößen welche Ausgabegröße resultiert.

Für das FuzzyContainment-Verhalten wird folgende Regeltabelle festgelegt:

 

Abstand

 

¯

 

 

 

 

 

 

 

NM

NS

ZE

PS

PM

¬ Auftreffwinkel

PS

ZE

PS

PS

NS

ZE

 

PM

ZE

PS

ZE

NS

ZE

 

PB

ZE

PS

ZE

NS

ZE

 

 

 

 

 

Die Defuzzifizierung

 

Als Ergebnis der Defuzzifizierung erhält man einen Wert zwischen -90 und +90 Grad, der die Steuerungsrichtung für das Ausweichen beschreibt. Der Betrag des Steuerungsvektors ist fest vorgegeben und bleibt immer konstant.

 

Abbildung 21: Diagramm zur Defuzzifizierung

 

Beispiel einer Ausweichsituation

Angenommen ein Fahrzeug befindet sich in der in Abbildung 22 gezeigten Situation. Dabei wird ein Abstand von 60% und ein Auftreffwinkel von 36° gemessen.

Abbildung 22: Fahrzeug in einer Ausweichsituation

Diese Werte werden nun als Eingabewerte für die Fuzzysteuerung verwendet.

 

Abbildung 23: Beispiel einer Fuzzysteuerung

Die dadurch resultierenden Werte von 0.67 NS und 0.33 NM für den Winkel bzw. 0.76 PM und 0.23 PB für den Abstand werden nun laut der Regeltabelle ausgewertet und in das Defuzzifizierungsdiagramm eingetragen:

 

Abbildung 24: Defuzzifizierung

 

Nach der Ermittlung des Schwerpunkts der eingeschlossenen Fläche erhält man einen Wert von +34°, der die Steuerungsrichtung des Fahrzeugs zum Ausweichen beschreibt.

 

Abbildung 25: Der Steuerungsvektor einer Fuzzy-Ausweichsteuerung

Probleme bei dieser Konfiguration der Fuzzy-Sets entstehen bei konkaven Hindernissen. Da das Verhalten nur eine rechts-/links-Steuerung vornimmt und keine rückstoßende Kraft erzeugt, bleibt das Fahrzeug ab einem bestimmten Grad von spitzwinkligen Hindernissen stecken. Das kommt daher, da das Fahrzeug einmal die Kante links davon erkennt und darum rechts steuert, und anschließend die Kante rechts erkennt und darum wieder nach links steuert (siehe Abbildung 26).

 

Abbildung 26: Problematik bei konkaven Hindernissen

Dieser Effekt lässt sich durch andere Fuzzy-Konfigurationen mehr oder weniger unterdrücken. Eine andere Möglichkeit wäre, die Testvektoren links und rechts dazu zu verwenden um einen solchen Engpass zu erkennen und dementsprechend zu handeln.

2.2.11.                 SimplePathFollowing

Anwendung

Ein weiteres in der Arbeit von Reynolds beschriebenes Verhalten ist das “PathFollowing” Verhalten. Hierbei wird das Fahrzeug entlang eines vordefinierten Pfades gesteuert. Der Pfad an sich besteht hierbei aus einer Folge von Wegpunkten, die in einer vorgegebenen Reihenfolge durchlaufen werden sollen. Wie von Robin Greene beschrieben, gibt es drei verschiedene Möglichkeiten, wie der nächste Wegpunkt für das Fahrzeug bestimmt werden kann. Diese  drei Methoden werden als „Dog on a string“ , „Reprojection“ und „Grappling Hooks“ bezeichnet. Die einfachste Art einem Pfad zu Folgen bietet die letzte Methode.

Implementierung

Bei „Dog on a string“ gibt es für das Fahrzeug einen festen Zielpunkt. Dieser wird linear entlang des Pfades mit einer vorgegebenen Geschwindigkeit bewegt. Es ergibt sich hierbei das Problem, diese Geschwindigkeit richtig zu wählen. Ist sie zu gering, erhält man das vom Seek Verhalten bekannte Phänomen, daß das Fahrzeug sich um den Zielpunkt wie eine Motte um das Licht bewegt. Ist die Geschwindigkeit zu schnell, können Situationen entstehen in denen das Fahrzeug sich durch vorgegebene Hindernisse bewegt.

Bei der als „Reprojection“ bezeichneten Methode wird die aktuelle Fahrtrichtung des Fahrzeugs verlängert und der nächste Schnittpunkt mit dem Pfad gesucht. Dadurch erscheint das Fahrzeug intelligenter, da es die Wegpunkte nicht immer ab den ersten durchlaufen muß, sonder in bestimmten Fällen diese überspringen kann und sofort den Pfad ab seiner aktuellen Position folgen kann. Falls man einen Grenzwert für die minimale Distanz  Problematisch sind bei dieser Methode Schleifen innerhalb des Pfades. Es muß darauf geachtet werden, das nicht plötzlich der Pfad in die falsche Richtung verfolgt wird, oder Teile des Pfades überhaupt nicht durchlaufen werden.

Die als „Grappling Hooks“ bezeichnete Methode funktioniert am besten, wenn die Verbindungslinie zwischen zwei aufeinanderfolgenden Wegpunkte kein Hindernis schneidet. Das Fahrzeug steuert dann einen Wegpunkt an, und sobald dieser erreicht wurde, wird der nächste ausgewählt und angesteuert. Das SimplePathFollowing Verhalten implementiert diese Methode. Für die Erstellung der Wegpunkte ist die TileNeighborhood Klasse verantwortlich. Dieser wird der Startpunkt und der gewünschte Zielpunkt vorgegeben. Daraus werden automatisch die Wegpunkte für das Fahrzeug generiert. Das „SimplePathFollowing“ Verhalten ruft nun die einzelnen Wegpunkte ab und steuert das Fahrzeug so zum gewünschten Ziel.

2.3.                   Mind

2.3.1.Einleitung

Die Mind Klasse implementiert den in Reynolds Arbeit als „action selection“ bezeichneten Teil der Steering Behaviors Logik. Ihre Aufgabe ist es auf Grund von vorgegebenen Regeln einen endgültigen Steuervektor zu erzeugen. Es spielt hierbei die Rolle des „Gehirns“ des Fahrzeuges. Die einzelnen Verhalten wie Seek, ObstacleAvoidance oder Separation spielen hierbei die Rolle von Sensoren. Jedes einzelne Verhalten kann die Umgebung auf bestimmte Art und Weise analysieren und auf Grund seiner internen Logik eine Steuerungskraft generieren. Diese Kraft basiert aber jeweils nur auf einer einzelnen speziellen Sicht der Dinge. Die Mind Klasse erhält diese „Vorschläge“ der Verhalten und trifft die Entscheidung was für eine Reaktion erfolgen soll. Für die Implementierung dieser Entscheidungsfindung gibt es mehrere Möglichkeiten, die alle ihre Vor- und Nachteile haben.

2.3.2.SimpleMind

Die SimpleMind Klasse implementiert die einfachste Art wie man die Entscheidung für die kombinierte Steuerungskraft treffen kann. Jedes einzelne Verhalten erhält einen als „Einfluss“ bezeichneten Wert (im Code als m_influnce bezeichnet) zugeteilt. Je nachdem wieviel Einfluß ein bestimmtes Verhalten auf den kombinierten Kraftvektor haben soll, ist dieser Einfluß höher oder niedriger angesetzt. Der vom Verhalten generierte Kraftvektor wird mit dem Einfluss multipliziert und die Vektoren werden aufaddiert. Durch dieses System lassen sich die Prioritäten der einzelnen Verhalten auf einfache Art und Weise gegeneinander abstimmen.

Abbildung 27: Arbeitsweise des SimpleMinds

Für wichtigere Verhalten wie Separation und ObstacleAvoidance wählt man in den meisten Fällen höhere Prioritäten. Verhalten wie Wander, die nicht in allen Fällen wichtig sind, werden mit niedrigerem Einfluß belegt. Dadurch stellt man sicher, daß z.B. vor einem Hindernis zuerst an das Ausweichen gedacht wird, bevor ein anderes Verhalten eine Chance auf Einfluß auf die steuernde Kraft hat.

2.3.3.PriorityMind

Mit Hilfe der PriorityMind Klasse kann die Einwirkung eines oder mehrerer Verhalten auf die Gesamtkraft in bestimmten Fällen unterdrückt werden. Hierzu wird wie bei der SimpleMindKlasse das als „influence“ bezeichnete Attribut der Verhalten verwendet. Dieser Wert gibt an wieviel Prozent der maximalen Kraft des Fahrzeuges erzeugt werden kann. Ein Wert von z.B. 0.8 entspricht hierbei 80%. Da dieser Wert frei gewählt werden kann, sind auch Werte größer als 100% möglich. Die PriorityMind Klasse verteilt die maximal verwendbare Kraft an die einzelnen Verhalten. Dabei kann aber nicht mehr Kraft erzeugt werden, als vorhanden ist. Sobald die maximale Kraft erreicht ist, kann das Verhalten entweder nur noch den übrigen Bruchteil nutzen falls ein solcher vorhanden ist, oder es wird ignoriert.

Abbildung 28: Beispiele für die mögliche Kraftverteilung bei PriorityMind

Von Vorteil ist das PriorityMind in Situation in denen sich mehrere Fahrzeuge innerhalb eines eng abgegrenzten Bereichs bewegen. Durch eine geschickte Wahl der Einflüsse kann hierbei sichergestellt werden, daß sich einerseits Fahrzeuge nicht überschneiden und die Hindernisse nicht ignoriert werden. 

 

2.4.                   Simulationen

2.4.1.Einleitung

Die Basis für alle Simulationen ist die Simulation-Klasse. Sie dient als Ausgangspunkt um komplexe Systeme zusammenzustellen. Erste Versionen der Steering Behaviors Applets hatten den Code zum Steuern der Simulation fest integriert. Dies war nicht besonders flexibel und bei Erweiterungen mußte auf Kompatibilität mit vorherigen Versionen Rücksicht genommen werden. Durch das Verlagern der allgemeinen Funktionalität in eine eigene Klassenhierarchie kann man nun jederzeit Veränderungen an der Simulation vornehmen, ohne das man dadurch vorherige Algorithmen überschreiben oder verändern muß.

2.4.2.Simulation Class

Die Basisklasse für die Hierarchie der Simulationen ist die Simulation-Klasse. Sie enthält die allgemeine Schnittstelle für alle davon abgeleiteten Klassen. Um Simulationen noch flexibler zu gestalten, besitzt die Basisklasse zwei Arrays mit sogenannten Pre- und Post-Simulationen.

Abbildung 29: Aufteilung der Simulation Klasse

Eine Pre-Simulation wird vor dem eigentlichen durchführen der Simulation aufgerufen. Dies kann für alle Arten von Simulationen verwendet werden, die ihre Daten zuerst initialisieren müssen, bevor Behaviors darauf zugreifen können. Ein Beispiel hierfür ist die Neighborhood Klasse, die ihre Distanzmatrix erst für jeden Simulationsschritt neu initialisieren muß, bevor sie verwendet werden kann.

Eine Post-Simulation dient zum Nachbereiten des eigentlichen Simulationsschrittes. Ein Beispiel hierfür ist die VehicleInfo Klasse. Sie zeigt die Einflüsse der einzelnen Behaviors auf das Gesamtverhalten an und benötigt deswegen die Informationen nach dem ausführen des eigentlichen Simulationsschrittes. Eine weitere mögliche Post - Simulation wäre z.B. eine Klasse zum Überprüfen des letzten Simulationsschrittes auf Fahrzeuge in unmöglichen Positionen, wie innerhalb von Hindernissen oder sich überschneidende Fahrzeuge, und anschließende Korrektur dieser Fehler.

Im eigentliche Simulationsschritt wird für jedes Fahrzeug in der Szene die zugehörige Mind Klasse aufgerufen. Diese führt dann die eigentliche Berechnung der Kräfte der einzelnen Verhalten aus und kombiniert diese anhand der jeweiligen implementierten Vorschrift.

2.4.3.Neighborhood

Übersicht

Die Neighborhood Klasse ist eine der wichtigsten Klassen innerhalb der Simulation. Sie ist für die korrekte Funktionweise von Verhalten wie Allignment, Cohesion und aller Verhalten zum Ausweichen von Hindernissen von größter Bedeutung. Ihre Hauptaufgabe besteht im Ermöglichen von räumlichen Abfragen innerhalb der Simulationsumgebung. Man kann sowohl alle Fahrzeuge innerhalb eines vorgegebenen Radius um ein bestimmtes Fahrzeug abfragen, als auch die Hindernisse innerhalb eines festgelegten Bereichs.

Arbeitsweise

Die Neighborhood Klasse verwendet zwei unterschiedliche Methoden für Fahrzeuge und Hindernisse, um räumliche Abfragen zu ermöglichen. Beide Methoden haben ihre Vor- und Nachteile, erfüllen aber beide die Vorgabe daß die Ergebnisse so schnell wie möglich vorliegen sollen.

Die Abfrage für Fahrzeuge basiert auf einer Distanzmatrix. In dieser Matrix wird für jedes Fahrzeug die Distanz zu allen anderen Fahrzeugen hinterlegt. Eine Abfrage besteht dann nur noch in der Auswahl der Zeile des jeweiligen Fahrzeuges und dem Vergleich der einzelnen Distanzen mit dem vorgegebenen Grenzwert. Bei diesem System ist der Mittelpunkt des Objekts entscheidend bei der Auswahl. Um den Aufbau der Distanzmatrix zu beschleunigen, gibt es mehrere Möglichkeiten zur Optimierung.

Abbildung 30: Distanzbestimmung für Neighborhood

Die Bestimmung der Distanz zwischen zwei Fahrzeugen innerhalb eines zweidimensionalen Raumes geschieht anhand der Formel . Hierbei ist die Wurzel der langsamste Teil der Berechnung. Um diesen Teil der Berechnung zu umgehen, verwendet man für die Abfragen grundsätzlich die quadratische Distanz zwischen den Fahrzeugen. Hierbei ist die Distanz . Durch diese einfache Änderung an der Formel ergibt sich keinerlei Unterschied zu den Ergebnissen bei Verwendung der ersten Formel. Der sich daraus ergebende Vorteil liegt darin, das Wurzelfunktion nicht jedesmal berechnet werden muß. Da diese Funktion im allgemeinen trotz Unterstützung durch den mathematischen Coprozessor sehr langsam ist, ergibt sich ein nicht zu unterschätzender Zeitgewinn. Natürlich muß man auch den bei den Abfragen verwendeten Grenzwert quadrieren, um die Vergleiche innerhalb des gleichen Koordinatensystems vorzunehmen.

Abbildung 31: Symmetrischer Aufbau der Distanzmatrix

Eine weitere Optimierungsmöglichkeit liegt im Ausnutzen der Symmetrieeigenschaft innerhalb der Matrix. Da die Fahrzeuge in den Zeilen der Matrix, den Fahrzeugen in den Spalten entsprechen, ist z.B. die Distanz zwischen Fahrzeug A und Fahrzeug B einmal in der Spalte A und Zeile B vorhanden, und ebenso in der Spalte B und Zeile A. Deswegen kann man beim Erstellen der Distanzinformationen die Anzahl der Berechnungen durch das Ausnutzen dieser Eigenschaft um die Hälfte reduzieren. Es wird nur die rechte obere Hälfte der Matrix berechnet, der Rest der Eintragungen ergibt sich dadurch automatisch.

Der Nachteil an der Distanzmatrix liegt in ihrer Größe. Diese ist abhängig von der Anzahl der Fahrzeuge innerhalb der Simulation. Die Matrix besteht aus  Elementen. Innerhalb jeder Simulationsschleife müssen jedesmal  Distanzen berechnet werden. Dadurch wird die Berechnung langsamer, je mehr Fahrzeuge sich innerhalb einer Simulation befinden.

Abbildung 32: Abfrage bei Hindernissen

Die Abfrage für Hindernisse benutzt ein anderes System, um die Objekte innerhalb einer vorgegebenen Distanz zu bestimmen. Diese Distanz beschreibt dabei nicht einen Kreis um das Fahrzeug, sondern wird als die halbe Breite bzw. Höhe eines Rechtecks mit dem Fahrzeug als Mittelpunkt betrachtet. Jedes Objekt besitzt ein umschließendes Rechteck, daß das gesamte Hindernis beinhaltet. Ein Hindernis wird als innerhalb der Distanz betrachtet, wenn sein umschließendes Rechteck, das Rechteck um das Fahrzeug schneidet, oder dieses sogar komplett beinhaltet. Da es sich um Rechtecke handelt, kann man rein durch vergleichen der x und y Werte die relevanten Hindernisse bestimmen. Ein Hindernis kann verworfen werden, falls die y Werte des Rechtecks um das Hindernis kleiner als das Minimum oder größer als das Maximum der y Werte des Rechtecks um das Fahrzeug sind. Das selbe gilt auch für die x Werte. In allen anderen Fällen schneiden sich die beiden Rechtecke, oder eines der beiden überdeckt das andere.

Ein Nachteil dieser Methode ist, das alle Hindernisse einer Szenerie im einzelnen überprüft werden müssen. Auch ist sie nicht sehr genau, da das umschließende Rechteck ja nur eine grobe Annäherung an das eigentliche Aussehen ist. Trotz dieser Nachteile ist die Methode schnell und einfach einsetzbar.

2.4.4.Tile Neighborhood

Übersicht

Die TileNeighborhood Klasse ist eine Erweiterung der Neighborhood Klasse. Sie dient zum Ermöglichen von räumlichen Abfragen, verwendet aber eine andere Art der internen Verwaltung als die Neighborhood Klasse. Anstelle der Distanzmatrix und der auf Clipping basierenden Abfrage für Hindernisse, wird für beide Objekttypen die gleiche Methode und eine gemeinsame Datenstruktur verwendet. Die TileNeighborhood Klasse teilt die Simulation in fest vorgegebene Abschnitte ein, die sogenannten „Tiles“. Es entsteht eine Art Schachbrettmuster. Jede einzelne dieser Flächen enthält Informationen über die Fahrzeuge und Hindernisse die diese Fläche schneiden, bzw. sich innerhalb der Fläche aufhalten. Diese Informationen werden mit Hilfe der TileInformation Klasse gespeichert. Sie enthält die Information, ob ein oder mehrere Hindernisse dieses Tile belegen, welche Hindernisse dies sind, und welche Fahrzeuge sich im Bereich des Tiles befinden. Für jede Iteration der Simulation werden die Informationen über Fahrzeuge innerhalb der Tiles aktualisiert. Das Fahrzeug wird vom vorherigem Tile entfernt, und dem neuen Tile zugeordnet. Dies erfordert nur zwei einfache Funktionen zum Umrechnen der Fahrzeugkoordinaten in TileNeighborhhod – Koordinaten, und das Entfernen, bzw. Hinzufügen eines Elements in eine Liste.

Erzeugen der Datenstruktur

Um diese Datenstruktur der Tiles aus den Informationen über die Szene zu generieren, muß man die Fahrzeuge und Hindernisse vom Koordinatensystem der Szenerie in das der TileNeighborhood Klasse umrechnen. Die einzelnen Tiles besitzen eine fest vorgegebene Breite und Höhe, auch die Anzahl in jede Richtung ist vorgegeben. Die Umwandlung erfolgt anhand dieser Formel: . Bei Fahrzeugen wird nur die eigentliche Position umgerechnet, um das zugehörige Tile zu bestimmen.

Da die Hindernisse grundsätzlich als Polygon definiert sind, kann für diese Umrechnung ein Standardverfahren aus der graphischen Datenverarbeitung verwendet werden. Das Schachbrettmuster des TileNeighborhood wird als Rasterbildschirm interpretiert. Zuerst werden die Punkte des Polygons in das TileNeighborhood Koordinatensystem umgerechnet. Als nächstes wird die Kantentabelle aufgebaut. In dieser Tabelle wird für jede einzelne Kante des Polygons die Informationen gespeichert, die zum Umrechnen benötigt werden. Die dafür verwendete EdgeInfo Klasse enthält die maximale y Position der Kante, um festzulegen wann die Kante komplett gezeichnet wurde. Es wird die x Position an der minimalen y Koordinate gespeichert, um den Startpunkt festzulegen. Um die Berechnungen so schnell wie möglich durchzuführen, werden nur Integer - Werte verwendet. Da aber die Steigung einer Kante eine Fliesskommazahl ist, wird Anstelle des Ergebnisses der Berechnung, der Zähler und der Nenner als einzelne Werte gespeichert. Diese Werte werden im weiteren dazu verwendet, um zu bestimmen an welcher x Koordinate die nächste Spalte beginnt. Der Algorithmus beginnt in der untersten Spalte und liest die zugehörige EdgeInfo aus und zeichnet alle vom Polygon überdeckten Linien. Für jede weitere Spalte werden schon ausgelesen EdgeInfo Objekte für die neue Zeile angepaßt und eventuell neue Kanteninformationen ausgelesen. Dies wird bis zur letzten Spalte des Polygons wiederholt.

Bei der Verwendung dieses Algorithmus zum Generieren der Tileinformationen tritt ein Problem auf. Es ergeben sich bei der Umwandlung gewisse Ungenauigkeiten. Die erste Ungenauigkeit ergibt sich bei der Umwandlung der Eckpunkte des Hindernispolygons von Weltkoordinaten die in Double Werten definiert sind in Tilekoordinaten die als Integer gespeichert sind und einen Bereich von mehreren Pixel überdecken. Bei der Anpassung der Start und Endwerte für das Zeichnen einer Spalte ist nicht garantiert, das die jeweils äußersten vom Algorithmus belegten Tiles auch das Hindernis komplett überdecken. In den meisten Fällen wird zwar der innere Teil des Hindernisses belegt, aber ein Großteil der Kanten bleibt unbelegt. Da aber diese unbelegten Tiles dazu führen, das Verhalten wie Cohesion und Obstacle Avoidance mit falschen Informationen arbeiten, wurde auf diesen Algorithmus bei der endgültigen Implementierung der TileNeighborhood Klasse verzichtet.

Um die Probleme des Rasterization Algorithmus zu umgehen, wurde auf eine einfachere, aber dafür weitaus rechenintensivere Methode zurückgegriffen. Da die Umwandlung von Hindernissen in Tile spezifischen Informationen nur einmal am Start der Simulation abgearbeitet werden muß, stellt die Verwendung eines rechenintensiveren Algorithmus kein großes Performanceproblem dar. Zuerst wird das in Weltkoordinaten definierte Polygon mit Hilfe eines Standard Java-Polygonobjekts dargestellt. Die dabei stattfindende Umwandlung der Koordinaten von double auf integer Werte stellt dabei eine zu Vernachlässigende Ungenauigkeit dar. Zunächst wird der zu betrachtende Ausschnitt innerhalb der Tiles festgelegt. Dazu bestimmt man die maximale und minimale x und y Position innerhalb des Hindernisses. Diese legen ein Rechteck fest, in dem sich das gesamte Objekt befindet. Innerhalb dieses Rechtecks werden zunächst die Eckpunkte jedes Tiles auf Überschneidung mit dem Polygon getestet. Dadurch kann schon hier in den meisten Fällen die Entscheidung getroffen werden, ob das Tile vom Hindernis belegt wird. Falls dieser Test zu keiner Überschneidung führt, wird jeder zweite Pixel innerhalb des Tiles auf Überschneidung getestet. Nur falls auch dieser Test ein negatives Ergebnis liefert, kann man sicher sein, das jedes Tile korrekt belegt wurde.

Bestimmen von Objekten im vorgegebenen Radius

Die Hauptaufgabe der Neighborhood Klassen ist die Bestimmung von Objekten innerhalb eines bestimmten Radius mit einem Fahrzeug als Mittelpunkt. In der TileNeighborhood Klasse legt der übergebene Radius die Anzahl an Tiles fest, die zu Überprüfen sind. Im Gegensatz zur Neighborhood Klasse, wird hier ein Rechteckiger Bereich um das Fahrzeug getestet, anstelle eines Kreisförmigen Bereichs. Dadurch kann es bei manchen Verhalten bei Verwendung der TileNeighborhood Klasse zu leicht abgeänderten Ergebnissen kommen.  Von jedem Tile innerhalb des festgelegten Bereichs wird je nach Abfrage das Array mit den Fahrzeugen, bzw. Hindernissen, ausgelesen und in das Ergebnisarray kopiert. Es muß nur bei der Abfrage nach Fahrzeugen darauf geachtet werden, daß das zentrale Fahrzeug nicht in das Ergebnis übernommen wird. In der Definition der Abfragefunktionen in der Neighborhood Klasse wird das zentrale Fahrzeug nicht zurückgeliefert, deshalb muß auch die TileNeighborhood Klasse diese Spezifikation erfüllen.

2.4.5.Path Generating

Übersicht

Die von Reynolds entwickelten Verhalten dienen alle zum Steuern eines Fahrzeuges. Hierbei wird im allgemeinen nur die nähere Umgebung des Fahrzeuges analysiert und auf Basis dieser Daten die Steuerungskraft berechnet. Um nun ein Fahrzeug durch eine einfach aufgebaute Simulation zu steuern reicht diese Art der Umgebungsanalyse aus um ansprechende Ergebnisse zu erzielen. Sobald die Umgebung eine gewisse Komplexität und einen gewissen Umfang erreicht, muß man seinen Weg durch die Simulation vorausplanen um gute Ergebnisse zu erzielen. Wenn zum Beispiel das Ziel durch Hindernisse verdeckt wird, kann es zu Situationen kommen, in denen eine Kombination von „Seek“ und „ObstacleAvoidance“ einfach keine Möglichkeit hat, das gewünschte Ziel zu erreichen.

Für diese Art von Problemen gibt es das „PathFollowing“ verhalten, das sich auf vordefinierte Pfade durch komplexe Situationen stützt. Um diese Pfade interaktive zu erzeugen, gibt es mehrere Algorithmen. Alle diese Algorithmen erwarten eine Darstellung der Welt als gewichteter, oder ungewichteter Graph. Da die Simulation aber aus einer Kombination von Fahrzeugen und Hindernissen innerhalb eines kontinuierlichen Raumes besteht, muß man eine andere Repräsentation der Daten verwenden. Wenn man Fahrzeuge außer acht läßt, besteht die Simulation aus Hindernissen, die wiederum aus Polygone bestehen. In [Bryan Stout] sind unterschiedliche Möglichkeiten der Repräsentationen beschrieben.

Abbildung 33: Beispiel für eine Umwandlung in eine auf Tiles basierende Darstellung

Die einfachste Methode, die auch als TileNeighborhood Klasse implementiert wurde, verwendet eine Aufteilung der Welt in Rechtecke mit vorgegebener Höhe und Breite. Falls ein Hindernis ein Rechteck überschneidet oder überdeckt, wird es als unzugänglich markiert. Je nach dem wie klein die Ausmaße der Rechtecke gewählt wurden, desto genauer wird die Darstellung aber der Speicherverbrauch steigt auch dementsprechend an. Der Vorteil dieser Methode liegt in der einfachen Umsetzung und der fast Stufenlosen Variierung der Genauigkeit. Ein Nachteil ist die Ungenauigkeit der Aufteilung bei einer Wahl von großen Rechtecken. Man muß bei der Wahl der Parameter abwägen, wie genau die Darstellung sein soll und wieviel Speicher man dafür zur Verfügung hat.

Eine Erweiterung davon sind sogenannte „Quadtrees“. Die Welt wird hierbei in vier Rechtecke eingeteilt. Jedes Rechteck, wird rekursiv in 4 weitere Rechtecke aufgeteilt, falls sein Inhalt nicht einen gewissen Anteil an Hindernissen aufweist. Durch diese Aufteilung erhält man einen Graphen, der sich sehr nah an die ursprüngliche, kontinuierliche Welt hält, wobei hier der Speicherverbrauch etwas niedriger anzusetzen ist, als es bei der einfachen Tile Methode der Falls ist.

Erstellen von Pfaden

Der am weitesten verbreitete Algorithmus zum schnellen Auffinden von Pfaden innerhalb eines Graphen ist der als „A*“ bezeichnete Algorithmus. Er ist eine Erweiterung der Breitensuche und berücksichtigt auch Gewichtungen bei der Erstellung  der Pfade. Grundlage sind zwei Datenstrukturen, die Open-List in der die als Nächstes zu betrachtenden Knoten abgelegt werden und die Closed-List, in der die bereits bewerteten Knoten gespeichert werden. Im Falle von A* ist die Open-List im allgemeinen als Prioritätswarteschlange implementiert. Knoten mit niedrigeren Bewertungen, d.h. mit am wenigsten Kosten verursachenden Pfaden,  werden bei der weiteren Suche favorisiert. Dadurch werden zunächst die momentan am besten Erscheinenden Pfade weiter verfolgt. Im Falle einer homogenen Simulationslandschaft wird durch dieses Bewertungs- und Auswahlschema sofort ein direkter Pfad zum Ziel erzeugt, ohne das zu viele Knoten überprüft werden müssen. Für die Closed-List eignen sich mehrere Datenstrukturen, diese Implementierung verwendet ein einfaches Array. Die Bewertung der Knoten geschieht anhand einer sogenannten „Distanzfunktion“. Diese Funktion liefert eine Schätzung zurück, wie hoch die Kosten für einen direkten Pfad von diesem Knoten bis zum Ziel sein werden. Hierfür gibt es vier mögliche Implementierungen. Der Unterschied liegt jeweils in der Bestimmung der Distanz zwischen dem Knoten und dem Ziel. Bei allen wird die berechnete Distanz mit den geschätzten Kosten für einen Schritt multipliziert. Die Wahl der geschätzten Kosten beeinflußt in nicht zu unterschätzender Weise die Qualität der Suche. Bei einer falschen Schätzung erhöht sich der Aufwand zum auffinden des Pfades in nicht unbeträchtlicher Weise. Die einfachste Funktion zum bestimmen der Distanz zwischen zwei Knoten, , bestimmt die Abweichung  in x und y Richtung, und wählt dann den maximalen Wert der beiden um die Schätzung zu berechnen. Die als „euclidean“ bezeichnete Funktion bestimmt die Distanz zum Ziel mit , der Standardformel zur Bestimmung der Distanz zwischen zwei Punkten. Bei der „Diagonal“ Funktion werden zuerst alle diagonalen Knoten gezählt, bis man in der Zeile, bzw. Spalte des Ziels ist. Dann werden noch die übrigen Knoten auf direktem Wege hinzugezählt. Die vierte Funktion, als „Manhattan“ bezeichnet, benutzt  als Distanz zwischen Knoten und Ziel.

Die Bewertung eines Knotens geschieht durch die Formel . Wobei hier  die Bewertung des Knotens darstellt. Je kleiner dieser Wert, desto wahrscheinlicher wird der Pfad über diesen Knoten im nächsten Schritt weiterverfolgt. g(n) stellt die momentan geringsten Kosten dar, die benötigt werden um zu diesem Knoten zu gelangen. Es sind die Kosten für den bisher am niedrigsten bewerteten Pfad vom Start zu diesem Knoten. Dieser Wert kann sich im Verlauf der Berechnungen noch ändern, falls ein besserer Pfad zu diesen Knoten gefunden wird. h(n) enthält die geschätzten Kosten um das Ziel von diesem Knoten aus zu erreichen. Für die Berechnung dieses Wertes wird eine der vier vorher beschriebenen Funktionen verwendet. Durch die Bewertung der Knoten und der Schätzung der erwarteten Kosten, arbeitet der A* Algorithmus wesentlich zielgerichteter als eine einfache Breiten- oder Tiefensuche. Es werden im allgemeinen Fall wesentlich weniger Knoten untersucht und dadurch ein nicht zu unterschätzender Teil an Rechenleistung eingespart. Ein weiterer Vorteil ergibt sich aus der Bewertung der Knoten. Da die Kosten für das Überqueren eines Knotens bei den Berechnungen berücksichtigt werden, werden Knoten mit hohen Kosten automatisch an das Ende der Prioritätswarteschlange angefügt. Dadurch werden zuerst Pfade durch „leichter“ zu bewältigendes Terrain gesucht. Trotz all dieser Vorzüge hängt die Rechenzeit nicht unwesentlich von der Größe des zu durchsuchenden Bereichs und der Verteilung der Hindernisse ab. Es ist ohne Probleme möglich, Situationen aufzubauen, in denen trotz aller Optimierungen jeder einzelne Knoten betrachtet werden muß, um ein Ergebnis zu liefern. Auch ist der erzeugte Pfad nicht immer der optimale Pfad. Dies stellt eher die Ausnahme dar, da beim ersten gefundenen Pfad die Suche abgebrochen wird. Der Algorithmus garantiert zwar einen Pfad solange es eine Lösung gibt, aber er garantiert nicht, daß es der absolut optimale Pfad vom Start zum Ziel ist. Um dies garantieren zu können, müßten alle möglichen Pfade erstellt und bewertet werden, was äußerst Aufwendig wäre und auch ein hohes Ausmaß an Rechenleistung erfordern würde.

Als Referenz ist der Algorithmus hier noch als Pseudocode aufgeführt, wie er auch in [Bryan Stout] beschrieben wird:

 

Textfeld: priorityQueue	Open
list			Closed
AStarSearch
	s.g = 0			
	s.h = CalcHeuristic(s)	// The estimate from start to finish
	s.f = s.g + s.h		// The evaluation of the node
	s.parent = null		// The first node terminates the path
	push s on Open		
	
	while Open is not empty
		pop Node n from Open		
		if n is goal node
			construct path	
			return success
		end if		
		for each successor n' of n 
			newg = n.g + cost(n', n)				
			if n' is in Open or Closed and n'.g <= newg skip
			n'.parent = n
			n'.g = newg
			n'.h = CalcHeuristic(n')
			n'.f = n'.g + n'.h			
			if n' is in Closed remove n' from Closed		
			if n' is not in Open push n' on Open
		end for 		
		push n onto Closed
	end while
end AStarSearch

struct Node
	g	// The cost for travelling to this node
	h	// The heuristics for going to the goal node
	f	// The evaluation of this node. f = g + h
	parent	// The path is defined by going back the parent node
end struct
 


Das Beispielapplet zum Generieren von Pfaden

Abbildung 34: Screenshot des AlgorithmTest Applets

Um die Arbeitsweise des A* - Algorithmus besser zu verdeutlichen, wurde ein Beispielapplet erstellt. Innerhalb des Applet kann man beliebige Situationen aufbauen und diese dann durch den Pfadfindealgorithmus lösen lassen.

 

Im linken unteren Bereich des Applets befindet sich die Darstellung des Szene. Hier kann man mit Hilfe der Maus den Start- und Endpunkt festlegen, und weitere Objekte wie undurchdringliche., oder schwer zugängliche Bereiche erstellen.

 

 

Abbildung 35: Die Karteneinstellungen des Applets

Im Bereich „Map“ wählt man aus, welches Element auf der Karte plaziert wird, wenn die linke Maustaste gedrückt wird. Die ersten vier Wahlmöglichkeiten, „Empty“ bis „Impossible“, stellen die jeweiligen Kosten für ein einen Knoten dar. Hierbei wird „Empty“ als weißes Kästchen gezeichnet, „Impossible“ als schwarzes Kästchen. „Medium“ und „Hard“ werden dementsprechend als hellgraues, bzw. dunkelgraues Kästchen gezeichnet. Knoten die mit „Impossible“ als Kosten deklariert sind, werden vom Suchalgorithmus nicht in Betracht gezogen. Sie stellen damit Hindernisse oder Mauern dar. Durch die Auswahl von „Start“ oder „Finish“ kann man den Start- und den Endpunkt auf der Karte festlegen. Hierbei wird der Startpunkt als grüner Kreis gezeichnet und der Endpunkt als roter Kreis.

Abbildung 36: Der Geschwindigkeitsregler

Das „Speed“ Steuerelement dient zum Einstellen der Geschwindigkeit der Simulation. Je weiter der Balken nach rechts gezogen wird, desto schneller läuft die Simulation ab. Dadurch kann der Ablauf der Suche im einzelnen dargestellt werden.

Abbildung 37: Das Algorithmus - Auswahlfeld

Mit Hilfe des „Algorithm“ Auswahlfeldes kann man den verwendeten Suchalgorithmus auswählen. Es ist nur der A* Algorithmus implementiert, man könnte im weiteren zu Vergleichszwecken noch andere Algorithmen, wie zum Beispiel Breitensuche, oder Dijkstra’s Suchalgorithmus implementieren.

Abbildung 38: Das Distanzfunktion - Auswahlfeld

Das „Distance Funktion“ Auswahlfeld dient zum Auswählen der verwendeten Distanzfunktion. Wie schon vorher beschrieben gibt es 4 Mögliche Funktionen, die zum Berechnen der geschätzten Kosten zum Ziel verwendet werden können. Durch Auswählen von unterschiedlichen Funktionen, kann man den Einfluß der Näherung auf den Erzeugten Pfad beobachten. Die erzeugten Pfade können dabei recht unterschiedlich ausfallen.

Abbildung 39: Der Regler für die geschätzen Kosten

„Heuristic Cost“ dient zum Einstellen der geschätzten mittleren Kosten um von einem Feld zum nächsten zu gelangen. Dadurch kann man die Näherung die aus den Berechnungen der Distanzfunktionen entstehen noch genauer einstellen. Die Werte hier liegen im Bereich von 2, was einem leerem Feld entspricht, bis zu 9, einem als „Hard“ definierten Feld. Veränderungen an diesem Wert, zeigen wie sehr die Effizienz des Algorithmus von gut gewählten Parametern abhängt. Falls dieser Wert zu klein gewählt wird, werden zu viele unnötige Knoten in Betracht gezogen. Die Suche ist breiter, und nicht mehr so zielgerichtet.

Abbildung 40: Die Steuerungsknöpfe für die Simulation

Mit Hilfe des „Start“ Buttons wird die Simulation gestartet. Der „Reset / Abort“ Button dient einerseits zum Abbrechen einer laufenden Simulation, andererseits werden die Ergebnisse der letzten Suche gelöscht. Der „Clear“ Button dient zum löschen der gesamten Erstellten Szene. Hierbei wird nur der Start- und Endpunkt nicht verändert. Alle Knoten werden wieder in den Status „Empty“ gesetzt.

Abbildung 41: Beispiel eines erzeugten Pfades

Sobald auf „Start“ gedrückt wurde, wird ein Pfad vom Start zum Ziel berechnet. Hierbei werden die Knoten in der „Open-List“ mit blauer Farbe markiert, die Knoten in der „Closed-List“ mit grüner Farbe. Jeder betrachtete Knoten enthält eine orange Linie, die ihn mit seinem übergeordneten Knoten verbindet. Dadurch kann man die bereits erzeugten Pfade erkennen. Sobald das Ziel erreicht wurde, werden die zum endgültigen Pfad gehörenden Knoten mit einem roten Rahmen versehen.

2.4.6.Regensburg Applet

 

Um den A* Pfadfindealgorithmus in Verbindung mit dem SimplePathFollowing Verhalten zu demonstrieren, wurde das Regensburg Applet erstellt. Bestandteil dieses Programms ist ein Kartenausschnitt aus der Regensburger Innenstadt. Diese wurde aus der auf der Homepage der Stadt Regensburg (www.Regensburg.de) online verfügbaren Karte der Stadt entnommen. Das Applet zeigt nur den Teil der Innenstadt, der in dieser Karte in der höchsten Zoomstufe verfügbar ist. Dies entspricht einem Kartenausschnitt von der Größe 1568 mal 1176 Pixeln.

Abbildung 42: Screenshot des Regensburg Applets

Das Fahrzeug in der Simulation wird von einem SimpleMind Objekt mit SimplePathFollowing als einziges Verhalten gesteuert. Die Simulation verwendet die TileNeighborhood Klasse für die interne Darstellung der Simulationsumgebung. Da der Pfadfindealgorithmus auf einem Netzwerk basiert, wird die Information über die Straßen in Regensburg mit Hilfe von einzelnen Tiles dargestellt. Ein einzelnes Tile hat eine Höhe und Breite von 10 Pixeln. Es enthält Informationen über die Zugänglichkeit des Tiles gespeichert im als m_accessible Bezeichneten Attribut. Des weiteren enthält es Informationen zur Bewertung des erzeugten Pfades wie g(n), h(n) und f(n).

Die Information für die Belegung der einzelnen Tiles ist ein einer eigenen Datei hinterlegt. Diese Datei ist sehr einfach aufgebaut und enthält alle notwendigen Informationen um die Tiles korrekt zu belegen.

 

Abbildung 43: Die Steuerelemente des Regensburg Applets

Im unteren Bereich des Applets befinden sich die Steuerelemente für die Simulation. Mit Hilfe der als „Show Grid“ bezeichneten Checkbox kann man das intern verwendete Gitternetz ein- oder ausschalten. Die Dargestellten Kästchen entsprechen den in der TileSimulation verwendeten, einzelnen Tiles. Die „Show Path“ Checkbox dient zum Einschalten der Anzeige des erzeugten Pfades. Sobald der Benutzer ein neues Ziel auf der Karte vorgibt, wird ein neuer Pfad vom Fahrzeug zum Ziel erstellt. Die Wegpunkte dieses Pfades werden als einzelne rote Kästchen auf der Karte dargestellt. Die vom Fahrzeug bereits erreichten Wegpunkte werden automatisch entfernt und verschwinden von der Darstellung. Auf der rechten Seite der Steuerelemente befindet sich eine Auswahlbox mit den zur Verfügung stehenden Zoomstufen. Der Benutzer kann hierbei zwischen 50%, 100%, 150% und 200% Zoom wählen. Der untere Bereich der Steuerelemente dient einem Anzeigefeld mit Hinweisen zu den Steuerelementen die sich gerade unter der Maus befinden. Dadurch erhält der Benutzer jederzeit kontextbezogene Hilfe zu den Elementen des Applet mit denen er interagieren kann.

 

2.5.                   SteeringRenderer

2.5.1.Übersicht

Die  Klasse SteeringRenderer dient der Darstellung aller Objekte innerhalb einer Simulation. Die Bestandteile der Szenerie, wie zum Beispiel Fahrzeuge oder Hindernisse, zeichnen sich nicht selbst, sondern enthalten nur die notwendigen Informationen über Position, Ausrichtung und weitere Informationen zur Darstellung. Die SteeringRenderer Klasse setzt diese Objektbeschreibungen in eine zweidimensionale Darstellung um. Dabei werden die von den Objekten in Weltkoordinaten angegebenen Positionen in Bildschirmkoordinaten umgerechnet, wobei Rücksicht auf den eingestellten Zoomfaktor und Größe und Position des sichtbaren Ausschnitts genommen wird.

Durch diese Aufteilung in eine Beschreibung der Simulation und eine Klasse zur Darstellung auf dem Bildschirm ergeben sich mehrere Vorteile. Die auf Java – AWT basierende SteeringRenderer Klasse, kann jederzeit durch eine neue und erweiterte Darstellungklasse ausgetauscht werden. So kann man die Vorteile von Java2d oder Java3d nutzen, sobald diese auch von den meisten Browsern unterstützt werden. Da zum Zeichnen ein Graphics-Objekt verwendet wird, kann die Klasse sowohl beim Applet als auch beim Editor eingesetzt werden. Dadurch muß nicht für jede Anwendung ein spezieller Code zum Zeichnen der Objekte geschrieben werden. Es lassen sich auch Dinge wie z.B. das Zoomen und Verschieben der Ansicht mit Hilfe des Renderers leichter lösen, als dies bei in den Objekten integriertem Zeichencode möglich wäre. Ein weiterer Vorteil ist die automatisch erzeugte Liste mit allen sichtbaren Objekten und ihren Positionen auf dem Bildschirm. Mit ihrer Hilfe kann man ohne großen Aufwand Benutzeraktionen wie selektieren und verschieben von Objekten realisieren. Dieser Effekt ließe sich zwar auch bei sich selbst zeichnenden Objekten realisieren, aber der Aufwand wäre bedeutend höher ausgefallen. Außerdem wäre man in diesem Fall gezwungen, den selben Code für jede Klasse von Objekten nochmals implementieren. Was umständlich und vor allem äußerst fehleranfällig ist.

2.5.2.Aufbau

Als Basis für die Objekte in der Szene dient die Geometrie Klasse. Sie enthält die notwendigen Informationen, um das Objekt mit Hilfe des SteeringRenderers darzustellen. Die m_pos Variable enthält die Position des Objekts in Weltkoordinaten. Die Ausrichtung wird durch m_localX und m_localY beschrieben. Diese beiden Variablen beinhalten die lokale X- und Y-Achse des Objekts. Sie werden verwendet, um mit Hilfe der Funktionen localToWorld und worldToLocal zwischen Objekt relativen Koordinaten und Weltkoordinaten umzurechnen.

Die Beschreibung für die Darstellung des Objekts ist im Vector m_shapes hinterlegt. Basis für alle Beschreibungen ist die RenderInfo Klasse. Ein Geometrie Objekt kann durch mehrere unterschiedliche RenderInfo Objekte beschrieben werden. Wobei hier auch unterschiedliche Typen verwendet werden können. Die Gestaltung der Objekte wird dadurch flexibler.

 

 

 

Abbildung 44: Klassendiagramm für den SteeringRenderer

Die am meisten verwendete, auf RenderInfo basierende Klasse, ist PolygonShape. Sie enthält die notwendigen Informationen, um ein Polygon auf dem Bildschirm auszugeben. Im allgemeinen besteht ein Polygon aus mindestens drei Punkten, die in Objektkoordinaten angegeben werden müssen. Dabei ist auch zu beachten, das die Punkte zwingend in einer bestimmten Reihenfolge zu übergeben sind. Dies ist notwendig, da die Berechnung des Normalenvektors einer Seite, je nach Reihenfolge der Punkte, verschiedene Ergebnisse liefert. Durch eine fest vorgegebene Reihenfolge können solche Fehlermöglichkeiten ausgeschlossen werden. Polygone können in zwei Arten ausgegeben werden. Einerseits als gefülltes Objekt, andererseits ungefüllt und nur den Umriß verwendend.

Die VectorShape Klasse dient zum Darstellen von Vektoren. Sie wird hauptsächlich innerhalb des Editors verwendet, um z.B. Geschwindigkeitsvektoren darzustellen. Gespeichert wird nur der eigentliche Vektor in der Variable m_vector unter Verwendung der Vector2d Klasse und eine zusätzliche Längeninformation in der Variable m_length. Der endgültige gezeichnete Vektor ergibt sich aus der in Weltkoordinaten umgerechneten m_vector Komponente, skaliert mit dem m_length Faktor.

Um Innerhalb der Simulation Bitmaps verwenden zu können, wurde die Tile Klasse implementiert. Sie enthält in der Variablen m_texture ein benutzerdefiniertes Bitmap. Im Gegensatz zu Polygonen und Vektoren, werden Bitmaps zusammen mit dem Geometrieobjekt skaliert, aber nicht rotiert. Dies hängt mit der fehlenden Unterstützung des AWT Toolkits von rotierten Bitmaps zusammen. Eine auf Java2D basierende SteeringRenderer Klasse könnte diesem Problem Abhilfe schaffen.

Die Circle Klasse dient zum Zeichnen von Kreisen. Diese werden im Gegensatz zum AWT mit Mittelpunkt und Radius definiert. Dabei ist die Position des Geometrie Objekts als Mittelpunkt fest vorgegeben. Die Umrechnung in die Werte für die Zeichnungsfunktionen des AWT werden von der Renderer Klasse automatisch erledigt. Wie auch Polygone können Kreise gefüllt, oder nur als Umriß dargestellt werden.

Die Umwandlung einer Szene in eine Darstellung auf dem Bildschirm geschieht in zwei Schritten:

Abbildung 45: Ablauf der Koordinatentransformation

Zuerst werden im Clipping Schritt alle Objekte verworfen, die den sichtbaren Bereich nicht schneiden. Hierbei wird der selbe Algorithmus wie bei der TileNeighborhood Klasse verwendet. Jedes Geometrieobjekt enthält Informationen über seinen Umfang. Durch diesen Wert kann man ein Rechteck festlegen, welches das Objekt komplett umschließt. Falls dieses Rechteck sich nicht im sichtbaren Bereich des Bildschirms befindet, also diesen Bereich auch nicht schneidet, kann es als nicht sichtbar angesehen werden. Nur die sichtbaren Geometrieobjekte werden von der Rendererklasse auch auf den Bildschirm gezeichnet. Dadurch kann bei großen Szenen ein Teil der Objekte schon in der Clipping Stufe entfernt werden. Es ergibt sich eine Liste mit den sichtbaren Bestandteilen der Szene. Diese werden nun von Weltkoordinaten in Bildschirmkoordinaten umgewandelt. Dabei wird auch die Skalierung der einzelnen Objekte berücksichtigt. Als Ergebnis erhält man eine Liste mit den transformierten, sichtbaren Objekten in Bildschirmkoordinaten. Im letzten Schritt werden dann die einzelnen Objekte auf das Graphics Objekt gezeichnet. Hierbei werden für alle definierten RenderInfo Objekte die vorhandenen AWT Funktionen zum Zeichnen auf einen Graphics Canvas verwendet.

Die vom Renderer in der Transformationsphase erstellte Liste mit den Objekten in Bildschirmkoordinaten bietet noch einen weiteren Vorteil. Sie kann für das Zuordnen von Objekten zu bestimmten Bildschirmkoordinaten verwendet werden. Dies dient zum Auswählen und Verschieben von Fahrzeugen oder Hindernissen per Maus. Dies wird im Editor zum bearbeiten der Szenenbeschreibung verwendet und im SimulationApplet zur Auswahl eines Fahrzeuges benutzt.

2.6.                   XML zur Szenenbeschreibung

2.6.1.Was ist XML?

 

Die EXtensible Markup Language (XML) gehört, wie HTML auch, zu den Auszeichnungssprachen. Sie enthält Anweisungen für die Darstellung von Informationen. Während HTML kaum in der Lage ist, Angaben zu den Inhalten selbst zu machen, wird in XML Form, Inhalt und die Gestaltung getrennt behandelt. XML kann man erweitern und an die persönlichen Bedürfnisse anpassen.

 

In der Document Type Definition (DTD) wird die Dokumentstruktur (Tags) und deren Attribute festgelegt. Dies ist jedoch im Gegensatz zu SGML nicht zwingend vorgeschrieben. Man unterscheidet zwischen gültigen und wohlgeformten Dokumenten: Gültig ist ein Dokument dann, wenn es entsprechend der DTD eine korrekte Syntax aufweist. Man spricht von wohlgeformt, wenn die Syntax korrekt ist, jedoch keine DTD definiert wurde.

2.6.2.XML Definitionen

 

XML-Dateien besitzen einige Vorabinformationen für das verarbeitende Programm. Erster Bestandteil eines XML Documentes ist immer die Deklaration:

 

 <?xml version=“1.0“?>

 

Anschliessend ist zwingend ein Wurzelelement erforderlich. Ein solches Element besitzt keine gleichgestellten Elemente. Innerhalb des Wurzelelements folgen die Elemente zur Darstellung der Informationen. Anders als in HTML ist XML case-sensitive, d.h. es müssen die Definitionen der Elemente und deren Attribute unbedingt beachtet werden. Jedes eröffnete Element muß auch wieder geschlossen werden:

 

<element>

.....

</element>

 

Enthält ein Element keine Unterelemente, kann das Tag folgendermaßen geschreiben werden:

 

<element/>

 

Attribute werden innerhalb des Tags aufgelistet. Im Gegensatz zu HTML müssen immer Anführungszeichen für die Attributwerte verwendet werden:

 

<element attr1=“1“ attr2=“abc“/>

 

 

2.6.3.XML als Szenenbeschreibung

 

Da eine SteeringBehaviors-Szene ein komplexes, aber geordnetes Objektmodell darstellt, bietet sich an, als Szenenbeschreibung XML zu verwenden. XML-Dokumente sind leicht zu erstellen und für den Menschen lesbar und verständlich.

2.6.4.XML-Parser

 

Zum Parsen von XML-Dokumenten wird der Xerces XML-Parser verwendet. Xerces ist ein Produkt eines aus insgesamt sieben Unterprojekten des Apache-XML-Projects. Das Apache-XML-Project verfolgt das Ziel, freie und professionelle XML-Lösungen anzubieten. Xerces unterstützt das Parsen und die Generierung von XML-Dokumenten und ist in Java und C++ erhältlich. Es implementiert die W3C XML und DOM (Level 1 und 2) Standards, sowie den SAX (Version 2) Standard.

2.6.5.Steering XML Referenz

Eine Steering Szene

 

Die einfachste Scenenbeschreibung hat die Form:

 

<?xml version="1.0" encoding="UTF-8"?>

<steering>

</steering>

 

Dieses Dokument ist wohlgeformt und es wird keine keine DTD benötigt. Elemente und Attribute werden in einer Steering-Szene grundsätzlich klein geschrieben.

 

Eine Steering Behaviors Szene verwendet das Root-Element <steering>.

Das <steering>-Elemement besitzt folgende Attribute:

 

<steering>

 

Attribut

Beschreibung

width

Die Breite der Szene

height

Die Höhe der Szene

image

Name des Hintergrundbildes

showgrid

Anzeige des Gitternetzes (true/false)

imgsizex

Breite des Hintergrundbildes in Pixeln

imgsizey

Höhe des Hintergrundbildes in Pixeln

 

 

Definition von Fahrzeugen

 

Zur Fahrzeugsdefinition wird das <vehicle> - Tag verwendet. Für ein Fahrzeug sind folgende Attribute definiert:

 

 

 

<vehicle>

 

Attribut

Beschreibung

name

Name des Fahrzeugs

x

Beschreibt die x-Position des Fahrzeugs

y

Beschreibt die y-Position des Fahrzeugs

maxvel

Die maximale Geschwindigkeit des Fahrzeugs

maxforce

Maximale Steuerungskraft, die auf das Fahrzeug wirken darf

radius

Radius des Bounding-Kreises

velx

x-Anteil des Geschwindigkeitsvektors

vely

y-Anteil des Geschwindigkeitsvektors

scalex

Skalierungsfaktor in x-Richtung

scaley

Skalierungsfaktor in y-Richtung

color

Die Farbe des Fahrzeuges

 

Eine einfache Fahrzeugdefinition an der Stelle (100,150) ohne Mind sieht demnach folgendermassen aus:

<vehicle x=“100“ y=“150“/>

 

Zuweisen von Minds und Behaviors

 

Innerhalb des <vehicle> - Tags kann dem Fahrzeug ein Mind und diesem wiederum ein oder mehrere Verhalten zugewiesen werden. Ein einfaches SimpleMind wird mit <simplemind> hinzugefügt. Für die Verhalten selbst sind die Tags nach dessen Namen benannt:

 

 

 

 

<obstacleavoidance>

 

Attribut

Beschreibung

radius

Radius für den Testzylinder

length

Die Länge des Testzylinders

influence

Einflussfaktor des Verhaltens

 

<containment>

 

Attribut

Beschreibung

frontdistance

Länge des vorderen Testvektors

sidex

x-Anteil der beiden seitlichen Testvektoren

sidey

y-Anteil der beiden seitlichen Testvektoren

influence

Einflussfaktor des Verhaltens

 

<fuzzycontainment>

 

Attribut

Beschreibung

frontdistance

Länge des vorderen Testvektors

sidex

x-Anteil der beiden seitlichen Testvektoren

sidey

y-Anteil der beiden seitlichen Testvektoren

influence

Einflussfaktor des Verhaltens

 

 

<arrive>

 

Attribut

Beschreibung

steps

Anzahl der Schritte für das Erreichen des Ziels

activedistance

Maximale Entfernung zum Ziel um das Verhalten zu aktivieren

target

Name des Zielobjekts

influence

Einflussfaktor des Verhaltens

 

 

<flocking>

 

Attribut

Beschreibung

neararearadius

Radius, innerhalb dem andere Fahrzeuge gesehen werden

cohesion

Einflussfaktor des verwendeten cohesions-Verhaltens

separation

Einflussfaktor des verwendeten separation-Verhaltens

alignment

Einflussfaktor des verwendeten alignment-Verhaltens

influence

Einflussfaktor des Verhaltens

 

<separation>

 

Attribut

Beschreibung

neararearadius

Radius, innerhalb dem andere Fahrzeuge gesehen werden

influence

Einflussfaktor des Verhaltens

lookaheadonly

Bei True werden nur die vorderen Fahrzeuge beachtet

 

<alignment>

 

Attribut

Beschreibung

neararearadius

Radius, innerhalb dem andere Fahrzeuge gesehen werden

influence

Einflussfaktor des Verhaltens

lookaheadonly

Bei True werden nur die vorderen Fahrzeuge beachtet

 

<cohesion>

 

Attribut

Beschreibung

neararearadius

Radius, innerhalb dem andere Fahrzeuge gesehen werden

influence

Einflussfaktor des Verhaltens

lookaheadonly

Bei True werden nur die vorderen Fahrzeuge beachtet

 

<evade>

 

Attribut

Beschreibung

activedistance

Maximale Distanz zum definierten Ziel innerhalb der das Verhalten einen Kraftvektor erzeugt

estimatefactor

Faktor zur Bestimmung der erwarteten zukünftigen Position des Ziels

influence

Einflussfaktor des Verhaltens

target

Name des Zielobjekts

 

<pursuit>

 

Attribut

Beschreibung

activedistance

Maximale Distanz zum definierten Ziel innerhalb der das Verhalten einen Kraftvektor erzeugt

estimatefactor

Faktor zur Bestimmung der erwarteten zukünftigen Position des Ziels

influence

Einflussfaktor des Verhaltens

target

Name des Zielobjekts

 

<wander>

 

Attribut

Beschreibung

x

Lokale x-Koordinate des Wander-Kreises

y

Lokale y-Koordinate des Wander-Kreises

radius

Radius des Wander-Kreises

influence

Einflussfaktor des Verhaltens

 

 

 

 

 

 

<seek>

 

Attribut

Beschreibung

aktivedistance

Maximale Entfernung zum Ziel um das Verhalten zu aktivieren

posx

x-Koordinate des Zielpunkts [deprecated]

posy

y-Koordinate des Zielpunkts [deprecated]

target

Name des Zielobjekts

influence

Einflussfaktor des Verhaltens

 

<simplepathfollowing>

 

Attribut

Beschreibung

arrivedistance

Minimale Entfernung zum nächsten Wegpunkt um den nächsten zu selektieren

influence

Einflussfaktor des Verhaltens

 

Beispiele für eine Vehicle-Definition:

 

<vehicle name=“BMW“ x=“132“ y=“234“>

      <simplemind>

            <wander x=“20“ y=“0“ radius=“10“ influence=“0.8“/>

            <separation neararearadius=“23“ influence=“1“/>      </simplemind>

</vehicle>

 

 

<vehicle name=“Audi“ x=“200“ y=“100“>

      <simplemind>

            <separation neararearadius=“20“ influence=“1“/>

            <seek target=“BMW“>

      </simplemind>

</vehicle>

 

Definition von Hindernissen

 

Das <obstacle>-Tag definiert ein Hindernis mit folgenden Attributen:

 

<obstacle>

 

Attribut

Beschreibung

name

Name des Hindernisses

x

Beschreibt die x-Position des Hindernisses

y

Beschreibt die y-Position des Hindernisses

radius

Radius des Bounding-Kreises

scalex

Skalierungsfaktor in x-Richtung

scaley

Skalierungsfaktor in y-Richtung

angle

Drehungswinkel des Hindernisses

color

Die Farbe des Hindernisses

 

Definition der Objektgeometrie

 

Die Form der Fahrzeuge und Hindernisse kann völlig frei definiert werden. Verhalten wie ObstacleAvoidance und Containment beachten dabei die geometrische Form des Hindernisses.

Die Form eines Objekts wird durch ein Polygon-Shape definiert. Zur Einleitung einer solchen Formbeschreibung wird das <description>-Tag verwendet. Die Definition eines Polygons geschieht mit <polygonshape>. Innerhalb dieses Elements werden die Punkte definiert:

 

 

 

 

<point2d>

 

Attribut

Beschreibung

x

Lokale x-Position des 2D-Punktes

y

Lokale y-Position des 2D-Punktes

 

Eine Formbeschreibung für ein rechteckiges Hindernis kann beispielsweise wie folgt aussehen:

 

<obstacle name=“Wall“ x=“100“ y=“300“>

      <description>

            <polygonshape>

                  <point2d x=“15.0“ y=“-10.0“>

                  <point2d x=“15.0“ y=“10.0“>

                  <point2d x=“-15.0“ y=“10.0“>

                  <point2d x=“-15.0“ y=“-10.0“>

            </polygonshape>

      </description>

</obstacle>

 

 

2.7.                   SteeringFactory

2.7.1.Übersicht

 

Die SteeringFactory ist ein wichtiger Bestandteil der vorbereitenden Initialisierung einer Simulation. Sie ist dafür zuständig, eine durch XML beschriebene Szenenbeschreibung in das von der Simulation verwendete Objektmodell umzusetzen. Dieses Objektmodell besteht im wesentlichen aus vier Teilen:

 

 

·        einer Fahrzeugliste

·        einer Hindernisliste

·        einem Hintergrundbild

·        Szenendetails (z.B. Breite/Höhe einer Szene)

 

Abbildung 46: Ein- und Ausgabeelemente der SteeringFactory

Aufgabe der SteeringFactory ist es nun ein XML-Dokument zu parsen und die oben aufgelisteten Bestandteile einer Szene zur Verfügung zu stellen. Zu diesem Zweck bestitzt die Factory folgende Zugriffsmethoden:

 

·        Geometrie getBackground()
Diese Methode liefert eine Geometrie-Instanz, die als Render-Info ein Tile-Objekt mit dem entsprechenden Hintergrundbild enthält.

·        Vector getVehicles()
Liefert eine Fahrzeugliste aller in der Szene enthaltenen Fahrzeuge. Jedem Fahrzeug sind laut der XML-Beschreibung die entsprechenden Behaviors zugeordnet.

 

 

·        Vector getObstacles()
Liefert die Liste der Hindernisse. Skalierung, Ausrichtung und die Form der Hindernisse wird entsprechend der XML-Beschreibung generiert.

·        int getSceneWidth(), int getSceneHeight()
Diese Methoden stellen die Szenenbreite bzw. –höhe zu Verfügung.

 

Als Eingabeparameter benötigt die SteeringFactory lediglich den Dateinamen des XML-Dokuments und eine Referenz zum Neighborhood-Objekt.

2.7.2.Arbeitsweise

 

Durch Aufruf der Methode createScene() wird die Szene generiert. Zunächst wird überprüft, ob das XML-Dokument eine Steering-Szenerie beschreibt. Damit dies der Fall ist, muß das Root-Element den Namen „steering“ besitzen. Anschliessend werden durch die Methode createSteering() die vorhanden Attribute des <steering>-Tags interpretiert und entsprechend gesetzt. Das sind beispielsweise die Attribute image, width, height und showgrid.

Nun werden die Hindernisse und Fahrzeuge generiert. Entsprechend der XML-Beschreibung wird den Fahrzeugen ein Mind und Behaviors hinzugefügt. Bei bestimmten Behaviors (z.B. Seek) ergibt sich jedoch ein Problem: Sie benötigen eine Objektreferenz zu einem anderen Fahrzeug bzw. Hindernis. Aus diesem Grund wird zuerst eine Hashtabelle aller Fahrzeuge und Hindernisse generiert. Als Schlüssel wird der Objektname verwendet. Bei der späteren Generierung eines Verhaltens wird auf diese Hashtabelle zurückgegriffen. Mit Angabe des Objektnamens erhält man als Ergebnis eine Referenz auf das entsprechende Objekt.

 

Abbildung 47: Zuweisung von Objektreferenzen

 

Das Szenen-Modell wird also zweimal durchlaufen:

1.)    Beim ersten Durchgang werden alle Objekte erzeugt und mit jeweiligen Namen als Schlüssel in einer Hash-Tabelle abgelegt.

2.)    Beim zweiten Durchgang werden diese Objekte zusätzlich in entsprechenden Listen (m_vehicles, m_obstacles) hinterlegt und die Fahrzeuge mit einem Mind und den zugeordneten Verhalten erweitert.

 

Für die Zuweisung der Verhalten werden alle Child-Knoten eines Minds durchlaufen und entsprechend des Elementnamens eine entsprechende Instanz erzeugt. Die Attribute werden mit der Methode

 

setObjectAttributes(ObjectAttributes obj, NamedNodeMap attr)

 

gesetzt. Diese Methode belegt alle in der Attributliste attr enthaltenen Attribute durch Aufruf von setAttribute(String name, String value) mit den in der XML Datei gespeicherten Werten. ObjectAttributes ist ein Interface, das ermöglicht, einzelnen Klassenvariablen anhand ihres Names Werte zuzuweisen. Dabei kann jede Klasse, die dieses Interface implementiert, selbst entscheiden welche Attribute benötigt werden und wie diese den übergebenen Wert interpretieren.

Das generierte Behavior wird zu einer Behavior-Liste hinzugefügt, die durch die setBehaviors(…)-Methode dem Mind zugewiesen wird.

 

Formbeschreibungen von Objekten werden durch die createDescription()-Methode generiert. Diese Methode wird aufgerufen, sobald ein <description>-Tag gefunden wurde. Die erstellte Geometrie-Instanz wird dem Parent-Objekt des <description>-Tags zugerodnet.

 

Nachdem die SteeringFactory Klasse die Szene generiert hat, können der Simulation die Objektlisten und Szenenparameter übergeben werden.

2.7.3.Erweiterung der SteeringFactory

 

Sollte die Szenenbeschreibung mit weiteren Behaviors zu erweitern sein, muß lediglich in der createBehavior()-Methode ein neuer Abschnitt eingefügt werden, in dem das neue Behavior instanziiert wird und dessen Attribute gesetzt werden. Das neue Behavior wird anschliessend noch der Behaviorliste hinzugefügt. Die Implementierung kann wie folgt aussehen:

if (type.equals("newbehavior"))

{    

NewBehavior b = new NewBehavior(); 

      setObjectAttributes(b, attr);

      behaviors.add(b);

}

2.8.                   SteeringCreator

2.8.1.Einleitung

 

Mit Hilfe von XML-Dokumenten können ziemlich einfach Szenerien aufgebaut werden. Jedoch sinkt die Übersichtlichkeit mit zunehmender Komplexität der Szene. Der SteeringCreator ist ein grafischer Editor der dem Anwender das manuelle Erstellen oder Bearbeiten eines XML-Dokuments abnimmt. Man erhält somit bei der Planung den vollen Überblick über das Aussehen und der Lage der Objekte. Attribute von Objekten, Minds und Behaviors können weiterhin beliebig verändert werden. Die Stärke dieses Editors liegt in der grafischen Benutzeroberfläche, die es dem Anwender ermöglicht, mit der Maus oder per manuelle Eingabe Objekte zu platzieren, skalieren oder zu drehen.

 

Der SteeringCreator ist in der Lage XML-Dokumente zu lesen als auch selbst zu erstellen. Wie bei der SteeringFactory wird dabei auf Xerces zurückgegriffen (siehe Abschnitt 2.6.4).

 

 

 

 

 

 

 

 

 

 

2.8.2. Bedienung des SteeringCreators

Bildschirmaufteilung

Abbildung 48: Die Oberfläche des SteeringCreators

Der Steering Creator besteht im wesentlichen aus 6 Teilen:

 

 

 

Menü

Über das Menü ist es möglich, Szenen zu laden, zu speichern bzw. neu zu erstellen. Außerdem kann über den Menüpunkt “Exit” das Programm beendet werden.

Abbildung 49: Das Menü

Der Objektbaum

Der Objektbaum stellt die Objektstruktur der Szene dar. Über ihn können die Verhalten der einzelnen Fahrzeuge verwaltet werden. Im Beispiel wie im Bild besteht die Szene aus vier Fahrzeugen und zwei Hindernissen. Dem Fahrzeug mit dem Namen “vehicle1 “ ist ein SimpleMind mit den Verhalten Wander, Containment und Separation zugewiesen. Um neue Objekte einzufügen steht ein Kontextmenü zur Verfügung, das durch Klick mit der rechten Maustaste geöffnet wird.

Abbildung 50: Der Objektbaum einer Szenenbeschreibung

 

 

 

 

 

 

 

 

 

 

Die Zeichenfläche

 

Abbildung 51: Die Zeichenfläche

 

Die Zeichenfläche stellt die Szene grafisch dar. Die Objekte können mit der Maus beliebig verschoben werden. Die Richtung der Fahrzeuge wird mit dem roten Angriffsknoten verändert. Hindernisse können mit dem blauen Knoten skaliert und mit dem roten Knoten gedreht werden. Außerdem stellt die Zeichenfläche ebenfalls ein Kontextmenü zur Verfügung, mit der Objekte zur Szene hinzugefügt werden können.

 

 

Die Toolbar

 

Abbildung 52: Toolbar

 

Die Toolbar enthält die wichtigsten Werkzeuge, die für die Erstellung einer Szene benötigt werden. Je nachdem welches Objekt im Objektbaum markiert ist, sind die Schaltflächen aktiviert bzw. deaktiviert.

 

Das Zoomwerkzeug:

 

Abbildung 53: Das Zoomwerkzeug

 

Mit diesem Schieberegler kann in die Szene hinein- bzw. herausgezoomt werden.

 

 

 

 

 

 

 

 

 

 

 

Die Buttons der Toolbar:

 

Erstellt ein neues Fahrzeug

Fügt ein neues Hindernis in die Szene ein

Entfernt das selektierte Objekt aus der Szene

Klont das Objekt. Bei Fahrzeugen wird das Mind-Objekt mit allen zugewiesenen Verhalten mitkopiert

Weist dem selektierten Fahrzeug ein Mind zu

Weist einem Mind ein neues Verhalten zu

Simulation Preview. Diese Schaltfläche öffnet ein neues Fenster in dem die Simulation der aktuell geöffneten Szene dargestellt wird

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Der Attribut-Editor

 

Ein wichtiger Bestandteil des Creators ist der Attribut-Editor. Ist ein Objekt bzw. ein Verhalten markiert, stellt er dessen Attribute dar, die manuell bearbeitet werden können. Die einzelnen Attribute sind in der Steering XML Referenz, Kapitel 2.6.5 auf Seite 36 näher erläutert. Bestimmte Attribute werden automatisch angepasst. Beispielsweise wird das x und y – Attribut bei Verschiebung eines Objekts in der Zeichenfläche automatisch der neuen Position angepasst. Mit den Schaltflächen können neue Attribute hinzugefügt und vorhandene gelöscht werden.

Abbildung 54: Der Attributeditor

 

 

 

 

 

Tutorial zum Erstellen einer Szene

 

Es soll nun kurz erläutert werden, wie eine Szene erstellt werden kann. Angenommen man will folgende Szene erstellen:

 

Abbildung 55: Szenenaufbau für Queueing

Diese Szene besteht aus drei Hindernissen und einer großen Anzahl an Fahrzeugen. Sie soll ein Beispiel für Schlangenbildung an einem Engpass darstellen. Die Fahrzeuge werden mit Hilfe von drei Verhalten gesteuert.

Das Seek-Verhalten zwingt sie, auf das Hinderniss außerhalb des definierten Bereiches zuzusteuern. Da beim Überschreiten der Grenze das Fahrzeug auf der anderen Seite der Szene platziert wird, kann somit ein unendliches Wiederholen der Simulation sichergestellt werden.

Damit die Fahrzeuge sich nicht durch die Wände, dargestellt durch zwei Hindernisse, bewegen, wurde ihnen das Containment-Verhalten zugewiesen. Dies verhindert das Fahrzeuge sich durch die vorgegebenen Hindernisse bewegen können. Sie werden gezwungen, sich durch den engen Durchgang zu zwängen.

Zuletzt erhalten die Fahrzeuge noch ein Separation-Verhalten, wodurch sie gezwungen werden, einen gewissen Abstand voneinander zu bewahren. Ohne dieses Verhalten, würden die Fahrzeuge einfach durch die Engstelle passieren und dabei einfach alle anderen Fahrzeuge ignorieren.

 

Um nun die Szene aufzubauen, muß man zuerst mit Hilfe von „File->New“ der Editor auf die Ausgangsszenerie zurückgesetzt werden. Diese hat eine vorgegebene Höhe von 480 und eine Breite von 640 Pixel. Für diese Simulation soll dies auf etwas kleinere Werte verringert werden. Dazu ändert man die Werte der beiden Attribute „height“ und „width“ auf 360. Um sicherzugehen, das die Änderungen auch wirklich übernommen worden sind, sollte man immer auf die „Return“ - Taste drücken um seine Eingaben zu bestätigen.

 

Als erstes werden die beiden Hindernisse eingefügt. Diese sollen einen schmalen Durchlaß bilden. Dazu klickt man auf das „Hinderniss hinzufügen“ – Icon (  ). Man erhält ein Dialogfenster und wählt hier den Typ „rectangle“ aus. Man erhält ein vorgegebenes, rechteckiges Hindernis auf seiner Zeichenfläche. Mit Hilfe des blauen Kästchens kann man dieses beliebig skalieren und unter Verwendung des roten Kreises die Ausrichtung ändern. Mit der Maus kann es beliebig innerhalb der Szene positioniert werden. Das Hindernis soll nun auf folgende Art platziert werden:

 

Abbildung 56: Erstellen des Engpasses

Nachdem der erste Teil des Durchgangs fertiggestellt ist, klickt man auf die weiße Zeichenfläche, damit kein Objekt markiert ist und benutzt dann wiederum das „Hindernis hinzufügen“ – Icon um den zweiten Teil des Durchgangs zu erstellen.

 

Der nächste wichtige Punkt ist das Festlegen des Ziels für das Seek-Verhalten. Hierzu benötigt man ein weiteres Hindernis. Dieses platziert man im grauen Bereich direkt hinter dem geschaffenen Durchgang. Dadurch werden die Fahrzeuge gezwungen, sich dorthin zu begeben. Sobald sich ein Fahrzeug innerhalb des grauen Bereichs befindet, also außerhalb der definierten Szene, wird es automatisch auf der anderen Seite und innerhalb des Erlaubten Bereichs platziert. Dadurch kann man eine Simulation erstellen, die nicht nach jedem Durchgang auf den Anfangszustand zurückgesetzt werden muß. Als Hindernis wird diesmal ein Kreis verwendet. Diesen kann man ebenso wie die vorherigen Hindernisse mit dem „Hindernisse hinzufügen“ Befehl einfügen. Anstelle von „rectangle“ wählt man diesmal „circle“ im Dialogfenster aus. Als nächstes wird der vorgegebene Name geändert. Dazu klickt man mit der rechten Maustaste auf den Kreis. Im nun erscheinenden Kontextmenü wählt man den Menüpunkt „Rename“. Man erhält einen neuen Dialog in dem man den Namen des Hindernisses wie folgt ändert:

Abbildung 57: Umbenennen des Ziels

Falls noch nicht getan, platziert man jetzt den Kreis in den grauen Bereich in direkter Linie hinter dem durch die zwei Blöcke gebildeten Durchgang.

 

Als nächstes erstellt man ein Fahrzeug. Dieses wird mit Hilfe des „Fahrzeug einfügen“ – Icons (  ) in die Szene eingefügt. Die vorgegebenen Attribute ändert man wie folgt:

 

Abbildung 58: Eigenschaften des Fahrzeuges

 

Dem Fahrzeug wird nun ein sogenanntes „Mind“ hinzugefügt. Dieses dient zur Steuerung der einzelnen Verhalten. Der Steering Creator stellt zwei vordefinierte „Mind“ – Klassen zur Auswahl. Das „simple Mind“ summiert die von den Verhalten erzeugten Kräfte auf und erzeugt daraus den endgültigen Steuerungsvektor. Das „priority Mind“ akzeptiert nur so lange Kräft von den Verhalten, bis die maximale Kraft des Fahrzeuges erreicht ist. Alle weiteren Kräfte der Behaviors werden ignoriert. In dieser Simulation wird das „simple Mind“ verwendet. Durch klicken auf das „Mind hinzufügen“-Icon erhält man ein Auswahlfenster mit verschiedenen „Mind“-Klassen. Hier wählt man das „simple Mind“ wie im folgenden Bild gezeigt:

Abbildung 59: Einfügen der "Mind" - Klasse

Nun kann mit der Definition der einzelnen Verhalten begonnen werden. Zuerst wird das „Seek“-Verhalten hinzugefügt. Dazu klickt man zuerst im Objektbaum auf das „Mind“ des Fahrzeuges und dann auf das „Verhalten Hinzufügen“-Icon (  ). Im nun erscheinenden Dialogfenster wählt man das „Seek“-Verhalten aus:

 

Abbildung 60: Hinzufügen  des Seek - Verhaltens

 

Die vorgegebenen Eigenschaften des Verhaltens ändert man nun wie folgt ab:

 

Abbildung 61: Attribute des Seek - Verhaltens

Das „activedistance“-Attribut legt hierbei fest, innerhalb welcher Distanz das „Seek“ – Verhalten auf das Ziel zusteuern soll. Da die Szene nur 360 Pixel breit ist, kann durch den Wert 500 garantiert werden, daß das Verhalten grundsätzlich seine Arbeit verrichtet. Den Wert für das „influence“-Verhalten reduziert man auf 0.7, d.h. der erzeugte Kraftvektor kann maximal 70% der maximalen Kraft des Fahrzeuges betragen. In das „target“-Attribut trägt man den Namen des gewünschten Ziels ein. In diesem Fall ist es der Name des kreisförmigen Hindernisses, der als „target“ festgelegt ist.

 

Um nun das „Containment“-Verhalten dem Fahrzeug zuzuordnen, klickt man zuerst auf das „Mind“ des Fahrzeuges und anschließend auf  „Verhalten hinzufügen“. Diesmal wählt man das als „Containment (simple)“ bezeichnete Verhalten aus. Die vorgegebenen Eigenschaften werden nun auf folgende Werte geändert:

 

Abbildung 62: Eigenschaften des Containment - Verhaltens

Das „frontdistance“-Attribut legt hier die Länge des nach vorne hin testenden Vektors fest. Bei der hier definierten Länge erkennt das Fahrzeug Hindernisse innerhalb einer Distanz von 25 Pixeln. Je größer dieser Wert gewählt ist, desto früher werden Hindernisse erkannt und darauf reagiert. Die Werte für „sidex“ und „sidey“ verringert man auf 7, dadurch kann das Fahrzeug näher an Hindernisse heran gesteuert werden.

 

Zuletzt fügt man das „Separation“-Verhalten hinzu. Die Attribute sollte man auf folgende Werte festlegen:

 

Abbildung 63: Attribute für Separation

Durch die Vergrößerung des „neararearadius“-Attributs wird das Fahrzeug gezwungen einen größeren Abstand von den ihm umgebenden Fahrzeugen zu halten. Durch das „lookaheadonly“-Attribut beschränkt sich das Fahrzeug jedoch nur auf die vorderen Fahrzeuge. Die hinteren werden ignoriert. Das ist nötig, damit die Fahrzeuge nicht von den hinteren Fahrzeugen nach vorne gedrängt werden.

 

Bevor nun die weiteren Fahrzeuge erzeugt werden, sollte man nochmals die Attributwerte der einzelnen Verhalten überprüfen. Falls diese korrekt sind, klickt man auf das Fahrzeug, um es auszuwählen. Nun kann man mit Hilfe des „Objekt klonen“ – Icons ( ) eine beliebige Anzahl an Kopien des Fahrzeuges erstellen. Es ist nur darauf zu achten, das sich die Fahrzeuge möglichst nicht überlappen, oder sich innerhalb von Hindernissen befinden. Mit Hilfe des „Objekt klonen“ Befehls kann man schnell eine große Zahl an Fahrzeugen nach einem vorher definierten Schema erzeugen. Falls man zu viele Fahrzeuge erstellt hat, kann man die überschüssigen mit dem „Objekt löschen“ Befehl (  ) wieder aus der Szene entfernen.

 

Um sich seine erzeugte Szene anzuschauen, klickt man auf den Startknopf (  ) und geniest die Show.

2.8.3.Implementierung

 

Die Verwaltung der Objekte

 

Falls einem Mind ein Verhalten zugewiesen werden soll, öffnet sich ein Dialogfenster mit einer Auswahl von möglichen Verhalten. Genau so bei den Hindernissen. Woher nimmt der SteeringCreator diese Informationen? Und woher übernimmt er Standardeinstellungen von Attributen? Die Anwort auf diese Fragen lautet: objects.xml

Diese XML-Datei enthält alle Objekte, deren Attribute, Aussehen und evtl. schon zugewiesenen Unterobjekte. Die Datei besteht aus folgenden Sektionen:

 

Für jede dieser 4 Sektionen sind Tags definiert. Fügt man beispielsweise ein neues Fahrzeug hinzu, zeigt eine Dialogbox die unter <vehicles> definierten Fahrzeuge zu Auswahl an! Auf diese Weise kann durch einfaches Editieren dieser Datei  ein eigenes Profil erstellt werden.

 

Neben den oben beschriebenen Tags und den Tags der Steering XML Referenz gibt es noch das <hint> - Tag. Der eingeschlossene Text wird im Creator im Hint-Window angezeigt. Auf diese Weise können dem Benutzer des Creators Infos über das jeweilige Objekt gegeben werden.

 

Ausschnitte einer object.xml – Datei:

 

<?xml version="1.0" encoding="UTF-8"?>

<steeringobjects>

   <vehicles>

<vehicle name="vehicle" ......>

            <description>

                  <polygonshape>

                        <point2d x="-5" y="5"/>

                        ......

                  </polygonshape>

            </description>

            <hint>This is a vehicle model.</hint>

      </vehicle>

   </vehicles>

  

   <obstacles>

      ....

   </obstacles>

  

   <minds>

      <simplemind name="Simple mind"/>

   </minds>

  

   <behaviors>

      ....

   </behaviors>

</steeringobjects>

 

Die Klasse ObjectGenerator ist dafür zuständig, diese Datei zu parsen und die Objekte zu verwalten. Mit den Methoden addVehicle(...), addMind(...), addObstacle(...), addBehavior(...) wird ein neues Objekt in den Objektbaum eingefügt. Der ObjectGenerator kümmert sich dann selbständig darum, ob eine Dialogbox bei mehreren Auswahlmöglichkeiten  benötigt wird und zeigt diese an.

 

Die EditorCanvas-Klasse

 

Die Klasse EditorCanvas implementiert die grafische Anzeige und behandelt die Mausereignisse. Wie im Applet auch, ist für die grafische Ausgabe selbst der SteeringRenderer zuständig. Dieser ist für die korrekte Darstellung der Szene verantwortlich. Außerdem ist er in der Lage, bei Mausklick eine Liste der angeklickten Objekte zurückzuliefern. Diese Funktion ist die Grundlage für das Verschieben der Objekte mit der Maus. Jedes darstellbare Objekt ist in die Klasse GeometrieObjekt eingebettet. Diese enthält einerseits die Geometrie selbst, andererseits die zusätzlichen Geometrieobjekte, wie Skalierungs- und Drehungsknoten. Außerdem werden darin objektspezifische Attribute, die z.B. angeben ob das Objekt selektiert ist, gespeichert. Aus dieser Klasse erhält EditorCanvas die Informationen, die zur Darstellung des Objekts benötigt wird. Ein Klick in den Canvas führt zu einer Anfrage an den SteeringRenderer, welche Objekte sich an dieser Stelle befinden. Nach der Verschiebung eines Objektes werden die Attribute x/y-Position durch die setAttribute(..)-Methode der Klasse SteeringTreeNode aktualisiert. Diese Attribute werden an GeometrieObjekt weitergeleitet. Nach einer visuellen Änderung wird die update()-Methode der GeometrieObjekt-Klasse aufgerufen, welche die Geometriedaten aktualisiert.

2.9.                   Simulation Applet

2.9.1.Einleitung

Um die mit dem Steering Editor erstellten Szenarien auf einer Webseite darzustellen, wurde das Simulation Applet entwickelt. Es setzt die vom Editor gespeicherten XML Dateien wieder in eine Simulation um. Zusätzlich bietet es die gleiche Funktionalität wie der Editor um Informationen über die laufende Simulation zu erhalten.

2.9.2.Bedienung des Simulation Applets

 

Bildschirmaufteilung

Das Applet ist ein drei Teilebereiche aufgeteilt. Im linken oberen Teil des Applets befindet sich die Darstellung der Simulation. Im rechten oberen Teil befindet sich die Anzeige für den Status des aktuell ausgewählten Fahrzeugs. Im unteren Bereich befinden sich die Steuerelemente für die Simulation.

 

Simulationsbereich

Im Simulationsbereich befindet sich die Darstellung der Fahrzeuge und Hindernisse. Fahrzeuge sind als Dreieck definiert, wobei die längere Spitze immer in Fahrtrichtung zeigt. Hindernisse werden als mehrseitige Polygone gezeichnet. In diesem Bereich kann der Benutzer ein Fahrzeug mit der rechten Maustaste auswählen und sich so Informationen über die Verhalten des Fahrzeuges ausgeben lassen. Diese Informationen werden auf der rechten Seite des Applets dargestellt. Hier wird jeweils der Name des Verhaltens angegeben und darunter ein blauer Balken mit der aktuellen Stärke des Verhaltens. Dadurch läßt sich sehr gut veranschaulichen, welche Verhalten einen konstanten Einfluß auf die Simulation aufweisen, und welche nur in bestimmten Situationen ihren Einfluß geltend machen.

 

Abbildung 64: Screenshot des Simulation Applets

Mit Hilfe der rechten Maustaste kann der dargestellte Ausschnitt der Simulation verschoben werden. Der Mauscursor verwandelt sich in ein Steuerkreuz und durch Bewegen der Maus wird der sichtbare Bereich verschoben. Eine Verschiebung in den negativen Bereich, oder über den maximal definierten Bereich hinaus ist nicht möglich.

 

 

Steuerelemente

Im unteren Bereich des Applets befinden sich die Steuerelemente mit den Einstellungen für das Applet.

 

Abbildung 65: Die Steuerelemente des Simulation Applets

Der wichtigste Button hier ist der mit „Open project...“ bezeichnete. Mit Hilfe dieses Steuerelements wird ein weiterer Dialog aufgerufen mit dem man aus den vorhandenen vordefinierten Simulationen auswählen kann.

Der „Start“ Button dient zum Starten der aktuellen Simulation. Während des Ablaufs wird der Button mit „Pause“ bezeichnet und pausiert die Simulation. Mit Hilfe des „Reset“ Buttons kann man die Simulation wieder in den Ausgangszustand bringen.

Im mittleren Bereich der Steuerelemente befindet sich die „Show Grid“ Checkbox, mit der man die Darstellung eines Gitternetzes über der Simulation einschalten kann. Die mit „Track selected Vehicle“ bezeichnete Checkbox schaltet das Tracking des gerade ausgewählten Fahrzeuges ein, oder aus. Hierbei wird der sichtbare Bereich automatisch so verschoben, daß sich das Fahrzeug im Mittelpunkt befindet. Falls kein Fahrzeug gewählt ist, hat diese Checkbox keine Auswirkungen auf die Ansicht. Auf der rechten Seite der Steuerelemente befindet sich eine Auswahlbox mit den zur Verfügung stehenden Zoomstufen. Der Benutzer kann hierbei zwischen 50%, 100%, 150% und 200% Zoom wählen.

Der untere Bereich der Steuerelemente dient einem Anzeigenfeld mit Hinweisen zum Steuerelement das sich gerade unter der Maus befinden. Dadurch erhält der Benutzer jederzeit kontextbezogene Hilfe zu den Elementen des Applet mit denen er interagieren kann.


3.   Abbildungsverzeichnis

Abbildung 1: Szene aus Stanley and Stella in: Breaking the Ice (1987).............. 4

Abbildung 2: Screenshot aus Dungeon Master 2, Bullfrog Productions Ltd...... 4

Abbildung 3: Kraftvektor beim Seek Verhalten.................................................. 6

Abbildung 4: Kraftvektor beim Arrive Verhalten............................................... 7

Abbildung 5: Beispiel für eine Fahrstrecke mit dem Wander-Verhalten............ 7

Abbildung 6: Steuerungsvektor, deren Spitze sich auf dem Kreis befindet........ 8

Abbildung 7: Berechnung des neuen Steuerungsvektors.................................... 8

Abbildung 8: Verschiedene Einstellungen der Attribute..................................... 9

Abbildung 9: Berechnung des Steuerungsvektors bei Separation....................... 9

Abbildung 10: Berechnung des Steuerungsvektors bei Alignment.................... 10

Abbildung 11: Berechnung des Steuerungsvektors bei Cohesion..................... 11

Abbildung 12: Beispiel für gute und schlechte Annäherung durch einen Kreis12

Abbildung 13: Steuerungsvektor zum Ausweichen eines Hindernisses............. 13

Abbildung 14: Beispiele für Kanten, die im 1. Test verworfen werden............. 14

Abbildung 15: Beispiele für Kanten, die im 2. Test verworfen werden............. 14

Abbildung 16: Beispiele für eine Rückkante, die verworfen werden kann........ 15

Abbildung 17: Ausschlusskanten des 4. Tests................................................... 15

Abbildung 18: Testvektoren beim Containment Verhalten.............................. 16

Abbildung 19: Unscharfe Grenzen der Entfernung.......................................... 17

Abbildung 20: Unscharfen Grenzen des Winkels.............................................. 17

Abbildung 21: Diagramm zur Defuzzifizierung................................................. 18

Abbildung 22: Fahrzeug in einer Ausweichsituation........................................ 19

Abbildung 23: Beispiel einer Fuzzysteuerung.................................................... 19

Abbildung 24: Defuzzifizierung......................................................................... 19

Abbildung 25: Der Steuerungsvektor einer Fuzzy-Ausweichsteuerung............ 19

Abbildung 26: Problematik bei konkaven Hindernissen................................... 20

Abbildung 27: Arbeitsweise des SimpleMinds................................................... 21

Abbildung 28: Beispiele für die mögliche Kraftverteilung bei PriorityMind.... 22

Abbildung 29: Aufteilung der Simulation Klasse.............................................. 23

Abbildung 30: Distanzbestimmung für Neighborhood...................................... 24

Abbildung 31: Symmetrischer Aufbau der Distanzmatrix................................ 24

Abbildung 32: Abfrage bei Hindernissen.......................................................... 25

Abbildung 33: Beispiel für eine Umwandlung in eine auf Tiles basierende Darstellung     27

Abbildung 34: Screenshot des AlgorithmTest Applets...................................... 29

Abbildung 35: Die Karteneinstellungen des Applets......................................... 29

Abbildung 36: Der Geschwindigkeitsregler...................................................... 29

Abbildung 37: Das Algorithmus - Auswahlfeld................................................. 30

Abbildung 38: Das Distanzfunktion - Auswahlfeld........................................... 30

Abbildung 39: Der Regler für die geschätzen Kosten....................................... 30

Abbildung 40: Die Steuerungsknöpfe für die Simulation.................................. 31

Abbildung 41: Beispiel eines erzeugten Pfades................................................. 31

Abbildung 42: Screenshot des Regensburg Applets.......................................... 32

Abbildung 43: Die Steuerelemente des Regensburg Applets............................. 32

Abbildung 44: Klassendiagramm für den SteeringRenderer............................. 33

Abbildung 45: Ablauf der Koordinatentransformation.................................... 34

Abbildung 46: Ein- und Ausgabeelemente der SteeringFactory....................... 42

Abbildung 47: Zuweisung von Objektreferenzen.............................................. 43

Abbildung 48: Die Oberfläche des SteeringCreators........................................ 45

Abbildung 49: Das Menü................................................................................... 46

Abbildung 50: Der Objektbaum einer Szenenbeschreibung.............................. 46

Abbildung 51: Die Zeichenfläche...................................................................... 47

Abbildung 52: Toolbar...................................................................................... 48

Abbildung 53: Das Zoomwerkzeug................................................................... 48

Abbildung 54: Der Attributeditor...................................................................... 49

Abbildung 55: Szenenaufbau für Queueing....................................................... 50

Abbildung 56: Erstellen des Engpasses............................................................. 51

Abbildung 57: Umbenennen des Ziels............................................................... 52

Abbildung 58: Eigenschaften des Fahrzeuges.................................................. 52

Abbildung 59: Einfügen der "Mind" - Klasse................................................... 53

Abbildung 60: Hinzufügen  des Seek - Verhaltens............................................ 53

Abbildung 61: Attribute des Seek - Verhaltens................................................. 53

Abbildung 62: Eigenschaften des Containment - Verhaltens........................... 54

Abbildung 63: Attribute für Separation............................................................ 54

Abbildung 64: Screenshot des Simulation Applets............................................ 57

Abbildung 65: Die Steuerelemente des Simulation Applets.............................. 58

 


 

4.   Literaturverzeichnis

 

[STO96]

 

Stout, Bryan:
Smart Moves: Intelligent Path-Finding
Game Developer Magazine, October / November 1996

[REY87]

 

Reynolds, Craig W.
Flocks, Herds, and Schools: A Distributed Behavioral Model
ACM SIGGRAPH 1987 Conference Proceedings, Anaheim, California, July 1987
www.cs.toronto.edu/~dt/siggraph97-course/cwr87

[REY88]

 

Reynolds, Craig W.
Not Bumping Into Things
ACM SIGGRAPH 1988 Conference Proceedings, Anaheim, California, August 1988
www.red3d.com/cwr/nobump/nobump.html

[REY99]

 

Reynolds, Craig W.

Steering Behaviors
GAME DEVELOPERS CONFERENCE, March 1999
www.red3d.com/cwr/steer

[GRE00]

 

Green, Robin
Steering Behaviours
ACM SIGGRAPH 2000 Conference Proceedings, Anaheim, California, August 2000

[KRÜ00]

 

Krüger, Guido
Java 2 – Handbuch der Java-Programmierung
Addison Wesley, Bonn, Paris, Reading, Massachusetts [u.a.] 2000
ISBN 3-8273-1710-X

[SA00]

 

Sauer, Jürgen
Neuronale Netze und Fuzzy-Control-Systeme
Vorlesungsskript im WS2000, FH Regensburg, Fachbereich Informatik