Asteroids 44: Targeting
Today I plan to give the saucer the ability to aim its shots. I anticipate zero trouble.
I did a bit of analysis on targeting, and have an idea for an interesting approach to it. However, I also found an algorithm that does the job, and translated it to Codea Lua. The article is on Scott Lembcke’s blog, gamasutra. I nearly understand what it does. I emphasize nearly.
The desired state of affairs is for our missile to arrive at the same place as the ship arrives, at the same time. We assume that the ship will continue moving in the direction it’s moving when we fire, at the same speed. Therefore the ship can be seem as generating a set of points over time, each one a bit further along the line of its direction.
The missile also generates a set of points over time, based on its speed, which to our misfortune in analyzing varies depending on the speed and direction of the saucer. Difficulty notwithstanding, the question is to find a point on the path of the ship such that the missile can get there at the same time as the ship does.
This generates two equations, and Scott glosses over the question of how this turns into a quadratic equation, and I’ve not figured it out yet. So I translated his code to Lua and wrote a small program to try it out. It works delightfully:
In my translation, I started with in line code and functions, like the article, and refactored after it worked to a class I called Targeter. My current plan is to import that tab into the game, and give the saucer an instance to use. I expect only one issue, namely that the saucer presently launches its missiles a bit away from itself, and that will probably make the targeting a bit wrong.
Here’s the Targeter, a simple mover that moves the test objects, and the main program that uses them. I’ve not looked at them yet this morning, but my recollection from doing them a couple of days ago is that Targeter isn’t bad, and Main is. The Main is just a test driver so I plead hackery.
Targeter = class()
function Targeter:init(shooter,target)
self.saucer = shooter
self.target = target
self.deltaPos = target.pos-shooter.pos
self.deltaVee = target.step-shooter.step
self.shotSpeed = shooter.shotSpeed
end
function Targeter:timeToTarget()
local a = self.deltaVee:dot(self.deltaVee) - self.shotSpeed*self.shotSpeed
local b = 2*self.deltaVee:dot(self.deltaPos)
local c = self.deltaPos:dot(self.deltaPos)
local desc = b*b - 4*a*c
if desc > 0 then
return 2*c/(math.sqrt(desc) - b)
else
return -1
end
end
function Targeter:fireDirection()
local dt = self:timeToTarget()
if dt < 0 then return vec2(1,0):rotate(2*math.pi*math.random()) end
local trueAimPoint = self.target.pos + self.target.step*dt
local relativeAimPoint = trueAimPoint - self.saucer.pos
local offsetAimPoint = relativeAimPoint - dt*self.saucer.step
local dir = offsetAimPoint:normalize()
return dir
end
Mover = class()
function Mover:init(pos,step, muzzlev, c)
self.pos = pos
self.step = step
self.shotSpeed = muzzlev or 0
self.c = c or color(255)
end
function Mover:draw()
pushStyle()
pushMatrix()
translate(self.pos.x, self.pos.y)
fill(self.c)
stroke(self.c)
ellipse(0,0,20)
popMatrix()
popStyle()
end
function Mover:move()
self.pos = self.pos + self.step/20
self.pos = vec2(self.pos.x%WIDTH, self.pos.y%HEIGHT)
end
-- target
function setup()
gp = vec2(300,900)
gs = vec2(2,-10)
tp = vec2(900,900)
ts = vec2(-6,-25)
muzzlev = 20
gun = Mover(gp,gs,muzzlev)
tgt = Mover(tp,ts)
deltapos = tp-gp
velr = ts-gs
targ = Targeter(gun,tgt)
dir = targ:fireDirection()
bulletstep = dir*muzzlev + gs
bullet = Mover(gp,bulletstep,0,color(255, 14, 0))
end
function draw()
background(40, 40, 50)
strokeWidth(2)
textMode(LEFT)
gun:draw()
tgt:draw()
gun:move()
tgt:move()
bullet:draw()
bullet:move()
end
Our job today is “just” to plug the targeter into the asteroids game, and use it to wreak havoc upon humanity. Standard space alien plan. Let’s get started.
Installing Targeter
First step is just to copy/paste the Targeter class into a new tab. I’m getting a lot of tabs here, but that’s how it goes when you like classes and objects.
Issues include getting a targeter installed in the saucer, and dealing with how it will access the ship. An issue is that I don’t really want to instantiate one on every shot, and as it’s set up, it knows both the saucer and ship. The ship isn’t always the same ship, so it can’t just hold on forever. I reckon I’ll pass more info in on the actual usage call. We’ll see.
The saucer’s current firing logic looks like this:
function Saucer:move()
U:moveObject(self)
if U.currentTime >= self.fireTime then
U:playStereo(U.sounds.saucerFire, self)
self.fireTime = U.currentTime + 0.5
SaucerMissile:fromSaucer(self)
end
end
An issue here is that we’ve updated the saucer position, but we don’t know if the ship has been moved yet, or not. Ideally we’d base our firing solution on current information. Anyway, we’ll see. I think I said that before. Looking at the missile creation, we find:
function SaucerMissile:fromSaucer(saucer)
local rot = math.random()*2*math.pi
local pos = saucer.pos + vec2(saucer:killDist() + 1, 0):rotate(rot)
local vel = U.missileVelocity:rotate(rot) + saucer.step
return SaucerMissile(pos, vel)
end
There’s the offsetting of the missile’s position:
vec2(saucer:killDist() + 1, 0):rotate(rot)
We’ll be replacing all this, I think, at least when we want to fire accurately. The game rules are, I think, that the large saucer fires randomly, and the small one fires accurately after the first shot. My plan for this morning is to make the large saucer fire accurately all the time, then deal with the nuances later.
The usage code in the sample I wrote is this:
targ = Targeter(gun,tgt)
dir = targ:fireDirection()
bulletstep = dir*muzzlev + gs
The targeter picks up additional info from the gun and target, which in our situation here are the saucer and the ship. I’ll just hammer it all in for the time being.
Well, that didn’t work. I hope you didn’t believe me when I said I anticipated zero trouble. I certainly didn’t believe me.
It’s time for some tests. What I’m seeing is that the saucer appears to be firing with intention, but it isn’t aimed remotely at the ship. Something must be wired up wrong, and there are plenty of opportunities for that. I’ll set up some tests with predictable numbers and see what I can read out.
Testing Targeter
My first sketched test looks like this:
_:test("firing from south of ship", function()
local ship = {pos=vec2(800,800), step=vec2(0,0)}
local saucer = {pos=vec2(800,400), step=vec2(0,0), shotSpeed=10}
local targ = Targeter(saucer,ship)
local dir = targ:fireDirection()
_:expect(dir).is(vec2(0,1))
end)
I’m just setting up tables to represent ship and saucer. Lua doesn’t care, and I wanted to try this approach and see if I like it.
To my slight surprise, the test runs:
24: firing from south of ship -- OK
I’ll do another less obvious one …
_:test("firing from southwest of ship", function()
local ship = {pos=vec2(800,800), step=vec2(0,0)}
local saucer = {pos=vec2(400,400), step=vec2(0,0), shotSpeed=10}
local targ = Targeter(saucer,ship)
local dir = targ:fireDirection()
_:expect(dir.x).is(0.707, 0.005)
_:expect(dir.y).is(0.707, 0.005)
end)
This works as well. Next, I’ll try one with the ship moving, while we’re due south.
_:test("firing from south of moving ship", function()
local ship = {pos=vec2(800,800), step=vec2(1,0)}
local saucer = {pos=vec2(800,400), step=vec2(0,0), shotSpeed=10}
local targ = Targeter(saucer,ship)
local dir = targ:fireDirection()
_:expect(dir).is(vec2(0,1))
end)
I just left the expect alone, since I really don’t know the answer.
26: firing from south of moving ship -- Actual: (0.100000, 0.994987), Expected: (0.000000, 1.000000)
Well, the ship is moving right, and that aiming point is just a bit right of straight up, so it’s probably right.
Now what if both are going the same speed?
_:test("firing from moving saucer south of moving ship", function()
local ship = {pos=vec2(800,800), step=vec2(1,0)}
local saucer = {pos=vec2(800,400), step=vec2(1,0), shotSpeed=10}
local targ = Targeter(saucer,ship)
local dir = targ:fireDirection()
_:expect(dir).is(vec2(0,1))
end)
That one works. I am gratified that they are working, and confused by why the real saucer doesn’t hit the real ship. For values of “real”. One more test:
_:test("firing from moving saucer south of anti-moving ship", function()
local ship = {pos=vec2(800,800), step=vec2(1,0)}
local saucer = {pos=vec2(800,400), step=vec2(-1,0), shotSpeed=10}
local targ = Targeter(saucer,ship)
local dir = targ:fireDirection()
_:expect(dir).is(vec2(0,1))
end)
28: firing from moving saucer south of anti-moving ship -- Actual: (0.200000, 0.979796), Expected: (0.000000, 1.000000)
Looks good to me. One issue is that I’m using a much larger miissile speed than we really have. Ours is 2. I’ll change all the tests to use that value.
The values change in a direction I expect, so I’ll adjust the expect statement accordingly. I think this is right.
Something has gone wrong with the last test.
28: firing from moving saucer south of anti-moving ship -- Actual: (-0.459068, -0.888401), Expected: (0.000000, 1.000000)
We’re moving the ship to the right and the saucer to the left. I expect the direction to have both coordinates positive, firing roughly northeast. We’re now firing southwestish. Have I missed up the test?
Ah. Our separation velocity is 2, even a bit more. I can’t hit the ship with a missile speed that slow, moving away from him. So the Targeter returned a random direction:
function Targeter:fireDirection()
local dt = self:timeToTarget()
if dt < 0 then return vec2(1,0):rotate(2*math.pi*math.random()) end
local trueAimPoint = self.target.pos + self.target.step*dt
local relativeAimPoint = trueAimPoint - self.saucer.pos
local offsetAimPoint = relativeAimPoint - dt*self.saucer.step
local dir = offsetAimPoint:normalize()
return dir
end
I wonder if the whole problem could be that we’re not able to hit the target very often. I’m going to bump up missile velocity and run the game and observe.
The saucer is definitely firing at a consistent but wrong direction. Am I setting something up wrong?
function SaucerMissile:fromSaucer(saucer)
if not Ship:instance() then return SaucerMissile:randomFromSaucer(saucer) end
local targ = Targeter(saucer, Ship:instance())
local dir = targ:fireDirection()
print(dir)
bulletStep = dir*saucer.shotSpeed
return SaucerMissile(saucer.pos, bulletStep)
end
Yes. The bullet needs to get the saucer’s velocity added in. Let’s see about that:
function SaucerMissile:fromSaucer(saucer)
if not Ship:instance() then return SaucerMissile:randomFromSaucer(saucer) end
local targ = Targeter(saucer, Ship:instance())
local dir = targ:fireDirection()
print(dir)
bulletStep = dir*saucer.shotSpeed + saucer.step -- <--
return SaucerMissile(saucer.pos, bulletStep)
end
And now the saucer never misses the ship when it is parked. I’ll try moving it …
The REDACTED saucer now never REDACTED misses, that REDACTED REDACTED.
Commit “targeter works”.
Now What?
I think the first thing is to tone this thing down. This is the big saucer anyway, and he’s not supposed to be any good at his job. And this feature is too good even for the small saucer. I’m pretty sure that with the present game settings, there’s no escape from that targeting.
We could inject error, or we could use a less accurate algorithm. For now, I think I’ll just set the chances of firing accurately very low but non zero.
function SaucerMissile:fromSaucer(saucer)
if not Ship:instance() or math.random(20) < 20 then
return SaucerMissile:randomFromSaucer(saucer)
end
local targ = Targeter(saucer, Ship:instance())
local dir = targ:fireDirection()
print(dir)
bulletStep = dir*saucer.shotSpeed + saucer.step
return SaucerMissile(saucer.pos, bulletStep)
end
Now the REDACTED only kills me one out of 20 shots. Ever so much better.
Commit: “saucer merciful 19/20”.
Let’s sum up before we break something.
Summing Up
My borrowed Gamasutra algorithm worked well: too well. I think I’ll continue analysis and see if I can come up with an aiming algorithm that’s good but not great. It would be easy to put an error factor into this one, but that seems wrong somehow.
It was interesting that my use of the algorithm was wrong, and that I jumped to testing the algorithm first. The good news was that I was able to come up with some pretty decent tests. So maybe my testing habit is coming back.
I’ve commented here and in some Twitter conversations that I’d lie to do something about making sure I run the tests. Someone – I regret that I’ve forgotten who – suggested running them during attract mode. I was thinking just to trigger them when the program starts, which is pretty easy, but it doesn’t ensure that I’d look at the results. So if I can figure out a way to display results on the attract mode screen, that would be pretty nice.
CodeaUnit explicitly uses print to display its messages. We might be able to override Codea print, or we might be able to extend CodeaUnit with some kind of pluggable connection for this sort of thing. I’ll take a look at that in my free time. (Which most of my time is.)
I feel a bit badly that I haven’t been able to derive the targeting algorithm formally. My vector math thinking is just a bit too rusty so far. Maybe I can polish it up. We’ll see.
All in all, a good session today, and a good start to the week.
See you next time. Keep those cards and letters coming!