Juego 2d: dispara a un objective en movimiento al predecir la intersección del proyectil y la unidad

De acuerdo, todo esto tiene lugar en un mundo 2D agradable y simple … 🙂

Supongamos que tengo un objeto estático A en la posición Apos y un objeto B en movimiento lineal en Bpos con bVelocity, y una munición redonda con velocidad Avelocidad …

¿Cómo averiguaría el ángulo que tiene que disparar A, para golpear B, teniendo en cuenta la velocidad lineal de B y la velocidad de la munición de A?

En este momento, el objective está en la posición actual del objeto, lo que significa que para cuando el proyectil llega allí, la unidad se ha movido a posiciones más seguras 🙂

    Primero rote los ejes para que AB esté vertical (haciendo una rotación)

    Ahora, divida el vector de velocidad de B en los componentes xey (digamos Bx y By). Puedes usar esto para calcular los componentes xey del vector al que debes disparar.

    B --> Bx | | V By Vy ^ | | A ---> Vx 

    Necesita Vx = Bx y Sqrt(Vx*Vx + Vy*Vy) = Velocity of Ammo .

    Esto debería darle el vector que necesita en el nuevo sistema. Transforma al sistema anterior y termines (haciendo una rotación en la otra dirección).

    Escribí una subrutina de apunte para xtank hace un tiempo. Trataré de explicar cómo lo hice.

    Descargo de responsabilidad: puedo haber cometido uno o más errores tontos en cualquier lugar aquí; Solo bash reconstruir el razonamiento con mis habilidades matemáticas oxidadas. Sin embargo, voy a ir al grano primero, ya que esta es una sesión de preguntas y respuestas de progtwigción en lugar de una clase de matemáticas 🙂

    Cómo hacerlo

    Todo se reduce a resolver una ecuación cuadrática de la forma:

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

    Tenga en cuenta que por sqr quiero decir cuadrado, en lugar de raíz cuadrada. Use los siguientes valores:

     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) 

    Ahora podemos ver al discriminante para determinar si tenemos una posible solución.

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

    Si el discriminante es menor que 0, olvídate de golpear al objective: tu proyectil nunca podrá llegar a tiempo. De lo contrario, mira dos soluciones candidatas:

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

    Tenga en cuenta que si disc == 0 entonces t1 y t2 son iguales.

    Si no hay otras consideraciones, como obstáculos intermedios, simplemente elija el valor positivo más pequeño. (¡Los valores negativos de t requerirían disparar hacia atrás en el tiempo de uso!)

    Sustituye el valor t elegido de nuevo en las ecuaciones de posición del objective para obtener las coordenadas del punto principal al que debes apuntar:

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

    Derivación

    En el tiempo T, el proyectil debe ser una distancia (euclidiana) del cañón igual al tiempo transcurrido multiplicado por la velocidad del proyectil. Esto da una ecuación para un círculo, paramétrica en tiempo transcurrido.

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

    De manera similar, en el tiempo T, el objective se ha movido a lo largo de su vector por tiempo multiplicado por su velocidad:

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

    El proyectil puede alcanzar el objective cuando su distancia del cañón coincide con la distancia del proyectil.

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

    ¡Maravilloso! Sustituyendo las expresiones por target.X y target.Y da

     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) 

    Sustituir el otro lado de la ecuación le da a esto:

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

    … restando sqr(t * projectile_speed) de ambos lados y dándole la vuelta:

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

    … ahora resuelve los resultados de cuadrar las subexpresiones …

     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 

    … y agrupar términos similares …

     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 

    … luego combinarlos …

     (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 una ecuación cuadrática estándar en t . Encontrar los ceros reales positivos de esta ecuación le da a la (cero, uno o dos) posibles ubicaciones de golpe, lo que se puede hacer con la fórmula cuadrática:

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

    +1 a la excelente respuesta de Jeffrey Hantin aquí. Busqué en Google y encontré soluciones que eran demasiado complejas o no específicamente sobre el caso en el que estaba interesado (proyectil de velocidad constante simple en espacio 2D). Era exactamente lo que necesitaba para producir la solución autónoma de JavaScript a continuación.

    El único punto que agregaría es que hay un par de casos especiales que debes observar además de que el discriminante es negativo:

    • “a == 0”: ocurre si el objective y el proyectil viajan a la misma velocidad. (la solución es lineal, no cuadrática)
    • “a == 0 y b == 0”: si tanto el objective como el proyectil son estacionarios. (no hay solución a menos que c == 0, es decir, src y dst son el mismo punto).

    Código:

     /** * 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) * * Eg * >>> 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 tiene una buena solución para este problema, aunque su derivación es demasiado complicada. Aquí hay una forma más clara de derivarlo con parte del código resultante en la parte inferior.

    Usaré xy para representar el producto vector punto, y si una cantidad de vector es cuadrada, significa que estoy salpicándome con ella misma.

     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 

    Sabemos que la posición del proyectil y el objective con respecto al tiempo t se puede describir con algunas ecuaciones.

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

    Queremos que estos sean iguales entre sí en algún punto (el punto de intersección), así que pongamos iguales entre sí y resuelva la variable libre, projvel .

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

    Olvidémonos de la noción de origen y la posición / velocidad objective. En cambio, trabajemos en términos relativos, ya que el movimiento de una cosa es relativo a otra. En este caso, lo que tenemos ahora es relpos = targetpos - originpos y relvel = targetvel - originvel

     projvel = relpos/t + relvel 

    No sabemos qué es projvel , pero sí sabemos que queremos que projvel.projvel sea ​​igual a speed^2 , por lo que projvel.projvel ambos lados y obtenemos

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

    Ahora podemos ver que la única variable libre es el tiempo, t , y luego usaremos t para resolver projvel . Resolveremos para t con la fórmula cuadrática. Primero sepárelo en a , c , luego resuelva para las raíces.

    Sin embargo, antes de resolver, recuerde que queremos la mejor solución donde t es la más pequeña, pero debemos asegurarnos de que t no sea negativo (no puede golpear algo en el pasado)

     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 

    Ahora, si tenemos un valor t , podemos volver a conectarlo a la ecuación original y resolver el projvel

      projvel = relpos/t + relvel 

    Ahora, para disparar al proyectil, la posición y velocidad global resultante para el proyectil es

     globalpos = origpos globalvel = origvel + projvel 

    ¡Y tu estas listo!

    Mi implementación de mi solución en Lua, donde vec * vec representa vector dot product:

     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 

    A continuación se muestra el código de orientación basado en coordenadas polares en C ++.

    Para usar con coordenadas rectangulares, primero deberías convertir la coordenada relativa de los objectives en ángulo / distancia, y los objectives x / y velocidad en ángulo / velocidad.

    La entrada de “velocidad” es la velocidad del proyectil. Las unidades de la velocidad y targetSpeed ​​son irrelevantes, ya que solo la relación de velocidades se usa en el cálculo. La salida es el ángulo en que debe dispararse el proyectil y la distancia al punto de colisión.

    El algoritmo proviene del código fuente disponible en 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 // // BA // // 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-ab // 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-ab; 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; } 

    Aquí hay un ejemplo en el que ideé e implementé una solución al problema de la orientación predictiva utilizando un algoritmo recursivo: http://www.newarteest.com/flash/targeting.html

    Tendré que probar algunas de las otras soluciones presentadas porque me parece más eficiente calcularlas en un solo paso, pero la solución que surgió fue para estimar la posición objective y alimentar el resultado con el algoritmo para crear un nuevo estimación más precisa, repitiendo varias veces.

    Para la primera estimación, “disparo” en la posición actual del objective y luego uso la trigonometría para determinar dónde estará el objective cuando el disparo scope la posición disparada. Luego, en la siguiente iteración, “disparo” en esa nueva posición y determino dónde estará el objective esta vez. Después de aproximadamente 4 repeticiones, obtengo un pixel de precisión.

    Acabo de hackear esta versión para apuntar en 2d espacio, no lo probé muy a fondo todavía, pero parece funcionar. La idea detrás de esto es esta:

    Crea un vector perpendicular al vector apuntando desde el hocico hacia el objective. Para que se produzca una colisión, ¡las velocidades del objective y del proyectil a lo largo de este vector (eje) deberían ser las mismas! Utilizando coseno bastante simple llegué a este código:

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

    He visto muchas maneras de resolver este problema matemáticamente, pero este era un componente relevante para un proyecto que se requería que mi clase hiciera en la escuela secundaria, y no todos en esta clase de progtwigción tenían antecedentes con cálculo, o incluso vectores para el caso. , así que creé una manera de resolver este problema con un enfoque de progtwigción más. El punto de intersección será preciso, aunque puede alcanzar 1 fotogtwig más tarde que en los cálculos matemáticos.

    Considerar:

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

    En la implementación estándar de este problema [S, E, P, Es, D] son ​​todos dados y usted está resolviendo bien encontrar T o el ángulo en el que disparar para que golpee T en el momento adecuado.

    El aspecto principal de este método para resolver el problema es considerar el scope del tirador como un círculo que abarca todos los puntos posibles que se pueden disparar en cualquier momento dado. El radio de este círculo es igual a:

     Sr = P*time 

    Donde el tiempo se calcula como una iteración de un ciclo.

    Por lo tanto, para encontrar la distancia que viaja un enemigo dada la iteración de tiempo, creamos el vector:

     V = D*Es*time 

    Ahora, para resolver realmente el problema, queremos encontrar un punto en el que la distancia desde el objective (T) hasta nuestro tirador (S) sea menor que el scope de nuestro tirador (Sr). Aquí hay algo de implementación de pseudocódigo de esta ecuación.

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

    Hice una función de dominio público Unity C # aquí:
    http://ringofblades.com/Blades/Code/PredictiveAim.cs

    Es para 3D, pero puede modificarlo fácilmente para 2D reemplazando el Vector3s con Vector2s y utilizando el eje descendente elegido para la gravedad si hay gravedad.

    En caso de que la teoría te interese, paso por la derivación de las matemáticas aquí:
    http://www.gamasutra.com/blogs/KainShin/20090515/83954/Predictive_Aim_Mathematics_for_AI_Targeting.php

    Básicamente, el concepto de intersección no es realmente necesario aquí, en la medida en que use movimiento de proyectil, solo necesita golpear en un ángulo particular e instanciar en el momento del disparo para obtener la distancia exacta de su objective desde la Fuente y luego una vez que tenga la distancia, puede calcular la velocidad adecuada con la que debería disparar para poder alcanzar el objective.

    El siguiente enlace aclara el concepto y se considera útil, podría ayudar: Movimiento del proyectil para golpear siempre un objective en movimiento

    Agarré una de las soluciones de aquí, pero ninguna de ellas tiene en cuenta el movimiento del tirador. Si su tirador se está moviendo, es posible que desee tener esto en cuenta (ya que la velocidad del tirador se debe agregar a la velocidad de su bala cuando dispare). Realmente todo lo que necesitas hacer es restar la velocidad de tu tirador de la velocidad del objective. Entonces, si está usando el código de broofa anterior (que recomendaría), cambie las líneas

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

    a

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

    y deberías estar todo listo.