Das Bewegen von Schiffen zwischen zwei Planeten entlang eines Beziers, wobei einige Gleichungen für die Beschleunigung fehlen

OK, ich habe dies bereits auf math.stackechange.com gepostet, aber keine Antworten erhalten :(

Als erstes hier ein Bild von meinem Problem, die Beschreibung folgt danach:

Also habe ich alle Punkte und Werte festgelegt.

Das Schiff bewegt sich P1mit einem S=0.27 DegreesGametick um den linken Planeten . Wenn es erreicht ist Point A, folgt es der Bézier-Kurve, bis es erreicht ist Point D, und bewegt sich dann P2mit einem S=0.42 DegreesTick ​​pro Spiel um den rechten Planeten . Der Unterschied Sbesteht darin, dass die Reise mit der gleichen Bewegungsgeschwindigkeit um die Planeten verläuft.

Soweit so gut, ich habe das in Gang gebracht, jetzt mein Problem.

Wenn S P1und zu S P2unterschiedlich, springt das Schiff zwischen den beiden Geschwindigkeiten, wenn es sein Ziel erreicht, was ziemlich schlecht aussieht. Also muss ich das Schiff zwischen beschleunigen Point Aund Point Dvon S P1zu S P2.

Was mir fehlt, ist lila. Das sind:

• Eine Möglichkeit, die Ticks zu berechnen, die das Schiff benötigt, um sich unter Berücksichtigung der Beschleunigung entlang des Beziers zu bewegen.

• Und eine Möglichkeit, eine Position auf der Bezierkurve basierend auf T zu finden, wiederum unter Berücksichtigung der Beschleunigung.

ATM Ich berechne die Länge des Beziers, indem ich den Abstand zwischen Nseinen Punkten berechne . Ich denke also, ich brauche eine Möglichkeit, das, was Tich in meine Bezier-Berechnung einbauen muss, entsprechend der Beschleunigung zu skalieren.

OK, ich habe alles zum Laufen gebracht, es hat ewig gedauert, also werde ich hier meine detaillierte Lösung veröffentlichen.
Hinweis: Alle Codebeispiele sind in JavaScript.

Zerlegen wir das Problem also in die grundlegenden Teile:

1. Sie müssen die Länge sowie die Punkte zwischen 0..1den Bezierkurven berechnen

2. Sie müssen jetzt die Skalierung anpassen T, um das Schiff von einer Geschwindigkeit zur nächsten zu beschleunigen

Den Bézier richtig machen

Es ist einfach, einen Code zum Zeichnen einer Bezier-Kurve zu finden. Es gibt jedoch eine Reihe verschiedener Ansätze. Einer davon ist der DeCasteljau-Algorithmus . Sie können jedoch auch einfach die Gleichung für kubische Bézier-Kurven verwenden:

// Part of a class, a, b, c, d are the four control points of the curve
x: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
           + 3 * ((1 - t) * (1 - t)) * t * this.b.x
           + 3 * (1 - t) * (t * t) * this.c.x
           + (t * t * t) * this.d.x;
},

y: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
           + 3 * ((1 - t) * (1 - t)) * t * this.b.y
           + 3 * (1 - t) * (t * t) * this.c.y
           + (t * t * t) * this.d.y;
}

Mit diesem kann man nun eine Bezierkurve zeichnen, indem man aufruft xund ymit twelchen Bereichen von 0 to 1, schauen wir uns das an:

Äh ... das ist nicht wirklich eine gleichmäßige Verteilung der Punkte, oder?
Aufgrund der Beschaffenheit der Bézier-Kurve sind die Punkte auf 0...1unterschiedlich arc lenghts, sodass Segmente nahe dem Anfang und dem Ende länger sind als diejenigen, die nahe der Mitte der Kurve liegen.

Abbildung T gleichmäßig auf die Kurve AKA Lichtbogenlängenparametrierung

Also, was ist zu tun? Nun, in einfachen Worten, wir brauchen eine Funktion, um unsere Tauf die tder Kurve abzubilden , so dass unsere T 0.25Ergebnisse tauf 25%der Länge der Kurve liegen.

Wie machen wir das? Nun, wir googeln ... aber es stellt sich heraus, dass der Begriff nicht so gut lesbar ist , und irgendwann werden Sie auf dieses PDF stoßen . Was sicher eine gute Lektüre ist, aber für den Fall, dass Sie bereits alle mathematischen Dinge vergessen haben, die Sie in der Schule gelernt haben (oder Sie diese mathematischen Symbole einfach nicht mögen), ist es ziemlich nutzlos.

