2d игра :ведите огонь по движущейся цели, предсказывая пересечение снаряда и единицы
-
20-09-2019 - |
Вопрос
Итак, все это происходит в приятном и простом 2D-мире...:)
Предположим, у меня есть статический объект A в положении Apos, и линейно движущийся объект B в положении Bpos со скоростью BV, и боекомплект со скоростью Avelocity...
Как бы я узнал угол, под которым A должен стрелять, чтобы поразить B, принимая во внимание линейную скорость B и скорость боеприпасов A ?
Прямо сейчас цель нацелена на текущее положение объекта, что означает, что к тому времени, когда мой снаряд попадет туда, юнит переместится на более безопасные позиции :)
Решение
Сначала поверните оси так, чтобы AB было вертикальным (выполнив поворот)
Теперь разделите вектор скорости B на компоненты x и y (скажем, Bx и By).Вы можете использовать это для вычисления компонент x и y вектора, по которому вам нужно стрелять.
B --> Bx
|
|
V
By
Vy
^
|
|
A ---> Vx
Вам нужно Vx = Bx
и Sqrt(Vx*Vx + Vy*Vy) = Velocity of Ammo
.
Это должно дать вам вектор, который вам нужен в новой системе.Вернитесь к старой системе, и все готово (выполнив поворот в другом направлении).
Другие советы
Я написал подпрограмму наведения для xtank ( экстанк ) некоторое время назад.Я попытаюсь рассказать, как я это сделал.
Отказ от ответственности: Возможно, я допустил одну или несколько глупых ошибок где-нибудь здесь;Я просто пытаюсь восстановить ход рассуждений с помощью моих пошатнувшихся математических навыков.Однако сначала я перейду к сути, поскольку это вопросы и ответы по программированию, а не урок математики :-)
Как это сделать
Это сводится к решению квадратного уравнения вида:
a * sqr(x) + b * x + c == 0
Обратите внимание, что по sqr
Я имею в виду квадратный, в отличие от квадратного корня.Используйте следующие значения:
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)
Теперь мы можем посмотреть на дискриминант, чтобы определить, есть ли у нас возможное решение.
disc := sqr(b) - 4 * a * c
Если дискриминант меньше 0, забудьте о попадании в цель - ваш снаряд никогда не сможет попасть туда вовремя.В противном случае рассмотрим два возможных решения:
t1 := (-b + sqrt(disc)) / (2 * a)
t2 := (-b - sqrt(disc)) / (2 * a)
Обратите внимание, что если disc == 0
тогда t1
и t2
равны.
Если нет других соображений, таких как возникающие препятствия, просто выберите меньшее положительное значение.(Отрицательный t значения потребовали бы отстрела назад во времени для использования!)
Замените выбранный t
введите значение обратно в уравнения положения цели, чтобы получить координаты начальной точки, в которую вы должны целиться:
aim.X := t * target.velocityX + target.startX
aim.Y := t * target.velocityY + target.startY
Происхождение
В момент времени T снаряд должен находиться на (евклидовом) расстоянии от пушки, равном затраченному времени, умноженному на скорость снаряда.Это дает уравнение для окружности, параметрическое по прошедшему времени.
sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
== sqr(t * projectile_speed)
Аналогично, в момент времени T цель переместилась вдоль своего вектора на время, умноженное на ее скорость:
target.X == t * target.velocityX + target.startX
target.Y == t * target.velocityY + target.startY
Снаряд может поразить цель, когда его расстояние от пушки соответствует расстоянию до снаряда.
sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
== sqr(target.X - cannon.X) + sqr(target.Y - cannon.Y)
Замечательно!Подставляя выражения для target.X и target.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)
Подставляя другую часть уравнения , получаем следующее:
sqr(t * projectile_speed)
== sqr((t * target.velocityX + target.startX) - cannon.X)
+ sqr((t * target.velocityY + target.startY) - cannon.Y)
...вычитание sqr(t * projectile_speed)
с обеих сторон и переворачиваем его:
sqr((t * target.velocityX) + (target.startX - cannon.X))
+ sqr((t * target.velocityY) + (target.startY - cannon.Y))
- sqr(t * projectile_speed)
== 0
...теперь решите результаты возведения в квадрат подвыражений ...
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
...и сгруппируйте похожие термины ...
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
...затем объедините их ...
(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
...дающее стандартное квадратное уравнение в t.Нахождение положительных действительных нулей этого уравнения дает (ноль, один или два) возможных местоположения попадания, что может быть выполнено с помощью квадратичной формулы:
a * sqr(x) + b * x + c == 0
x == (-b ± sqrt(sqr(b) - 4 * a * c)) / (2 * a)
+ 1 к превосходному ответу Джеффри Хантина здесь.Я поискал в Google и нашел решения, которые были либо слишком сложными, либо не относились конкретно к интересующему меня случаю (простой снаряд с постоянной скоростью в 2D-пространстве).) Это было именно то, что мне было нужно для создания автономного решения JavaScript, приведенного ниже.
Единственный момент, который я бы добавил, это то, что есть пара особых случаев, на которые вы должны обратить внимание в дополнение к отрицательному дискриминанту:
- "a == 0":происходит, если цель и снаряд движутся с одинаковой скоростью.(решение линейное, а не квадратичное)
- "a == 0 и b == 0":если и цель, и снаряд неподвижны.(решения нет, если c == 0, т. е.src и dst - это одна и та же точка.)
Код:
/**
* 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;
}
У Джеффри Хантина есть хорошее решение этой проблемы, хотя его вывод чрезмерно сложен.Вот более чистый способ вывести его с помощью некоторого результирующего кода внизу.
Я буду использовать x.y для представления векторного точечного произведения, и если векторная величина возведена в квадрат, это означает, что я расставляю ее саму по себе.
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
Мы знаем, что положение снаряда и цели относительно t
время можно описать с помощью некоторых уравнений.
curprojpos(t) = origpos + t*origvel + t*projvel
curtargpos(t) = targpos + t*targvel
Мы хотим, чтобы они были равны друг другу в некоторой точке (точке пересечения), поэтому давайте установим их равными друг другу и решим для свободной переменной, projvel
.
origpos + t*origvel + t*projvel = targpos + t*targvel
turns into ->
projvel = (targpos - origpos)/t + targvel - origvel
Давайте забудем о понятии начала координат и целевого положения / скорости.Вместо этого давайте работать в относительных терминах, поскольку движение одной вещи относительно другой.В этом случае то, что мы сейчас имеем, это relpos = targetpos - originpos
и relvel = targetvel - originvel
projvel = relpos/t + relvel
Мы не знаем, что projvel
есть, но мы точно знаем, что хотим projvel.projvel
быть равным speed^2
, итак , мы выровняем обе стороны и получим
projvel^2 = (relpos/t + relvel)^2
expands into ->
speed^2 = relvel.relvel + 2*relpos.relvel/t + relpos.relpos/t^2
Теперь мы можем видеть, что единственной свободной переменной является время, t
, и тогда мы будем использовать t
чтобы решить для projvel
.Мы решим для t
с помощью квадратичной формулы.Сначала разделите его на a
, b
и c
, затем решите для корней.
Однако, прежде чем решать, помните, что нам нужно наилучшее решение, при котором t
является наименьшим, но мы должны убедиться, что t
не является отрицательным (вы не можете поразить что-то в прошлом)
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
Теперь, если у нас есть t
значение, мы можем подключить t
вернитесь к исходному уравнению и решите для projvel
projvel = relpos/t + relvel
Теперь, чтобы выстрелить снарядом, результирующее глобальное положение и скорость снаряда равны
globalpos = origpos
globalvel = origvel + projvel
И с тобой покончено!
Моя реализация моего решения в Lua, где vec * vec представляет векторное точечное произведение:
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
Ниже приведен код наведения на основе полярных координат на C ++.
Чтобы использовать с прямоугольными координатами, вам нужно будет сначала преобразовать относительную координату целей в угол / расстояние, а скорость целей x / y в угол / скорость.
Ввод "скорость" - это скорость снаряда.Единицы измерения скорости и targetSpeed не имеют значения, поскольку при расчете используется только соотношение скоростей.Результат - это угол, под которым должен быть выпущен снаряд, и расстояние до точки столкновения.
Алгоритм взят из исходного кода, доступного по адресу 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;
}
Вот пример, в котором я разработал и внедрил решение проблемы прогнозирующего таргетинга с использованием рекурсивного алгоритма: http://www.newarteest.com/flash/targeting.html
Мне придется опробовать некоторые из других представленных решений, потому что кажется более эффективным вычислить это за один шаг, но решение, которое я придумал, состояло в том, чтобы оценить целевое положение и ввести этот результат обратно в алгоритм, чтобы сделать новую, более точную оценку, повторив это несколько раз.
Для первой оценки я "стреляю" по текущему положению цели, а затем использую тригонометрию, чтобы определить, где будет находиться цель, когда выстрел достигнет позиции, по которой был произведен.Затем на следующей итерации я "стреляю" в эту новую позицию и определяю, где будет находиться цель на этот раз.Примерно после 4 повторений я получаю точность в пределах пикселя.
Я только что взломал эту версию для прицеливания в 2d-пространстве, я еще не тестировал ее очень тщательно, но, похоже, она работает.Идея, стоящая за этим, заключается в следующем:
Создайте вектор, перпендикулярный вектору, указывающему от дула к цели.Чтобы произошло столкновение, скорости цели и снаряда вдоль этого вектора (оси) должны быть одинаковыми!Используя довольно простой косинусный материал, я пришел к этому коду:
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;
}
Я видел много способов решить эту проблему математически, но это был компонент, относящийся к проекту, который мой класс должен был выполнять в средней школе, и не у всех в этом классе программирования был опыт работы с исчислением или даже с векторами, если уж на то пошло, поэтому я создал способ решить эту проблему, используя больше подхода программирования.Точка пересечения будет точной, хотя она может появиться на 1 кадр позже, чем при математических вычислениях.
Рассмотреть:
S = shooterPos, E = enemyPos, T = targetPos, Sr = shooter range, D = enemyDir
V = distance from E to T, P = projectile speed, Es = enemy speed
В стандартной реализации этой задачи [S, E, P, Es, D] все заданы, и вы решаете либо найти T, либо угол, под которым стрелять, чтобы попасть в T в нужное время.
Основным аспектом этого метода решения задачи является рассмотрение дальности стрельбы стрелка как окружности, охватывающей все возможные точки, по которым можно стрелять в любой данный момент времени.Радиус этой окружности равен:
Sr = P*time
Где время вычисляется как итерация цикла.
Таким образом, чтобы найти расстояние, которое проходит враг с учетом итерации времени, мы создаем вектор:
V = D*Es*time
Теперь, чтобы действительно решить проблему, мы хотим найти точку, в которой расстояние от цели (T) до нашего стрелка (Ов) меньше, чем дальность нашего стрелка (Sr).Вот что-то вроде псевдокодовой реализации этого уравнения.
iteration = 0;
while(TargetPoint.hasNotPassedShooter)
{
TargetPoint = EnemyPos + (EnemyMovementVector)
if(distanceFrom(TargetPoint,ShooterPos) < (ShooterRange))
return TargetPoint;
iteration++
}
Я создал здесь функцию Unity C #, являющуюся общественным достоянием:
http://ringofblades.com/Blades/Code/PredictiveAim.cs
Это для 3D, но вы можете легко изменить это для 2D, заменив Vector3s на Vector2s и используя выбранную вами ось вниз для гравитации, если гравитация есть.
На случай, если вас заинтересует теория, я расскажу здесь о выводе математических данных:
http://www.gamasutra.com/blogs/KainShin/20090515/83954/Predictive_Aim_Mathematics_for_AI_Targeting.php
В принципе, концепция пересечения здесь на самом деле не нужна, поскольку вы используете движение снаряда, вам просто нужно ударить под определенным углом и создать экземпляр во время стрельбы, чтобы получить точное расстояние до вашей цели от источника, а затем, когда у вас будет расстояние, вы сможете рассчитать подходящую скорость, с которой он должен выстрелить, чтобы поразить цель.
Следующая ссылка проясняет концепцию и считается полезной, может помочь:Движение снаряда, чтобы всегда попадать в движущуюся цель
Я взял одно из решений отсюда, но ни одно из них не учитывает движение стрелка.Если ваш стрелок движется, вы можете захотеть принять это во внимание (поскольку скорость стрелка должна быть добавлена к скорости вашей пули при стрельбе).На самом деле все, что вам нужно сделать, это вычесть скорость вашего стрелка из скорости цели.Поэтому, если вы используете приведенный выше код broofa (который я бы рекомендовал), измените строки
tvx = dst.vx;
tvy = dst.vy;
Для
tvx = dst.vx - shooter.vx;
tvy = dst.vy - shooter.vy;
и у вас должно быть все готово.