A*-Plugin für Unity

  • Unity Editor Interface mit geöffneten Plugin Window
  • Unity Editor Interface mit geöffneten Plugin Window
zur Demonstration (not optimized for mobile devices)


Es wurde ein Plugin entwickelt, das die einfache Integration des A*-Algorithmuses in ein Unity Projekt ermöglicht. Hierbei kann durch eine grafische Benutzeroberfläche, in Form eine Fensters im Editor-Mode, ein 3-dimensionales Grid mit Quadraten und Knoten erstellt werden. Dieses Grid dient nur als visuelle Repräsentation der Mapstruktur, wodurch ein verständliches und nutzerfreundliches Erstellen der Kartendaten ermöglicht wird. Anschließend können diese Quadrate und Knoten auf Begehbarkeit, Gewichtung und Position angepasst werden. Hieraus wird eine Datenstruktur erzeugt, die dem Pfadfindungsalgorithmus später als Map-Datei dient. Die visuelle Repräsentation der Quadrate und Knoten kann dann gelöscht werden. Implementiert wurden die Manhattan-Heuristik und zwei Varianten der Chebyshev-Heuristik mit unterschiedlichen Kosten in der diagonalen Bewegung. Die Verwaltung der OpenList erfolgt als einfache Liste und nicht als Heap.

Die Zeitkomplexität beträgt bei einer zulässigen Heuristik, welche die realen Kosten nicht stark unterschätzt i.d.R.:
Best-Case: O(1)
Average-Case: O(n*log2(n))
Worst-Case: O(n²)

Durch Nutzung eines Min-Heaps bzw. Priority-Heap könnte der Aufwand beim durchsuchen der Openlist dennoch weiter reduziert werden, da wir mit einer einfachen Liste jedesmal alle Elemente durchsuchen müssen um das kostengünstigste zu ermitteln. Die Auswahl des kostengünstigsten Knoten ist hierbei am effizientesten, wenn die OpenList als Min-Heap bzw. Priority-Heap implementiert wird. Der Aufwand für das Einfügen eines neuen Elements beträgt:
O(log2(n))
Da das kostengünstigste Element immer an der Spitze steht, beträgt der Aufwand für den Zugriff auf dieses Element:
O(1)
Der Gesamtaufwand beim erstmaligen sortieren bzw. aufbauen eines Heaps mit n Elementen beträgt im Worst-Case:
O(n * log2(n))

  • Datum: Juni 2013