Was jetzt? Dann gehen Sie doch mal zu Google (Lies: 6 Stunden) und Sie finden endlich einen tollen Artikel zum Thema (inklusive schöner Bilder! ^ _ ^ "):
Http://www.planetclegg.com/projects/WarpingTextToSplines.html

Den eigentlichen Code machen

Falls Sie einfach nicht widerstehen konnten, diese PDFs herunterzuladen, obwohl Sie bereits vor langer, langer Zeit Ihr mathematisches Wissen verloren hatten (und es Ihnen gelungen ist, den großartigen Artikel-Link zu überspringen ), könnten Sie jetzt denken: "Gott, das wird dauern Hunderte von Codezeilen und Tonnen von CPU "

Nein es wird nicht. Weil wir das tun, was alle Programmierer tun, wenn es um Mathe geht:
Wir betrügen einfach.

Lichtbogenlängenparametrierung auf die faule Art und Weise

Seien wir ehrlich, wir brauchen keine endlose Präzision in unserem Spiel, oder? Wenn Sie also nicht bei der Nasa arbeiten und vorhaben, Menschen auf den Mars zu schicken, brauchen Sie keine 0.000001 pixelperfekte Lösung.

So wie bilden wir Tauf t? Es ist einfach und besteht nur aus 3 Schritten:

1. Berechnen Sie die NPunkte auf der Kurve mit tund speichern Sie die arc-length(auch bekannt als die Länge der Kurve) an dieser Position in einem Array

2. Zum TAbbilden tmultiplizieren Sie zuerst Tmit der Gesamtlänge der Kurve, um udas Längenfeld nach dem Index des größten Werts zu durchsuchen, der kleiner als istu

3. Wenn wir einen genauen Treffer hatten, geben Sie den Array-Wert an diesem Index geteilt durch zurück N. Wenn Sie nicht ein bisschen zwischen dem gefundenen und dem nächsten Punkt interpolieren, teilen Sie das Ding erneut durch Nund geben Sie zurück.

Das ist alles! Schauen wir uns nun den kompletten Code an:

function Bezier(a, b, c, d) {
    this.a = a;
    this.b = b;
    this.c = c;
    this.d = d;

    this.len = 100;
    this.arcLengths = new Array(this.len + 1);
    this.arcLengths[0] = 0;

    var ox = this.x(0), oy = this.y(0), clen = 0;
    for(var i = 1; i <= this.len; i += 1) {
        var x = this.x(i * 0.05), y = this.y(i * 0.05);
        var dx = ox - x, dy = oy - y;        
        clen += Math.sqrt(dx * dx + dy * dy);
        this.arcLengths[i] = clen;
        ox = x, oy = y;
    }
    this.length = clen;    
}

Dies initialisiert unsere neue Kurve und berechnet die arg-lenghts, es speichert auch die letzte der Längen als die total lengthder Kurve, wobei der Schlüsselfaktor hier ist, this.lenwelcher unsere ist N. Je höher, desto präziser das Mapping, denn eine Kurve der Größe im obigen Bild 100 pointsscheint ausreichend zu sein. Wenn Sie nur eine gute Längenschätzung benötigen, erledigt so etwas 25bereits die Aufgabe , wenn Sie nur 1 Pixel von unserem entfernt sind Beispiel, aber dann haben Sie eine weniger genaue Zuordnung, die zu einer nicht so gleichmäßigen Verteilung führt, Twenn sie zugeordnet wird t.

Bezier.prototype = {
    map: function(u) {
        var targetLength = u * this.arcLengths[this.len];
        var low = 0, high = this.len, index = 0;
        while (low < high) {
            index = low + (((high - low) / 2) | 0);
            if (this.arcLengths[index] < targetLength) {
                low = index + 1;

            } else {
                high = index;
            }
        }
        if (this.arcLengths[index] > targetLength) {
            index--;
        }

        var lengthBefore = this.arcLengths[index];
        if (lengthBefore === targetLength) {
            return index / this.len;

        } else {
            return (index + (targetLength - lengthBefore) / (this.arcLengths[index + 1] - lengthBefore)) / this.len;
        }
    },

    mx: function (u) {
        return this.x(this.map(u));
    },

    my: function (u) {
        return this.y(this.map(u));
    },

Den eigentlichen Mapping-Code ermitteln wir zunächst einfach binary searchanhand unserer gespeicherten Längen, um die größte Länge zu ermitteln, die dann kleiner ist targetLength. Dann geben wir einfach zurück oder interpolieren und geben zurück.

    x: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
               + 3 * ((1 - t) * (1 - t)) * t * this.b.x
               + 3 * (1 - t) * (t * t) * this.c.x
               + (t * t * t) * this.d.x;
    },

    y: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
               + 3 * ((1 - t) * (1 - t)) * t * this.b.y
               + 3 * (1 - t) * (t * t) * this.c.y
               + (t * t * t) * this.d.y;
    }
};

