لعبة 2D: حريق هدف متحرك من خلال التنبؤ تقاطع القذائف والوحدة
https://stackoverflow.com/questions/2248876
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
حسنا، كل هذا يحدث في عالم لطيف وبسيط 2D ... :)
لنفترض أن لدي كائن ثابت في موقع APOS في الموضع، وكائن متحرك خطي B في BPOS مع أوراق الاستلام، وجولة الذخيرة مع سرعة Avelocity ...
كيف يمكنني معرفة الزاوية التي يجب أن تطلق النار عليها، لضرب ب، مع الأخذ في الاعتبار السرعة الخطية B وسرعة الذخيرة؟
الآن الهدف في الموضع الحالي للكائن، مما يعني أنه بحلول الوقت الذي يحصل فيه القذيفة على هناك الوحدة قد انتقلت إلى مواقع أكثر أمانا :)
المحلول
قم أولا بتدوير المحاور بحيث يكون AB عموديا (عن طريق القيام بالتناوب)
الآن، قم بتقسيم متجه السرعة من B إلى مكونات X و Y (قل BX واو). يمكنك استخدام هذا لحساب مكونات 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 القيمة مرة أخرى في معادلات موقف الهدف للحصول على إحداثيات النقطة الرائدة يجب أن تهدف إلى:
aim.X := t * target.velocityX + target.startX
aim.Y := t * target.velocityY + target.startY
الاشتقاق
في الوقت المناسب، يجب أن يكون القذيفة مسافة (Euclidean) المسافة من المدفع يساوي الوقت المنقضي مضروب من سرعة القذيفة. هذا يعطي معادلة لدائرة، حدوث حدودي في الوقت المنقضي.
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)
رائع! استبدال التعبيرات للمستهدف. يعطي الهدف
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
... إعطاء المعادلة التربيعية القياسية في ب. وبعد العثور على الأصفار الحقيقية الإيجابية لهذه المعادلة يعطي المواقع (صفر أو واحد أو واحد أو سنتين)، والتي يمكن القيام بها مع الصيغة التربيعية:
a * sqr(x) + b * x + c == 0
x == (-b ± sqrt(sqr(b) - 4 * a * c)) / (2 * a)
+1 على إجابة جيفري هانتين الممتازة هنا. أنا غاضب حولها وعثرت على حلول كانت إما معقدة للغاية أو غير محددة على وجه التحديد حول هذا القضية التي كنت مهتما بها (قذيفة السرعة المستمرة البسيطة في مساحة ثنائية الأبعاد.) كان له بالضبط ما أحتاجه لإنتاج حل جافا سكريبت ذاتيا أدناه.
النقطة الوحيدة التي سأضيفها هي أن هناك حالات خاصة زوجين عليك أن تشاهدها بالإضافة إلى كونها سلبية للغاية:
- "A == 0": يحدث إذا كان الهدف والقذيفة يسافرون بنفس السرعة. (الحل خطي، وليس من الدرجة الثانية)
- "A == 0 و B == 0": إذا كانت كل من الهدف والقذيفة ثابتة. (لا يوجد حل ما لم تكن ج == 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;
}
لدى جيفري هانتين حل لطيف لهذه المشكلة، على الرغم من أن اشتقاقه معقد للغاية. إليك طريقة نظافة لاستكشافها مع بعض الكود الناتج في الأسفل.
سأؤدي باستخدام XY لتمثيل منتج Vector DOT، وإذا تربيع كمية متجه، فهذا يعني أنني تنقيطها بنفسها.
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 منتج Vector DOT:
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 سرعة الزاوية / السرعة.
المدخلات "السرعة" هي سرعة القذيفة. وحدات السرعة والهدفين غير صحيحة، حيث يتم استخدام نسبة السرعات فقط في الحساب. الإخراج هو الزاوية يجب أن يتم إطلاق القذيفة والمسافة إلى نقطة الاصطدام.
الخوارزمية هي من شفرة المصدر المتاحة في 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 تكرر، أحصل على ضمن دقة بكسل.
لقد اخترقت للتو هذا الإصدار للحصول على مساحة ثنائية الأبعاد، لم أقم باختبارها جيدا تماما ولكن يبدو أنها تعمل. الفكرة وراء ذلك هي:
قم بإنشاء ناقلات عموديا على الموجه الذي يشير من كمامة إلى الهدف. للحصول على تصادم يحدث، يجب أن تكون سرية الهدف والقذيفة على طول هذا المتجه (المحور) هو نفسه! باستخدام أشياء جيب التمام البسيطة إلى حد ما وصلت إلى هذا الرمز:
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;
}
لقد رأيت العديد من الطرق لحل هذه المشكلة رياضيا، ولكن هذا كان مكونا ذو صلة بمشروع مطلب من صفي أن أفعله في المدرسة الثانوية، وليس كل شخص في فئة البرمجة هذه خلفية مع حساب التفاضل والتكامل، أو حتى ناقلات لهذه المسألة ، لذلك قمت بإنشاء طريقة لحل هذه المشكلة مع أكثر من نهج البرمجة. ستكون نقطة التقاطع دقيقة، على الرغم من أنها قد تصل إلى إطار واحد في وقت لاحق من الحسابات الرياضية.
يعتبر:
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
الآن، لحل المشكلة في الواقع، نريد العثور على نقطة يتم بها المسافة من الهدف (T) إلى مطلق النار لدينا أقل من نطاق مطلق النار لدينا (SR). هنا إلى حد ما من التنفيذ الكفيد من هذه المعادلة.
iteration = 0;
while(TargetPoint.hasNotPassedShooter)
{
TargetPoint = EnemyPos + (EnemyMovementVector)
if(distanceFrom(TargetPoint,ShooterPos) < (ShooterRange))
return TargetPoint;
iteration++
}
أنا جعلت وحدة المجال العام C # وظيفة هنا:
http://ringoflades.com/blades/code/predictiveaim.cs.
إنه ل 3 ثلاثي الأبعاد، ولكن يمكنك بسهولة تعديل هذا لمدة 2D عن طريق استبدال المتجهات 3S مع Vector2s واستخدام محورك المنخفض من الاختيار للجاذبية إذا كان هناك جاذبية.
في حالة الاهتمام بالنظرية، أمشي عبر اشتقاق الرياضيات هنا:
http://www.gamasutra.com/blogs/kainshin/20090515/83954/predictive_aim_mathematics_for_ai_targeting.php.
أساسا، لم يكن هناك حاجة إلى مفهوم التقاطع هنا بالفعل، بقدر ما تستخدم حركة قذيفة، تحتاج فقط إلى الضغط على زاوية معينة وثباتة في وقت التصوير حتى تحصل على المسافة الدقيقة لهدفك من المصدر ثم بمجرد أن تكون لديك المسافة، يمكنك حساب السرعة المناسبة التي يجب أن تسطلق بها من أجل ضرب الهدف.
الرابط التالي يجعل مفهوم Teh واضح ويعتبر مفيدا، قد يساعد:حركة قذيفة تصل دائما إلى هدف متحرك
أمسكت بأحد الحلول من هنا، لكن لا أحد منهم يأخذ في الاعتبار حركة مطلق النار. إذا كان مطلق النار الخاص بك يتحرك، فقد ترغب في أخذ ذلك في الاعتبار (حيث يجب إضافة سرعة مطلق النار إلى سرعة رصاصة عند إطلاق النار). حقا كل ما عليك فعله هو طرح سرعة مطلق النار الخاص بك من سرعة الهدف. لذلك إذا كنت تستخدم رمز Briooda أعلاه (الذي أوصي به)، فقم بتغيير الخطوط
tvx = dst.vx;
tvy = dst.vy;
ل
tvx = dst.vx - shooter.vx;
tvy = dst.vy - shooter.vy;
ويجب أن تكون كل مجموعة.
