Calculate closest to player

[Havie]

So in my Target Renegade I have more than two attackers on screen at once.

Anyone got a suggest for the most speedy way of working out an order of closeness taking into account both x and y distances?

I was thinking to sort by x+y (where x and y are the number of pixels away from the coordinators of the player) but if you have a bad guy 4,3 away and another 0,6 away then wrong one will be put top of the list!

Trying to avoid complicated maths that will take time!

Perhaps it could be a Pythagoras thing thinking about it as I type...

But then I'm into square roots which has got to be slow?

[deimos]

Originally Posted by Havie

Perhaps it could be a Pythagoras thing thinking about it as I type...

But then I'm into square roots which has got to be slow?

Except that you don't need to do the square root, just x * x + y * y, that's enough to sort by / search for the minimum.

[Havie]

Yes - I realised my stupidity as I thought about it - doh!

But thanks for confirming it for me. And if I want speed, I could always put the squares in a look up table but am guessing this won't be necessary?

[deimos]

Originally Posted by Havie

Yes - I realised my stupidity as I thought about it - doh!

But thanks for confirming it for me. And if I want speed, I could always put the squares in a look up table but am guessing this won't be necessary?

I've got no idea what blitz basic will compile the two options down to, but I bet you could write a a test to see which is quickest in less than 30 minutes.

[Havie]

Originally Posted by deimos

I've got no idea what blitz basic will compile the two options down to, but I bet you could write a a test to see which is quickest in less than 30 minutes.

Probably more like 10 mins!

[E-Penguin]

look-up tables (LUTs) are always faster than calculating but you could potentially end up with a 320x200 LUT (to cover all the x,y combinations). You could cut this to 160x100 by right-shifting the x,y values first to 1/2 them. I doubt that would make much difference to the accuracy of the game. Or you could, for example, clip x,y to 80x50 and then a 80x50 LUT is much more manageable - treat all enemies at distances greater than that the same.

[Havie]

I was thinking a look up table for squares of numbers as it is probably faster to retrieve a value from an array then calculate it. You'd (in theory) need the squares of 1 to 319 so the array would be 320 items. But saying that, with a maximum of 6 enemies on screen (possibly 5 - not quite sure) then you'd not be doing that many calculations to make it worth it?

Something to consider if I need to optimise later I think!

[Master484]

I looked at my old notes, and reading a value from a single dimension array is indeed faster than doing a single multiply.

But reading a value from a two dimensional array ( which looks like: MyArray (X,Y) ), is slower than multiply or even a division.

So if you make a LUT, then a single dimensional array is recommended.

And there is of course that old Basic trick to make single dimensional arrays behave like two dimensional arrays. So for example if you need store values for a 160*100 grid then simply make a single dimensional array with 16000 elements in it, and then use -1 and +1 to move in the X dimension and -100 and +100 to move in the Y dimension.

---

Also if I was doing this sort of "find the closest enemy" routine, then most likely I would do something like this:

Before the enemy collection is processed I would first reset these variables:

CurrentClosestXY = 999
TheClosestEnemyID = 999

And then, as the enemy collection is processed, I would have something like this:

Count distanceX between ThisEnemy X and player X.

If distanceX is smaller than CurrentClosestXY
 CurrentClosestXY = distanceX
 TheClosestEnemyID = ThisEnemy
End if

Count distanceY between ThisEnemy Y and player Y.

If distanceY is smaller than CurrentClosestXY
 CurrentClosestXY = distanceY
 TheClosestEnemyID = ThisEnemy
End if

And so, after all enemies have been processed, you'll know the ID number of the closest enemy. No need to sort enemies in a list or something like that.

And of course those distance values could be useful for other purposes too, like when should enemies make their attack moves, and so on. So to optimize things all of that should be integrated with general enemy AI behaviour.

And also, if possible, integrate enemy blitting commands into the enemy collection browsing, so that the code follows a cycle like this:

handle enemy 1 logic
Draw enemy 1
handle enemy 2 logic
Draw enemy 2
handle enemy 3 logic
Draw enemy 3

