Gioco 2D:sparare a un bersaglio in movimento prevedendo l'intersezione tra proiettile e unità

StackOverflow https://stackoverflow.com/questions/2248876

  •  20-09-2019
  •  | 
  •  

Domanda

Ok, tutto questo si svolge in un mondo 2D carino e semplice...:)

Supponiamo di avere un oggetto statico A nella posizione Apos, e un oggetto B in movimento lineare in Bpos con bVelocity e un proiettile con velocità Avelocity...

Come potrei scoprire l'angolo che A deve sparare per colpire B, tenendo conto della velocità lineare di B e della velocità delle munizioni di A?

In questo momento il mio obiettivo è la posizione attuale dell'oggetto, il che significa che nel momento in cui il mio proiettile arriva lì l'unità si sarà spostata in posizioni più sicure :)

È stato utile?

Soluzione

Prima ruotare gli assi in modo che AB sia verticale (facendo una rotazione)

Ora, dividere il vettore velocità B in componenti xey (dire Bx e By). È possibile utilizzare questo per calcolare le componenti X e Y del vettore è necessario sparare. 

B --> Bx
|
|
V

By


Vy
^
|
|
A ---> Vx

È necessario Vx = Bx e Sqrt(Vx*Vx + Vy*Vy) = Velocity of Ammo.

Questo dovrebbe dare il vettore è necessario nel nuovo sistema. Trasformare di nuovo al vecchio sistema e si è fatto (facendo una rotazione nella direzione opposta).

Altri suggerimenti

ho scritto una subroutine puntando xtank un po 'indietro. Cercherò di lay out come ho fatto.

Avviso: Posso aver fatto uno o più stupidi errori in tutto qui; Sto solo cercando di ricostruire il ragionamento con le mie abilità matematiche arrugginite. Tuttavia, ti taglio per la caccia prima, dal momento che si tratta di una programmazione Q & A invece di una classe di matematica: -)

Come fare

Si riduce a risolvere un'equazione di secondo grado della forma: 

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

Si noti che sqr intendo quadrato, al contrario di radice quadrata. Utilizzare i seguenti valori: 

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)

Ora possiamo guardare la discriminante per determinare se abbiamo una possibile soluzione. 

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

Se il discriminante è minore di 0, dimenticare colpire il bersaglio - il vostro proiettile non potrà mai arrivare in tempo. In caso contrario, guarda due soluzioni candidate: 

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

Si noti che se disc == 0 poi t1 e t2 sono uguali.

Se non ci sono altre considerazioni, come intervenire ostacoli, è sufficiente scegliere il valore più piccolo positivo. (Negativo t valori richiederebbero sparare a ritroso nel tempo per usare!)

sostituire il valore t scelto di nuovo in equazioni di posizione del bersaglio per ottenere le coordinate del punto di primo piano che si dovrebbe puntare a: 

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

Derivazione

Al tempo T, il proiettile deve essere un (euclideo) distanza dal cannone pari al tempo trascorso moltiplicato per la velocità del proiettile. Questo dà un'equazione per un cerchio, parametrico nel tempo trascorso. 

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

Analogamente, al tempo T, il bersaglio è spostato lungo il suo vettore da tempo per la sua velocità: 

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

Il proiettile può colpire il bersaglio, quando la sua distanza dal cannone corrisponde la distanza del proiettile. 

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

Meraviglioso! Sostituendo le espressioni per target.X e target.Y dà 

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)

Sostituendo l'altro lato dell'equazione dà questa: 

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

... sottraendo sqr(t * projectile_speed) da entrambi i lati e lanciando in giro: 

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

... ora risolvere i risultati della quadratura del sottoespressioni ... 

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

... e di gruppo termini simili ... 

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

... poi combinarli ... 

