spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo,

ich bin neu hier und habe ein Problem mit der Routenplanung in meinem Projekt:

Ich habe eine Spielfigur, von der ich die Position in (x,y)-Koordinaten kenne, und einen vorgeschriebene Route in einem Graphen, die ich per A*-Algorithmus berechne.

Mein Problem: Wie erkenne ich nun, welche Punkte der Zielroute von der Figur schon "abgelaufen" wurden? Ich kann zwar immer die Abstände Spielfigur -> Knoten berechnen, aber das zeigt mir nicht an, ob der Bereich um den Knoten schon passiert wurde...

Ich habe schon versucht, alternative Metriken einzuführen, wie den Raum aufzuteilen in Bereiche, die zu einem Knoten gehören etc. aber das löst das Problem der Routenführung nicht.

Naja, bin für alle Tipps dankbar.

AlGaN

Hallo,

@knivil: Es handelt sich nicht um ein Spiel, sondern um einen GPS-Tracker. Ich update die aktuelle Position jede Sekunde, sobald eben das GPS eine neue Message liefert.
Im Programm lassen sich Routen auf einem vorher definierten Graphen festlegen; die Routen berechne ich durch den A*-Algorithmus (euklidischer Abstand zum Ziel als Heuristik-Funktion). Damit man nicht genau den einzelnen Wegpunkt "treffen" muss, definiere ich ein Proximity-Rechteck um die einzelnen Wegpunkte, in dem man sich befinden muss, damit der aktuelle Wegpunkt als passiert gilt.

@Zera: Das ist genau das Problem. Ich brauche sozusagen eine Nearest-Neighbour-Metrik, der alleinige Abstand zu den einzelnen Wegpunkten reicht nicht aus. Alle Teilstücke zu durchsuchen ist inpraktikabel, da man sich auch neben der Graphenkante befinden kann, wo soll ich da die Grenze ziehen?

Bisher bin ich so vorgegangen, dass ich in einer Statusvariable den nächsten abzulaufenden Wegpunkt speichere, und zwei die Distanzen von zwei aufeinanderfolgenden Zeitschritten zu diesem vergleiche:
Ist d_neu < d_alt => Hinbewegung zu Wegpunkt
d_neu > d_alt => Wegbewegung zu Wegpunkt
Der Wegpunkt-Index erhöht sich dann um 1, wenn ich einen Wegpunkt (bzw. dessen Fläche) passiert habe.
Probleme mit diesem Ansatz:
- ich kann an einem Knoten vorbeilaufen -> Index stimmt nicht mehr
- ich kann rückwärts laufen
- ich kann eine völlig andere Route einschlagen -> A* muss Neuberechnung machen (ähnlich Navi-System im Auto)

Ok, die Erklärung ist jetzt ganz schön lang geworden, vll. bin ich ja auch auf dem Holzweg, mein Problem ist nicht die Routenberechnung (A*), sondern die Routenführung

Danke für alle Tipps,
AlGaN

Hallo zera,

die Idee mit dem Abstand hatte ich auch schon mal, leider versagt diese einfache Berechnung, wenn der Graph nicht aus nur linear hintereinander angeordneten Wegpunkten besteht, sondern auch Abzweigungen, Kreuzungen usw. beinhaltet. Dann kann es passieren, dass sich Benutzer in der Nähe eines solchen Kreuzungspunkts befindet und der kleinste Abstand gerade zur falschen Kante führt; ganz nutzlos wird der Ansatz, wenn ich einen Graphen habe der ein Quadrat an Wegpunkten beinhaltet und sich der Benutzer in der Mitte befindet:

Vll. kann man sich's so besser vorstellen:


Trotzdem danke für die Antwort, muss mich wohl noch mehr mit Routenplanung befassen...

AlGaN

Hm, ja an sowas in der Art hab ich auch schon mal gedacht; eine Art "Map Matching" mittels Ort / mittlerer Richtungsvektor, das geht dann aber schon in Richtung Ähnlichkeits-Algorithmus... aber sowas ähnliches wurde m.W. vom Ansatz her auch schon in anderen Routenplanern versucht...