This way the Blitter is constantly drawing the enemies in the background, while the CPU is calculating that distance stuff and AI logic. This is one of the biggest speed tricks in Blitz.

[bebbo]

sometimes it's good enough to consider min(dx + dy)...
... i's not a perfect circle but it's quick^^

[E-Penguin]

I did a quick test of sqrt(x^2 + y^2) vs (|dx| + |dy|) and over 10000 random points the average error of rank is ~5%. For 20 enemies this is 1 enemy being incorrectly judged closest.

I've not tried it in blitz to see if this is faster than, eg, a LUT.

[bebbo]

Originally Posted by E-Penguin

I did a quick test of sqrt(x^2 + y^2) vs (|dx| + |dy|) and over 10000 random points the average error of rank is ~5%. For 20 enemies this is 1 enemy being incorrectly judged closest.

I've not tried it in blitz to see if this is faster than, eg, a LUT.

there is no need for SQRT to find the closest.



And for small values can get more precision by using just one smul,
so discard too big values in advance(if the word overflows it's not accurate).

The smul should be around 40-50 cycles and a lookup might be faster, but you have to fix the sign in that case which eats some cycles up too...

; d0=x1 d1=x2 d2=y1 d3=y2
sub.w  d1,d0
bpl.s  .L1
neg.w  d0
.L1:            ; d0 = |d1-d0|

sub.w  d3,d2
bpl.s  .L2
neg.w  d2
.L2:            ; d2 = |d3-d2|

move.w d2,d1
add.w  d2,d0    ; d0 = |d1-d0| + |d3-d2|

sub.w  d1,d2     ; d2 = |d3-d2| - |d1-d0|
muls.w d2,d2
lsl.w  #2,d0
add.w  d2,d0    ; d0 = 4*(|d1-d0| + |d3-d2|)) + (|d3-d2| - |d1-d0|)²

with x2/y2 = 0

x1 y1 r
2 0 12
1 1 8
0 2 12



still not 100% accurate but close^^

[Havie]

Originally Posted by Master484

I looked at my old notes, and reading a value from a single dimension array is indeed faster than doing a single multiply.

But reading a value from a two dimensional array ( which looks like: MyArray (X,Y) ), is slower than multiply or even a division.

So if you make a LUT, then a single dimensional array is recommended.

And there is of course that old Basic trick to make single dimensional arrays behave like two dimensional arrays. So for example if you need store values for a 160*100 grid then simply make a single dimensional array with 16000 elements in it, and then use -1 and +1 to move in the X dimension and -100 and +100 to move in the Y dimension.

---

Also if I was doing this sort of "find the closest enemy" routine, then most likely I would do something like this:

Before the enemy collection is processed I would first reset these variables:

CurrentClosestXY = 999
TheClosestEnemyID = 999

And then, as the enemy collection is processed, I would have something like this:

Count distanceX between ThisEnemy X and player X.

If distanceX is smaller than CurrentClosestXY
 CurrentClosestXY = distanceX
 TheClosestEnemyID = ThisEnemy
End if

Count distanceY between ThisEnemy Y and player Y.

If distanceY is smaller than CurrentClosestXY
 CurrentClosestXY = distanceY
 TheClosestEnemyID = ThisEnemy
End if

And so, after all enemies have been processed, you'll know the ID number of the closest enemy. No need to sort enemies in a list or something like that.

And of course those distance values could be useful for other purposes too, like when should enemies make their attack moves, and so on. So to optimize things all of that should be integrated with general enemy AI behaviour.

And also, if possible, integrate enemy blitting commands into the enemy collection browsing, so that the code follows a cycle like this:

handle enemy 1 logic
Draw enemy 1
handle enemy 2 logic
Draw enemy 2
handle enemy 3 logic
Draw enemy 3

This way the Blitter is constantly drawing the enemies in the background, while the CPU is calculating that distance stuff and AI logic. This is one of the biggest speed tricks in Blitz.

