DevDiary #3 – August 2018

Hallo zusammen,

In diesem Dev Diary möchten wir euch einen Einblick in das Navigationssystem für Charaktere in Die Gilde 3 geben. Dieses System hat in der Vergangenheit für viele Probleme gesorgt und wir mussten einen Weg finden, es zu optimieren.

Zuerst mussten wir uns einen Überblick über die genaue Funktionsweise des Systems verschaffen. Im Kern wurden Charaktere in zwei Schritten von ‚A‘ nach ‚B‘ bewegt.
1. Das Spiel verwendete das Straßennetz, um einen groben Pfad zum Ziel zu berechnen.
2. Mit diesem Pfad bestimmte der Charakter eine Richtung, in die er sich bewegte. Diese Information wurde in ein separates Fortbewegungs-Simulationssystem eingespeist. Diese Simulation war dafür verantwortlich, alle Charaktere so zu ihrem Ziel zu bewegen, ohne dass sie miteinander kollidierten. Die Simulation verwendete eine sogenannte ‚Bibliothek‘.

Probleme mit dem alten Navigationssystem
Wir identifizierten zwei Hauptprobleme im alten System, das wir angehen wollten.
1. Charaktere hatten direkte Kollisionen miteinander. Wenn sie einander nicht auswichen, konnten sie sich miteinander verhaken.
2. Die Fortbewegungssimulation erzeugte eine sehr unnatürlich aussehende Bewegung. Um Kollisionen zu vermeiden, wurden Charaktere „verschoben“, auch wenn diese Charaktere sich nicht selbst in Bewegung befanden. Dies führte dazu, dass „stehende“ Charaktere ziemlich wild herumgeschubst wurden und in manchen Situationen auch Charaktere, welche gerade eine Maßnahme ausführten, wie beispielsweise Taschendiebstahl, vom herannahenden Charakter einfach weg gedrängt wurden.
Darüber hinaus war das Ausweichen oft nicht mit einer Animation verbunden. Wenn ein stehender Charakter sich zur Seite bewegte, um jemandem auszuweichen, dann tat er dies ohne entsprechende Animation – er glitt also mit seiner aktuellen Animation (stehend, tanzend, flirtend, beim Taschendiebstahl, etc.) ein paar Meter über den Boden. Auch berücksichtigte die Fortbewegungssimulation die Sichtlinie von Charakteren nicht. Ein recht häufiges Vorkommnis waren Charaktere, die über den Boden glitten, um einem Wagen auszuweichen, der sich in ihrem Rücken näherte, also außerhalb ihres Sichtfeldes.

Unser Lösungsansatz
Fast alle Probleme, die wir beobachteten, standen im Zusammenhang mit der Fortbewegungssimulation. Leider bot die verwendete Bibliothek nur sehr wenige Möglichkeiten zur Optimierung. Also entschieden wir uns, nach alternativen Bibliotheken zu suchen. Eine Bibliothek, die vielversprechend aussah, war ‚OpenSteer‘. Diese Bibliothek schien perfekt in die Simulation von Die Gilde 3 zu passen. Sie bietet zudem Werkzeuge zur visuellen Darstellung und eine Vorausberechnung, wo sich welcher Charakter zu welchem Zeitpunkt während einer Bewegung befindet. Und – nicht minder wichtig – man kann den Code der Bibliothek schnell überblicken und begreifen und muss nicht erst viel Zeit in Vorarbeiten investieren.

‚OpenSteer‘ funktioniert ein bisschen anders als die vorherige Bibliothek. In der Simulation führt jeder Charakter seine eigene Berechnung durch, auch wenn er jemand anderem ausweichen muss. Kein Charakter verschiebt einen anderen Charakter, denn die Simulation berechnet schon im Voraus, wie sich beide bewegen müssen, um nicht zu kollidieren – und sie bietet auch die Funktion, sich die Vorausberechnung des Pfades grafisch anzusehen. Wenn sich Charaktere nicht aus dem Weg gehen können, werden sie sich gegenseitig ignorieren und durch einander hindurch gehen, anstatt sich ineinander zu verhaken.

