Bewegungsrichtung anhand von Bewegungspfad ermitteln

[Thorium]

Hab aktuell ein Problem bei dem ich irgendwie feststecke.

Die Aufgabenstellung erscheint erstmal einfach: Der Spieler soll ein Sprite "greifen" können. Dieses frei über den Bildschirm bewegen und wenn er es "loslässt" soll es in die Richtung weiterfliegen in die er es zuletzt bewegt hat.

Alles kein Problem bis auf das letzte. Das eigentliche Problem bei der Sache ist der menschliche Faktor. Ich brauche eine Gerade um mir den Winkel der Flugrichtung zu errechnen. Aber kein Mensch bewegt seine Hand genau gerade. Ich habe nun also einen Bewegungspfad aufgezeichnet in einem Array aus Punkten. Die Wegpunkte liegen sehr nah beisammen. Das Aufzeichnen der Position läuft frameweise ab, also z.b. 60 mal die Sekunde. Wenn ich jetzt einfach hingehe und meine Gerade aus dem Endpunkt und dem letzten Wegpunkt erstelle, dann bekomme ich natürlich die falsche Richtung. Da die Gerade zu Kurz sein wird, sollte der Spieler keine extrem ruckartige Bewegung gemacht haben. Ist die Gerade nur 2 Pixel lang, kommen gerade mal 8 mögliche Richtungen raus, was natürlich Käse ist. Also ich brauch eine möglichst lange Gerade. Aber der Spieler ist nunmal ein Mensch und der Pfad enthält keine langen Geraden, da ein Mensch nunmal keine exakten Geraden ziehen kann mit seiner Hand. Einfach den Startpunkt und den Endpunkt zu nehmen funktioniert aber auch nicht, da der Spieler das Sprite ja frei umherbewegen kann und nicht die erste Bewegung schon in die Zielrichtung zeigen muss.

Also im Prinzip bräuchte ich einen Algo, der mir aus meinem "hubbeligen" Pfad mit vielen Wegpunkten einen "glatten" Pfad mit wenig Wegpunkten macht. Also quasie den menschlichen Faktor rausrechnet. Dazu müsste er erkennen ob sich die Richtung nun tatsächlich ändert im Pfad oder ob das nur die Ungenauigkeit der Hand ist.

Und da stehe ich und weis nicht wie ich das machen kann. Oder gibt es gar einen anderen viel einfacheren Ansatz dafür?

Den Aufzeichnungsinterval einfach zu ändern so das weniger Wegpunkte und längere Geraden enstehen ändert im Grunde nichts am Problem, da der Spieler durchaus auch mal für einen Moment verharren kann. Und wenn der Spieler verharrt, wird er sich wohl trotzdem um den ein oder anderen Pixel bewegen (zittrige Hand z.B.) und damit hab ich wieder ne 2 Pixel Gerade.

Hier sind ja ein paar Leute unterwegs die Fitt in Trigonometrie und Bewegungsberechnung sind, also bitte helft mir, bevor ich mir alle Haare ausgerissen hab.

[c4s]

Ich kann dir nur einen kleinen Anstoß geben: Mach einfach aus deinen Werten einen Mittelwert.

Hier nochmal auf die Schnelle verdeutlicht:

[Kaeru Gaman]

am Einfachsten wäre es vielleicht, als vektor die Strecke zwischen dem letzten und dem 30st-letzten Punkt im Pfad zu nehmen,
das ist dann die Bewegungsrichtung der letzten halben sekunde vorm loslassen...

[Little John]

Also im Prinzip bräuchte ich einen Algo, der mir aus meinem "hubbeligen" Pfad mit vielen Wegpunkten einen "glatten" Pfad mit wenig Wegpunkten macht. Also quasie den menschlichen Faktor rausrechnet. Dazu müsste er erkennen ob sich die Richtung nun tatsächlich ändert im Pfad oder ob das nur die Ungenauigkeit der Hand ist.

Das hört sich für mich so an, als wenn eine Regressionsgerade das ist was Du suchst.

Gruß, Little John

[Thorium]

Also im Prinzip bräuchte ich einen Algo, der mir aus meinem "hubbeligen" Pfad mit vielen Wegpunkten einen "glatten" Pfad mit wenig Wegpunkten macht. Also quasie den menschlichen Faktor rausrechnet. Dazu müsste er erkennen ob sich die Richtung nun tatsächlich ändert im Pfad oder ob das nur die Ungenauigkeit der Hand ist.

Das hört sich für mich so an, als wenn eine Regressionsgerade das ist was Du suchst.

Ich hab bei Wikipedia grad mal danach geschaut und die Regressionsanalyse gefunden. Aber bei dem Anblick der Formeln ist mir schwindlig geworden. ^^

Allerdings bin ich auf eine andere Lösung gekommen, die mag nicht perfekt sein aber sie funktioniert und dürfte sehr viel performanter sein als so eine Regressionsanalyse. Ich brauche ja nur eine Gerade mit einer bestimmten Mindestlänge, welche Mindestlänge gut ist kann ich ja einfach austesten. Auf jeden Fall brauche ich ja nur vom Endpunkt aus rückwärts meinen Pfad abgehen und schauen wie weit die einzelnen Punkte vom Endpunkt entfernt sind. Sobald ich einen Punkt gefunden habe der weit genug entfernt ist für meine Mindestlänge nehme ich den als Startpunkt meiner Geraden.

Von der Zeit auszugehen wie Kaeru vorgeschlagen hat funktioniert, wenn der Spieler das Sprite schnell bewegt, aber bewegt er es langsam wird meine Gerade möglicherweise zu Kurz. Bewegt er es zu schnell überspringe ich möglicherweise eine große Richtungsänderung. Unabhängig von der Zeit zu arbeiten dürfte ein besseres Ergebnis bringen.

Na morgen programmiere ich es, dann werden wir sehen. ^^

[Little John]

Ja, die Regressionsanalyse ist nicht so performant. Aber falls Du sie doch noch brauchst sag Bescheid, dann schreib ich Dir den Code.

Gruß, Little John

[Little John]

Mir ist eingefallen, dass ich hier noch was posten wollte.

Eine Regressionsanalyse wie sie im wissenschaftlichen Bereich oft benutzt wird ist hier wohl etwas übertrieben. Eine einfachere Ausgleichsgerade sollte es in diesem Fall auch tun. Man kann z.B. die gegebenen Punkte in der Reihenfolge ihres Auftretens in zwei Hälften teilen, und von jeder Hälfte den "Schwerpunkt" berechnen. Das ist wahrscheinlich auch schneller als die übliche Regressionsanalyse. Durch die beiden berechneten "Schwerpunkte" ist dann die Ausgleichsgerade festgelegt. (Ich vermute c4s meinte auch sowas in der Art.)

//edit 22.2.2010:
Code leicht modifiziert und in die Tipps & Tricks-Abteilung verlagert

Gruß, Little John

[c4s]

(Ich vermute c4s meinte auch sowas in der Art.)

Ehrlich gesagt meinte ich genau das. Du hast nur die passenderen Worte gefunden.
Wobei ich auch dachte, dass die Grafik es sowieso ausreichend erläutert.