Dies berechnet sich wiederum tauf der Kurve.

Zeit für Ergebnisse

Indem Sie jetzt verwenden mxund mySie erhalten eine gleichmäßig Tauf der Kurve verteilt :)

War das nicht schwer? Wieder stellt sich heraus, dass eine einfache (wenn auch nicht perfekte) Lösung für ein Spiel ausreichen wird.

Für den Fall, dass Sie den vollständigen Code sehen möchten, steht eine Liste zur Verfügung:
https://gist.github.com/670236

Schließlich beschleunigen die Schiffe

Jetzt müssen Twir nur noch die Schiffe auf ihrem Weg beschleunigen, indem wir die Position abbilden, auf der wir dann die tauf unserer Kurve finden.

Zuerst brauchen wir zwei der Bewegungsgleichungen , nämlich ut + 1/2at²und(v - u) / t

Im eigentlichen Code würde das so aussehen:

startSpeed = getStartingSpeedInPixels() // Note: pixels
endSpeed = getFinalSpeedInPixels() // Note: pixels
acceleration = (endSpeed - startSpeed) // since we scale to 0...1 we can leave out the division by 1 here
position = 0.5 * acceleration * t * t + startSpeed * t;

Dann verkleinern wir das wie 0...1folgt:

maxPosition = 0.5 * acceleration + startSpeed;
newT = 1 / maxPosition * position;

Und los geht's, die Schiffe bewegen sich nun reibungslos auf dem Weg.

Falls es nicht funktioniert ...

Wenn Sie dies lesen, funktioniert alles einwandfrei, aber ich hatte anfangs einige Probleme mit dem Beschleunigungsteil, als ich jemandem im Chatroom von Gamedev das Problem erklärte, fand ich den letzten Fehler in meinem Denken.

Falls Sie das Bild in der ursprünglichen Frage noch nicht vergessen haben, wie ich dort erwähne s, stellt sich heraus, dass ses sich um eine Geschwindigkeit in Grad handelt , aber die Schiffe bewegen sich auf dem Pfad in Pixeln und ich hatte diese Tatsache vergessen. In diesem Fall musste ich die Verschiebung in Grad in eine Verschiebung in Pixel umwandeln. Dies ist also recht einfach:

function rotationToMovement(planetSize, rotationSpeed) {
    var r = shipAngle * Math.PI / 180;
    var rr = (shipAngle + rotationSpeed) * Math.PI / 180;
    var orbit = planetSize + shipOrbit;
    var dx = Math.cos(r) * orbit - Math.cos(rr) * orbit;
    var dy = Math.sin(r) * orbit - Math.sin(rr) * orbit;
    return Math.sqrt(dx * dx + dy * dy);
};

Also und das ist alles! Danke fürs Lesen ;)

Das Problem ist, dass ein Schiff diese Flugbahn natürlich nicht nehmen würde. Selbst wenn es perfekt funktioniert, sieht es immer noch nicht richtig aus.

Wenn Sie den fließenden Übergang zwischen Planeten simulieren möchten, würde ich vorschlagen, ihn tatsächlich zu modellieren. Die Gleichungen sind sehr einfach, da Sie nur zwei wesentliche Kräfte haben: Schwerkraft und Schubkraft.

Sie müssen nur Ihre Konstanten einstellen: Masse von P1, P2, Schiff

Mit jedem Tick (Zeit: t) machst du 3 Dinge

1. Berechnen Sie die Schwerkraft von p1 auf dem Schiff und p2 auf dem Schiff und addieren Sie die resultierenden Vektoren zum Schubvektor.

2. Berechnen Sie Ihre neue Geschwindigkeit basierend auf Ihrer neuen Beschleunigung aus Schritt 1

3. Bewegen Sie das Schiff entsprechend Ihrer neuen Geschwindigkeit

Es mag wie viel Arbeit erscheinen, aber es kann in einem Dutzend Codezeilen erledigt werden und sieht sehr natürlich aus.

