2d-Spiel :Feuer auf bewegliche Ziele durch die Vorhersage Kreuzung von Projektil und Gerät

https://stackoverflow.com/questions/2248876

20-09-2019
|

Frage

Okay, das ganze findet in eine schöne und einfache 2D-Welt...:)

Angenommen, ich habe ein statisches Objekt, das Eine an position Apos, und ein Linear bewegliches Objekt B an Bpos mit bVelocity, und eine ammo Runde mit Geschwindigkeit Avelocity...

Wie würde ich herausfinden, die Winkel, die Eine hat, um zu Schießen, zu schlagen, B, unter Berücksichtigung von B die lineare Geschwindigkeit und die Geschwindigkeit der Munition ?

Jetzt das Ziel ist, an der aktuellen position des Objekts, was bedeutet, dass von die Zeit mein Projektil wird es die Einheit zog auf sicherer Position :)

Lösung

Zunächst drehen, um die Achsen so, dass AB vertikal ist (durch eine Drehung tun)

aufgeteilt nun den Geschwindigkeitsvektor von B in die x- und y-Komponenten (sagen Bx und By). Sie können diese verwenden, um die x- und y-Komponenten des Vektors Sie müssen zu schießen.

berechnen

B --> Bx
|
|
V

By


Vy
^
|
|
A ---> Vx

Sie müssen Vx = Bx und Sqrt(Vx*Vx + Vy*Vy) = Velocity of Ammo.

Dies sollten Sie den Vektor Sie in dem neuen System benötigen. Verwandeln Sie zurück zum alten System und Sie sind fertig (durch eine Drehung in der anderen Richtung zu tun).

Andere Tipps

Ich schrieb ein Zielunterprogramm für xtank eine Weile zurück. Ich werde versuchen, zu legen, wie ich es tat.

Hinweis: Ich habe vielleicht hier ein oder mehrere dumme Fehler überall gemacht; Ich versuche nur, die Argumentation mit meinen rostigen mathematischen Fähigkeiten zu rekonstruieren. Allerdings werde ich zum ersten Mal auf den Punkt, da dies eine Programmierung Q & A statt eine Math-Klasse ist: -)

Wie es

tun

Es läuft darauf hinaus, eine quadratische Gleichung der Form zu lösen:

a * sqr(x) + b * x + c == 0

Beachten Sie, dass durch sqr I mittlere quadratische, wie zum Quadratwurzel gegenüber. Verwenden Sie die folgenden Werte:

a := sqr(target.velocityX) + sqr(target.velocityY) - sqr(projectile_speed)
b := 2 * (target.velocityX * (target.startX - cannon.X)
          + target.velocityY * (target.startY - cannon.Y))
c := sqr(target.startX - cannon.X) + sqr(target.startY - cannon.Y)

Jetzt können wir die Diskriminante schauen, um festzustellen, ob wir eine mögliche Lösung.

disc := sqr(b) - 4 * a * c

Wenn die Diskriminante weniger als 0, vergisst Ihr Ziel zu treffen - Ihr Projektil kann nie dort in der Zeit. Ansonsten Blick auf zwei Kandidatenlösungen:

t1 := (-b + sqrt(disc)) / (2 * a)
t2 := (-b - sqrt(disc)) / (2 * a)

Beachten Sie, dass, wenn disc == 0 dann t1 und t2 gleich sind.

Wenn es keine anderen Überlegungen wie dazwischen Hindernisse sind, einfach den kleineren positiven Wert wählen. (Negative t Werte würden in der Zeit rückwärts zu verwenden erfordern Brennen!)

Ersetzen Sie den gewählten t Wert wieder in die Position Gleichungen Ziel die Koordinaten des führenden Punkt zu kommen, sollten Sie mit dem Ziel werden:

aim.X := t * target.velocityX + target.startX
aim.Y := t * target.velocityY + target.startY

Ableitung

Zum Zeitpunkt T muss das Projektil sein, ein (euklidischer) Abstand von der Kanone auf die verstrichene Zeit gleich die Projektilgeschwindigkeit multipliziert. Daraus ergibt sich eine Gleichung für einen Kreis, parametrischer in verstrichene Zeit.

sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
  == sqr(t * projectile_speed)

In ähnlicher Weise zu dem Zeitpunkt T, das Ziel entlang des Vektor durch die Zeit durch seine Geschwindigkeit multipliziert bewegt hat:

target.X == t * target.velocityX + target.startX
target.Y == t * target.velocityY + target.startY

Das Projektil kann das Ziel treffen, wenn ihr Abstand von der Kanone des Abstand des Projektils entspricht.

sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
  == sqr(target.X - cannon.X) + sqr(target.Y - cannon.Y)

Wonderful! Setzt man die Ausdrücke für target.X und target.Y gibt

sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
  == sqr((t * target.velocityX + target.startX) - cannon.X)
   + sqr((t * target.velocityY + target.startY) - cannon.Y)

, um die andere Seite der Gleichung Substituieren ergibt dies:

sqr(t * projectile_speed)
  == sqr((t * target.velocityX + target.startX) - cannon.X)
   + sqr((t * target.velocityY + target.startY) - cannon.Y)

... sqr(t * projectile_speed) von beiden Seiten subtrahiert und blättert es um:

sqr((t * target.velocityX) + (target.startX - cannon.X))
  + sqr((t * target.velocityY) + (target.startY - cannon.Y))
  - sqr(t * projectile_speed)
  == 0

... löst nun die Ergebnisse der Teilausdrücke quadriert ...

sqr(target.velocityX) * sqr(t)
    + 2 * t * target.velocityX * (target.startX - cannon.X)
    + sqr(target.startX - cannon.X)
+ sqr(target.velocityY) * sqr(t)
    + 2 * t * target.velocityY * (target.startY - cannon.Y)
    + sqr(target.startY - cannon.Y)
- sqr(projectile_speed) * sqr(t)
  == 0

... und Gruppe ähnliche Begriffe ...

sqr(target.velocityX) * sqr(t)
    + sqr(target.velocityY) * sqr(t)
    - sqr(projectile_speed) * sqr(t)
+ 2 * t * target.velocityX * (target.startX - cannon.X)
    + 2 * t * target.velocityY * (target.startY - cannon.Y)
+ sqr(target.startX - cannon.X)
    + sqr(target.startY - cannon.Y)
  == 0

... kombinieren sie dann ...

(sqr(target.velocityX) + sqr(target.velocityY) - sqr(projectile_speed)) * sqr(t)
  + 2 * (target.velocityX * (target.startX - cannon.X)
       + target.velocityY * (target.startY - cannon.Y)) * t
  + sqr(target.startX - cannon.X) + sqr(target.startY - cannon.Y)
  == 0

... Standard-quadratische Gleichung gibt in t . Das Finden der positiven reellen Nullstellen dieser Gleichung ergibt die (null, eins oder zwei) möglich Trefferstellen, die mit der quadratischen Formel getan werden kann:

a * sqr(x) + b * x + c == 0
x == (-b ± sqrt(sqr(b) - 4 * a * c)) / (2 * a)

1 auf Jeffrey Hantin des ausgezeichneten Antwort hier. Ich googeln um und fand Lösungen, die entweder zu komplex waren oder nicht speziell über den Fall ich interessiert war (einfach konstanter Geschwindigkeit Projektil im 2D-Raum.) Er war genau das, was ich brauchte, unter der sich geschlossene JavaScript-Lösung herzustellen.

Der einzige Punkt, den ich hinzufügen würde, ist, dass es ein paar Sonderfälle Sie zusätzlich zu der Diskriminante negativ zu sehen haben:

„a == 0“: tritt auf, wenn Ziel und Geschoss sind die gleichen Geschwindigkeit bewegt. (Lösung ist linear, nicht quadratisch)
"a == 0 und b == 0": wenn beide Ziel und Projektil stationär sind. (Keine Lösung, es sei denn c == 0, das heißt src & dst sind selben Punkt.)

Code:

