Ein Stern Wegfindung und diskrete / glatte Positionen

Der A * -Algorithmus (A-Stern) repräsentiert normalerweise einen Pfad in einem Gitter.

Sobald ein Pfad gefunden wurde, sieht der Pfad jedoch blockartig aus und ist nicht geeignet, wenn Sie Ihre Einheiten mit Gleitkomma-Datentypen verschieben.

Hier ist ein Bild, das das Problem beschreibt. Die weißen Kacheln repräsentieren den von A * gefundenen Pfad. Der Pfad der schwarzen Linie ist der Pfad, den ich möchte, der Pfad der roten Linie ist der Pfad, den ich nicht möchte.

Eine Lösung wäre, eine Ecke auszuwählen, wenn sich der Pfad dreht, und die Seite zu wechseln, wenn sich der Pfad in die andere Richtung dreht. Scheint der logischste und sauberste Weg zu sein, dies zu tun.

Als andere Option können Sie den Pfad in gerade Teile aufteilen. Dann müssen Sie nur noch die Punkte finden, an denen Ihr ursprünglicher Pfad einen Pfadteil verlässt (keine Berechnung erforderlich, wechseln Sie einfach in Richtung des nächsten Teils). Es bleiben nur noch Verbindungspunkte Ihres neuen glatten Weges!

BEARBEITEN: Wenn Sie auf dem Pfad bestehen, den Sie gezeichnet haben, vergleichen Sie einfach die beiden extremen Möglichkeiten, wie der Pfad einen geraden Teil verlassen kann (= Punkt am einen oder anderen Ende der Kante), und wählen Sie, was auch immer ein kürzeres Liniensegment erzeugt (Satz von Pythagoras) ).

Was die Heldenbreite betrifft, wenn Sie genau hinschauen - wo ist der Pfad am nächsten an der Kante? In der Verbindung der letzten "Kachel" und der vorher. Überprüfen Sie den Pfadabstand zur Kante in diesem Punkt (Sie müssen jetzt rechnen, der Wechsel reicht nicht aus). Wenn er kleiner als die Heldenbreite / 2 ist, fügen Sie dem Pfad einen neuen Punkt bei der Heldenbreite / 2 Abstand von der Kante hinzu.

Entschuldigung für Bildinkonsistenz, bereits gelöschte Quelle des Originalbildes.

Eine Möglichkeit zur Pfadglättung besteht darin, Strahlen von der aktuellen Position zum am weitesten sichtbaren Knoten zu werfen und dorthin zu gelangen. Sie können dies entweder in Echtzeit tun oder einfach einen neuen Pfad aus dem bereits vorhandenen erstellen, damit der Navigationsalgorithmus unverändert bleibt.

Wirf ausgehend von der aktuellen Position Strahlen auf jeden Knoten im Pfad. Wenn es einen Knoten gibt, der vom Strahl nicht erreicht werden kann, muss der vorherige Knoten berücksichtigt werden. Wiederholen Sie den Vorgang unter Berücksichtigung des letzten Knotens bis zum letzten Knoten.

Am Ende erhalten Sie ein ähnliches Ergebnis wie im Bild unten (grüner Pfad), abhängig von der Breite des Strahls und den zusätzlichen Parametern, die Ihr Spiel benötigt.

Es gibt auch die Präsentation dieses Ventils über die in L4D verwendete KI. Es lohnt sich, einen Blick darauf zu werfen und Ideen daraus zu gewinnen.

Der A * -Algorithmus arbeitet mit Pfaden in einem Diagramm . Das Diagramm muss kein Raster sein .

Wenn Sie sich die gewünschten Pfade ansehen, gehen sie durch die Ecken der quadratischen Kacheln. Insbesondere gehen sie durch die Ecken, in denen drei Fliesen begehbar sind und eine Fliese eine Wand ist. Anstatt A * ein Diagramm mit den Kachelmitten zu geben, können Sie ein Diagramm nur mit diesen "äußeren" Ecken erstellen, mit Diagrammkanten von Ecke zu Ecke (wenn Sichtlinie vorhanden ist). Möglicherweise möchten Sie die Ecken einige Pixel von den Ecken entfernen, um das Problem der „Heldengröße“ zu lösen.

Wenn Sie dieses Diagramm von Ecke zu Ecke anstelle des Rasterdiagramms erstellen, ist A * sogar schneller als Nachbearbeitungspfade oder unter Verwendung eines beliebigen Winkelalgorithmus (Theta *). Das Erstellen des Diagramms dauert jedoch einige Zeit (hauptsächlich, um die Sichtlinie zu verarbeiten). Daher ist es möglicherweise keine gute Wahl, wenn der Spieler die Karte während des Spiels ändern kann.