Unless I have misunderstood - not sure this would work as if baddie A is closer than baddie B on the x axis but the opposite is true then initially A would be closer and then B would be considered closer?

I am interested in the concept of blitting at different times. At the moment I just have a blitting loop in my game (all my games) and blit everything over the same loop. Had never thought of blitting at different times! Not sure this would work for TR though as the Bobs are z-ordered to print from top to bottom so once I have z-ordered them the only thing left to do is Blit and I can do this out of sequence as I have to have updated them all first before z-ordering but this is something I will bare in mind for future games.

Thanks.

[Havie]

Originally Posted by bebbo

there is no need for SQRT to find the closest.



And for small values can get more precision by using just one smul,
so discard too big values in advance(if the word overflows it's not accurate).

The smul should be around 40-50 cycles and a lookup might be faster, but you have to fix the sign in that case which eats some cycles up too...

; d0=x1 d1=x2 d2=y1 d3=y2
sub.w  d1,d0
bpl.s  .L1
neg.w  d0
.L1:            ; d0 = |d1-d0|

sub.w  d3,d2
bpl.s  .L2
neg.w  d2
.L2:            ; d2 = |d3-d2|

move.w d2,d1
add.w  d2,d0    ; d0 = |d1-d0| + |d3-d2|

sub.w  d1,d2     ; d2 = |d3-d2| - |d1-d0|
muls.w d2,d2
lsl.w  #2,d0
add.w  d2,d0    ; d0 = 4*(|d1-d0| + |d3-d2|)) + (|d3-d2| - |d1-d0|)²

with x2/y2 = 0

x1 y1 r
2 0 12
1 1 8
0 2 12



still not 100% accurate but close^^

How dare you contaminate the Blitz thread with assembly code!!!

But seriously, it's interesting to see the same concept in assembler - actually pretty clear. Thanks.

We might all be converted to the dark side one day...

[Master484]

Unless I have misunderstood - not sure this would work as if baddie A is closer than baddie B on the x axis but the opposite is true then initially A would be closer and then B would be considered closer?

Initially this system always marks the first enemy in the list as the closest, because the comparison value starts at 999, and so any XY distance value is smaller than that.

And after that, as the rest of the enemies are processed, the comparision value "CurrentClosestXY" and the "closest enemy ID" will only be updated if enemy X or Y are found to be smaller than the value held in "CurrentClosestXY".

So, if the list has two enemies, A and B, then it goes like this:

Baddie A is processed first, and will initially be marked as the closest.
Then Baddie B is processed.
If baddie B's X or Y were found to be smaller, then it'll be marked as the closest.
But if it's X or Y were equal or larger, then nothing happens, and baddie A will remain as the closest.

And if there were a baddie C, then it in turn would be compared against the "current closest" candidate, either A or B.

In other words, it's a simple "find the best case" routine:

The routine browses through the entire collection, and compares the current "best case" with the XY distance values of each object. If a better case is found (=smaller distance value), then the "best case" gets updated and it's ID number is saved. But if no better case is found, then the old "best case" and the old ID remain untouched.

The first object is always assumed to be the "best case", and will remain so, unless a better case is found. And when a better case is found, then that in turn is assumed to be the "best case". And this goes on, until all objects have been browsed, leaving us with the actual "best case" in the end.

---

And about the blitting commands, when Blitz sees any graphics drawing command such as "Blit", it won't start executing it unless the blitter is free to receive new orders. And so, if the blitter is already busy, Blitz (or the CPU) has no other choice than to wait until the current blitting operation has been finished. This is the classic "waiting for the blitter" situation, that all Amiga coders try to avoid. It may not matter so much if you don't draw a lot of stuff, but if you start getting slowdown, then this is one of the tricks to try out.

[Havie]

Thanks for this - I was originally working form this premise except I was checking all the x coords first which wasn't working. I have it working using squaring of numbers so will keep it like that for now - just a few bugs to work through and then movement of baddies is sorted!

Thanks for your help - it's always good to see how others approach a problem (usually in a simpler way than me).