/**
 * Return the firing solution for a projectile starting at 'src' with
 * velocity 'v', to hit a target, 'dst'.
 *
 * @param Object src position of shooter
 * @param Object dst position & velocity of target
 * @param Number v   speed of projectile
 * @return Object Coordinate at which to fire (and where intercept occurs)
 *
 * E.g.
 * >>> intercept({x:2, y:4}, {x:5, y:7, vx: 2, vy:1}, 5)
 * = {x: 8, y: 8.5}
 */
function intercept(src, dst, v) {
  var tx = dst.x - src.x,
      ty = dst.y - src.y,
      tvx = dst.vx,
      tvy = dst.vy;

  // Get quadratic equation components
  var a = tvx*tvx + tvy*tvy - v*v;
  var b = 2 * (tvx * tx + tvy * ty);
  var c = tx*tx + ty*ty;    

  // Solve quadratic
  var ts = quad(a, b, c); // See quad(), below

  // Find smallest positive solution
  var sol = null;
  if (ts) {
    var t0 = ts[0], t1 = ts[1];
    var t = Math.min(t0, t1);
    if (t < 0) t = Math.max(t0, t1);    
    if (t > 0) {
      sol = {
        x: dst.x + dst.vx*t,
        y: dst.y + dst.vy*t
      };
    }
  }

  return sol;
}


/**
 * Return solutions for quadratic
 */
function quad(a,b,c) {
  var sol = null;
  if (Math.abs(a) < 1e-6) {
    if (Math.abs(b) < 1e-6) {
      sol = Math.abs(c) < 1e-6 ? [0,0] : null;
    } else {
      sol = [-c/b, -c/b];
    }
  } else {
    var disc = b*b - 4*a*c;
    if (disc >= 0) {
      disc = Math.sqrt(disc);
      a = 2*a;
      sol = [(-b-disc)/a, (-b+disc)/a];
    }
  }
  return sol;
}

Jeffrey Hantin hat eine schöne Lösung für dieses Problem, obwohl seine Ableitung übermäßig kompliziert ist. Hier ist ein sauberer Weg, um es mit einem Teil des resultierenden Code am unteren abzuleiten.

Ich werde x.y werden unter Verwendung von Vektorpunktprodukt darstellen, und wenn eine Vektorgröße im Quadrat ist, es bedeutet, dass ich es mit sich selbst bin Punktierung.

origpos = initial position of shooter
origvel = initial velocity of shooter

targpos = initial position of target
targvel = initial velocity of target

projvel = velocity of the projectile relative to the origin (cause ur shooting from there)
speed   = the magnitude of projvel
t       = time

Wir wissen, dass die Position des Geschosses und Ziel in Bezug auf t Zeit kann mit einigen Gleichungen beschrieben werden.

curprojpos(t) = origpos + t*origvel + t*projvel
curtargpos(t) = targpos + t*targvel

Wir wollen diese irgendwann zueinander gleich sein (der Schnittpunkt), so lassen Sie uns setzen sie einander gleich und lösen für die freie Variable, projvel.

origpos + t*origvel + t*projvel = targpos + t*targvel
    turns into ->
projvel = (targpos - origpos)/t + targvel - origvel

Vergessen sie über den Begriff der Herkunfts- und Ziel Position / Geschwindigkeit. Stattdessen lassen die Arbeit relativ gesehen, da Bewegung von einer Sache zur anderen relativ ist. In diesem Fall, was wir jetzt haben, ist relpos = targetpos - originpos und relvel = targetvel - originvel

projvel = relpos/t + relvel

Wir wissen nicht, was projvel ist, aber wir wissen, dass wir projvel.projvel gleich speed^2 sein wollen, so dass wir beide Seiten quadrieren werden und wir bekommen

projvel^2 = (relpos/t + relvel)^2
    expands into ->
speed^2 = relvel.relvel + 2*relpos.relvel/t + relpos.relpos/t^2

Wir sehen jetzt, dass die einzige freie Variable ist an der Zeit, t, und dann werden wir t für projvel zu lösen verwenden. Wir werden für t mit der quadratischen Formel lösen. Zuerst es auszusondern in a, b und c, dann lösen die Wurzeln.

