Wegfindung, Wegpunkte und Influence Mapping

In modernen Spielen gehört die Echtzeit-Wegfindung zu den wichtigsten KI-Komponenten überhaupt. Grundlage dieser Berechnungen ist in vielen Anwendungen ein sogenanntes Wegpunktesystem, welches bereits im Vorfeld – beispielsweise direkt im Level Editor – generiert wird (Preprocessing). Längere Wege lassen sich auf diese Weise in kürzere Abschnitte unterteilen, deren Anfangs- bzw. Endpunkte man als Wegpunkte bezeichnet. Entlang dieser Abschnitte finden sich im Idealfall keinerlei Hindernisse, welche die Bewegung der KI-Einheiten stören könnten.
Im Spielverlauf werden einzelne Wegabschnitte hin und wieder zeitweise oder dauerhaft unpassierbar – beispielsweise wenn eine Brücke oder Straße zerstört wird. Auch kommt es vor, dass bestimmte Wege erst zu einem späteren Zeitpunkt passierbar werden (beispielsweise nachdem eine Brücke oder Straße gebaut wurde). Ein Wegpunktesystem muss daher dynamisch modifizierbar sein. Als Entwickler muss man demzufolge die Möglichkeit vorsehen, dass sich Wegpunkte zur Laufzeit sowohl aktivieren wie auch deaktivieren lassen.

In einem Spiel geht es in der Regel nicht darum, immer den kürzesten Weg zu ermitteln, denn hierdurch würde die KI letztlich vorhersagbar werden. Das eigentliche Ziel muss es sein, sinnvolle Wege zu finden, die dem aktuellen Spielverlauf Rechnung tragen:

  • Ausweichrouten, wenn der Spieler gegnerische Nachschubwege blockiert
  • Zangentaktik – Angriff des Spielers aus unterschiedlichen Richtungen (unterschiedliche Wege)
  • Aufklärung – effektive Erkundung ein großes Gebiets
  • sichere Wege – geringe Gefahr eines gegnerischen Angriffs



Die nachfolgend verlinkten Artikel und Vorträge dienen sowohl der Einführung wie auch der Vertiefung und konzentrieren sich auf jeweils unterschiedliche Aspekte der Thematik.




Deutschsprachige Links:

Das Media-Wiki der Fachhochschule Trier bietet eine solide Einführung in die Themen Wegfindung, Pfadplanung und strategische Navigation:


Weitaus detaillierter als das Media-Wiki der Fachhochschule Trier ist die nachfolgende schriftliche Ausarbeitung eines Vortrags zum Thema 3D Pathfinding für das Seminar Computer Graphics / Aspects of Game Design aus dem Jahr 2006 (vorgetragen von Daniel Kastenholz an der TU München):



Englischsprachige Links:

Der im Jahr 2011 veröffentlichte Artikel von Alex J. Champandard behandelt die grundlegenden Konzepte des Influence-Mappings – eine Methode für die taktische Analyse der Spielewelt:



Der 7-seitige Gamasutra-Artikel von Marco Pinter aus dem Jahr 2001 befasst sich schwerpunktmäßig mit der Simulation von glaubhaften Bewegungsabläufen einzelner Spieleobjekte im Rahmen der Wegfindung:



Die 46-seitige Arbeit (Final Year Project) von Matt Hall mit dem Titel Pathfinding in an Entity Cluttered 3D Virtual Environment (2004/2005) behandelt das Thema Wegfindung praxisbezogen – am Beispiel einer konkreten 3D-Anwendung: