In fast jedem Computerspiel wird früher oder später das eine oder andere Geschoss abgefeuert. Wenn vom Computer gesteuerte Charaktere, Flugzeuge oder Raumschiffe in der Lage sein sollen, ihre Gegner halbwegs zuverlässig zu treffen, dann sollte man sich Gedanken darüber machen, wie man das Geschoss genau so abfeuert, dass es sein Ziel vermutlich treffen wird.

Eine Alternative ist, den Geschossen einfach eine unendlich schnelle Geschwindigkeit zu verleihen, so dass die Bewegung des Schützen, des Ziels und des Geschosses und auch die Gravitation keine Rolle mehr spielen. Wer jedoch Wert auf ein Minimum an Realismus legt, der muss all diese Parameter berücksichtigen, denn sonst wird der größte Teil der Schüsse daneben gehen.

Intuitiv ist klar: Je schneller das Ziel sich relativ zum Schützen bewegt, desto weiter muss er vorhalten, um zu treffen. Aber wie weit genau? Diese Frage lässt sich mit ein wenig Mathematik beantworten. In diesem Artikel wird ein Algorithmus vorgestellt, mit dem das möglich ist.

Die Ausgangssituation

Folgende Parameter müssen bekannt sein:

• Position und Bewegungsvektor (enthält Bewegungsrichtung und Geschwindigkeit) des Schützen
• Position und Bewegungsvektor des Ziels
• Mündungsgeschwindigkeit des Projektils
• Gravitationsvektor

Wir gehen für die Berechnungen davon aus, dass das Ziel seine Flugrichtung und Geschwindigkeit nicht oder nur geringfügig ändert, während das Projektil seinen Weg zurücklegt. Außerdem soll das Projektil durch die Gravitation ständig nach unten (oder in eine beliebige andere Richtung) gezogen werden, so dass seine Flugbahn keine Gerade, sondern eine Parabel bildet. Bei der Flugbahn des Ziels gehen wir jedoch von einer geraden Linie aus, da es sich meist um ein Flugzeug oder ein ähnliches Objekt handeln wird, das darauf ausgelegt ist, der Gravitation entgegenzuwirken und in einer geraden Linie mit gleichbleibender Geschwindigkeit zu fliegen. Die Reibung, die das Geschoss durch die Luft erfährt und die es kontinuierlich langsamer werden lässt, wird von dem Algorithmus jedoch nicht berücksichtigt, da die Berechnungen andernfalls viel komplizierter würden. Bei relativ kurzen Entfernungen zum Ziel fällt dieser Umstand nicht allzusehr ins Gewicht.

Unser Ziel soll es nun sein, aus diesen Parametern die Richtung zu ermitteln, in die das Geschoss abgefeuert werden muss, um zu treffen. Die Abschussgeschwindigkeit ist dabei festgelegt, es geht also nur um die Richtung. Zusätzlich werden wir den voraussichtlichen Ort und den Zeitpunkt des Treffers berechnen.

Bezeichnungen

Im Folgenden werden folgende Bezeichnungen für die Parameter verwendet:

• §\vec v_T§ ist der Bewegungsvektor des Ziels zum Zeitpunkt des Schusses, relativ zum Schützen (Differenz zwischen Bewegungsvektor des Ziels und der des Schützen). Die Dimension des Vektors spielt keine Rolle (üblich wäre 2 oder 3).
• §\vec p_T§ ist die Position des Ziels zum Zeitpunkt des Schusses, ebenfalls relativ zum Schützen.
• §\vec d_H§ ist die Richtung, in der das Projektil abgefeuert werden muss, um das Ziel zu treffen. Diesen Vektor zu berechnen ist unser Ziel.
• §v_0§ ist die Mündungsgeschwindigkeit des Projektils.
• §t§ bezeichnet allgemein die Zeit, wobei die Schussabgabe zum Zeitpunkt §t = 0§ erfolgt.

Warum arbeiten wir mit einem relativen Bewegungs- und Positionsvektor? Da wir die Reibung vernachlässigen, macht es beispielsweise keinen Unterschied, ob sich der Schütze mit §20 \mathrm{\tfrac{m}{s}}§ nach links bewegt und das Ziel mit §50 \mathrm{\tfrac{m}{s}}§, oder ob der Schütze still steht und sich das Ziel mit §30 \mathrm{\tfrac{m}{s}}§ von ihm weg bewegt. Was zählt, ist die Position und die Bewegung des Ziels relativ zum Schützen. Wir betrachten also alles aus seiner Sicht, wobei er den Mittelpunkt der Welt (den Koordinatenursprung) darstellt und alles sich um ihn bewegt. Das vereinfacht die spätere Rechnung.

Berechnung des Trefferzeitpunkts

Aufenthaltskreise für t = 1, 2, 3, ..., 10 Sekunden mit einer Mündungsgeschwindigkeit von 50 m/s, ohne Berücksichtigung der Gravitation.

Wir beginnen mit einer Gleichung, die alle Positionen beschreibt, die ein vom Schützen abgefeuertes Projektil zu einem bestimmten Zeitpunkt einnehmen kann. Vernachlässigen wir dabei erst einmal die Gravitation, die das Projektil nach unten zieht.

Nehmen wir also an, der Schütze würde unendlich viele Geschosse gleichzeitig in alle erdenklichen Richtungen abfeuern. Nach einer Sekunde halten wir das Universum an und betrachten die Positionen der Geschosse. Sie haben in dieser einen Sekunde alle dieselbe Distanz zurückgelegt und befinden sich damit auf einer Kugel (im dreidimensionalen Fall), in deren Mittelpunkt sich der Schütze befindet. Der Radius der Kugel entspricht genau dieser Distanz, und die können wir einfach berechnen, indem wir die vergangene Zeit mit der Geschossgeschwindigkeit multiplizieren, also §v_0 \cdot t§ berechnen. Wenn die Geschosse beispielsweise §300 \mathrm{\tfrac{m}{s}}§ schnell sind, dann hat die Kugel nach einer Sekunde einen Radius von §300 \mathrm{m}§, nach zwei Sekunden §600 \mathrm{m}§, nach fünf Sekunden §1500 \mathrm{m}§, und so weiter. Würden wir die Reibung berücksichtigen, ließe sich der Radius nicht mehr so leicht ausrechnen, da die Geschosse gebremst würden.

Was haben wir dadurch gewonnen? Wir können jetzt für jeden Zeitpunkt ausrechnen, welche Stellen der Schütze treffen kann. Bei den weiteren Betrachtungen werden wir den zweidimensionalen Fall bevorzugen, da er sich grafisch leichter darstellen lässt. Hier haben wir es nicht mit Kugeln, sondern mit Kreisen zu tun. Für das Verfahren an sich ist es jedoch, wie gesagt, völlig unerheblich, welche Dimension die Vektoren haben.

Wir wollen diese Kreise von nun an Aufenthaltskreise nennen, da sie genau die Punkte beschreiben, auf denen sich nach Ablauf einer bestimmten Zeit ein Geschoss befinden kann. Als nächstes müssen diese Kreise mathematisch dargestellt werden. Da wir alles vom Schützen aus betrachten, ist der Mittelpunkt der Kreise jeweils der Koordinatenursprung. Der Radius beträgt §v_0 \cdot t§, denn dies ist die Distanz, die ein Geschoss in der Zeit §t§ zurücklegt.

Die Formel für den Aufenthaltskreis zum Zeitpunkt §t§ lautet also:

§k(t): \vec x^2 = (t \cdot v_0)^2§

Aufenthaltskreise mit Berücksichtigung der Gravitation.

Wenn wir jetzt die Gravitation mit einbeziehen, dann wird die ursprüngliche gleichförmige Bewegung der Projektile von einer gleichmäßig beschleunigten Bewegung in Richtung des Gravitationsvektors überlagert. Dies hat zur Folge, dass die Kreise nicht mehr konzentrisch sind, sondern sich mit der Zeit nach unten bewegen. Sie werden jedoch nicht gestreckt. Diese Kreise werden nun beschrieben durch:

