A*-Pfadfindung in Unity: Tutorial für Cs7632 mit Manhattan & Euklidisch

Einführung in die A*-Pfadfindung für Spiele-KI

In der Spieleentwicklung ist die Pfadplanung eine der zentralen Aufgaben der künstlichen Intelligenz. Ob ein Gegner in einem Actionspiel den Spieler verfolgt, eine Spielfigur in einem Strategiespiel Ressourcen sammelt oder ein NPC in einer offenen Welt navigiert – überall steckt Pfadfindung dahinter. Der A*-Algorithmus ist dabei der Goldstandard, weil er garantiert den kürzesten Weg findet (mit einer zulässigen Heuristik) und gleichzeitig effizient arbeitet.

In diesem Tutorial zeigen wir dir, wie du A* in Unity für die Hausaufgabe Cs7632 Homework 3 implementierst. Du lernst die wichtigsten Komponenten kennen: Kostenfunktionen, Heuristiken, die inkrementelle Suche und den Umgang mit der FindPathIncremental-Methode. Am Ende wirst du nicht nur die Aufgabe lösen, sondern auch verstehen, warum A* in so vielen Spielen – von Minecraft über StarCraft bis hin zu Fortnite – eingesetzt wird.

Voraussetzungen und Projektstruktur

Bevor wir loslegen, stelle sicher, dass du das Unity-Projekt aus früheren Aufgaben importiert hast. Die zentrale Klasse ist AStarPathSearchImpl, die du vervollständigen musst. Wichtig: Die anderen Algorithmen wie Greedy Best First Search und Dijkstra bauen auf deiner A*-Implementierung auf – also arbeite sorgfältig.

Folgende Funktionen sind bereits vorgegeben und sollten nicht geändert werden:

CostNull(Vector2 nodeA, Vector2 nodeB) – für Greedy Best First Search
HeuristicNull(Vector2 nodeA, Vector2 nodeB) – für Dijkstra

Deine Aufgabe ist es, die folgenden drei Funktionen zu implementieren:

Cost(Vector2 nodeA, Vector2 nodeB) – gibt die gewichtete Kantenkosten zurück (Euklidische Distanz)
HeuristicManhattan(Vector2 nodeA, Vector2 nodeB) – gibt die Manhattan-Distanz als Heuristik zurück
HeuristicEuclidean(Vector2 nodeA, Vector2 nodeB) – gibt die Euklidische Distanz als Heuristik zurück

Zusätzlich musst du die FindPathIncremental-Methode implementieren, die den eigentlichen A*-Suchprozess steuert.

Kostenfunktion und Heuristiken implementieren

Cost – Die Euklidische Distanz

Die Kostenfunktion misst die tatsächlichen Kosten, um von einem Knoten zum benachbarten Knoten zu gelangen. In einem Gitter oder Graphen ist die Euklidische Distanz die natürlichste Wahl:

public float Cost(Vector2 nodeA, Vector2 nodeB) {
    return Vector2.Distance(nodeA, nodeB);
}

Stelle sicher, dass der Rückgabewert nicht negativ ist – das ist durch die Distanzfunktion automatisch gegeben.

HeuristicManhattan – Die Manhattan-Distanz

Die Manhattan-Distanz eignet sich besonders für Gitter, in denen man sich nur horizontal und vertikal bewegen kann (z.B. in Städten oder Dungeons). Sie berechnet die Summe der absoluten Differenzen der Koordinaten:

public float HeuristicManhattan(Vector2 nodeA, Vector2 nodeB) {
    return Mathf.Abs(nodeA.x - nodeB.x) + Mathf.Abs(nodeA.y - nodeB.y);
}

Diese Heuristik ist zulässig, solange die Bewegung auf das Gitter beschränkt ist – sie überschätzt nie die tatsächlichen Kosten.

HeuristicEuclidean – Die Euklidische Distanz

Für offene Welten oder wenn diagonale Bewegungen erlaubt sind, ist die Euklidische Distanz die bessere Heuristik:

public float HeuristicEuclidean(Vector2 nodeA, Vector2 nodeB) {
    return Vector2.Distance(nodeA, nodeB);
}

Auch hier ist die Zulässigkeit gegeben, da die gerade Linie immer kürzer oder gleich dem tatsächlichen Weg ist.

Die FindPathIncremental-Methode – Herzstück von A*

Die FindPathIncremental-Methode wird wiederholt aufgerufen, um die Suche Schritt für Schritt durchzuführen. Das ist besonders nützlich für Echtzeitspiele, wo die Berechnung auf mehrere Frames verteilt werden muss. Die Methode erhält folgende Parameter:

getNodeCount – Anzahl der Knoten
getNode – liefert die Position eines Knotens
getAdjacencies – liefert die Nachbarn eines Knotens
G – Kostenfunktion (z.B. deine Cost)
H – Heuristikfunktion (z.B. HeuristicEuclidean)
doInitialization – ob die Suche neu gestartet werden soll
currentNodeIndex – aktueller Knoten (für Visualisierung)
searchNodeRecords – Dictionary mit Metadaten zu jedem Knoten
closedNodes – Menge der bereits besuchten Knoten
returnPath – Liste der Knotenindizes des gefundenen Pfads

