Tutorial 13 – Wegfindung, Flocking

Routinen zur Wegfindung sind ein zentraler Bestandteil der KI-Programmierung und kommen dementsprechend in nahezu allen Spielen zum Einsatz. Nur selten führt die kürzeste Verbindung – eine gerade Linie – zum gewünschten Ziel; in der Realität verkomplizieren Hindernisse und Wegbegrenzungen die Routenplanung erheblich. Aus technischen Gründen ist es unmöglich, alle nur denkbaren Routen in die Planungen einzubeziehen. Stattdessen begnügt man sich mit den für den Spielverlauf relevanten Wegabschnitten und fasst diese zu einem „virtuellen Straßennetz“ – zu einem Wegpunkte-System – zusammen. Längere Wege werden hierbei in kürzere Abschnitte unterteilt, deren Anfangs- und Endpunkte man als Wegpunkte bezeichnet.

Tutorial 13 demonstriert den Einsatz eines solchen Wegpunkte-Systems. Im konkreten Fall werden zunächst 1000 Wegpunkte nach dem Zufallsprinzip im Raum positioniert. Ebenfalls nach dem Zufallsprinzip wird einer dieser Wegpunkte als ein mögliches Ziel ausgewählt, das die Spiele-Einheiten (die sogenannten Boids) ansteuern müssen. Haben die Einheiten das Ziel erreicht, dann wird ein neuer Zielpunkt ausgewählt. Der Wegpunkt, den die Einheiten auf dem Weg zum Ziel momentan ansteuern, wird blau dargestellt, der Ziel-Wegpunkt gelb.


Literatur:

Wegfindung – Einführung

Entwurf eines Wegpunkte-Systems

Routinen für die Wegfindung

Boids, Flocking



Hinweise zum Erstellen eines neuen Projekts:

  • Kopieren Sie den Ordner GraphicsAndPhysicsFrameworkImports ins Projektverzeichnis
  • Kopieren sie alle dll-Dateien sowie die Konfigurationsdatei ResolutionAndRendering.txt aus besagtem Ordner ins gleiche Verzeichnis, in dem sich auch die exe-Datei befindet (in unseren Programmbeispielen ist dies das Bin-Verzeichnis)
  • Binden Sie die folgenden Dateien in Ihr Projekt ein: GraphicsAndPhysics_Framework_Imports.h, GraphicsAndPhysics_Framework_Imports.lib, glew32.lib, glew32s.lib, glut32.lib. Die Glew- und Glut-Bibliotheken ermöglichen die Nutzung der aktuellen OpenGL-Spezifikationen unabhängig vom Framework.

GraphicsAndPhysicsFrameworkDemo13.zip