Vor der Lösung, erinnern aber, dass wir die beste Lösung wollen, wo t am kleinsten ist, aber wir müssen sicherstellen, dass t nicht negativ ist (man kann etwas in der Vergangenheit nicht getroffen)

a  = relvel.relvel - speed^2
b  = 2*relpos.relvel
c  = relpos.relpos

h  = -b/(2*a)
k2  = h*h - c/a

if k2 < 0, then there are no roots and there is no solution
if k2 = 0, then there is one root at h
    if 0 < h then t = h
    else, no solution
if k2 > 0, then there are two roots at h - k and h + k, we also know r0 is less than r1.
    k  = sqrt(k2)
    r0 = h - k
    r1 = h + k
    we have the roots, we must now solve for the smallest positive one
    if 0<r0 then t = r0
    elseif 0<r1 then t = r1
    else, no solution

Wenn wir nun einen t Wert haben, können wir t wieder in die ursprüngliche Gleichung stecken und für die projvel

lösen

 projvel = relpos/t + relvel

Nun, in dem Sproß das Projektil, die resultierende globale Position und Geschwindigkeit für das Projektil ist

globalpos = origpos
globalvel = origvel + projvel

Und du bist fertig!

Meine Umsetzung meiner Lösung in Lua, wo vec * VEC stellt Vektor-Punktprodukt:

local function lineartrajectory(origpos,origvel,speed,targpos,targvel)
    local relpos=targpos-origpos
    local relvel=targvel-origvel
    local a=relvel*relvel-speed*speed
    local b=2*relpos*relvel
    local c=relpos*relpos
    if a*a<1e-32 then--code translation for a==0
        if b*b<1e-32 then
            return false,"no solution"
        else
            local h=-c/b
            if 0<h then
                return origpos,relpos/h+targvel,h
            else
                return false,"no solution"
            end
        end
    else
        local h=-b/(2*a)
        local k2=h*h-c/a
        if k2<-1e-16 then
            return false,"no solution"
        elseif k2<1e-16 then--code translation for k2==0
            if 0<h then
                return origpos,relpos/h+targvel,h
            else
                return false,"no solution"
            end
        else
            local k=k2^0.5
            if k<h then
                return origpos,relpos/(h-k)+targvel,h-k
            elseif -k<h then
                return origpos,relpos/(h+k)+targvel,h+k
            else
                return false,"no solution"
            end
        end
    end
end

Folgenden ist polar-Koordinaten-basierend Ziel code in C++.

Zu verwenden mit rechtwinkligen Koordinaten müssen Sie zuerst konvertieren Sie die Ziele relativ zu koordinieren, um den Winkel/Abstand, und die Ziele, die x/y-Geschwindigkeit/Winkel und Geschwindigkeit.

Die "speed" - Eingang ist die Geschwindigkeit des Projektils.Die Einheiten der Geschwindigkeit und targetSpeed spielen keine Rolle, da nur das Verhältnis der Geschwindigkeiten sind in der Berechnung verwendet werden.Die Ausgabe der Winkel der Geschoss soll auf Sie geschossen werden und der Abstand zu den kollisionspunkt.

Der Algorithmus ist aus dem source-code verfügbar unter http://www.turtlewar.org/ .


// C++
static const double pi = 3.14159265358979323846;
inline double Sin(double a) { return sin(a*(pi/180)); }
inline double Asin(double y) { return asin(y)*(180/pi); }