Wenn Sie Hilfe in der Physik brauchen, lassen Sie es mich wissen.

Ich habe einen ausgezeichneten Artikel gefunden , in dem eine mögliche Lösung für dieses Problem anhand eines in Javascript geschriebenen Codebeispiels erläutert wird. Es funktioniert, indem der t-Wert in die richtige Richtung bewegt wird.

Stattdessen können wir die Tatsache verwenden, dass die durchschnittliche Schenkellänge d_avg für jede Punktverteilung nahezu identisch mit den Schenkellängen ist, die gleichmäßig verteilte Punkte erzeugen würden (diese Ähnlichkeit nimmt zu, wenn n zunimmt). Wenn wir die Differenz d_err zwischen den tatsächlichen Schenkellängen d und der durchschnittlichen Schenkellänge d_avg berechnen, kann der jedem Punkt entsprechende Zeitparameter t angestupst werden, um diese Differenz zu verringern.

Diese Frage hat bereits viele coole Antworten, aber ich fand diese Lösung bemerkenswert.

Vielen Dank für Ihre ausgezeichnete Seite, auf der beschrieben wird, wie Sie dieses Problem gelöst haben. Ich habe in einem Detail etwas anderes gemacht als Sie, da mir der Speicher sehr schwerfiel: Ich erstelle kein Array oder muss es mit einer binären Suche nach dem richtigen "Segment" durchsuchen. Das liegt daran, dass ich immer weiß, dass ich mich von einem Ende meiner Bézier-Kurve zum anderen bewege. Deshalb erinnere ich mich einfach an das „aktuelle“ Segment und wenn ich sehe, dass ich die Grenzen dieses Segments überschreite, um mein nächstes zu berechnen Position berechne ich das nächste (oder vorherige) Segment (basierend auf der Fahrtrichtung). Dies funktioniert für meine Anwendung recht gut. Die einzige Panne, die ich herausfinden musste, war, dass die Segmentgröße in einigen Kurven so gering war, dass mein nächster zu zeigender Plot - in seltenen Fällen - mehr als ein Segment vor dem aktuellen war, anstatt einfach loszulegen zum '

Ich weiß nicht, ob das wirklich Sinn macht, aber das hat mir sicherlich geholfen.

Diese Art der Modellierung ist seltsam und kann zu seltsamen unlogischen Ergebnissen führen. Vor allem, wenn die Geschwindigkeit der Startplaneten sehr gering ist.

Modellieren Sie die Schiffe mit einer Schubkraft.

Wenn sich die Schiffe auf ihrer letzten Umlaufbahn auf dem Startplaneten befinden, beschleunigen Sie mit vollem Schub.

Wenn sich das Schiff einer bestimmten Entfernung nähert, bremsen Sie es mit dem Rückwärtsschub auf die Umlaufgeschwindigkeit des Zielplaneten ab.

Bearbeiten: Führen Sie die gesamte Simulation auf einmal durch, wenn ein Knoten die Umlaufbahn verlassen soll. Senden Sie entweder alle Daten oder senden Sie nur einige Bewegungsvektoren in Intervallen und interpolieren Sie zwischen ihnen.

Wenn ich es richtig verstehe, ist Ihr Problem überfordert.

Ich glaube, Sie möchten, dass das Raumschiff in einer bestimmten Zeit t auf einem bestimmten Weg zwischen den Umlaufbahnen fährt , und Sie möchten, dass es in derselben Zeit t von Geschwindigkeit s1 auf Geschwindigkeit s2 beschleunigt . Leider kann man (im Allgemeinen) keine Beschleunigung finden, die beide Bedingungen gleichzeitig erfüllt.

Sie müssen Ihr Problem ein wenig lösen, um es lösbar zu machen.

Ich bin auf diese Antwort gestoßen, weil ich Punkte auf einem SVG-Pfad, der eine Bezier-Kurve verwendet, gleichmäßig verteilen möchte.

Obwohl MDN sagt, dass es veraltet ist, können Sie das verwenden path.getPointAtLength, um das richtige Ergebnis zu erhalten. https://developer.mozilla.org/en-US/docs/Web/API/SVGPathElement/getPointAtLength

Es funktioniert derzeit in Chrome / Safari / Firefox und sollte auch in IE / Edge funktionieren, aber ich habe diese 2 nicht verifiziert.

Das Problem mit der akzeptierten Lösung

Da Bezier eine Exponentialfunktion ist, erwarten wir unterschiedliche Vorschubgeschwindigkeiten in verschiedenen Bereichen der Kurve.

