Funktion und Nutzung des A* Algorithmus

Für mein Projekt, ein Echtszeitstrategiespiel (RTS) zu entwickeln, habe ich mich konsequenterweise mit der Wegfindung einer KI beschäftigt.

In diesem Beitrag möchte ich die Funktion des A* Algorithmus erklären und demonstrieren, wie dies mit Unity realisiert werden kann. Genutzt wird hierbei das bereits bestehende A*-Project von Aron Granberg.

Beginnen wir mit dem Konzept der Wegfindung. Als Gottgleiches Individuum können wir einem Pixelhaufen das Kommando geben, sich von Punkt A nach B im Raum zu bewegen. Diese Punkte sind in Unity als Vector3 (x,y,z) verfügbar.
Ein einfaches Bewegungsskript würde die beiden Punkte entgegennehmen und die Einheit auf direktem Wege (Stichwort: Abstand zweier Vektoren) mit einer Geschwindigkeit moveSpeed bewegen. Beispiel:

private void MakeMove(Vector3 dir)
    {
        transform.LookAt(dir);
        transform.position = Vector3.MoveTowards(transform.position, dir, Time.deltaTime * moveSpeed);
        if (transform.position == destination) move = false;
}
if(move) MakeMove(B)

Dies mag für einen Prototypen oder das Pendant eines Hallo Welt Programmes in der Spieleentwicklung durchgehen. Doch was passiert, wenn die Einheit (im Falle ohne Collider) auf ein Hindernis, z.B eine Mauer stößt? Sie läuft durch. Für das Bewegungsskript gibt es keine Hindernisse.

Hierbei kommt die Wegfindung in’s Spiel (wortwörtlich). Salopp gesagt ist folgendes die Aufgabe der Wegfindungsskripte: Finde den Schnellstmöglichen weg von A nach B, ohne gegen eine Wand zu laufen.

Und das geht am besten mit effizienten Algorithmen wie dem A*.

Definition: Der A* Algorithmus ist ein heuristischer Suchagorithmus zur Berechnung des  kürzesten Pfades zweier Punkte auf einem Graphen.

A* Iterationsdarstellung
A* Iterationsdarstellung

Kurze Erklärung zum GIF: Es sind 2 Punkte gegeben, A (rot) und B (grün). Diese liegen auf einem Raster mit gleichgroßern Felder = Knoten.
Würde man sich frontal (o/l/u/r) bewegen, ergibt es die Kosten 10 für die Bewegung. Diagonale Bewegungen haben einen Wert von 14. Somit sind Gerade Bewegungen zu bevorzugen. Die Sogenannten G-Kosten bezeichnen die Distanz des Knotens vom Startpunkt.
Dazu kommen zwei weitere Werte: H-Kosten; wie weit ist der Punkt vom Zielpunkt entfernt ist; und die F Kosten; die Summe beider Werte.

Während jeder Iteration werden um alle Knoten die angrenzenden Knoten markiert und die G/H/F Kosten berechnet. Dann wird der geringste F Wert gesichtet, iteriert, dann der zweithöchste, etc, solange, bis ein Pfad zum Ziel gefunden wurde; der Pfad mit den geringsten F Kosten.
Kleine Grafik:

Beispielgraph A*
Beispielgraph A*

Der blaue Weg ist konsequenterweise der Schnellste.

Dieser Algorithmus ist eine nette Alternative zum nativen Unity Nav-Mesh System, weshalb ich es auch für meine Projekte nutzen werde.