Pfadfindung: Kachelbasiertes Navigationsnetz

8

Ich entwickle ein Echtzeit-RTS auf Kachelbasis. Dies ist eine Beispielkarte:

Karte

Diese Karte besteht aus 4 Regionen mit jeweils 256 Kacheln. Blaue Kacheln stehen für Hindernisse. Einheiten können sich in die üblichen acht Richtungen bewegen. Einheiten sind an Kacheln gebunden; Eine Kachel kann eine Einheit aufnehmen.

Dies sind einige Beispiele für die idealen Wege, die ich suche. Typisches A * Zeug:

Geben Sie hier die Bildbeschreibung ein

Meine Frage ist: Ist ein Navigationsnetz auf ein kachelbasiertes RTS anwendbar? Ich habe nur Navigationskarten gesehen, die in Spielen verwendet wurden, in denen sich Einheiten frei bewegen und nicht an ein Raster von Kacheln gebunden sind. Wie würde das Navigationsnetz auf dieser bestimmten Karte aussehen? Ein Beispielbild wäre ausgezeichnet.

path-finding rts navmesh mario_sunny
quelle
Für das, was es wert ist, erinnere ich mich an das Hören, dass ein Teil der "Seltsamkeit" von Starcraft I auf die späte Entscheidung zurückzuführen war, von 2D auf isometrisches 3D umzusteigen - der gesamte Pfadcode wurde in Erwartung von 2D-Gelände geschrieben!
Raven Dreamer

Antworten:

10

Ja, Navigationsnetze gelten weiterhin für kachelbasierte Spiele. Sie würden jedoch hauptsächlich als Optimierung verwendet. Zum Beispiel habe ich unten links in Ihrem Bild ein Navigationsnetz konvertiert:

Geben Sie hier die Bildbeschreibung ein

In diesem Fall wäre jedes grüne Quadrat ein Navigationsknoten. Wie Sie sehen, reduziert dies die Anzahl der Knoten, die A * verarbeiten muss, drastisch. Einheiten können dann einfach zur Mitte jedes dieser Knoten wechseln.

Die Erzeugung dieser Knoten ist ein anderes Problem. Die Entscheidung, wie die Knoten gebildet werden sollen, kann komplex sein. Auf der Website gibt es einige Fragen, auf denen Sie einige Ideen finden, wie Sie dies implementieren möchten:

Unterteilen eines Polygons in Felder unterschiedlicher Größe

Identifizieren von Quad-Mustern in einem zweidimensionalen Array

/programming/20220215/minimum-number-of-rectangles-in-shape-made-from-rectangles

Dieses Navigationsnetz kann im Wesentlichen auch als "First Pass" -Pfadfindung verwendet werden. Wenn ein Pfad durch das Navigationsnetz gefunden wird, wissen Sie, dass ein Pfad vorhanden ist. Dies ist ein schnellerer Test, um festzustellen, ob zwei Punkte verbunden sind.

MichaelHouse
quelle
1
Es fällt mir schwer zu verstehen, wie überlegen dies gegenüber reinem A * ist. Wie würde Ihr Navmesh beispielsweise die Pfadfindungsberechnung für den grünen Pfad in der ursprünglichen Antwort optimieren?
mario_sunny
4
Der grüne Pfad hat 15 Knoten, der Netzpfad hat 5. Dies beinhaltet nicht einmal die Anzahl der Sackgassen, die analysiert werden müssen, wenn dieser Pfad gefunden wird. Der Punkt des Navigationsnetzes besteht nicht unbedingt darin, die direktesten Routen zu erstellen, sondern die Anzahl der Knoten zu verringern, die A * durchsuchen muss, wodurch die Geschwindigkeit von A * drastisch erhöht wird. Es gibt Strategien zum Platzieren von Knoten in Ihrem Navigationsnetz, mit denen ein Gleichgewicht zwischen direkten Pfaden und weniger Knoten gefunden werden kann (z. B. Knoten an jeder Ecke aller Hindernisse). Es gibt auch Optimierungen, die für den fertigen Pfad durchgeführt werden können.
MichaelHouse
Ich fange an zu verstehen. Würde der grüne Pfad bei der Navmesh-Optimierung anders aussehen? Sie scheinen zu implizieren, dass sich die Einheit auf dem Weg zum Endpunkt in die Mitte jedes Rechtecks ​​bewegt. Schlagen Sie vor, dass die Post-A * -Optimierungen den Pfad verkürzen würden?
mario_sunny
3
Ja, wenn Sie die Mitte jedes Knotens verwenden, sieht der Pfad anders aus. Sie können sich jedoch dafür entscheiden, etwas anderes als die Mitte zu verwenden (wie Sie die Ecken jedes Knotens verwenden könnten). Oder Sie können festlegen, dass Ihre Knoten nicht größer als vier Quadrate sind (weniger Knoten, aber die Knoten folgen der Geometrie näher). Oder Sie können einige Optimierungen am Pfad vornehmen, um direkter zu sein, nachdem Sie ihn gefunden haben. Sie können das Navigationsnetz sogar als ersten Durchgang verwenden und dann mit A * durch jeden Knoten navigieren (so können Sie "Pfad während Sie gehen", während sich das Gerät bewegt, wodurch sich die Auswirkungen auf die Leistung über die Zeit verteilen).
MichaelHouse