bool/*ok*/ Rendezvous(double speed,double targetAngle,double targetRange,
   double targetDirection,double targetSpeed,double* courseAngle,
   double* courseRange)
{
   // Use trig to calculate coordinate of future collision with target.
   //             c
   //
   //       B        A
   //
   // a        C        b
   //
   // Known:
   //    C = distance to target
   //    b = direction of target travel, relative to it's coordinate
   //    A/B = ratio of speed and target speed
   //
   // Use rule of sines to find unknowns.
   //  sin(a)/A = sin(b)/B = sin(c)/C
   //
   //  a = asin((A/B)*sin(b))
   //  c = 180-a-b
   //  B = C*(sin(b)/sin(c))

   bool ok = 0;
   double b = 180-(targetDirection-targetAngle);
   double A_div_B = targetSpeed/speed;
   double C = targetRange;
   double sin_b = Sin(b);
   double sin_a = A_div_B*sin_b;
   // If sin of a is greater than one it means a triangle cannot be
   // constructed with the given angles that have sides with the given
   // ratio.
   if(fabs(sin_a) <= 1)
   {
      double a = Asin(sin_a);
      double c = 180-a-b;
      double sin_c = Sin(c);
      double B;
      if(fabs(sin_c) > .0001)
      {
         B = C*(sin_b/sin_c);
      }
      else
      {
         // Sin of small angles approach zero causing overflow in
         // calculation. For nearly flat triangles just treat as
         // flat.
         B = C/(A_div_B+1);
      }
      // double A = C*(sin_a/sin_c);
      ok = 1;
      *courseAngle = targetAngle+a;
      *courseRange = B;
   }
   return ok;
}

Hier ist ein Beispiel, wo ich ausgedacht und eine Lösung für das Problem der Predictive Targeting implementiert einen rekursiven Algorithmus verwendet: http://www.newarteest.com/flash/targeting.html

Ich muss werden präsentiert einige der anderen Lösungen auszuprobieren, weil es effizienter, so scheint es, in einem Schritt zu berechnen, aber die Lösung kam ich mit war die Zielposition zu schätzen und Futtermittel, dass Ergebnis wieder in den Algorithmus macht eine neue genauere Schätzung, wiederholt mehrmals.

Für die erste Schätzung I „Feuer“ an dem aktuellen Position des Ziels und dann Trigonometrie verwenden, um zu bestimmen, wo das Ziel sein wird, wenn der Schuss die Position beschossen erreicht. Dann in der nächsten Iteration ich „Feuer“ in dieser neuen Position und bestimmen, wo das Ziel dieses Mal sein wird. Nach ca. 4 Wiederholungen ich innerhalb eines Pixels an Genauigkeit erhalten.

ich gehackt gerade diese Version für im 2D-Raum Ziel, ich habe es nicht getestet sehr gründlich noch nicht, aber es scheint zu funktionieren. Die Idee dahinter ist folgende:

Erstellen Sie einen Vektor senkrecht zu dem Vektor Zeigte von der Mündung zum Ziel. Für eine Kollision auftreten, sollten die Geschwindigkeiten des Ziels und das Projektil entlang dieses Vektors (Achse) gleich sein! Mit relativ einfachen Kosinus Zeug kam ich in diesem Code:

private Vector3 CalculateProjectileDirection(Vector3 a_MuzzlePosition, float a_ProjectileSpeed, Vector3 a_TargetPosition, Vector3 a_TargetVelocity)
{
    // make sure it's all in the horizontal plane:
    a_TargetPosition.y = 0.0f;
    a_MuzzlePosition.y = 0.0f;
    a_TargetVelocity.y = 0.0f;

    // create a normalized vector that is perpendicular to the vector pointing from the muzzle to the target's current position (a localized x-axis):
    Vector3 perpendicularVector = Vector3.Cross(a_TargetPosition - a_MuzzlePosition, -Vector3.up).normalized;

    // project the target's velocity vector onto that localized x-axis:
    Vector3 projectedTargetVelocity = Vector3.Project(a_TargetVelocity, perpendicularVector);

    // calculate the angle that the projectile velocity should make with the localized x-axis using the consine:
    float angle = Mathf.Acos(projectedTargetVelocity.magnitude / a_ProjectileSpeed) / Mathf.PI * 180;

    if (Vector3.Angle(perpendicularVector, a_TargetVelocity) > 90.0f)
    {
        angle = 180.0f - angle;
    }

    // rotate the x-axis so that is points in the desired velocity direction of the projectile:
    Vector3 returnValue = Quaternion.AngleAxis(angle, -Vector3.up) * perpendicularVector;

    // give the projectile the correct speed:
    returnValue *= a_ProjectileSpeed;

    return returnValue;
}

