Distractions Deluxe
Posted by DrPetter
Someone (partly me) derailed the IRC into wild discussion of a math problem. I think some 5-6 people were involved at some points, and we still haven’t arrived at a conclusion as far as I can tell.
Here’s an image I cooked up to help visualize the problem:
The problem is deceptively simple: Determine what angle to fire a bullet in, if it is to hit a target that’s moving past you at a constant velocity. In other words, both objects are moving at a fixed speed, and you just have to figure out in what direction to launch the bullet so that it’ll hit the target perfectly. Iterative solutions need not apply. Good luck with interpreting the image, it’s pretty confus(ed/ing).
Tags: aiming, algorithms, bullets, math
April 19th, 2008 at 12:57 pm
Why not just figure out where the target will be when the bullet should hit it?
It should simply be a problem of finding where the bullet will be in the time it will take for the bullet to reach that spot…
I don’t have a specific algorithm or anything ATM but I’d think it would be fairly simple…
April 19th, 2008 at 12:58 pm
If you mean: vector math dot product simple, then yes, you’re right.
April 19th, 2008 at 1:03 pm
According to my scribblings above it should “simply” be a problem of finding t. When you know the time it’ll take the bullet to arrive at its destination you can also calculate the angle it needs to be fired in. Finding the position of the target at that time is equivalent to finding the time itself since the position is just start+velocity*time.
HOWEVER - how long it takes depends on which angle you fire in, and all that… so the problem isn’t so simple after all (depending on who you ask of course, math geeks are probably laughing).
This all seems like a routine exam question. I’m just lucky I don’t have to take that exam.
April 19th, 2008 at 1:15 pm
My answer:
http://www.ludumdare.com/compo/2008/04/19/re-distractions-deluxe/
April 19th, 2008 at 1:21 pm
well depending on how fast you want it - you could brute-force it.
ie: (pseudo code code, —- = tab
)
tpos = target.pos
mpos = turret.pos
time = 1
Lpos = target.pos + target.vel * time
bpos = turret.pos + angle_to_target * time
while not bpos == Lpos:
—-if bpos is too far - overshot:
——–time -= how_far_overshot
—-if bpos is too short - undershot:
——–time += how_far_undershot
—-recalculate Lpos and bpos
If that makes any sense…
Basically, test where the target will be in 1 sec,
find how close to the target your shot would be in 1 sec - moving towards the new target pos.
Then adjust the time until you find a collision…
But depending on how much you are doing this it could be kinda slow…
April 19th, 2008 at 1:23 pm
Yeah, that would be the iterative solution. Easy to understand and implement, usually fast enough to use as well (particularly if coded well and using binary search or even better methods using local slope etc) BUT the point was to find an analytical/exact solution, just for the “fun” of it
(I generally prefer iterative as it’s more like making my computer do the thinking and me getting on with more interesting stuff, also I like to stop at a point where I still fully understand what’s going on)
April 19th, 2008 at 1:30 pm
LOL
Ok, sorry then
Off in lala land over here - which is why I’m not competing - so I guess I missed you didn’t want that particular solution :/
Good luck the rest of the compo
July 15th, 2008 at 10:03 am
If I understood it correctly, I think this problem has a closed form solution using the quadratic formula.
Here is an approach for solving the constant acceleration case. http://board.flashkit.com/board/showthread.php?t=754442
(View post #20)
And here are a few remarks about reducing it to the constant velocity case.
http://board.flashkit.com/board/showthread.php?t=771117
(Check post #6)
PS: Sorry to resurrect this old post but didn’t see a satisfactory explanation listed here. Love your SFXR program!