Die Integration von OpenSteer
Der Austausch der alten Bibliothek durch ‚OpenSteer‘ erwies sich als ein größeres Unterfangen als zuerst angenommen. ‚OpenSteer‘ erwartet, dass jedem sich bewegenden Charakter ein Pfad zugewiesen wird. Die alte Bibliothek erwartete jedoch nur eine Richtung und bevorzugte Geschwindigkeit. Allein dieser Unterschied zwang uns dazu, an vielen Stellen im Code Änderungen vorzunehmen.
‚OpenSteer‘ selbst funktionierte nicht sofort so, wie wir es uns erhofft hatten und erforderte zusätzliche Arbeit. Zunächst benutzten die Charaktere in der Simulation direkt das Berechnungssystem der vorgefertigten Demo von ‚OpenSteer‘ zur Bestimmung ihrer Positionen entlang des Pfades. Wir mussten dies mit dem Berechnungssystem in Die Gilde 3 kompatibel machen.
Das nächste Problem war die Tatsache, dass Charaktere nicht stark genug „steuerten“, wenn sie um eine Ecke gehen wollten. Dies wurde durch einen Unterschied in der Größe der Welt von Die Gilde 3 im Vergleich zur ‚OpenSteer‘-Demo verursacht. Im Vergleich zur Demo ist bei uns alles größer und einige Steuerungsparameter waren nicht für diese Größe ausgelegt. Zum Glück war das nicht schwer zu beheben, sobald wir die Ursache herausgefunden hatten.
Es dauerte eine Weile, bis wir alle Probleme identifiziert und behoben hatten. Die Bemerkenswertesten davon waren:
– Höhenunterschiede bei Pfaden wurden von der Simulation nicht berücksichtigt, was Schiffe auf den Flüssen dazu brachte, Fußgängern auf Brücken auszuweichen.
– Es wurden Pfade ermittelt, die unter die Geometrie führten und damit unerreichbar waren.
– Pfade auf Brücken „verbanden“ sich mit dem Schiffsweg auf der Wasseroberfläche und nicht an der Oberfläche der Brücke.
– Sehr hektische Richtungsänderungen beim Umgehen anderer Charaktere, welche zu unberechenbaren Bewegungen führten.
Bei all diesen Problemen erwies sich die Funktion zur grafischen Darstellung der Pfadberechnungen als unschätzbar: wir konnten die Pfad-Visualisierung von ‚OpenSteer‘ einfach aktivieren und uns direkt ansehen, was schief ging.

Hier ein Beispiel für die Pfad-Visualisierung

– Die lange rote Linie zeigt den generellen Pfad an, dem der Charakter folgen soll.
– Die orangefarbenen Linien zeigen die Breite des Pfades an. Charaktere werden versuchen, innerhalb dieser Begrenzungslinien zu bleiben.
– Die grünen und roten Kreise zeigen die vorhergesagte Position unseres Charakters bzw. eine Kollisionsgefahr an. Die Tatsache, dass sich die Kreise überlappen, zeigt, dass sich beide auf Kollisionskurs befinden.
– Der blaue Kreis zeigt die Richtung an, in die unser Charakter zielt, um die Kollision zu vermeiden.

Letzte Worte
Die Überarbeitung des Navigationssystems von Die Gilde 3 hat sich als große Aufgabe erwiesen. Aber wir denken, es hat sich gelohnt. Jetzt sind wir an einem Punkt, an dem es gut funktioniert und wir nicht mehr viele Änderungen vornehmen müssen. Und wenn doch, dann sollte dies problemlos möglich sein.
Viele der Änderungen am Navigationssystem waren bereits im Patch EA 0.5.3 enthalten. Einige zusätzliche Verbesserungen (besonders geschmeidige Bewegungen bei der Vermeidung von Kollisionen) werden mit dem kommenden Patch EA 0.5.5 geliefert. Uns ist bewusst, dass es immer noch das Problem gibt, dass Charaktere ‚im Verkehr‘ stecken bleiben und dann ihr Ziel bzw. ihre Tätigkeit vergessen. Das steht ganz oben auf unserer Prioritätenliste.

Ich hoffe, dass wir euch mit diesem Dev Diary einen interessanten Einblick in die Funktionsweise des Navigationssystems geben konnten. Trotz all der Arbeit bei der Implementierung von ‚OpenSteer‘ und den folgenden Herausforderungen bei den Anpassungen der neuen Bibliothek, hatte ich sehr viel Spaß dabei – besonders, als ich endlich die Ergebnisse präsentieren konnte 🙂

Christoph Erhardt
Gameplay Programmierung für Die Gilde 3
Purple Lamp Studios