(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

... dando un'equazione quadratica standard t . Trovare i zeri reali positivi di questa equazione fornisce la (zero, uno o due) possibili posizioni hit, che può essere fatto con la formula quadratica: 

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

+1 sul eccellente risposta di Jeffrey Hantin qui. Googled intorno e trovato soluzioni che erano o troppo complessi o non specificatamente sul caso mi interessava (semplice proiettile velocità costante nello spazio 2D.) La sua era esattamente quello che mi serviva per produrre la soluzione JavaScript autosufficiente sotto.

L'unico punto che vorrei aggiungere è che ci sono un paio di particolari casi si deve guardare per in aggiunta alla discriminante essere negativo:

  • "a == 0": si verifica se destinazione e proiettili stanno viaggiando alla stessa velocità. (Soluzione è lineare, non è quadratica)
  • "a == 0 e b == 0": se bersaglio e proiettile sono stazionari. (Senza soluzione se c == 0, cioè src e dst sono stesso punto.)

Codice: 

/**
 * 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 ha una bella soluzione per questo problema, anche se il suo derivazione è eccessivamente complicato. Ecco un modo più pulito di derivare con una parte del codice risultante in basso.

sarò con X.Y per rappresentare vettore prodotto scalare, e se una grandezza vettoriale è squadrato, significa che sto punteggiano con sé. 

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

Sappiamo che la posizione del proiettile e bersaglio rispetto al t tempo può essere descritto con alcune equazioni. 

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

Vogliamo che questi siano uguali tra loro ad un certo punto (il punto di intersezione), quindi cerchiamo di loro set uguali tra loro e risolvere per la variabile libera, projvel. 

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

Lasciamo perdere la nozione di origine e target di posizione / velocità. Invece, lavoriamo in termini relativi dal movimento di una cosa è relativa ad un altro. In questo caso, ciò che oggi abbiamo è relpos = targetpos - originpos e relvel = targetvel - originvel 

projvel = relpos/t + relvel

Non sappiamo che cosa è projvel, ma sappiamo che vogliamo projvel.projvel l'essere uguale a speed^2, quindi dovremo quadrare entrambi i lati e otteniamo 

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

Ora possiamo vedere che l'unica variabile libera è giunto il momento, t, e poi useremo t risolvere per projvel. Noi risolveranno per t con la formula quadratica. In primo luogo separare fuori in a, b e c, poi risolvere per le radici.

Prima di risolvere, però, ricordare che noi vogliamo la soluzione migliore in cui t è più piccolo, ma abbiamo bisogno di fare in modo che t non è negativo (non si può colpire qualcosa in passato) 

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

Ora, se abbiamo un valore t, siamo in grado di collegare t indietro nell'equazione originale e risolvere per il projvel 

 projvel = relpos/t + relvel

Ora, per le riprese del proiettile, la posizione globale risultante e la velocità del proiettile è 

globalpos = origpos
globalvel = origvel + projvel

E il gioco è fatto!

La mia realizzazione della mia soluzione in Lua, dove vec * vec rappresenta prodotto scalare: 

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

Di seguito è riportato il codice di mira basato sulle coordinate polari in C++.

Per utilizzare le coordinate rettangolari è necessario prima convertire le coordinate relative dei target in angolo/distanza e la velocità x/y dei target in angolo/velocità.

L'input "velocità" è la velocità del proiettile.Le unità di velocità e targetSpeed ​​sono irrilevanti, poiché nel calcolo viene utilizzato solo il rapporto tra le velocità.L'output è l'angolo con cui dovrebbe essere sparato il proiettile e la distanza dal punto di collisione.

L'algoritmo proviene dal codice sorgente disponibile su 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;
}

Ecco un esempio in cui ho ideato e realizzato una soluzione al problema della previsione mira utilizzando un algoritmo ricorsivo: http://www.newarteest.com/flash/targeting.html

Dovrò provare alcune delle altre soluzioni presentate perché sembra più efficiente per calcolarlo in un solo passaggio, ma la soluzione mi è venuta è stato quello di stimare la posizione di destinazione e dei mangimi che risultano nuovamente dentro l'algoritmo a fare una nuova stima più accurata, ripetendo più volte.

Per la prima stima I "fuoco" alla posizione corrente del bersaglio e poi usare la trigonometria per determinare dove l'obiettivo sarà quando il colpo raggiunge la posizione sparato. Poi nella prossima iterazione I "fuoco" in quella nuova posizione e determinare dove l'obiettivo sarà questa volta. Dopo circa 4 ripetizioni ricevo all'interno di un pixel di precisione.

Ho appena hackerato questa versione per prendere la mira nello spazio 2d, non ho la prova molto bene ancora, ma sembra funzionare. L'idea alla base è questa:

Crea un vettore perpendicolare al puntamento vettore dal muso al bersaglio. Per una collisione si verifichi, le velocità del bersaglio e il proiettile lungo questo vettore (asse) dovrebbero essere uguali! Utilizzando roba coseno abbastanza semplice Sono arrivato a questo codice: 

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;
}

Ho visto molti modi per risolvere questo problema matematicamente, ma questa è stata una componente rilevante per un progetto la mia classe è stato richiesto di fare al liceo, e non tutti in questa classe di programmazione ha avuto uno sfondo con il calcolo, o anche vettori se è per questo, così ho creato un modo per risolvere questo problema con più di un approccio di programmazione. Il punto di intersezione sarà accurata, anche se può colpire 1 frame più tardi nei calcoli matematici.

Si consideri: 

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

Nell'implementazione standard di questo problema [S, E, P, Es, D] sono tutti i dati di fatto e si sta risolvendo sia per trovare T o l'angolo in cui a sparare in modo da colpire T alla giusta tempistica.

L'aspetto principale di questo metodo per risolvere il problema è quello di considerare la gamma del tiratore come un cerchio che comprende tutti i possibili punti che può essere sparato in un dato momento. Il raggio di questo cerchio è pari a: 

Sr = P*time

Dove il tempo è calcolato come iterazione di un ciclo.

Così per trovare la distanza un viaggio nemico dato il tempo di iterazione che creiamo il vettore: 

V = D*Es*time

Ora, per risolvere realmente il problema vogliamo trovare un punto in cui la distanza dal bersaglio (T) al nostro tiratore (S) è inferiore alla gamma della nostra tiratore (Sr). Ecco un po 'di un'implementazione pseudocodice di questa equazione. 

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

Ho fatto una funzione # Unità C di dominio pubblico qui:
http://ringofblades.com/Blades/Code/PredictiveAim.cs

E 'per il 3D, ma si può facilmente modificare questo per il 2D sostituendo il Vector3s con Vector2s e utilizzando le assi giù di scelta per gravità se non v'è la gravità.

Nel caso in cui gli interessi di teoria si, cammino attraverso la derivazione della matematica qui:
http://www.gamasutra.com/blogs/KainShin/20090515/83954 /Predictive_Aim_Mathematics_for_AI_Targeting.php

In sostanza, il concetto di intersezione non è realmente necessario qui, Per quanto si sta utilizzando moto del proiettile, basta colpire ad un angolo particolare e creare un'istanza al momento dello scatto in modo da ottenere la distanza esatta del bersaglio dalla fonte e poi una volta che hai la distanza, è possibile calcolare la velocità appropriata con cui dovrebbe girato al fine di colpire il bersaglio.

Il seguente link rende teh concetto chiaro ed è considerato utile, potrebbe aiutare: Proiettile movimento per sempre colpire un bersaglio in movimento

Ho afferrato una delle soluzioni da qui, ma nessuno di loro prendo in considerazione il movimento del tiratore. Se il tiratore è in movimento, si potrebbe desiderare di prendere in considerazione (come la velocità del tiratore deve essere aggiunto alla velocità del vostro proiettile quando il fuoco). Davvero tutto quello che dovete fare è sottrarre la velocità del vostro tiratore dalla velocità del bersaglio. Quindi, se si sta utilizzando il codice di broofa sopra (che consiglio), modificare le linee 

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

a 

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

e si dovrebbe essere tutto a posto.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top