Was wäre ein ordentliches Game ohne glaubhafte und stabile KI? Einer der wichtigsten Bestandteile der Game KI ist das Pathfinding, denn nicht nur die Gegner, auch die verbündeten oder neutralen NPCs benutzen die Wegfindung um sich durch die Spielwelt zu bewegen. Aber was ist die Schwierigkeit daran einen NPC durch das Level laufen zu lassen? Wer erinnert sich nicht an die guten alten Super Nintendo Zeiten wo die Bewohner Hyrules immer wieder die selben Grids abgelaufen sind?

Pathfinding

Mit der Zeit sind die Spiele größer und realistischer geworden, auch aus den Levelabschnitten sind immer größere weiter begehbare Spielewelten geworden. Je nach Genre gibt es mehr Barrieren und Einschränkungen (typische Shooter und Adventure Schlauchlevel) oder weniger bis gar keine (riesige, frei erkund- und begehbare Welten in RPGs).
Umso wichtiger ist es auch geworden dass sich NPCs realistisch durch die riesigen Welten bewegen. Mit vorkompilierten Pfaden erhält man alles andere als eine realistische KI.

Aber gerade die riesigen Welten machen das Pathfindig so komplex. Die Algorithmen die im Pathfinding eingesetzt werden stammen aus der Mathematik und können mit den 3D Modellen der Levels nichts anfangen. Die Spielwelt muss durch einen Graphen repräsentiert werden. Aber das ist nicht der einzige Stolperstein. Die Algorithmen wie der A* selbst sind sehr solide, aber eine ungenaue Repräsentation der Spielwelt kann Orte für NPCs unerreichbar machen oder zu seltsamen verhalten führen. NEhmen wir doch zum Beispiel die Companions in Skyrim, die, anstatt über einen Stein zu springen gleich den ganzen Berg überrunden.

Wie so ein Spielwelt im Pathfinding dargestellt wird und wie die Pathfinding-Algorithmen funktionieren kann man in meiner Bachelor-Arbeit: Pathfinding-Algorithmen in verschiedenen Spielegenres nachlesen.