Der Rückgabewert ist ein PathSearchResultType: Complete (Ziel gefunden), Partial (nur Teilpfad), InProgress (noch nicht fertig) oder InitializationError.

Initialisierung

Wenn doInitialization true ist, musst du die Suche neu starten. Setze currentNodeIndex auf den Startknoten (Index 0, oder wie in der Aufgabenstellung vorgegeben). Leere die searchNodeRecords, closedNodes und returnPath. Erstelle einen Eintrag für den Startknoten: CostSoFar = 0, EstimatedTotalCost = H(Start, Ziel), FromNodeIndex = -1. Füge den Startknoten zur openNodes-Prioritätswarteschlange hinzu.

Hauptschleife (ein Schritt pro Aufruf)

Bei jedem Aufruf (außer Initialisierung) führst du einen Schritt aus:

Wenn die openNodes leer sind, brich ab: return Partial (kein Weg gefunden).
Entnimm den Knoten mit der niedrigsten EstimatedTotalCost aus der Warteschlange. Das ist der currentNodeIndex.
Wenn dieser Knoten das Ziel ist, baue den Pfad über die FromNodeIndex-Kette und gebe Complete zurück.
Füge den Knoten zu closedNodes hinzu.
Für jeden Nachbarn (aus getAdjacencies(currentNodeIndex)):
- Wenn der Nachbar bereits in closedNodes ist, überspringe ihn.
- Berechne die neuen Kosten: tentativeCostSoFar = searchNodeRecords[currentNodeIndex].CostSoFar + G(currentNode, neighbor).
- Wenn der Nachbar nicht in openNodes ist oder die neuen Kosten niedriger sind, aktualisiere den Eintrag: CostSoFar = tentativeCostSoFar, EstimatedTotalCost = tentativeCostSoFar + H(neighbor, goal), FromNodeIndex = currentNodeIndex. Füge ihn zur Warteschlange hinzu (oder aktualisiere die Priorität).
Gebe InProgress zurück, damit die Suche im nächsten Frame fortgesetzt wird.

Pfadrückgabe bei Partial

Wenn die Suche beendet ist, ohne das Ziel zu erreichen, musst du den Knoten finden, der dem Ziel am nächsten ist. Durchsuche dazu alle Knoten in closedNodes und wähle den mit der geringsten EstimatedTotalCost (bzw. wenn Heuristik null ist, die manuelle Euklidische Distanz). Baue dann den Pfad von diesem Knoten zurück zum Start.

Häufige Fehler und Tipps

Heuristik nie überschätzen: A* findet nur dann den kürzesten Weg, wenn die Heuristik zulässig ist. Manhattan und Euklidisch sind zulässig, solange du keine diagonalen Bewegungen mit Manhattan schätzt.
Prioritätswarteschlange richtig nutzen: Die SimplePriorityQueue aus dem Projekt erwartet, dass du die Priorität bei Bedarf aktualisierst. Verwende UpdatePriority oder entferne und füge neu hinzu.
Inkrementelle Suche testen: Rufe die Methode mehrmals mit doInitialization = false auf. Überprüfe, ob der Zustand korrekt erhalten bleibt.
Closest-Node-Logik bei Partial: Vergiss nicht, bei Partial den dem Ziel am nächsten gelegenen Knoten zu wählen – das ist eine häufige Fehlerquelle.

Beispiel aus der Praxis: Wie Spiele A* nutzen

Stell dir vor, du spielst das aktuelle Spiel Hades II (Early Access 2026). Die Gegner in den Dungeons müssen dich durch enge Gänge verfolgen – genau dafür ist A* perfekt. Oder denk an League of Legends: Wenn dein Champion einen Befehl bekommt, berechnet das Spiel in Millisekunden den Pfad um Hindernisse herum. Auch in der Logistik von Lieferdiensten wie Lieferando oder Uber Eats steckt A* – nur dass dort die Heuristik oft die Straßenentfernung ist.

Ein aktuelles Beispiel: Im Mai 2026 ist das Spiel Elder Scrolls VI noch immer in Entwicklung, aber die Pfadfindung für NPCs wird sicherlich auf A* basieren. Wenn du also heute A* lernst, investierst du in Fähigkeiten, die in der Spieleindustrie heiß begehrt sind.

Fazit

Mit diesem Tutorial hast du alle Werkzeuge, um die Cs7632 Hausaufgabe 3 zu meistern. Implementiere zuerst die Kosten- und Heuristikfunktionen, dann die inkrementelle Suche. Teste mit verschiedenen Heuristiken – du wirst sehen, wie Manhattan und Euklidisch das Suchverhalten beeinflussen. Vergiss nicht, den Sonderfall der Null-Heuristik (Dijkstra) zu behandeln.

Wenn du einmal nicht weiterkommst: Die Unity-Community und Foren wie Stack Overflow helfen schnell. Viel Erfolg bei deiner Implementierung!