Хорошо, все это происходит в приятном и простом 2D мире...:)
Предположим, что у меня есть статический объект A в положении Apos и линейно движущийся объект B в Bpos с bVelocity и боеприпасы со скоростью 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 некоторое время назад. Я попытаюсь выложить, как я это сделал.
Отказ от ответственности: Я, возможно, сделал здесь одну или несколько глупых ошибок; Я просто пытаюсь восстановить рассуждения с помощью моих ржавых математических навыков. Однако я сначала перейду к преследованию, так как это программирование Q & A вместо математического класса: -)
Это сводится к решению квадратичного уравнения вида:
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)
Аналогично, в момент времени Т мишень перемещалась вдоль своего вектора по времени, умноженному на его скорость:
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 на Джеффри Хантина отличный ответ здесь. Я googled вокруг и нашел решения, которые были либо слишком сложны, либо не были конкретно о том, в каком я был заинтересован (простой планет с постоянной скоростью в 2D-пространстве). Его было именно то, что мне нужно для создания автономного JavaScript-решения ниже.
Я бы добавил, что есть несколько особых случаев, в которых вы должны следить за тем, чтобы дискриминант был отрицательным:
код:
/**
* 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
Ниже приведен код цели, ориентированный на полярную координату, на С++.
Для использования с прямоугольными координатами вам необходимо сначала преобразовать целевую относительную координату в угол/расстояние, а целевые скорости 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 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 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 current position (a localized x-axis):
Vector3 perpendicularVector = Vector3.Cross(a_TargetPosition - a_MuzzlePosition, -Vector3.up).normalized;
// project the target 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] все получаются, и вы решаете либо найти Т, либо угол, на который нужно стрелять, чтобы вы набрали Т в нужное время.
Основной аспект этого метода решения проблемы - рассмотреть диапазон стрелка как круг, охватывающий все возможные точки, которые можно снимать в любой момент времени. Радиус этого круга равен:
Sr = P*time
Где время рассчитывается как итерация цикла.
Таким образом, чтобы найти расстояние, которое враг перемещает с учетом итерации времени, мы создаем вектор:
V = D*Es*time
Теперь, чтобы решить проблему, мы хотим найти точку, в которой расстояние от цели (Т) до нашего стрелка (S) меньше, чем диапазон нашего стрелка (Sr). Вот несколько вариантов реализации этого уравнения в псевдокоде.
iteration = 0;
while(TargetPoint.hasNotPassedShooter)
{
TargetPoint = EnemyPos + (EnemyMovementVector)
if(distanceFrom(TargetPoint,ShooterPos) < (ShooterRange))
return TargetPoint;
iteration++
}
Я сделал функцию общего доступа Unity С# здесь:
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
В принципе, концепция пересечения на самом деле здесь не нужна. Насколько вы используете движение снарядов, вам просто нужно нажать под определенным углом и создать экземпляр во время съемки, чтобы получить точное расстояние от цели Источник, а затем, как только вы пройдете дистанцию, вы можете рассчитать соответствующую скорость, с которой она должна быть снята, чтобы попасть в цель.
Следующая ссылка делает концепцию понятной и считается полезной, может помочь: Движение снаряда всегда попадает в движущуюся цель
Я схватил одно из решений отсюда, но никто из них не учитывает движение стрелка. Если ваш стрелок перемещается, вы можете принять это во внимание (так как скорость стрелка должна быть добавлена к вашей скорости пули при стрельбе). На самом деле все, что вам нужно сделать, это вычесть скорость стрелка от целевой скорости. Поэтому, если вы используете выше код брофы (который я бы рекомендовал), измените строки
tvx = dst.vx;
tvy = dst.vy;
к
tvx = dst.vx - shooter.vx;
tvy = dst.vy - shooter.vy;
и все должно быть установлено.