Hypercell ein ] Hypercell aus ] Zeige Navigation ] Verstecke Navigation ]
c++.net  
   

Die mobilen Seiten von c++.net:
https://m.c-plusplus.net

  
C++ Forum :: Spiele-/Grafikprogrammierung ::  Pathfinding: Grid to Waypoints     Zeige alle Beiträge auf einer Seite Auf Beitrag antworten
Autor Nachricht
Tachyon76
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.04.2008
Beiträge: 66
Beitrag Tachyon76 Mitglied 12:30:04 13.03.2018   Titel:   Pathfinding: Grid to Waypoints            Zitieren

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

Benutzerprofil
Anmeldungsdatum: 07.02.2011
Beiträge: 275
Beitrag XMAMan Mitglied 15:39:16 14.03.2018   Titel:              Zitieren

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?

_________________
Anfänger vom Dienst und Raytracingfreund
Tachyon76
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.04.2008
Beiträge: 66
Beitrag Tachyon76 Mitglied 15:57:33 14.03.2018   Titel:              Zitieren

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/


Zuletzt bearbeitet von Tachyon76 am 16:08:32 14.03.2018, insgesamt 1-mal bearbeitet
rapso
Moderator

Benutzerprofil
Anmeldungsdatum: 17.06.2002
Beiträge: 8807
Beitrag rapso Moderator 13:58:37 15.03.2018   Titel:              Zitieren

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

_________________
follow me|
-Mod im Spiele-/Grafikprogrammierung
Tachyon76
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.04.2008
Beiträge: 66
Beitrag Tachyon76 Mitglied 09:20:06 21.03.2018   Titel:              Zitieren

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.


Zuletzt bearbeitet von Tachyon76 am 09:22:03 21.03.2018, insgesamt 1-mal bearbeitet
C++ Forum :: Spiele-/Grafikprogrammierung ::  Pathfinding: Grid to Waypoints   Auf Beitrag antworten

Zeige alle Beiträge auf einer Seite




Nächstes Thema anzeigen
Vorheriges Thema anzeigen
Sie können Beiträge in dieses Forum schreiben.
Sie können auf Beiträge in diesem Forum antworten.
Sie können Ihre Beiträge in diesem Forum nicht bearbeiten.
Sie können Ihre Beiträge in diesem Forum nicht löschen.
Sie können an Umfragen in diesem Forum nicht mitmachen.

Powered by phpBB © 2001, 2002 phpBB Group :: FI Theme

c++.net ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de Werbekostenerstattung verdient werden kann.

Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info und www.c-plusplus.net enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt (vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden. Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.