14 November 2021, 15:01 | #1 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
Calculate closest to player
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? |
14 November 2021, 15:44 | #2 |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
|
14 November 2021, 17:34 | #3 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
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? |
14 November 2021, 18:06 | #4 |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
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.
|
14 November 2021, 19:18 | #5 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
|
15 November 2021, 16:40 | #6 |
Banana
Join Date: Jul 2016
Location: Darmstadt
Posts: 1,214
|
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.
|
15 November 2021, 18:56 | #7 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
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! |
17 November 2021, 17:53 | #8 |
Registered User
Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 525
|
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: Code:
CurrentClosestXY = 999 TheClosestEnemyID = 999 Code:
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 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. |
18 November 2021, 14:54 | #9 |
bye
Join Date: Jun 2016
Location: Some / Where
Posts: 680
|
sometimes it's good enough to consider min(dx + dy)...
... i's not a perfect circle but it's quick^^ |
18 November 2021, 19:23 | #10 |
Banana
Join Date: Jul 2016
Location: Darmstadt
Posts: 1,214
|
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. |
19 November 2021, 08:32 | #11 | |
bye
Join Date: Jun 2016
Location: Some / Where
Posts: 680
|
Quote:
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... Code:
; 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|)² x1 y1 r 2 0 12 1 1 8 0 2 12 still not 100% accurate but close^^ |
|
20 November 2021, 08:17 | #12 | |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
Quote:
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. |
|
20 November 2021, 08:20 | #13 | |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
Quote:
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... |
|
20 November 2021, 10:34 | #14 | |
Registered User
Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 525
|
Quote:
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. |
|
20 November 2021, 17:23 | #15 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
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). |
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
How to calculate possible blit times? | Tigerskunk | Coders. Asm / Hardware | 32 | 11 January 2022 08:24 |
Closest Amiga game to Geometry Wars? | Octopus66 | Retrogaming General Discussion | 6 | 16 January 2018 21:02 |
Which sound frequency setting is closest to original Amiga | rsn8887 | support.WinUAE | 19 | 03 December 2011 19:36 |
Closest console to the Amiga. | Fred the Fop | Retrogaming General Discussion | 57 | 21 April 2009 21:48 |
The closest you'll get to a modern day Amiga experience | Galaxy | Retrogaming General Discussion | 8 | 15 June 2008 20:31 |
|
|