A*-Algorithmus - Pathfinding - AI

Guten Abend,

Update! - 18.05.2017 -
Knapp 3 Jahre nach dem Release kommt endlich die Veranschaulichung sowie den Fix der UDF.
Die UDF unterstützt mittlerweile vernünftiges Error-Handling und kommt mit einer Funktionsdokumentation daher.

Ich möchte hier ein Skript vorstellen welches mittels A*-Algorithmus (A-Star) den kürzesten Weg vom Start- bis zum Endpunkt findet.
Anleitungen zum A*-Algorithmus gibt es viele im Internet, einfach mal nachschauen.

Die .mesh-Datei von der ihr die Koordinaten und Wegpunkte bezieht muss wie folgt aufgebaut sein.

x;y;verbindung_zum_wp;verbindung_zum_wp;...
a;b;verbindung_zum_wp;verbindung_zum_wp;...
m;n;verbindung_zum_wp;verbindung_zum_wp;...

Es sieht vielleicht unverständlich aus aber hier ist eine Beispieldatei (Die Verbindung zu einem Wegpunkt wird mittels Zeile dargestellt).

2;3;2;3
4;5;1;3
9;9;1;2

Ich habe einen Visualizer gebaut der den Graphen anzeigt und einen gewünschten Pfad berechnet.
Das Netz ist allerdings gestreckt, damit es in das schwarze Quadrat in der GUI passt.

Wichtig! Die UDF arbeitet mit gerichteten Graphen!
Wenn ihr überprüfen wollt, ob euer Netz ein gerichteter Graph ist, nutzt die Mesh Checker.au3!

Wichtig! Die UDF arbeitet intern mit Indizes also sind im Netz eingetragene Wegpunkte immer um eins subtrahiert. Wenn ihr den Pfad von 1 zu 5 berechnen wollt, dann müsst ihr die Wegpunkte 0 und 4 nehmen. Der Grund warum ich in den Dateien es bei 1 anfangen lasse und im Script mit 0 arbeite ist der, dass man im Editor wenn man das Netz eintippt immer bei Zeile 1 anfängt und es einfach nur ekelhaft ist, wenn man beim Tippen immer eins abziehen oder draufaddieren muss!

Viel Spaß damit! Kritik und Lob sind gerne gesehen!

Bisherige Downloads (alte Versionen): 462

UDF wurde geupdatet. Siehe Post 1.

@Lesato hat mir vor ein paar Tagen eine E-Mail geschickt indem er mich auf die NavMesh-UDF angesprochen hatte.

Da die UDF ein paar Probleme hatte und ich noch keine vernünftige Visualisierungsfunktion gebaut habe, dachte ich mir, dass ich das ganze mal nachliefere.
Also findet ihr jetzt im Startpost die neue UDF mit einer Beispiel-Zip mit der man sich das ganze mal angucken kann.

Der Visualizer zeigt nur den berechneten Pfad, da ich die UDF komplett auseinander nehmen müsste um die Pfadberechnung zu zeigen.

Dieses Typenhandling wird mich noch eines Tages ins Grab bringen!
Dreistellige negative Koordinaten erkennt er hervorragend aber bei vierstelligen stellt er sich plötzlich quer.

Naja. Ich hab die UDF nochmal aktualisiert und sie ist nun kompatibel mit negativen Koordinaten.
Die Darstellung sollte jetzt gut funktionieren und ich hoffe, dass jetzt keinerlei Bugs mehr auftreten.

Kleiner Fix noch hinterher:

- _NavMesh_GetPathDistance wurde hinzugefügt: Diese Funktion gibt die komplett zurückgelegte Distanz auf einem Pfad zurück.
- Mesh Checker.au3 hinzugefügt: Dieses Script überprüft, ob es sich um einen ungerichteten Graphen handelt.

Zitat von Alina

Wie kann ich eigene Strecken eingeben?

Momentan habe ich dafür noch kein Script gebastelt aber ich werds vielleicht demnächst (hust hust, in 3 Jahren) tun.
Im Moment zumindest muss man das Netz im Editor angeben mit dem oben beschriebenen Format.