§k_G(t): (\vec x - \tfrac{1}{2} \vec g \cdot t^2)^2 = (t \cdot v_0)^2§

Wie man in der Abbildung erkennen kann, gibt es keine Möglichkeit, Punkte oberhalb der Grenze von ungefähr §y = 140§ zu treffen, da dort keine Kreise verlaufen. Das liegt daran, dass die Gravitation die Geschosse daran hindert, höher zu steigen. Die Projektile verlieren ihre vertikale Geschwindigkeit nach oben und gehen in den Fall über. Eine höhere Mündungsgeschwindigkeit §v_0§ würde die Reichweite vergrößern.

Betrachten wir nun die geradlinige Bewegung des Ziels. Dessen Position zum Zeitpunkt §t§ lässt sich ganz leicht wie folgt berechnen:

§\vec x(t) = \vec p_T + t \cdot \vec v_T§

Diese Gleichung beschreibt eine einfache Gerade. Wir wollen jetzt den Zeitpunkt §t_H§ ermitteln, zu dem ein Projektil das Ziel treffen kann, um dann später daraus die Abschussrichtung zu berechnen. Zu dem gesuchten Zeitpunkt §t_H§ muss sich das Ziel also genau auf dem dazugehörigen Aufenthaltskreis §k_G(t_H)§ befinden, denn dieser Kreis beschreibt alle möglichen Orte, an denen sich ein Projektil zu diesem Zeitpunkt befinden kann. Um den Zeitpunkt berechnen zu können, müssen wir die beiden Gleichungen ineinander einsetzen:

§\left((\vec p_T + t_H \cdot \vec v_T) - \tfrac{1}{2} \vec g \cdot {t_H}^2\right)^2 = (t_H \cdot v_0)^2§

Jetzt muss diese Gleichung nach §t_H§ aufgelöst werden. Die Arbeit besteht im Wesentlichen im Ausmultiplizieren der Quadrate. Wenn man anschließend die verschiedenen Potenzen von §t_H§ ausklammert, ergibt sich folgende quartische Gleichung:

§{t_H}^4 \cdot (\tfrac{1}{4} \vec g^2) + {t_H}^3 \cdot (-\vec v_T \cdot \vec g) + {t_H}^2 \cdot (\vec {v_T}^2 - {v_0}^2 - \vec p_T \cdot \vec g) + t_H \cdot (2 \vec p_T \cdot \vec v_T) + \vec {p_T}^2 = 0§

So wie es die "pq-Formel" zum Lösen quadratischer Gleichungen gibt, existieren auch für quartische Gleichungen direkte Lösungsverfahren, allerdings sind diese bei weitem nicht so einfach. Wir nehmen für den Moment einmal an, dass wir die Gleichung bereits lösen können. Dann können folgende Fälle auftreten:

1. Die Gleichung besitzt keine positive reelle Lösung. Für unseren Fall bedeutet das, dass das Ziel schlichtweg nicht getroffen werden kann, sofern es seinen momentanen Kurs beibehält (und auf dieser Annahme beruht das Verfahren).
2. Es gibt mindestens eine positive reelle Lösung. Das heißt, dass es eine oder mehrere Möglichkeiten gibt, wie das Projektil abgefeuert werden könnte, so dass es das Ziel irgendwann trifft. Manche dieser Möglichkeiten könnten etwas ungewöhnlich erscheinen, würde man sie in die Tat umsetzen. Der Schütze würde das Geschoss beispielsweise im hohen Bogen auf das Ziel befördern, obwohl es sich direkt vor ihm befindet (eine solche Lösung wäre dann interessant, wenn der direkte Weg zum Ziel durch ein Hindernis versperrt ist). Negative Lösungen sind deswegen uninteressant, da die Lösungen schließlich für den voraussichtlichen Trefferzeitpunkt stehen, und ein negativer Wert würde bedeuten, dass das Ziel in der Vergangenheit getroffen wurde.

Für unsere Zwecke sind wir daher an der kleinsten positiven Lösung dieser Gleichung interessiert, denn mit dieser Lösung bleibt dem Ziel die kürzeste Zeit zum Ausweichen.

