Gra 2d: strzelaj do ruchomego celu, przewidując przecięcie pocisku i jednostki

Jakiś czas temu napisałem podprogram celowania dla xtank. Postaram się wyjaśnić, jak to zrobiłem.

Zastrzeżenie: mogłem popełnić jeden lub więcej głupich błędów gdziekolwiek tutaj; próbuję tylko zrekonstruować rozumowanie za pomocą moich zardzewiałych umiejętności matematycznych. Jednak najpierw przejdę do sedna, ponieważ jest to Programowanie Q&A zamiast klasy matematycznej: -) {]}

Jak to zrobić

Sprowadza się do rozwiązania równania kwadratowego postaci:

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

Zauważ, że przez sqr mam na myśli kwadrat, w przeciwieństwie do pierwiastka kwadratowego. Użyj następujących wartości:

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)

Teraz możemy spojrzeć na dyskryminującego, aby określić, czy mamy możliwe rozwiązanie.

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

Jeśli rozróżniacz jest mniejszy niż 0, zapomnij o trafieniu celu -- twój pocisk nigdy nie dotrze tam na czas. W przeciwnym razie spójrz na dwa kandydujące rozwiązania:

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

Zauważ, że jeśli disc == 0 to t1 i t2 są równe.

Jeśli nie ma inne względy, takie jak interweniowanie przeszkód, po prostu wybierz mniejszą wartość dodatnią. (Ujemne T wartości wymagałyby odpalenia w czasie do użycia!)

Zastąp wybraną wartośćt z powrotem do równań pozycji celu, aby uzyskać współrzędne punktu wiodącego, na który powinieneś celować:

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

Wyprowadzenie

W czasie T pocisk musi znajdować się w odległości (euklidesowej) od armaty równej upływającemu czasowi pomnożonemu przez prędkość pocisku. Daje to równanie dla okręgu, parametryczne w czasie.

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

Podobnie, w czasie T, cel poruszał się wzdłuż swojego wektora przez czas pomnożony przez jego prędkość:

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

Pocisk może trafić w cel, gdy jego odległość od armaty odpowiada odległości pocisku.

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

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)

Podstawienie drugiej strony równania daje to:

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

... odejmowanie sqr(t * projectile_speed) z obu stron i odwracanie:

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

... teraz rozwiąż wyniki wyrównania podekspresji ...

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

... i grupować podobne pojęcia ...

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

... następnie połącz je ...

