C++ Forum :: Pathfinding: Grid to Waypoints

Tachyon76 Mitglied 12:30:04 13.03.2018 Titel:

Hallo zusammen,

ich versuche gerade mich gerade wieder an einem Lernprojekt: Pathfinding.
Dafür habe ich ein Grid-basierte Map (2D-Array)
z.b.: Tiles[x,y]

Bei einer großen Map kommen dann aber viele "Nodes" fürs Pathfinding zusammen, weshalb ich mich über ein Optimierungs-Algorithmus schlau machen wollte. Habe sowas gefunden:
https://www.redblobgames.com/pathfinding/grids/algorithms.html
aber ich finde keine Beschreibung, _wie_ man ein Grid in Waypoints convertiert.
Hat jemand paar Infos oder Schlagwörter, nach denen ich weiter suchen kann?

Danke und Grüße

XMAMan Mitglied 15:39:16 14.03.2018 Titel:

Meiner Meinung kann es für eine Grid-zu-Waypoint-Konvertierung nur dann ein allgemeine Lösung geben, wenn du davon ausgehst, dass du wie in dein Beispiel lauter Wände hast, wo es dann einzelne Durchbrüche gibt. Jeder Wand-Durchbruch wäre dann ein Waypoint. Dann bildest ein neues Netz von den ganzen Waypoints.

Hat deine 2D-Karte auch so Bereiche, wo du sagen kannst: Hier ist es wichtig, dort macht es Sinn,dass man dort lang geht. Hier dieser Kartenbereich wird eh nie betreten?

Tachyon76 Mitglied 15:57:33 14.03.2018 Titel:

Habe mir die App mal was angesehen und getestet:
Scheinbar wir an jedem Eckpunkt ein Wegpunkt gesetzt (Außer am Rand bei dieser App)-
Wenn man z.B. einen einzigen Block hat, werden außen rum 4 Waypoints gesetzt.

Habe das im Programm auch schon umgesetzt. Aber dann werden scheinbar (aus den deutlich wenigeren Waypoints) mittels Dijkstra-Algo die Connections zwischen diesen Waypoints erstellt. Außerdem muss da geprüpft werden, das keine Verbindung eine Mauer/Block schneidet/berührt.

Auch interessant: https://www.reddit.com/r/RimWorld/comments/52a4dm/rimworld_pathfinding_in_a_nutshell/

rapso Moderator 13:58:37 15.03.2018 Titel:

wenn du es schon umgesetzt hast, koenntest du hier beschreiben wie genau du das implementiert hast. Das koennte anderen hier vielleicht mal helfen.

Tachyon76 Mitglied 09:20:06 21.03.2018 Titel:

Habe nur umgesetzt, dass ich die "Eckpunkte" finde und dort ein Wegpunkt erstelle.
Also z.B.: (# = Wand o=Waypint)

Code:
....... ..o.o.. ...#... ..o.o.. .......

Dadurch werden die Waypoints schonmal deutlich reduziert.

Dafür prüfe ich die Karte jeweils horizontal und vertikal:
Ist das aktuelle Feld eine Wand und das nächste (horizontale bzw. vertikale) Feld nicht, dann prüfe ich die Diagonalen (der horizontalen bzw. vertikalen Richtung). Ist dort keine Wand, so plaziere ich dort ein Waypoint. Gibt bestimmt auch eine einfachere Methode dafür.

Aber wie gesagt geht's aber dann erst los, und das habe ich noch nicht umgesetzt.
Meine Idee: die Waypoints müssen ja _effizient_ verbunden werden. Dafür müssen wohl mittels A* bzw. Dijkstra-Algo die nächstliegenden Waypoints gesucht werden - aber ohne dass ein Weg/connection durch eine Wand verläuft.

Außerdem muss wohl dem Pfad zum Schluß der letzten Wegpunkt manuell hinzugefügt werden, da nun nicht mehr jedes Feld einen eigenen Wegpunkt hat.