Wohin zielen?

Wenn wir die kleinste positive Lösung §t_H§ gefunden haben, können wir als nächstes den Ort des Treffers §\vec p_H§ berechnen (immer relativ zum Schützen). Dazu müssen wir nur §t_H§ in die Gleichung für die Flugbahn des Ziels einsetzen:

§\vec p_H = \vec p_T + t_H \cdot \vec v_T§

Damit kennen wir den Ort und den Zeitpunkt eines möglichen Treffers, aber wir kennen noch nicht die Richtung §\vec d_H§, in die das Projektil vom Schützen abgefeuert werden muss, damit es zu diesem Treffer kommen kann. Glücklicherweise ist das nun nicht mehr besonders schwierig. Zuerst stellen wir eine Gleichung für die Flugbahn des Geschosses relativ zum Schützen auf, wenn es von ihm in die Richtung §\vec d§ abgeschossen wurde:

§\vec x(t) = \vec d \cdot v_0 \cdot t + \tfrac{1}{2} \vec g \cdot t^2§

Die Bewegung des Geschosses besteht also aus zwei Bewegungen, die sich überlagern: Die Komponente §\vec d \cdot v_0 \cdot t§ ist die gleichförmige Bewegung, die das Geschoss durch den Abschuss erhalten hat, und §\tfrac{1}{2} \vec g \cdot t^2§ ist die gleichmäßig beschleunigte Bewegung, die es durch die Gravitation erfährt.

Da wir vorhin bereits den Zeitpunkt des Treffers §t_H§ und auch den Ort §\vec p_H§ berechnet haben, können wir beides in die Gleichung einsetzen und nach §\vec d§ auflösen:

§\begin{align}

\vec x(t_H) &= \vec p_H \\ \vec d \cdot v_0 \cdot t_H + \tfrac{1}{2} \vec g \cdot {t_H}^2 &= \vec p_H \\ \vec d &= \frac{\vec p_H - \tfrac{1}{2} \vec g \cdot {t_H}^2}{v_0 \cdot t_H} \end{align}§

Mit dem Vektor §\vec d§ kennen wir jetzt die Richtung, in die der Schütze von sich aus gesehen das Geschoss abfeuern muss, um das Ziel (wahrscheinlich) zu treffen. Dieser Vektor ist automatisch normiert, hat also die Länge 1. Da wir bei allen Überlegungen die Position und die Bewegung des Schützen nicht benötigt haben, weil wir mit relativen Positionen und Geschwindigkeiten gearbeitet haben, müssen wir, um den endgültigen absoluten Bewegungsvektor §\vec v_P§ des Projektils zu erhalten, den Bewegungsvektor §\vec v_S§ des Schützen wieder hinzuaddieren:

§\vec v_P = \vec v_S + \vec d \cdot v_0§

Implementierung in C++

In der folgenden Beispielimplementierung wird zum Lösen der quartischen Gleichung die Funktion magnet::math::quarticSolve verwendet, deren Implementierung unter der unten angegebenen Referenz^[1] zu finden ist. Es wird außerdem davon ausgegangen, dass Vector eine Vektorklasse ist, auf der die üblichen Operationen definiert sind. Die statische Methode dot muss das Skalarprodukt zweier Vektoren berechnen, die Methode lengthSq() das Quadrat der Vektorlänge (das Skalarprodukt mit sich selbst).

/* Parameter:
 * ----------
 * shooterPosition: [in]  Position des Schützen
 * shooterVelocity: [in]  Bewegungsvektor des Schützen
 * targetPosition:  [in]  Position des Ziels
 * targetVelocity:  [in]  Bewegungsvektor des Ziels
 * projectileSpeed: [in]  Geschossgeschwindigkeit
 * gravity:         [in]  Gravitationsvektor
 * outHitPosition:  [out] Position des voraussichtlichen Treffers (absolut)
 * outHitTime:      [out] Zeitpunkt des voraussichtlichen Treffers
 * outShootDir:     [out] Richtung, in die das Projektil abgefeuert werden muss
 *
 * Rückgabewert:    true, wenn das Ziel getroffen werden kann,
 *                  false, wenn es nicht getroffen werden kann.
 */
