Wie kann ich ein Navigationsnetz für ein Kachelraster generieren?

18

Ich habe noch nicht angefangen, für dieses Programm zu programmieren, aber ich wollte sehen, wie ich das trotzdem machen würde.

Angenommen, ich habe ein Raster von Kacheln, alle von gleicher Größe, einige sind überfahrbar, andere nicht. Wie würde ich vorgehen, um ein Navigationsnetz aus Polygonen aus diesem Raster zu erstellen?

Meine Idee war es, die nicht überquerbaren Kacheln herauszunehmen und die Linien von diesen Kanten zu verlängern, um Polygone zu bilden ... das ist alles, was ich bisher habe. Irgendein Rat?

2d mathematics algorithm navmesh Ross Hays
quelle
2
Technisch entspricht das Raster einem Navigationsnetz. Ich vermute, Sie fragen tatsächlich nach einer Möglichkeit, das Raster zu optimieren und benachbarte Quadrate zusammenzuführen.
Kylotan
@Kylotan Ja, genau das habe ich gemeint, nur um benachbarte Polygone zu kombinieren.
Ross Hays

Antworten:

28

Hier ist eine der Methoden, die ich mir ausgedacht habe, als ich Navmesh für ein RTS-Spiel gemacht habe. Beachten Sie, dass es sich um Homebrew handelt und keine Tools von Drittanbietern verwendet wurden. Die Implementierung und Fehlerbehebung dauerte ca. 3 Wochen.

  1. Verwenden Sie den Marching Squares- Algorithmus, um Hindernisplättchen in Umrisse umzuwandeln . Beachten Sie, dass die Kartenränder ebenfalls eine Kontur sind und ebenfalls einbezogen werden müssen.
  2. Reduzieren Sie die Anzahl der Punkte in Konturen mithilfe des Douglas-Peucker- Algorithmus (violette Linien im unteren Bild)
  3. Führe alle Punkte in die Delaunay- Triangulation ein (um die gleichmäßigsten Dreiecke zu erhalten)
  4. Fügen Sie zusätzliche Punkte in leeren Bereichen und entlang der Kartenränder hinzu (um ein gleichmäßigeres Navmesh zu erhalten)
  5. Überprüfen Sie die Umrisse von Hindernissen und drehen Sie die von Delaunay erstellten Polygone um, um sie an die Umrisse anzupassen. - Oft kann Delaunay Dreiecke (grau) platzieren, die nicht mit Ihren Konturen (rot) übereinstimmen. Dann müssen Sie sie erkennen und spiegeln. Fügen Sie sie wieder zu einem Polygon zusammen, teilen Sie es entlang der Konturen und triangulieren Sie es manuell Bildbeschreibung hier eingeben
  6. Clip Hindernisse Innereien - entfernen Sie Polygone, die innerhalb von Hindernissen sind (rosa auf dem Bild oben)
  7. Füllen Sie nach Bedarf Verbindungsdaten zwischen verbleibenden Dreiecken und Scheitelpunkten aus - das ist Ihr Navigationssystem.

Ergebnis:

tilemap navmesh

Kromster sagt Unterstützung Monica
quelle
1

Netze werden normalerweise als Diagramme implementiert. Wenn Sie die Pfadsuche in einer Karte basierend auf einem Raster implementieren möchten, gehen Sie wie folgt vor:

Erstellen Sie ein Diagramm, in dem jedes durchfahrbare Quadrat als Scheitelpunkt dargestellt wird. Jedes Paar benachbarter überfahrbarer Quadrate, die als Eckpunkte dargestellt werden, hat eine Kante zwischen sich. Und du bist fertig.

wolfdawn
quelle
1
Auf diese Weise werden Navmeshes normalerweise nicht implementiert. Der Zweck eines Navmeshs (und, wie ich mir vorstellen kann, der Grund, warum der Fragesteller diese Frage gestellt hat) besteht darin, das Diagramm auf eine minimale erforderliche Anzahl von Polygonen (normalerweise Dreiecke) zu optimieren, die sich über die nützlichsten Bereiche erstrecken, um beide zu reduzieren Schritte, die erforderlich sind, um einen guten Pfad zu finden, und der zum Definieren des Netzes erforderliche Speicherbedarf. Eine rohe Implementierung würde sowohl eine Tonne mehr Speicher aufbrauchen als auch wertvolle AI-Verarbeitungszeit verschwenden.
Gurgadurgen
Du hast Recht. Natürlich ist die Dezimierung (Polygonreduktion) eine sinnvolle und erwünschte Optimierung. Es ist nur so, dass Sie, wenn Sie die Frage der Operation lesen , das Gefühl bekommen, dass er nur ein Raster in ein Diagramm verwandeln möchte.
Wolfdawn