Da Ivos Lösung linear zwischen diesen anfänglichen Exponentialabtastwerten interpoliert , werden Ungenauigkeiten in Richtung der Enden / Mitte der (typischerweise kubischen) Kurve stark vorgespannt, wo diese Deltas am größten sind. Wenn also die Abtastrate nicht Nstark erhöht wird, wie er vorschlägt, sind Fehler offensichtlich, und bei einer gewissen Zoomstufe sind sie für eine gegebene Situation immer offensichtlich N, dh, die Verzerrung ist für diesen Algorithmus intrinsisch. Nicht gut für vektorbasierte Grafiken, bei denen der Zoom möglicherweise unbegrenzt ist.

Gegenvorspannung durch geführte Probenahme

Eine alternative Lösung besteht darin, eine lineare Neuzuordnung vorzunehmen distance, tnachdem der natürlichen Vorspannung, die die Bezier-Funktion erzeugt, entgegengewirkt wurde.

Angenommen, dies ist das, was wir im Idealfall wollen:

curve length = 10

t      distance
0.2    2
0.4    4
0.6    6
0.8    8
1.0    10

aber das bekommen wir von der Bezier-Positionsfunktion:

t      distance
0.2    0.12
0.4    1.22
0.6    2.45
0.8    5.81
1.0    10.00

Durch die bei der Suche NProben genommen, können wir bei denen der Abstand Deltas sind sehen am größten, und resample ( „split“) in der Mitte zwischen den beiden benachbarten Entfernungen, die Erhöhung Num 1 zum Beispiel Spaltung bei t=0.9(die in der Mitte der größten Delta ist), könnten wir bekommen:

0.8    5.81
0.9    7.39
1.0    10.00

Wir wiederholen diesen Vorgang für das nächstgrößere Entfernungsintervall, bis das maximale Delta zwischen zwei beliebigen Entfernungen in der gesamten Menge unter einigen liegt minDistanceDelta, genauer gesagt, weniger als epsilonvon bestimmten Entfernungen entfernt, die wir auf Schritte von abbilden möchten t. wir können dann unsere gewünschten tSchritte linear auf entsprechende distances abbilden . Dies erzeugt eine Hash-Tabelle / Map, auf die Sie kostengünstig zugreifen können und zwischen deren Werten Sie zur Laufzeit ohne Verzerrung wechseln können.

Wenn das Set wächst N, steigen die Kosten für die Wiederholung. Idealerweise tun Sie dies als Vorverarbeitung. Fügen Sie bei jeder NErhöhung die beiden neuen resultierenden Intervalle zu einer intervalsSammlung hinzu, während Sie das alte, einzelne Intervall entfernen, das sie ersetzt haben. Dies ist die Struktur, an der Sie arbeiten, um das nächstgrößere Intervall für die Zweiteilung zu finden. Die intervalsSortierung nach Entfernung vereinfacht die Arbeit, da Sie einfach das nächste Arbeitselement vom Ende entfernen und es aufteilen können.

Am Ende haben wir so etwas wie das, was wir uns im Idealfall gewünscht haben:

epsilon: 0.01

t            distance
0.200417     2.00417
0.3998132    3.9998132
0.600703     6.00703
0.800001     8.00001
0.9995309    9.995309

Da wir Vermutungen bei jedem Schritt nehmen, werden wir nicht genau die genauen Abstände erhalten 2, 4usw. Wir wollten, aber durch Wiederholen Sie diese Iteration nahe genug , um den gewünschten Abstand Werte zu erhalten , so dass Sie Ihre Karte können tSchritte mit ziemlicher Genauigkeit, Bias eliminiert durch zu nahezu äquidistanten Abtastungen.

Sie können dann z. B. t=0.5wie Ivo in seiner Antwort abrufen , indem Sie zwischen den beiden nächstgelegenen Werten ( 3.9998132und 6.00703) interpolieren .

Fazit

In den meisten Fällen funktioniert die Lösung von Ivo gut. In Fällen, in denen eine Verzerrung unbedingt vermieden werden muss, stellen Sie sicher, dass Ihre distances so gleichmäßig wie möglich verteilt und dann linear zugeordnet sind t.

Beachten Sie, dass die Aufteilung stochastisch erfolgen kann, anstatt jedes Mal in der Mitte aufzuteilen. Beispielsweise haben wir das erste Beispielintervall möglicherweise t=0.827eher um als um aufgeteilt t=0.9.