Algorithm for tracking a target

[+johnnywc]

Hello all,

 

I'm working on the logic in Rip Off and I was wondering if anyone can give suggestions as to the best way I can implement the enemy ships moving towards a "target" (either a pod or another ship) and avoid division.

 

For example:

 

If an enemy ship is at X1, Y1 and I want it to move towards a point X2, Y2

 

I need to determine the direction the enemy ship needs to face. In my game, the enemy ship can move in any one of 16 directions (0-15), with 0 being up, 4 being right, 8 down and 12 left.

 

So, if the point was directly to my right, I would want to rotate the enemy ship to direction 4; if it is directly below, rotate to direction 8, etc. Since the enemies are constantly moving (exept when picking up a pod), the horizontal and vertical vectors are applied to the ship's position each frame.

 

If I remember correctly from math, if I determine the slope (dy/dx) and took the arctangent (I'm digging here) I'll get the angle between the two. I could use this angle to determine which of the 16 directions the enemy ship should be facing (and moving) to reach the destination point. Of course, doing this in 6502 assembler would not be that efficient I'm sure...

 

Does anybody have any suggestions as to a better way to implement this?

 

Thanks!

[SeaGtGruff]

I was wondering if anyone can give suggestions as to the best way I can implement the enemy ships moving towards a "target" (either a pod or another ship) and avoid division.

What about dividing the area around the ship into 16 zones, with the boundaries between these zones corresponding to the midpoints of directional zones the ship can point/move in? This is rather hard to describe in words, so I've drawn a picture:

 

 

So for example, direction 0 corresponds to an angle of 0 degrees, and direction 1 corresponds to an angle of 22.5 degrees. Therefore the midpoint between them is at angle 11.25 degrees.

 

On the other side, direction 0 corresponds to an angle of 0 degrees-- but let's call it 360 degrees this time-- and direction 15 corresponds to an angle of 337.5 degrees. Therefore the midpoint between them is at angle 348.75 degrees.

 

Consequently, if you check the dx and dy values between the ship and its target, and if you determine that the vector between them lies somewhere between 348.75 degrees and 11.25 degrees, then you know that you want to point/move the ship in direction 0.

 

Likewise, if the vector lies between 11.25 degrees and 33.75 degrees, then you know that you want to point/move the ship in direction 1.

 

Perhaps the easiest way to implement this would be with some lookup tables. First you could test for the obvious cases, and then anything not covered by the obvious cases would be handled with lookup tables. It wouldn't have to be exact, just reasonably close, since this isn't rocket science.

 

For example, suppose the ship's x and y coordinates are SX and SY, the target's coordinates are TX and TY, and the differences between them are DX (= TX - SX) and DY (= TY - SY). First, check for the obvious cases (note that I'm assuming Y = 0 is at the top of the screen):

 

Is DX = 0? (i.e., Is TX = SX?)
  Yes:
  Is DY = 0? (i.e., Is TY = SY?)
	 Yes:
		The ship is on top of the target. Exit.
	 No:
		Is DY < 0? (i.e., Is TY < SY?)
		   Yes:
			  The ship needs to point/move in direction 0. Exit.
		   No:
			  The ship needs to point/move in direction 8. Exit.
		End-If
  End-If
End-If

Is DY = 0? (i.e., Is TY = SY?)
  Yes:
  Is DX < 0? (i.e., Is TX < SX?) [We already checked for DX = 0.]
	 Yes:
		The ship needs to point/move in direction 12. Exit.
	 No:
		The ship needs to point/move in direction 4. Exit.
  End-If
End-If

Is |DX| = |DY|? [Note: These are their absolute values.]
  Yes:
  Is DX < 0? (i.e., Is TX < SX?)
	 Yes:
		Is DY < 0? (i.e., Is TY < SY?)
		   Yes:
			  The ship needs to point/move in direction 14. Exit.
		   No:
			  The ship needs to point/move in direction 10. Exit.
		End-If
	 No:
		Is DY < 0? (i.e., Is TY < SY?)
		   Yes:
			  The ship needs to point/move in direction 2. Exit.
		   No:
			  The ship needs to point/move in direction 6. Exit.
		End-If
  End-If
End-If

This takes care of the obvious cases where either DX or DY (or both) are 0, or where |DX| = |DY|. The remaining cases can either be handled with lookup tables-- IF YOU WANT THE RESULTS TO BE AS EXACT AS POSSIBLE-- or (if you don't care so much about how exact the results are) you could simply split the remaining cases between directions 1, 3, 5, 7, 9, 11, 13, and 15, without worrying whether they might actually be closer to directions 0, 2, 4, 6, 8, 10, 12, or 14.

 

Assuming you do NOT want to use lookup tables, then all you need to do is check the signs of DX and DY, and see which one is larger than the other. Note that you would still want to do this check even if you ARE using lookup tables for greater accuracy. (The only reason for the lookup tables would be to see which direction the vector is actually closest to.)

 

Is DX < 0? (i.e., Is TX < DX?)
  Yes:
  Is DY < 0? (i.e., Is TY < SY?)
	 Yes:
		Is |DX| < |DY|?
		   Yes:
			  The ship needs to point/move in direction 15. Exit.
			  (Or: Check if it's closer to direction 14, 15, or 0.)
		   No:
			  The ship needs to point/move in direction 13. Exit.
			  (Or: Check if it's closer to direction 12, 13, or 14.)
		End-If
	 No:
		Is |DX| < |DY|?
		   Yes:
			  The ship needs to point/move in direction 9. Exit.
			  (Or: Check if it's closer to direction 8, 9, or 10.)
		   No:
			  The ship needs to point/move in direction 11. Exit.
			  (Or: Check if it's closer to direction 10, 11, or 12.)
		End-If
  End-If
  No:
  Is DY < 0? (i.e., Is TY < SY?)
	 Yes:
		Is |DX| < |DY|?
		   Yes:
			  The ship needs to point/move in direction 1. Exit.
			  (Or: Check if it's closer to direction 0, 1, or 2.)
		   No:
			  The ship needs to point/move in direction 3. Exit.
			  (Or: Check if it's closer to direction 2, 3, or 4.)
		End-If
	 No:
		Is |DX| < |DY|?
		   Yes:
			  The ship needs to point/move in direction 7. Exit.
			  (Or: Check if it's closer to direction 6, 7, or 8.)
		   No:
			  The ship needs to point/move in direction 5. Exit.
			  (Or: Check if it's closer to direction 4, 5, or 6.)
		End-If
  End-If
End-If

As far as the lookup tables, I would use the smaller of the two absolute values (|DX| or |DY|) and use it to find the value of the appropriate trigonometric function (sine or cosine) for the two angles that need to be tested. The table would assume that the smaller absolute value is 1, and the lookup value would then be multiplied as needed to get the appropriate value. Then you can compare the larger of the two absolute values with the two lookup values to see if the vector is between them, or lies to either side, to see which direction is closest.

 

I think you would actually only need two lookup values-- so you wouldn't even need to store them in a table per se-- because you could use the same two values for all of the angles. I'm not certain that the following is correct, so you need to verify it, but to see how it would work, let's take the case where we found the tentative direction to be 15, and we want to check to see if the vector is closest to direction 14, 15, or 0.

 

In this example, we know that DX < 0, DY < 0, and |DX| < |DY|, so |DX| is the smaller value. For an angle of 348.75 degrees (i.e., halfway between direction 15 and direction 0), if |DX| were 1, then |DY| would be 5.0273394921258481045149750710641. If you're using an 8.8 fixed-point variable, then this would be roughly "5.7" (i.e., 5 plus 7/256). So we multiply "5.7" by |DX| to get the value we need to compare with |DY|. Thus, if |DX| were 4, then the test value would be "20.28" (i.e., 20 plus 28/256).

 

Likewise, for an angle of 326.25 degrees (i.e., halfway between direction 14 and direction 15), if |DX| were 1, then |DY| would be 1.4966057626654890176011351349425. Again, using an 8.8 fixed-point variable, this would be roughly "1.127" (i.e., 1 plus 127/256). So we multiply "1.127" by |DX| to get the test value. Thus, if |DX| were 4, then the test value would be "5.252" (i.e., 5 plus 252/256).

 

Taking these two test values together, if |DY| were 21 or greater, then we would know that the vector is closest to direction 0. If |DY| were between 6 and 20 inclusive, then we would know that the vector is closest to direction 15. And if |DY| were 5 or less, then we would know that the vector is closest to direction 14.

 

So the logic could be as follows (this replaces the preceding pseudocode, after the obvious cases have been handled):

 

Is DX < 0? (i.e., Is TX < DX?)
  Yes:
  Is DY < 0? (i.e., Is TY < SY?)
	 Yes:
		Is |DX| < |DY|?
		   Yes:
			  Is |DY| > "5.7" * |DX|?
				 Yes:
					The ship needs to point/move in direction 0.
				 No:
					Is |DY| < "1.127" * |DX|?
					   Yes:
						  The ship needs to point/move in direction 14.
					   No:
						  The ship needs to point/move in direction 15.
					End-If
			  End-If
		   No:
			  Is |DX| > "5.7" * |DY|?
				 Yes:
					The ship needs to point/move in direction 12.
				 No:
					Is |DX| < "1.127" * |DY|?
					   Yes:
						  The ship needs to point/move in direction 14.
					   No:
						  The ship needs to point/move in direction 13.
					End-If
			  End-If
		End-If
	 No:
		Is |DX| < |DY|?
		   Yes:
			  Is |DY| > "5.7" * |DX|?
				 Yes:
					The ship needs to point/move in direction 8.
				 No:
					Is |DY| < "1.127" * |DX|?
					   Yes:
						  The ship needs to point/move in direction 10.
					   No:
						  The ship needs to point/move in direction 9.
					End-If
			  End-If
		   No:
			  Is |DX| > "5.7" * |DY|?
				 Yes:
					The ship needs to point/move in direction 12.
				 No:
					Is |DX| < "1.127" * |DY|?
					   Yes:
						  The ship needs to point/move in direction 10.
					   No:
						  The ship needs to point/move in direction 11.
					End-If
			  End-If
		End-If
  End-If
  No:
  Is DY < 0? (i.e., Is TY < SY?)
	 Yes:
		Is |DX| < |DY|?
		   Yes:
			  Is |DY| > "5.7" * |DX|?
				 Yes:
					The ship needs to point/move in direction 0.
				 No:
					Is |DY| < "1.127" * |DX|?
					   Yes:
						  The ship needs to point/move in direction 2.
					   No:
						  The ship needs to point/move in direction 1.
					End-If
			  End-If
		   No:
			  Is |DX| > "5.7" * |DY|?
				 Yes:
					The ship needs to point/move in direction 4.
				 No:
					Is |DX| < "1.127" * |DY|?
					   Yes:
						  The ship needs to point/move in direction 2.
					   No:
						  The ship needs to point/move in direction 3.
					End-If
			  End-If
		End-If
	 No:
		Is |DX| < |DY|?
		   Yes:
			  Is |DY| > "5.7" * |DX|?
				 Yes:
					The ship needs to point/move in direction 8.
				 No:
					Is |DY| < "1.127" * |DX|?
					   Yes:
						  The ship needs to point/move in direction 6.
					   No:
						  The ship needs to point/move in direction 7.
					End-If
			  End-If
		   No:
			  Is |DX| > "5.7" * |DY|?
				 Yes:
					The ship needs to point/move in direction 4.
				 No:
					Is |DX| < "1.127" * |DY|?
					   Yes:
						  The ship needs to point/move in direction 6.
					   No:
						  The ship needs to point/move in direction 5.
					End-If
			  End-If
		End-If
  End-If
End-If

Note that |DX| and |DY| are swapped around in some of these computations!

 

I'm not certain that the preceding is correct, so if anyone can spot any errors (assuming it isn't too difficult to follow my line of thinking!), PLEASE correct them!

 

Michael

Edited May 14, 2007 by SeaGtGruff

[Heaven/TQA]

Thomas helped me some time ago with something similar in my Game Boinxx. Maybe usefull for your game:

 

"my aim is to bring some emenies to boinxx and i would like to use some dynamic approach to give boinxx a more "professional" look...

 

so i played around with some approaches and asked one of my mates who is a doctor of physics and he gave me this formular:

 

* vex=(px-ex)/16

* vey=(py-ey)/16

* ex=ex+vex

* ey=ey+vey

 

where Vex,y is velocity of the enemy while px,y is the position of the player. ex,y is the enemy position... it took me a little while and with the help of Thomas J. i implemented the code. the difficulty was that we have to deal with signed numbers and to move smooth on screen even with 8.8 fixed point maths. and this is something i managed to understand on 68000 but not on 6502... esp. signed numbers + division. so Thomas - the 2600 maniac behind thrust+ conversion - gave me this:

 

calc lda px

sec

sbc ex

sta vex

lda px+1

sbc ex+1

cmp #$80

ror

ror vex

cmp #$80

ror

ror vex

cmp #$80

ror

ror vex

cmp #$80

ror

ror vex

sta vex+1

lda vex

clc

adc ex

sta ex

lda vex+1

adc ex+1

sta ex+1

lda py

sec

sbc ey

sta vey

lda py+1

sbc ey+1

cmp #$80

ror

ror vey

cmp #$80

ror

ror vey

cmp #$80

ror

ror vey

cmp #$80

ror

ror vey

 

sta vey+1

lda vey

clc

adc ey

sta ey

lda vey+1

adc ey+1

sta ey+1

rts

 

and here is the link to the Atari 800 game (WIP):

 

http://www.atariage.com/forums/index.php?s...5&hl=Boinxx

[PacMan]

*Hehe* that assembler block sure could use some comments

[Thomas Jentzsch]

Actually the assembler code is doing pretty straightforward what the pseudo code above describes.

The cmp #$80 are necessary to keep the sign correct. Alternatively you could check the high bit after shifting (bit 3 then) and set the upper bits accordingly. Might be a bit faster.

 

I think Heaven is right, the code I helped him with should work for this problem pretty well too. Only the shift value may have to be adjusted.

[Heaven/TQA]

check out the "enemy1.zip" on the last page of the Boinxx thread and load the .obx file into atari800win 4.0 plus and you know what it does... i havent figured out what thomas' code does but it works perfect...

[+johnnywc]

Wow! Thank you all for the insight and example code! This should be more enough to get me going on this ...

 

I'll post my results once I have it implemented.

 

Thanks again!

[Heaven/TQA]

btw the enemy code is really cool. i will use that for my new game as well... thanks Thomas for that...

[djmips]

A system with 8 directions is as follows.

 

snip %<

 

Code removed because it was bad and I didn't want anyone else wasting time on these bugs.

 

Look for better code later in thread.

Edited May 19, 2007 by djmips

[Heaven/TQA]

the last algorithm is quite simple and usefull esp. for my game but am i stupid or does the algorithm not work for an enemy coming from SE? SE gives same results as S if i am right.

 

assume following

 

E1E2E3

E4PLE5

E6E7E8

 

PL(2,2) while E1(0,0),E2(2,0),E3(4,0),E4(0,2),E5(4,2),E6(0,6),E7(2,6),E8(4,6)

 

now lets have a look on E7 and E8

 

E7(2,6)

 

adx=abs(2-2)=0 ; dx=2-2=0

ady=abs(6-2)=4 ; dy=6-2=4

 

dir=1 --> dir=1

 

E7(4,6)

 

adx=abs(4-2)=2 ; dx=4-2=2

ady=abs(6-2)=4 ; dy=6-2=4

 

dir=1 --> dir=1

 

?

[djmips]

the last algorithm is quite simple and usefull esp. for my game but am i stupid or does the algorithm not work for an enemy coming from SE? SE gives same results as S if i am right.

 

No it is I who is stupid. I have posted up some bad pseudo code. I apologize. I will post up a couple of things, first the correct code, and two another routine which I think is cool that is longer, but more accurate and I'll also be posting it in 6502.

 

So for now, just ignore that pitiful code.

[djmips]

Thomas helped me some time ago with something similar in my Game Boinxx. Maybe usefull for your game:

 

"my aim is to bring some emenies to boinxx and i would like to use some dynamic approach to give boinxx a more "professional" look...

 

so i played around with some approaches and asked one of my mates who is a doctor of physics and he gave me this formular:

 

* vex=(px-ex)/16

* vey=(py-ey)/16

* ex=ex+vex

* ey=ey+vey

 

where Vex,y is velocity of the enemy while px,y is the position of the player. ex,y is the enemy position...

 

A little off topic, but I'd like to boast that I invented this very same technique while making a kamikaze robot in Silas Warner's Robot Wars for the Apple ][ when I was a child. Of course, I didn't do anything but play Robot Wars for months on end, and so you might expect something to come from that...

[djmips]

* vex=(px-ex)/16

 

  cmp #$80
 ror 
 ror vex
 cmp #$80
 ror 
 ror vex
 cmp #$80
 ror 
 ror vex
 cmp #$80
 ror 
 ror vex
 sta vex+1

 

In Thomas's code here, he is doing the signed divide by 16 using the 6502 equivalent of an Arithmetic Shift Right, (ASR) which doesn't exist in the instruction set - so the clever two instruction replacement is used, cmp #$80 followed by ror.

 

I have also needed a multi bit ASR and have found the following improved code which could also replace the quoted section above. It is slightly smaller and slightly faster.

 

  lsr
 ror vex
 lsr
 ror vex
 lsr
 ror vex
 lsr
 ror vex
 clc
 adc #$F8
 eor #$F8
 sta vex+1

Edited May 24, 2007 by djmips

[djmips]

I've posted an ATAN2 routine in my BLOG.

 

http://www.atariage.com/forums/index.php?a...&blogid=131

 

It's slow, yet fast-ish for the 6502 for what it does. Around 2100 cycles. It could be sped up versus more memory or less accuracy. It already has some compromises.

[Robert M]

Hello all,

 

I'm working on the logic in Rip Off and I was wondering if anyone can give suggestions as to the best way I can implement the enemy ships moving towards a "target" (either a pod or another ship) and avoid division.

 

For example:

 

If an enemy ship is at X1, Y1 and I want it to move towards a point X2, Y2

 

I need to determine the direction the enemy ship needs to face. In my game, the enemy ship can move in any one of 16 directions (0-15), with 0 being up, 4 being right, 8 down and 12 left.

 

So, if the point was directly to my right, I would want to rotate the enemy ship to direction 4; if it is directly below, rotate to direction 8, etc. Since the enemies are constantly moving (exept when picking up a pod), the horizontal and vertical vectors are applied to the ship's position each frame.

 

If I remember correctly from math, if I determine the slope (dy/dx) and took the arctangent (I'm digging here) I'll get the angle between the two. I could use this angle to determine which of the 16 directions the enemy ship should be facing (and moving) to reach the destination point. Of course, doing this in 6502 assembler would not be that efficient I'm sure...

 

Does anybody have any suggestions as to a better way to implement this?

 

Thanks!

 

I have been bothered by this same problem for a project I am working on too. So I went ahead and finally found a solution I think works well. I have attached a demostration binary. Use joystick 1 to move the white source arrow around the purple target arrow.

 

I have also attached the subroutine that does the calculation. It is not optimized for space or speed. I just wanted it to work at this point. I hope its useful.

 

findtarget.bin

target.txt

 

Cheers!

[djmips]

I have been bothered by this same problem for a project I am working on too. So I went ahead and finally found a solution I think works well. I have attached a demostration binary. Use joystick 1 to move the white source arrow around the purple target arrow.

 

I have also attached the subroutine that does the calculation. It is not optimized for space or speed. I just wanted it to work at this point. I hope its useful.

 

Cheers!

 

 

Hmmm. Nice! I was pondering a geometric solution as well and my thoughts touched on how we can classify points on either sides of dividing planes in 3D and whittling it down in a by using several appropriately placed planes.

 

Basically a Binary Space Partition (BSP) set up around the player with each 'room' being one of the 16 slices. Then you would just need to classify your point against the BSP to find out which 'room' it was in, and thusly which direction it was.

 

It sounds a lot like what you've derived, probably from a different approach. I was concerned that the plane (line) test would be expensive and it seems like you've managed to solve that fairly well. Congratulations.

 

BTW - have you measured the cycle time? It's fairly easy to do in Stella I've found. Just a breakpoint before and after you call the routine and note the global cycle time. I realize that your times are not going to be consistent and will depend partially upon the direction.

 

Also, in your solution for the line test, what shortcuts and/or approximations did you manage to discover?

 

thanks,

 

David

[djmips]

Here are a few test results that I did.

 

SW - 108 cycles

 

SE - 122 cycles

 

E - 108 cycles

 

NE - 110 cycles

 

N - 119 cycles

 

NW - 120 cycles

 

W - 110 cycles

 

I hope these aren't inaccurate as I did this when I was well tired.

[Robert M]

Here are a few test results that I did.

 

SW - 108 cycles

 

SE - 122 cycles

 

E - 108 cycles

 

NE - 110 cycles

 

N - 119 cycles

 

NW - 120 cycles

 

W - 110 cycles

 

I hope these aren't inaccurate as I did this when I was well tired.

 

Thanks for taking the measurements. That looks about right since the path through the code is 4 line tests no matter what the direction is. I have not optimized the code yet either. I suspect 6 to 10 cycles could be shaved off by exploiting the known state of Carry after each test. If the program is able to deal with the 16 directions not being in rotational order, then a further optimization of shifting the Carry into a direction byte after each test, would reduce the ROM size (4 tests -> 4 bits = 16 directions).

 

Cheers

[Robert M]

Also, in your solution for the line test, what shortcuts and/or approximations did you manage to discover?

 

David

 

The main trick was finding slopes for lines between the 16 zones that are easy to calculate, but close enough to accept the error. I choose lines that all have positive or negative slopes of 5, 1/5, 3/2, or 2/3. I treat the input values as 4x the delta and divide the inputs to get 2x the delta and 1x delta as smaller values. That let's the math stay in a single signed byte resolution at the expense of possibly conditioning the inputs as explained in the txt file. A slope of 1/5 suggests a nasty division, but the equation Y > 1/5 X is the same as 5Y > X. 5Y is simply 4Y + Y which is easy to calculate. From there it was simply a matter of jumping to the right test based on the result of the previous test.

 

It would be possible to use testing lines with slopes of 4, 1/4, 2, and 1/2 and speed the routine up, but the error grows considerably.

 

Cheers!

[djmips]

Another approach is to save the signs of dx, dy and then take abs(dx) abs(dy). You then shift right max(adx,ady) ,and also shifting the other, until it is in the range (0:15). You then can use the coordinates adx,ady nto a lookup table which give you the direction. The table can be compacted somewhat because you only need 4 bits per entry. You may be able to play with the range to see how large a table you will need. You would also probably want to scale up small dx, dy to get a better result. The original signs combined with the table result would give you the final direction.

[Robert M]

Another approach is to save the signs of dx, dy and then take abs(dx) abs(dy). You then shift right max(adx,ady) ,and also shifting the other, until it is in the range (0:15). You then can use the coordinates adx,ady nto a lookup table which give you the direction. The table can be compacted somewhat because you only need 4 bits per entry. You may be able to play with the range to see how large a table you will need. You would also probably want to scale up small dx, dy to get a better result. The original signs combined with the table result would give you the final direction.

 

I looked at using the signs as a short cut at the beginning but I found that even though it divides the space quickly by 4 there are still 5 possible directions because the vertical and horizontal slices each share two quadrants. That means that 3 tests still remain to find 1 of 5, so I abandoned that idea for my design.

 

Cheers!