navigation/wegeberechnung per landkarte
-
hallo.
mein thema ansich passt eigentlich nicht in die spiele ecke (ich versuch ein navigationsprogramm für meinen pda zu schreiben mit routenplaner).aber dafür um so mehr mein prob.
ich habe nicht die leiseste ahnung wie ich einen routenplaner schreiben soll bzw. wie dazu die theorie aussieht.da man vor allem in strategiespielen eine KI-für die wegeberechnung seiner einheiten braucht dachte ich mir das ich mir ein paar tips von euch holen kann.
ein tutorial zu diesem thema hab ich auch im netz nicht gefunden.
es wäre schön wenn ihr mir ein paar standart wege zeigen würdet.danke schon im voraus
-
Als erstes müsstest du dir eine Art digitale Karte erstellen. In der Regel ein 2D Array welches den Zustand einens bestimmten Feldes representiert. Im einfachsten Fall reicht dafür 0 = keine Strasse , 1 = Strasse. Dabei muss du die Ausschnitte für ein Arrayfeld klein genug wählen um mehrdeutigkeiten zu verhindern. Da eine Strasse in der regel wenigstens 2 m breit ist würde ich sagen sollte ein Arrayfeld eine Fläche von 2*2 m representieren.
Wenn du so eine Karte erstellt hast schickst du dann einfach einen Wegberechnungsalgo drüber. z. Bsp A* (A-Star) gibt noch ne Menge mehr, das ist der den ich benutze.
Eine erste kleine und vor allem deutsche Einführung in A-tar gibts unter anderem hier:
http://www.blitzbase.de/artikel/path_1.htm
Diese bietet allerdings noch eine Menge spielraud für Verbesserungen.Im fall eines Routen´planners könnte man das evntl auch etwas vereinfachen, indem man jede Wegkreuzung/mündung als Wegpunkt mit seinen angrenzen punkten spechert. Anstatt alle Felder, spart ne Menge Speicherplatz.
P.S. Nur ums mal anzumerken. Das Programm zu schreiben dürfte in denim Fall das kleinste Problem sein, aber dafür dann auch die passenden Karten anzufertigen, damit dürftest du ne halbe Ewigkeit beschäftigt sein, wenn du nicht ne Möglichkeit findest das zu automatisieren.
-
Für nen Routenplaner würde ich nur lauter Navigationspunkte (Städte, Kreuzugen) speichern und welcher mit welchem durch Straßen direkt verbunden ist.
Außerdem muss für jede Verbindung die Entfernung bzw. geschätzte Zeit gespeichert werden. Wenn du das hast, kannst du darauf A* anwenden, jetzt aber erstmal viel Spaß mit der ersten Aufgabe
btw, in meinem Game funktioniert die Wegfindung genauso. An den Ecken von Hindernissen werdeen Wegpunkte erstellt und deren Entfernung und Verbindung zu anderen Wegpunkten geprüft.
Der Suchbereich ist im Moment aus Performancegründen noch sehr klein, bei einem Routenplaner hast du aber eine statische Karte und die Performance ist auch nicht so wichtig.
-
find ich ziemlich kompliziert ein routenplaner...
-
Ein Routenplaner ist auch kompliziert. Wegfindung ist ein kompliziertes Thema.
-
Naja, das ist wohl relativ zu betrachten, wenn man sich damit mal auseinander gesetzt hat, ist es gleich viel einfacher. Das Problem in den meisten fällen ist ja , das es eine zeitkritische Größe ist und das ist ja bei nehm Routenplaner relativ egal.
-
die wegfindung seh ich nicht als das hauptproblem an, sondern eher die brauchbare interne darstellung der daten wie straßen, welche straße welchen namen hat...usw.
bye
tt
-
Da Du die Karte ja sicher auch zoomen willst, würd' ich die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern (ggf. dann z.B. in SVG umwandeln oder so - wär' sicher generell 'ne gute Möglichkeit für XML).
-
Sgt. Nukem schrieb:
die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern
IMHO hat das eine mit dem anderen nichts zu tun.
-
TGGC schrieb:
Sgt. Nukem schrieb:
die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern
IMHO hat das eine mit dem anderen nichts zu tun.
Eben. Deswegen das "sondern"...
-
ich bin es nochmal.
zuerst möcht ich mich für eure zahlreichen antworten bedanken.
ja das mit den wegepunkten habe ich mir auch schon gedacht,
ist aber für meinen fall nicht anzuwenden,
da der routenplaner den weg für wanderer fahradfahrer und autofahrer berechnen soll.das heißt das proggie muß den "zustand"(mit was der weg befahren werden darf)
wissen.das mit dem array hört sich für mich da eher nach einer passablen lösung an.
das array zu erstellen wird kein prob sein.
ich speichere erst die farbe die mein weg auf meiner karte hat (die digitale karte hab ich schon) und lasse dann von einem proggie einfach den weg anhand der farbe in ein array speichern.danke erstmal vieleicht komm ich ja nochmal.
cu
-
Informationen zu A Stern:
-
Du musst sowieso mehrere Informationen pro Verbindung speichern, also kannst du auch das Fahrzeug, mit dem der Weg gefahren werden soll, speichern.
-
Optimizer schrieb:
Du musst sowieso mehrere Informationen pro Verbindung speichern, also kannst du auch das Fahrzeug, mit dem der Weg gefahren werden soll, speichern.
Yo. So seh' ich das auch. Ich glaube irgendwie, hier reden zwei Gruppen aneinander vorbei, oder?! TGGC's comment hat mich schon verwirrt...
-
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern
IMHO hat das eine mit dem anderen nichts zu tun.
Eben. Deswegen das "sondern"...
Du hast mich offensichtlich nicht ganz verstanden. Beides schliesst sich nicht aus, weil es eben nichts miteinander zu tun hat. Daher ist gerade das "sondern" unangebracht, weil nachts ist es kälter als draussen.
-
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern
IMHO hat das eine mit dem anderen nichts zu tun.
Eben. Deswegen das "sondern"...
Du hast mich offensichtlich nicht ganz verstanden. Beides schliesst sich nicht aus, weil es eben nichts miteinander zu tun hat. Daher ist gerade das "sondern" unangebracht, weil nachts ist es kälter als draussen.
Eben. Genau das meint' ich. Wir reden aneinander vorbei...
Bigwill schrieb:
Als erstes müsstest du dir eine Art digitale Karte erstellen. In der Regel ein 2D Array welches den Zustand einens bestimmten Feldes representiert. Im einfachsten Fall reicht dafür 0 = keine Strasse , 1 = Strasse. Dabei muss du die Ausschnitte für ein Arrayfeld klein genug wählen um mehrdeutigkeiten zu verhindern. Da eine Strasse in der regel wenigstens 2 m breit ist würde ich sagen sollte ein Arrayfeld eine Fläche von 2*2 m representieren.
Dieses hab' ich so verstanden, daß man ein "Gitter" über die Real-Daten legen soll. Die Karte quasi aus Tiles besteht.
Ich wäre halt für Punkte mit Koordinaten, und gewichteten und ggf. gerichteten Verbindungen (Graph) dazwischen.Daß man die Knoten (Punkte) in einem Array speichern kann, sollte klar sein...
Hoffe alle (Un-)Klarheiten beseitigt zu haben...
-
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern
IMHO hat das eine mit dem anderen nichts zu tun.
Eben. Deswegen das "sondern"...
Du hast mich offensichtlich nicht ganz verstanden. Beides schliesst sich nicht aus, weil es eben nichts miteinander zu tun hat. Daher ist gerade das "sondern" unangebracht, weil nachts ist es kälter als draussen.
Eben. Genau das meint' ich. Wir reden aneinander vorbei...
Was nichts an der Unsinnigkeit deiner Aussage ändert.
-
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern
IMHO hat das eine mit dem anderen nichts zu tun.
Eben. Deswegen das "sondern"...
Du hast mich offensichtlich nicht ganz verstanden. Beides schliesst sich nicht aus, weil es eben nichts miteinander zu tun hat. Daher ist gerade das "sondern" unangebracht, weil nachts ist es kälter als draussen.
Eben. Genau das meint' ich. Wir reden aneinander vorbei...
Was nichts an der Unsinnigkeit deiner Aussage ändert.
???
???
-
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern
IMHO hat das eine mit dem anderen nichts zu tun.
Eben. Deswegen das "sondern"...
Du hast mich offensichtlich nicht ganz verstanden. Beides schliesst sich nicht aus, weil es eben nichts miteinander zu tun hat. Daher ist gerade das "sondern" unangebracht, weil nachts ist es kälter als draussen.
Eben. Genau das meint' ich. Wir reden aneinander vorbei...
Was nichts an der Unsinnigkeit deiner Aussage ändert.
???
???Das ist als wenn man sagt: "Ich würde die Daten nicht als Array speichern, sondern als float."
-
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern
IMHO hat das eine mit dem anderen nichts zu tun.
Eben. Deswegen das "sondern"...
Du hast mich offensichtlich nicht ganz verstanden. Beides schliesst sich nicht aus, weil es eben nichts miteinander zu tun hat. Daher ist gerade das "sondern" unangebracht, weil nachts ist es kälter als draussen.
Eben. Genau das meint' ich. Wir reden aneinander vorbei...
Was nichts an der Unsinnigkeit deiner Aussage ändert.
???
???Das ist als wenn man sagt: "Ich würde die Daten nicht als Array speichern, sondern als float."
...wenn Du meinst...
-
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
TGGC schrieb:
Sgt. Nukem schrieb:
die Daten nicht in ein statisches Array ablegen, sondern vektororientiert speichern
IMHO hat das eine mit dem anderen nichts zu tun.
Eben. Deswegen das "sondern"...
Du hast mich offensichtlich nicht ganz verstanden. Beides schliesst sich nicht aus, weil es eben nichts miteinander zu tun hat. Daher ist gerade das "sondern" unangebracht, weil nachts ist es kälter als draussen.
Eben. Genau das meint' ich. Wir reden aneinander vorbei...
Was nichts an der Unsinnigkeit deiner Aussage ändert.
???
???Das ist als wenn man sagt: "Ich würde die Daten nicht als Array speichern, sondern als float."
...wenn Du meinst...
Klar meine ich das.