(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

... podanie standardowego równania kwadratowego w t . Znalezienie dodatnich zer rzeczywistych tego równania daje (zero, jeden lub dwa) możliwe miejsca trafienia, co można zrobić za pomocą kwadratu formuła:

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

+1 na doskonałą odpowiedź Jeffreya Hantina tutaj. Szukałem w googlach i znalazłem rozwiązania, które były albo zbyt złożone, albo nie konkretnie w sprawie, którą byłem zainteresowany (prosty pocisk o stałej prędkości w przestrzeni 2D.) Jego było dokładnie to, czego potrzebowałem, aby wyprodukować samodzielne rozwiązanie JavaScript poniżej.

Jedna kwestia, którą chciałbym dodać jest to, że jest kilka szczególnych przypadków, na które trzeba uważać, oprócz dyskryminującego jest negatywna:

• "a = = 0": występuje, jeśli cel i pocisk poruszają się z tą samą prędkością. (rozwiązanie jest liniowe, nie kwadratowe)
• "A = = 0 i b = = 0": jeśli zarówno cel, jak i pocisk są nieruchome. (brak rozwiązania, chyba że c = = 0, tzn. src i dst są tym samym punktem.)

Kod:

/**
 * 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 ma dobre rozwiązanie tego problemu, choć jego wyprowadzenie jest zbyt skomplikowane. Oto czystszy sposób wyprowadzenia go z częścią wynikowego kodu na dole.

Użyję x.y do reprezentowania iloczynu wektorowego kropki, a jeśli wielkość wektorowa jest kwadratowa, oznacza to, że zaznaczam ją ze sobą.

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

Wiemy, że położenie pocisku i celu w odniesieniu do czasu t można opisać za pomocą pewnych równań.

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

Chcemy są one równe sobie w pewnym punkcie (punkcie przecięcia), więc ustawmy je równe sobie i rozwiążmy dla zmiennej swobodnej, projvel.

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

Zapomnijmy o pojęciu pochodzenia i pozycji celu/prędkości. Zamiast tego, pracujmy w kategoriach względnych, ponieważ ruch jednej rzeczy jest względem drugiej. W tym przypadku mamy teraz relpos = targetpos - originpos i relvel = targetvel - originvel

projvel = relpos/t + relvel

Nie wiemy, czym jest projvel, ale wiemy, że chcemy projvel.projvel być równi speed^2, więc wyrównamy obie strony i otrzymamy

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

Widzimy teraz, że jedyną wolną zmienną jest czas, t, a następnie użyjemy t do rozwiązania dla projvel. Rozwiążemy dla t wzorem kwadratowym. Najpierw rozdziel go na a, b i c, następnie rozwiąż dla korzeni.

Zanim jednak rozwiążemy, pamiętajmy, że chcemy najlepszego rozwiązania, gdzie {[9] } jest najmniejsze, ale musimy się upewnić, że t nie jest ujemne (nie można trafić czegoś w przeszłość)

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

Teraz, jeśli mamy t wartość, możemy podłączyć t z powrotem do oryginalnego równania i rozwiązać dla projvel

 projvel = relpos/t + relvel

Teraz, aby wystrzelić pocisk, wypadkowa globalna pozycja i prędkość dla pocisku wynosi {[29]]}

globalpos = origpos
globalvel = origvel + projvel

Moja implementacja mojego rozwiązania w Lua, gdzie vec * vec reprezentuje iloczyn wektorowy kropki:

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

Poniżej znajduje się kod oparty na współrzędnych biegunowych w C++.

Aby użyć współrzędnych prostokątnych, należy najpierw przeliczyć współrzędne względne celów na kąt/odległość, a prędkość celów x / y na kąt/prędkość.

Wejście "speed" to prędkość pocisku. Jednostki prędkości i prędkości targetSpeed są nieistotne, ponieważ w obliczeniach wykorzystuje się tylko stosunek prędkości. Wyjściem jest kąt, w który pocisk powinien zostać wystrzelony oraz odległość do punkt kolizji.

Algorytm pochodzi z kodu źródłowego dostępnego pod adresem 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;
}

Oto przykład, w którym opracowałem i zaimplementowałem rozwiązanie problemu kierowania predykcyjnego za pomocą algorytmu rekurencyjnego: http://www.newarteest.com/flash/targeting.html

Będę musiał wypróbować niektóre z innych przedstawionych rozwiązań, ponieważ wydaje się bardziej efektywne obliczenie go w jednym kroku, ale rozwiązaniem, które wymyśliłem, było oszacowanie pozycji docelowej i podanie tego wyniku z powrotem do algorytmu, aby dokonać nowego dokładniejszego oszacowania, powtarzając kilka razy.

Dla pierwszego oszacowania "strzelam" w aktualną pozycję celu, a następnie używam trygonometrii, aby określić, gdzie cel będzie, gdy strzał osiągnie pozycję, w którą strzelał. Następnie w kolejnej iteracji "strzelam" w tę nową pozycję i ustalam, gdzie tym razem będzie cel. Po około 4 powtórzeniach dostaję się w piksel dokładności.

Właśnie zhakowałem tę wersję za celowanie w przestrzeni 2d, nie testowałem jej jeszcze bardzo dokładnie, ale wydaje się, że działa. Idea stojąca za tym jest taka:

Stwórz wektor prostopadły do wektora skierowanego od kufy do celu. Aby doszło do kolizji, prędkości celu i pocisku wzdłuż tego wektora (osi) powinny być takie same! Używając dość prostych cosinusów doszedłem do tego kodu:

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

Widziałem wiele sposobów na rozwiązanie tego problemu matematycznie, ale był to element istotny dla projektu, który moja klasa musiała wykonać w szkole średniej, a nie każdy w tej klasie programowania miał doświadczenie z rachunkami, a nawet wektorami, więc stworzyłem sposób na rozwiązanie tego problemu z większym podejściem do programowania. Punkt przecięcia będzie dokładny, choć może trafić o 1 klatkę później niż w matematyce obliczenia.

Rozważmy:

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

W standardowej implementacji tego problemu [S,E,P,Es,D] są wszystkie podane i rozwiązujesz albo znaleźć T lub kąt, pod którym strzelać tak, że trafisz T w odpowiednim momencie.

Głównym aspektem tej metody rozwiązywania problemu jest rozważenie zasięgu strzelca jako okręgu obejmującego wszystkie możliwe punkty, które mogą być wystrzelone w danym momencie. Promień tego okręgu jest równy:

Sr = P*time

Gdzie czas jest obliczana jako iteracja pętli.

Tak więc, aby znaleźć odległość, jaką pokonuje wróg biorąc pod uwagę iterację czasu, tworzymy wektor:

V = D*Es*time

Teraz, aby faktycznie rozwiązać problem chcemy znaleźć punkt, w którym odległość od celu (T) do naszego strzelca (S) jest mniejsza niż zasięg naszego strzelca (Sr). Oto nieco pseudokodowa implementacja tego równania.

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

Zrobiłem tutaj funkcję public domain Unity C# :
http://ringofblades.com/Blades/Code/PredictiveAim.cs

Jest to dla 3D, ale możesz łatwo zmodyfikować to dla 2D, zastępując Vector3s na Vector2s i używając wybranej przez siebie dolnej osi dla grawitacji, jeśli istnieje grawitacja.

W przypadku, gdy teoria Cię interesuje, przechodzę przez wyprowadzenie matematyki here:
http://www.gamasutra.com/blogs/KainShin/20090515/83954/Predictive_Aim_Mathematics_for_AI_Targeting.php

Zasadniczo, koncepcja przecięcia nie jest tak naprawdę potrzebna tutaj, o ile używasz ruchu pocisku, wystarczy uderzyć pod określonym kątem i utworzyć instancję w czasie strzelania, aby uzyskać dokładną odległość celu od źródła, a następnie po uzyskaniu odległości, można obliczyć odpowiednią prędkość, z jaką powinien strzelać, aby trafić w cel.

Poniższy link wyjaśnia koncepcję teh i jest uważany za pomocny, może pomoc: ruch pocisku, aby zawsze trafić w ruchomy cel

Chwyciłem stąd jedno z rozwiązań, ale żadne nie bierze pod uwagę ruchu strzelca. Jeśli twój strzelec się porusza, możesz wziąć to pod uwagę (ponieważ prędkość strzelca powinna być dodana do prędkości pocisku podczas strzału). Naprawdę wszystko, co musisz zrobić, to odjąć prędkość strzelca od prędkości celu. Więc jeśli używasz kodu broofa powyżej( co polecam), Zmień linie

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

Do

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

And you should be all gotowi.