How do you shoot a moving target algorithmically?

[LHACK4142]

I'm programming a robot with a shooter on it and I want to hit a moving target (well, hit a stationary target while the robot's moving, but it's just a matter of reference frames).  It's got a holonomic drivetrain (so it can detach its heading from its direction and thus aim anywhere while moving) and the shooter's angle is adjustable.  The velocity of the shooter is also adjustable, but I'd rather not use that feature (too inconsistent on this robot) Anyone got any advice on doing this?

Edited April 4 by LHACK4142
clarify post

[monophonic]

Well, for a stationary target you just head straight at it. This also works for moving targets as long as they move slower than your robot. That is called pure pursuit and is an unoptimal strategy though. Improving from there depends on what kind of sensor your robot is using to track the target.

If your sensor gives direction and range, you can track the target for a short while to get its motion vector and use those to calculate where to move your robot to hit the target.

If you only get direction, you can steer to keep the angular velocity at zero. This has two solutions though, and only one closes in on the target. The other steers you away from it. You can distinguish them by whether the direction to target is closer to the nose or the tail of the robot.

[magnemoe]

52 minutes ago, monophonic said:

Well, for a stationary target you just head straight at it. This also works for moving targets as long as they move slower than your robot. That is called pure pursuit and is an unoptimal strategy though. Improving from there depends on what kind of sensor your robot is using to track the target.

If your sensor gives direction and range, you can track the target for a short while to get its motion vector and use those to calculate where to move your robot to hit the target.

If you only get direction, you can steer to keep the angular velocity at zero. This has two solutions though, and only one closes in on the target. The other steers you away from it. You can distinguish them by whether the direction to target is closer to the nose or the tail of the robot.

Yes, to optimize how to hit an moving target you have to consider the targets heading, if it moves away from you at an angle you will intercept it farter away so it would have traveled longer if it moves towards you it will intercept earlier and you have to aim shorter. This is the same issue as fire control system faces. WW 2 US torpedo launch fire control computers solved this, it was an analog computer who took range, speed and heading of target to calculate how to launch torpedoes. Unlike an WW 2 torpedo however your robot can update this continually. 

[darthgently]

6 hours ago, LHACK4142 said:

I'm programming a robot and I want to hit a moving target (well, hit a stationary target while the robot's moving, but it doesn't matter).  Anyone got any advice on doing this?

Do a dive on proportional navigation.  It is related to the maritime skill of avoiding collisions with other craft:

1.  While maintaining course, record the bearing of the other craft.

2.  If the bearing moves aft over time you will pass ahead of the other craft.

3. If the bearing moves fore you will pass behind it. 

4. If the bearing remains constant over time a collision is possible if neither changes course. 

For pro-nav, do this in 3D and steer accordingly

[Shpaget]

1 hour ago, darthgently said:

Do a dive on proportional navigation.  It is related to the maritime skill of avoiding collisions with other craft:

Just do whatever this book tells you not to.

https://www.amazon.com/Avoid-Huge-Ships-John-Trimmer/dp/0870334336

[LHACK4142]

I guess I was unclear in the OP- I don't want to intercept the target with the robot's chassis, I want to shoot the target with a previously unmentioned shooter.  Thanks for the help already given, though- they are interesting reads.

Edited April 4 by LHACK4142

[Nuke]

its all vector math. i wrote something like this for a custom lead indicator back in my freespace modding days. now its a matter of finding the damn code.

leadtarg = function(epos, evel, ppos, wvel)		--pretty much the same math as wanderers, but reduced in size
	local vlen = evel:getMagnitude()
	local edis = ppos - epos
	local dlen = edis:getMagnitude()
	local trig = edis:getDotProduct(evel)
	local a = (wvel^2) - (vlen^2)
	local b = trig * 2
	local c = -(dlen^2)
	local d = (b^2) - 4 * a * c

	if d >= 0 and a ~= 0 then
		local m1 = ( -b + math.sqrt(d) ) / ( 2 * a)
		local m2 = ( -b - math.sqrt(d) ) / ( 2 * a)

		if (m1 >= 0 and m1 <= m2 and m2 >= 0) or (m1 >= 0 and m2 < 0) then
			return epos + ( evel / (1 / m1) )
		elseif m2 >=0 then
			return epos + ( evel / (1 / m2) )
		else
			return epos
		end
	else
		return epos
	end
end

here is the lua function from my mod. should note that this is for a non-newtonian game, but i do seem to recall it working in my newtonian mod attempt (i think the only difference is you need to add your ship velocity to your weapon velocity, but i do believe this was done in the engine when certain command line parameters were set). ymmv.

evel and epos are the enemy position and velocity. the thing you want to shoot at. ppos is player position, and wvel is weapon velocity. returns a point in space you need to shoot at. all calculations are done in world space.

Edited April 4 by Nuke

[Shpaget]

Are the accuracy and precision in stationary situation good enough to consistently hit the target? Can you consider the time of flight negligible? If the projectile takes a fraction of a second to cover the distance and you robot is not moving all that quickly, just ignore the movement, point the shooter in the general direction of your target, spray and pray. Or are you lobbing your projectiles in high and slow arcs?

[Hannu2]

If you assume that target and projectile moves at constant velocities problem is relatively simple. You can make calculations in robot's frame of reference and take current time as t=0 moment.

At first you can formulate a pair of equations for target. For example if target's position at t=0 is (ax,ay) and velocity (ux,uy) it is simple tx(t) = ax + ux*t and ty(t) = ay+uy*t.

For projectile you get px(t) = vx*t and py(t) = vy*t. Now we have 2 equations for 3 variables, vx, vy and t at hit. Fortunately we know the speed of the projectile v and can write vx^2 + vy^2 = v^2. Now we have 3 equations.

ax + ux*t = vx*t

ay + uy*t = vy*t

vx^2+vy^2 = v^2

Non linear equation systems are generally very nasty to solve but this is not. We can square 2 first equations and add them together. After little algebraic manipulation we get nice second degree equation for time. Generally you have 2 solutions and you can take one which is smaller positive (it means trajectories meet at future) and calculate vx and vy and aiming direction. If you do not have any positive t it means that projectile can not hit target (it happens if target's speed is larger than projectile's and geometry do not allow hit from front).

Generalization to 3 dimensions is very straightforward. If yoy want to take target's acceleration or projectile's drag into account, things go very complicated very soon.

 

 

20 minutes ago, Shpaget said:

Are the accuracy and precision in stationary situation good enough to consistently hit the target? Can you consider the time of flight negligible? If the projectile takes a fraction of a second to cover the distance and you robot is not moving all that quickly, just ignore the movement, point the shooter in the general direction of your target, spray and pray. Or are you lobbing your projectiles in high and slow arcs?

If velocities are constant it is. With more realistic model it depends on many things. Usually one bullet is easy to avoid but that's why they use machine guns for aerial defense. Shoot few tens of bullets per second and give small deviation for individual bullets and target's day will be long and hard.

I made decades ago a small game in which I flew simple craft in 2D world and tired to avoid and shoot enemy's machine gun turrets.  They assumed that I have constant velocity and even I could dodge bullets I had to nerf their guns many times before it was playable.

 

Edited April 4 by Hannu2
Error correction