bool computeHitWithGravity(const Vector& shooterPosition,
                           const Vector& shooterVelocity,
                           const Vector& targetPosition,
                           const Vector& targetVelocity,
                           double projectileSpeed,
                           const Vector& gravity,
                           Vector& outHitPosition,
                           double& outHitTime,
                           Vector& outShootDir)
{
    // Relative Zielposition und -geschwindigkeit berechnen.
    const Vector targetRelPosition = targetPosition - shooterPosition;
    const Vector targetRelVelocity = targetVelocity - shooterVelocity;
 
    // Koeffizienten der quartischen Gleichung berechnen.
    const double A = 0.25 * gravity.lengthSq();
    const double B = -Vector::dot(targetRelVelocity, gravity);
    const double C = targetRelVelocity.lengthSq() - projectileSpeed * projectileSpeed - Vector::dot(targetRelPosition, gravity);
    const double D = 2 * Vector::dot(targetRelPosition, targetRelVelocity);
    const double E = targetRelPosition.lengthSq();
 
    // Reelle Lösungen der Gleichung bestimmen.
    // Wichtig: magnet::math::quarticSolve geht davon aus, dass A = 1 ist.
    // Also dividieren wir alle übrigen Koeffizienten durch A.
    double r[4];
    size_t n = magnet::math::quarticSolve(B / A, C / A, D / A, E / A, r[0], r[1], r[2], r[3]);
 
    // Gibt es Lösungen?
    if(!n)
    {
        // Keine Lösung - das Ziel kann nicht getroffen werden.
        return false;
    }
 
    // Die kleinste positive Lösung suchen.
    double smallestPositive = -1.0;
    for(size_t i = 0; i < n; i++)
    {
        if(r[i] > 0.0 &&
           (smallestPositive == -1.0 || r[i] < smallestPositive))
        {
            smallestPositive = r[i];
        }
    }
 
    // Gab es überhaupt eine positive Lösung?
    if(smallestPositive == -1.0)
    {
        // Nein - kein Treffer möglich!
        return false;
    }
 
    // Wir übernehmen die gefundene Lösung.
    const double t = smallestPositive;
 
    // Ort des Treffers (relativ zum Schützen) berechnen.
    const Vector hitRelPosition = targetRelPosition + t * targetRelVelocity;
 
    // Richtung des Abschusses berechnen.
    const Vector shootDir = (hitRelPosition - 0.5 * gravity * t * t) / (projectileSpeed * t);
 
    // Gefundene Werte ausgeben.
    outHitTime = t;
    outHitPosition = targetPosition + t * targetVelocity;
    outShootDir = shootDir;
 
    return true;
}

Mögliche Erweiterungen

Wie bereits erwähnt, berücksichtigt das hier vorgestellte Verfahren nicht den Luftwiderstand, der ein Geschoss ständig langsamer werden lässt. Eine andere Erweiterung besteht darin, nicht nur die momentane Geschwindigkeit des Ziels (die erste Ableitung der Position), sondern auch seine momentane Beschleunigung (die zweite Ableitung) in die Berechnung einzubeziehen. Damit würde das Ziel nicht nur garantiert getroffen, wenn es seinen Kurs nicht ändert, sondern es würde ausreichen, dass es seine Beschleunigung nicht ändert. Solche Erweiterungen führen zu Gleichungen noch höheren Grades, die algebraisch nicht mehr gelöst werden können, sondern nur noch numerisch.

Eine Alternative zur direkten Berechnung ist die Verwendung von Monte-Carlo-Simulation. Dabei könnte man die Bewegung des Ziels probabilistisch modellieren, eventuell sogar "intelligent" auf der Basis vergangener Beobachtungen, und so eine Abschussrichtung mit maximaler Trefferwahrscheinlichkeit finden.

Einzelnachweise

1. ↑ dynamo - Event driven molecular dynamics simulator. Marcus Bannerman. 2011.