Leading fire

I am trying to get my aliens to shoot are where the player's ship will be, rather than where it is at the moment, I have come up with the following (assuming I have the relevant functions correct)

range_to_target = range(shooter_x,shooter_y,target_x,target_y)
time_to_target = range_to_target / Bullet_velocity
x_velocity_difference = target_x_velocity - shooter_x_velocity
y_velocity_difference = target_y_velocity - shooter_y_velocity
new_target_x = shooter_x + (x_velocity_difference * time_to_target)
new_target_y = shooter_y + (y_velocity_difference * time_to_target)
bearing_to_target = bearing(shooter_x,shooter_y,new_target_x,new_target_y)
spawn_bullet(shooter_x,shooter_y,bearing)

I think it will work, with one main shortcoming, it assumes the range remains constant , when this is not the case. Without giving me an actual answer or a link to one (I am after a challenge here) can anyone let me know if am I barking up the wrong tree and need to use,

a) an iterative approach
b) the right formula

or am I looking for perfection where none is needed, who needs aliens that hit you EVERY time.

Your on the right lines ... you need to estimate where the player will be based on it's current heading and the time the bullet will take to reach this point.

For a more realistic AI you'd also want to add in a random element so that the player can't just continually change direction to avoid being shot. You could do this by offsetting the estimated position by random x and y values in either direction.

Stevie

Because of the nature of the control system (think asteroids), a player that constantly changes direction would find it very difficult to be able to fire upon the aliens.

The main problem I have is that you cannot tell how long the bullet will take to reach the future location of the player without knowing where the player will be, and visa versa.

I think I may try some work on the interative approach, do the intital code as above, and compare the before and after range difference, the larger the difference the lower the accuracy of the shot, then make changes to time_to_target till you cross an accuracy threshold. Its kinda fuzzy in my head at the moment, I may have to try and code it to get it clear.

I have just read this again and sorry that it makes almost no sense.

What you want is a line-line intersect algorithm, there should be one in the code archives :)

;ooops i did it again...

Something to play with at least :-)

------------------------
www.moonworx.de

Wouldn't a line intersect algorithm just tell me if the course of two objects interected, not if they will occupy the same area of space at the same time?

Thanks lo-tekk, I am currently working outside the Blitz3d entity movment structure so converting this code into my games framework should produce sufficent challenge.

Ian.

Attach a pivot to the player ship, which points in the direction the ship is moving. This pivot is then moved forward away from the ship or backward closer to the ship depending on the speed of the ship. Point the guns at the pivot and the projectile will hit the ship when it reaches the point where the pivot used to be.


Andy

just imagine the enemy ( which is the predator ) isn't a ship but a bullet, make it much faster then the player, then the yellow spot is your leading point to fire. Short: adjust the speed-ratings to your laser,bullet,rocket and ship speeds, so add ship-speed to the bullet speed and let your gun fire at the yellow point in a straight line and thats all about it. As with every interception you must be faster then the target and the target should travel at a straight line for best results, with a little tweaking you should be fine.

Cheers
------------------------
www.moonworx.de

Find the distance to your target as a function of time. Once you know the time that your bullet will reach your target, you can calculate where he will be at that point in time and figure out the heading() to that position.

If you only know his initial position, this would be:
distance_to_target = sqr(target_x0² + target_y0²)

If you also know his velocity, it would be:
distance_to_target = sqr((target_x0 + t * target_vx)² + (target_y0 + t * target_vy)²)

Now find the distance to your bullet as a function of time:

distance_to_bullet = t * bullet_speed

Find their intersection:

distance_to_bullet = distance_to_target

t * bullet_speed = sqr((target_x0 + t * target_vx)² + (target_y0 + t * target_vy)²)

Solving for time, you get a polynomial after a bunch of factoring:

t² * (target_vx² + target_vy² - bullet_speed²) + t * (2 * (target_x0 * target_vx + target_y0 * target_vy)) + 1 * (target_vx² + target_vy²) = 0

Plugging those into the quadratic formula will give you the time(s) of intersection. As stated earlier, once you know the time that your bullet will reach your target, you can calculate where he will be at that point in time and figure out the heading() to that position.

Note that there are two answers to the quadratic formula! That's shown by the +/- symbol in the formula.

Sometimes there are two valid answers: if your target is doing a fly-by, you could fire at one angle and smoke him on his approach, or fire almost parallel to his trajectory and he'll catch up with the bullet after he passes you. It's also possible that the target is moving away from you at a speed greater than your bullet speed, in which case there will be no positive answers - you'd have to travel back in time to be able to hit him. If your target is travelling away from you at the same speed as your bullet, there are no valid answers. This will be reflected by a divide-by-zero in the quatratic formula - which is perfectly safe to do with floats, and will result in Infinity. I haven't thought about it too hard, but there's also the possibility that a square root of a negative number will be taken in the quadratic formula - this is also perfectly safe with floats and will result in NaN.