Ich habe viele Möglichkeiten gesehen, dieses Problem mathematisch zu lösen, aber dies war eine Komponente relevant für ein Projekt meiner Klasse erforderlich war in der High School zu tun, und nicht jeder in dieser Programmier Klasse hatte einen Hintergrund mit Kalkül oder sogar Vektoren was das betrifft, so habe ich eine Möglichkeit, dieses Problem mit mehr eines Programmier Ansatz zu lösen. Der Schnittpunkt wird genau sein, obwohl es einen Rahmen treffen kann später als in den mathematischen Berechnungen.

Bedenken Sie:

S = shooterPos, E = enemyPos, T = targetPos, Sr = shooter range, D = enemyDir
V = distance from E to T, P = projectile speed, Es = enemy speed

In der Standardimplementierung dieses Problems [S, E, P, Es, D] sind alle Givens und Sie lösen entweder T oder der Winkel, in dem zu finden, so zu schießen, dass Sie T Hit auf dem richtigen Timing.

Der Hauptaspekt dieser Methode das Problem zu lösen, ist die Reichweite des Schützen als Kreis betrachten alle möglichen Punkte umfasst, die zu einem bestimmten Zeitpunkt gedreht werden kann. Der Radius dieses Kreises ist gleich:

Sr = P*time

Wo die Zeit als Iteration einer Schleife berechnet wird.

So finden Sie den Abstand ein Feind der Zeit Iteration wir den Vektor erstellen gegeben Reisen:

V = D*Es*time

Nun, um tatsächlich zu lösen das Problem, das wir bei der einen Punkt finden, wollen, dass die Entfernung zum Ziel (T) zu unserem Schützen (S) kleiner ist als die Reichweite unserer Shooter (Sr). Hier ist ein wenig von einer Pseudo-Code Implementierung dieser Gleichung.

iteration = 0;
while(TargetPoint.hasNotPassedShooter)
{
    TargetPoint = EnemyPos + (EnemyMovementVector)
    if(distanceFrom(TargetPoint,ShooterPos) < (ShooterRange))
        return TargetPoint;
    iteration++
}

Ich habe eine public domain Unity C # Funktion hier:
http://ringofblades.com/Blades/Code/PredictiveAim.cs

Es ist für 3D, aber Sie können dies leicht für 2D ändern, indem sie die Vector3s mit Vector2s ersetzt und mit Ihrer unten Achse der Wahl für die Schwerkraft, wenn die Schwerkraft ist.

Falls die Theorie interessiert, ich durch die Ableitung der Mathematik gehen hier:
http://www.gamasutra.com/blogs/KainShin/20090515/83954 /Predictive_Aim_Mathematics_for_AI_Targeting.php

Grundsätzlich Kreuzung Konzept ist nicht wirklich hier gebraucht, so weit Sie Wurfbewegung verwenden, Sie müssen nur Treffer in einem bestimmten Winkel und instantiate zu der Zeit so zu schießen, dass Sie die genaue Entfernung von Ihrem Ziel aus der get Quelle und dann, wenn Sie den Abstand haben, können Sie die entsprechende Geschwindigkeit berechnen, mit denen sie um Schuss sollte das Ziel zu treffen.

Der folgende Link macht teh Konzept klar und gilt als hilfreich, helfen kann: Projektil Bewegung immer ein sich bewegendes Ziel zu treffen

packte ich eine der Lösungen von hier, aber keiner von ihnen berücksichtigen Bewegung des Schützen. Wenn Ihr Shooter bewegt, möchten Sie vielleicht, dass berücksichtigen (wie die Geschwindigkeit des Shooter sollte auf Ihre Kugel der Geschwindigkeit, wenn Sie Feuer hinzugefügt werden). Wirklich alles, was Sie tun müssen, ist Ihre Schütze Geschwindigkeit von der Geschwindigkeit des Ziels subtrahiert. Also, wenn Sie broofa den angezeigten Code verwenden (was ich empfehlen würde), ändern Sie die Zeilen

  tvx = dst.vx;
  tvy = dst.vy;

  tvx = dst.vx - shooter.vx;
  tvy = dst.vy - shooter.vy;

und Sie sollten alle eingestellt werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow