Ein Stern Wegfindung und diskrete / glatte Positionen

8

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.

Hier ist das Bild

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.

Jokoon
quelle
Die übliche Lösung ist die Pfadglättung. Oft ist es jedoch eine bessere (einfachere / schnellere) Lösung, einen Pfadfindungsalgorithmus mit beliebigen Winkeln zu verwenden. Sehen Sie hier für weitere Details.
BlueRaja - Danny Pflughoeft

Antworten:

4

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!

Geben Sie hier die Bildbeschreibung ein

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.

Geben Sie hier die Bildbeschreibung ein

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

wondra
quelle
Sehr schön. Haben Sie zufällig eine einfache Möglichkeit, mit der Größe des Helden umzugehen? Ich frage mich, ob wenn man bedenkt, dass die Korridore Breite = Breite haben - der Radius des Helden (unter Beibehaltung der gleichen Koordinaten der Korridormitte) nicht ausreichen würde.
GameAlchemist
@GameAlchemist: Ja, das ist die übliche Art, damit umzugehen.
Ilmari Karonen
Danke für dein Update. Da es sich um Korridorbreite = Korridorbreite - Heldenbreite handelt, sollten Sie auf jeder Seite nur berücksichtigen (Heldenbreite / 2) oder noch besser Radius = sqrt (sq (Breite / 2) + sq (Höhe / 2)). falls der Held sich frei drehen kann. (In Ihrem Schema sind die Korridore zu eng) (Rq: Ich gehe davon aus, dass wir hier das Zentrum des Helden betrachten - der einzige Weg, um Albträume zu vermeiden -)
GameAlchemist
@GameAlchemist guter Punkt, es sollte Breite / 2 sein. Der Radius ist allerdings etwas übertrieben (nehmen Sie einfach eine der beiden Dimensionen höher).
Wondra
In der Tat über Radius, eine Präzision: Wenn man achsenausgerichtete Bounding Box-Kollisionstests verwendet, sollte der 'Radius' maximal sein (Breite / 2, Höhe / 2). Für einen, der Kollisionstests mit Begrenzungskreisen verwendet, ist die Formel die obige (einmal für jede Objekterstellung berechnet).
GameAlchemist
3

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.

Geben Sie hier die Bildbeschreibung ein


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.

Reefaktor
quelle
Ihr grüner Pfad scheint falsch zu sein ... Sie werfen einen Strahl von der Einheitsposition und nicht von der Kachelposition, oder?
Jokoon
@jokoon Es hängt davon ab, wie Sie es anwenden. Der erste Strahl wird von der Position der Einheit und dann vom am weitesten sichtbaren Knoten geworfen, es sei denn, Sie wenden ihn an, wenn die Einheit navigiert (aber andererseits wird er von der Position des am weitesten sichtbaren Knotens aus aufgenommen). Der Pfad ist nur ein Beispiel und hängt, wie gesagt, von der Breite Ihres Strahls ab. Ich habe beim Zeichnen nur die Ecken vermieden.
Reefaktor
1

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.

amitp
quelle