Wegfindung mit Navigation Meshes

Luki hat mir vor kurzem einen interessanten Link über Navigation Meshes geschickt: http://www.ai-blog.net/archives/000152.html

Der Unterschied zu den meisten herkömmlichen Verfahren ist, dass keine einzelnen Wegpunkte gespeichert werden, über die der kürzeste Weg berechnet wird, sondern Polygone, die angeben, welche Flächen begehbar sind. Dadurch kriegt man im Allgemeinen glaubwürdigere Ergebnisse.

Da ich momentan selbst wieder an einem Spiel arbeite, das auf zuverlässige Wegfindung angewiesen ist, werde ich das wohl in Betracht ziehen. Leider scheint es aber noch keine wirklich gute Referenzimplementierung zu geben. Was im Artikel verlinkt ist, kostet alles und ansonsten habe ich bis jetzt nur den Quelltext von Bitfighter gefunden, der das alles sehr stark vereinfacht und dadurch ziemlich sicher keine optimalen Ergebnisse bekommt.

Wirklich nette Idee.

Weißt du, ob die Suchheuristic (etwa bei A*) schon die optimale Bewegung über die Flächen beachtet oder ob das noch mit einem vereinfachten Modell (wieder ein Graph, jeweils mit Mittelpunkt der Fläche) passiert und die fertige Strecke dann in einem 2. Schritt optimiert wird?

Sollte letztes der Fall sein hab ich schon eine Idee, wie man das halbwegs anständig optimieren kann, glaube ich.

Du musst bei Polygonen, wo der Charakter um die Ecke geht (d.h. nicht über gegenüberliegenden Kanten durchwandert) den finalen Bewegungspunkt in die Ecke legen, an den die beiden Kanten, die durchwandert werden, anliegen. Dazwischen musst du dann so gut wie möglich die Linie zwischen beiden Punkten approximieren.

Für viele Fälle würde das Verfahren schon gute Resultate liefern, denke ich. Gibt aber auch fälle wo es daneben geht. Etwa wenn der Charakter zickzack über Polygone läuft. In dem Fall wäre die optimale Route oft eine gerade Linie, aber mit dem Algorithmus würden die Wegpunkte in den ecken liegen was dann im Endeffekt wieder in eine Zickzack Bewegung resultiert...

Aber eventuell kann man das auch optimieren - muss man mal drüber nachdenken.

C ya

Lachsen

Edit: Ich bin jetzt davon ausgegangen, dass jedes Polygon ein Viereck ist. Wenn beliebige Polygone unterstützt werden klappt dieses Verfahren entsprechend nicht so toll...

Edit#2: Okay, selbst bei Vierecken geht das nicht immer gut. Da muss man mehr drüber nachdenken

Edit#3:
Ich hab etwas mehr drüber nachgedacht. Ich denke man sollte nicht zu sehr überlegen, wie man die Route global optimieren kann sondern so wie es glaubwürdig ist: soweit wie man die Route sieht (und vielleicht ein Schritt darüber hinaus)

D.h. die Route ist bekannt über die einzelnen Polygone, wobei die Routenpunkte eher auf den Kanten der Polygone liegen sollten, nicht in den Mittelpunkten. Dann geht man die Kante für Kante und testet, ob sich diese Kante noch im Sichtbaren Bereich befindet (was recht einfach ist. Für jede Kante muss man den Sichtkegel auf diese Kante mit dem aktuellen Sichtkegel schneiden. Das tut man so lange bis der Sichtkegel ganz weg ist. Die Kante für die das der Fall ist wird dann angesteuert - der Mittelpunkt dieser Kante ist dann der temporäre Zielpunkt. Die Einheit bewegt sich dann über alle Polygons Kanten so, dass sie möglichst nah auf der direkten Linie zum Zielpunkt liegt.

Diese Berechnung kann man wiederholen, wann immer die Einheit eine neue Kante erreicht.
So sollte sich eine schön Effektive Route ergeben, denke ich. Kann sein, das die in einigen Fällen nicht ganz optimal ist - aber ich glaube das würde noch glaubwürdig rüber kommen, weil die Einheit soweit vorausberechnet wie es sichtbar ist.

Aus gegebenem Anlass (Vorlesung Algorithmen 2 in der Uni und allgemein mal wieder Interesse an dem Thema) eine kleine Linksammlung:

http://wiki.delphigl.com/index.php/Navigation_Meshes
http://royalexander.wordpress.com/tag/pathfinding/

(more to come, ich habe grade entschieden, schlafen zu gehen)