In summary, you'll want to choose the smallest positive root, being careful of special case floats such as NaN and +/-Infinity. You'll also need logic to take care of cases where there is no valid answer (does the enemy just fire at a random angle, always fire due North, or wait?)

Note that the target's position and velocity should be relative to your own.

DISCLAIMER: I haven't checked my math; you should derive the formulae yourself to make sure it's correct.

I don't know if this is what Octothorpe's saying, and I haven't sat down and thought about it, but you should be able to get the distance to the target, the speed of your bullets, and where your target will be in a certain amount of time that is greater than the amount of time it takes for your bullets to get there, and calculate the angle.

You know what? Go with Octothorpe's answer. He uses numbers.

octothorpe, thanks I have a computing maths degree, but havent really used anything I learnt in about 15 years. I'll give it a go.

I couldn't resist. I wanted to make sure it'd work. Had to go over my math again; sure enough, "c" was wrong in my original post.

Graphics 800, 600
SetBuffer BackBuffer()

Type colour
	Field r, g, b
End Type
Function create_colour.colour(r, g, b) : c.colour = New colour : c\r = r : c\g = g : c\b = b : Return c : End Function

Type body
	Field x#, y#, vx#, vy#, age, destructible, colour.colour, radius%
End Type

Global p.body = New body
p\x = 100
p\y = 100
p\colour = create_colour(255, 0, 0)
p\radius = 5

Global e.body = New body
e\x = 400
e\y = 300
e\colour = create_colour(0, 255, 0)
e\radius = 5

While Not KeyHit(1)
	Cls

	If KeyDown(54) Or KeyDown(42) Then
		e\vx = e\vx + (KeyDown(205) - KeyDown(203)) * .1
		e\vy = e\vy + (KeyDown(208) - KeyDown(200)) * .1
	Else
		p\vx = p\vx + (KeyDown(205) - KeyDown(203)) * .1
		p\vy = p\vy + (KeyDown(208) - KeyDown(200)) * .1
	EndIf
	
	enemy_gun_heat = enemy_gun_heat - 1
	If enemy_gun_heat < 1 Then
		bullet_speed# = 2
		firing_angle# = get_firing_angle(p\x-e\x, p\y-e\y, p\vx-e\vx, p\vy-e\vy, bullet_speed)
		If isReal(firing_angle) Then
			b.body = New body
			b\destructible = True
			b\x = e\x
			b\y = e\y
			b\vx = e\vx + Sin(firing_angle) * bullet_speed
			b\vy = e\vy + Cos(firing_angle) * bullet_speed
			b\colour = create_colour(255, 255, 255)
			b\radius = 2
			enemy_gun_heat = 10
		EndIf
	EndIf
	
	For b.body = Each body
		b\x = b\x + b\vx
		b\y = b\y + b\vy
		Color(b\colour\r, b\colour\g, b\colour\b)
		Oval(b\x-b\radius, b\y-b\radius, 2*b\radius, 2*b\radius, False)
		
		bounced = False
		If b\x < 0    Then b\vx =  Abs(b\vx) : bounced = True
		If b\x >= 800 Then b\vx = -Abs(b\vx) : bounced = True
		If b\y < 0    Then b\vy =  Abs(b\vy) : bounced = True
		If b\y >= 600 Then b\vy = -Abs(b\vy) : bounced = True
		If bounced And b\destructible Then
			Delete b\colour
			Delete b
		EndIf
	Next
	
	Flip
Wend



Function get_firing_angle#(target_x0#, target_y0#, target_vx#, target_vy#, bullet_speed#)
	a# = target_vx^2 + target_vy^2 - bullet_speed^2
	b# = 2 * (target_x0 * target_vx + target_y0 * target_vy)
	c# = target_x0^2 + target_y0^2

	time_1# = (-b + Sqr(b^2 - 4*a*c)) / (2*a)
	time_2# = (-b - Sqr(b^2 - 4*a*c)) / (2*a)
	
	time_1_valid = time_1 >= 0 And isReal(time_1)
	time_2_valid = time_2 >= 0 And isReal(time_2)

	selected_time# = Sqr(-1)
	If time_1_valid Then
		If time_2_valid And time_2 < time_1 Then
			selected_time = time_2
		Else
			selected_time = time_1
		EndIf
	ElseIf time_2_valid Then
		selected_time = time_2
	Else
		Return Sqr(-1)
	EndIf

	target_x# = target_x0 + target_vx * selected_time
	target_y# = target_y0 + target_vy * selected_time
	
	Return ATan2(target_x, target_y)
End Function

Const Inf# = 99^99
Function isReal(n#)
	Return (Abs(n) <> Inf) ; this function has been tested for all known reals (0, +-huge, +-tiny, +-Inf, NaN)
End Function

P.S. I dropped out of highschool. ;) But I'm going back almost 10 years later in a week's time! Chemistry and Physics, then I can start on first year university courses.