English Amiga Board Quickest way to test collisions
 Register Amiga FAQ Rules & Help Members List  /  Moderators List Today's Posts Mark Forums Read

17 June 2018, 14:33   #101
Master484
Registered User

Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 323
Quote:
 This sounds like a good use case for macros - effectively automated loop unrolling, where you can leave your code referencing the macro, and the compiler will insert the subroutine at compile time for you.
Yeah I know about macros, and some day I'll probably try to learn how to use them.

Quote:
 I need to check the syntax but you should be able to replace the direction change "multiplication by - 1" with a negation and an addition (dir = (~dir) + 1). Assuming two's complement.
I'll check if this is possible, but I'm not sure if that sort of variable change trick from positive to negative and vice versa can be done.

Quote:
 I only ask because some times I know it seems strange but seems to be quicker sometimes than spaghetti, especially when you have loops in loops.
Hmm, I don't know why that would happen, but I guess it's possible, and this is one thing that could be tested.

Quote:
 That's just absurd. Are there any edge cases RectsHit must handle? Otherwise I can't understand how Acid Software could come up with a library routine that is slower than basic.
The 4 IF method means the technique where 4 nested IF..End IFs are used, and where the checks dont progress to the next IF unless the previous IF was true.

Although RectsHit is faster in the case where the collision actually happens, in most non-collision cases the 4 IFs is faster.

I made a quick test that compared RectsHit against the 4 IF.
Code:
```loop=0

x = 5
y = 5
a = 5
b = 5

Repeat

If RectsHit (x,y,16,16,a,b,16,16) then hit = 1

If x + 20 > a
If x < a + 20
If y +20 > b
If y < b +20
hit = 1
End If
End If
End If
End If

loop + 1

Until loop = 1000```
Results for RectsHit:

Hit happens = Frame 3 Vpos at 240
No hit = Frame 3 Vpos at 80

Results for 4 IF method:

4 IFs processed, hit happens = Frame 4 Vpos at 28
4 IFs processed, no hit = Frame 3 Vpos at 274
3 IFs processed, no hit = Frame 3 Vpos at 106
2 IFs processed, no hit = Frame 2 Vpos at 239
1 IF processed, no hit = Frame 2 Vpos at 67

---

So only if the checks progress to the 3rd IF, then RectsHit is faster.

But when you have a scenario where bullets randomly bounce in screen, then the first IF always eliminates approximately half of the bullets.

Because the first IF makes an "is bullet right side larger than target left side" check, then all smaller x values cause a fail, and the checks dont progress past the first IF. On a scenario where all bullets and objects are at random places in the screen, this means that about 50 % of the bullets will fail this first test.

And for those 50 % of bullets that pass the first test, then comes the second IF, that checks "is bullet left side smaller than target right side". This second check eliminates almost all cases in the screen, because with these X checks we have actually cheked entire two halves of the screen, and only a very small "corridor" still remains between the targets left and right wall + some small offsets.

And the 3rd and 4th IF checks only happen for those objects that are inside this corridor. This is the worst case scenario, and the point where speed starts to drop in comparison to RectsHit. But it happens so rarely, that it doesn't matter.

---

Another benefit of the 4 IF is that you can have many versions that check things in different order. For example if player bullets travel upwards only, then for them it makes sense to make the "Is bullet top side smaller than target bottom side" first, to maximize the cases where the checks stop at the first IF.

 17 June 2018, 17:08 #102 Retro1234 Bo Bo   Join Date: Jun 2006 Location: 5150 Posts: 3,911 4 IF method lol - Bounding Box and it should be more like 8 IFs or the use of up/down symbol or your checking 1 box against only one point of the other box. I still find it unlikely to be faster than inbuilt collision. Last edited by Retro1234; 17 June 2018 at 17:14.
18 June 2018, 13:43   #103
Master484
Registered User

Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 323
Quote:
 I still find it unlikely to be faster than inbuilt collision.
Believe it or not, it's true.

The speed of the 4 IFs is based on the fact that in most cases it only checks one or two IFs. The third and fourth IF almost never get executed.

But despite this, this is a true and accurate bounding box collision method.

The logic of how this 4 IF collision check works is reverse: instead of trying to find out if a collision has happened, it tries to find out the first condition where we can rule that a collision HAS NOT happened, and it tries to do this as fast as possible, with the least amount of checks possible.

If the screen has 100 bullets and 100 targets, then in 50 % of the cases the first IF is enough, because almost 50 % of the time bullet X will be smaller than target X. And the second IF does the same check but for other X direction, this time checking if bullet X is bigger than target X. And therefore after the second IF has been executed, 80 % to 90 % of the bullets have failed the test, because they were in the areas where a collision with the target cant happen. And so the last two IFs only happen for some 20 % to 10 % of the bullets, and these two last IFs check the targets in the narrow vertical corridor in the screen that still remains.

Quote:
 checking 1 box against only one point of the other box
I don't think this would be any faster. There would still need to be 4 IFs, because we would be checking 4 box walls against one (X,Y) point. So 2 checks for X axis and 2 checks for Y axis.

One method that would be faster would be if both boxes would have a XY point in the middle, and we would check the X and Y distance difference of the two points. But such a mathematical operation results in either a negative or positive value, like this:

X1 = 50
X2 = 70

X1 - X2 = -20
X2 - X1 = 20

But if there would be a fast way or a fast command to convert values from negative to positive and the other way around, then this would be the method to use.

---

And also I tested the Gosubs inside a For...Next, and I didn't see any speed boost for using Gosubs. But I only tested a simple case of two nested For...Nexts, where I put the inner one to a gosub.

---
---

But anyways I have found one other way to speed up the demo that I posted: I divided the screen into 4 "hit zones", and gave each enemy a variable that tells in which zone it is. And then I added a 5th IF to the 4 IF checks, which checks the bullets zone vs enemys zone. This ruled out 75 % of collisions cases right away, and brought a nice speed boost, although not as much as I hoped.

I'll post the updated demo version soon.

18 June 2018, 15:04   #104
Shatterhand
Warhasneverbeensomuchfun

Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,930
Quote:
 One method that would be faster would be if both boxes would have a XY point in the middle, and we would check the X and Y distance difference of the two points. But such a mathematical operation results in either a negative or positive value, like this: X1 = 50 X2 = 70 X1 - X2 = -20 X2 - X1 = 20 But if there would be a fast way or a fast command to convert values from negative to positive and the other way around, then this would be the method to use.
This really could be fast, but like you said (and I also proved it here), the ABS command is incredibly slow. There should be some way to do it faster.

 18 June 2018, 15:09 #105 E-Penguin Banana   Join Date: Jul 2016 Location: Darmstadt Posts: 569 Only four checks are required to test overlaps of two axis-aligned bounding boxes. The "zones" concept is analogous to the "cells" approach, but with vary large cells. There's probably a happy medium between cell/zone size and memory/computation tradeoff. I'm going to propose 16, as it's a nice power of 2
 18 June 2018, 16:42 #106 Retro1234 Bo Bo   Join Date: Jun 2006 Location: 5150 Posts: 3,911 4 point on a bullet only checks 1 point on an enemies that's no good.
18 June 2018, 16:46   #107
Shatterhand
Warhasneverbeensomuchfun

Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,930
Quote:
 Originally Posted by Retro1234 4 point on a bullet only checks 1 point on an enemies that's no good.
Look at Master484 code again. He is testing bounding box against bounding box with just 4 ifs.

 18 June 2018, 16:48 #108 Retro1234 Bo Bo   Join Date: Jun 2006 Location: 5150 Posts: 3,911 Ok I haven't looked, you can do it if you check the distance in-between otherwise your only checking one box against one pixel of the other object.
 18 June 2018, 16:52 #109 Shatterhand Warhasneverbeensomuchfun   Join Date: Jun 2001 Location: Rio de Janeiro / Brazil Age: 35 Posts: 2,930 His code is written above. Code: ```If x + 20 > a If x < a + 20 If y +20 > b If y < b +20``` It's testing a 20x20 box against another 20x20 box.
 18 June 2018, 17:57 #110 Retro1234 Bo Bo   Join Date: Jun 2006 Location: 5150 Posts: 3,911 Not sure Just Width IF X or X+Width > A-1 and < A+Width2 : Then hit
18 June 2018, 20:09   #111
E-Penguin
Banana

Join Date: Jul 2016
Posts: 569
Quote:
 Originally Posted by Shatterhand This really could be fast, but like you said (and I also proved it here), the ABS command is incredibly slow. There should be some way to do it faster.
You should be able to test the status register after the subtract and if negative negate the result. I'm not near a compiler right now but something like...
Code:
```Function FastAbsDiff{a.w, b.w}
;a is in d0
;b is in d1

sub.w d1, d0 ;result in d0
bmi .resultIsNegative

AsmExit ;end statement if result is positive

.resultIsNegative
neg d0 ; negate it
AsmExit ;

End Function

NPrint FastAbsDiff{3,4}```
Close; this seems to work. Use in place of ABS(a - b)
Code:
```Function.w AbsDiff{a.w, b.w}
SUB.w d1, d0
End Function

NPrint AbsDiff{100,3}
NPrint AbsDiff{3,100}```
prints 97 in both cases

-- edited again to add... --
I've done a quick compare to ABS(a-b) and the performance is practically identical. Damn.

Last edited by E-Penguin; 18 June 2018 at 21:58.

19 June 2018, 19:14   #112
Master484
Registered User

Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 323
Quote:
 I've done a quick compare to ABS(a-b) and the performance is practically identical. Damn.
Thanks for doing the tests with the ABS function.

I have tried to solve this problem on paper, trying to come up with formulas for counting the distance between X1 and X2, that would always bring either a negative or positive value as a result, no matter in which order the two values are, but it seems to be impossible.

---

But an updated version of the demo is now ready, and the ADF with source is in the attachment of this post.

It now uses the Display library instead of Slice library, and lots of small improvements have been made. The structure is better and code faster.

Also I added some sprites, press 7 and 8 to activate them. The Display Librarys CustomSprites command is used to multiplex all 8 sprites once at VPOS 100, which brings 16 sprites to screen. But the limitation of this method is that placing sprites to that multiplex Y line causes side effects. But surely it can be used for something.

The four hit-zones method that I mentioned is not used, because it caused "dead-zones" to the screen where collisions didn't register, and the speed increase in collisions was pretty much negated by having to count the zones for every object each frame.

I also tested sorting both the enemies and bullets by the Y-axis with the SortList command, and then tried to use this to limit the amount of list browsing. But the sorting took too much time, and the result was too slow, even if just the enemy collection was sorted each frame.

But, despite this, the program is now faster. The performance now is this on standard A500 without fast RAM, with cycle exact ON:

Drawing speed at 50 FPS:

Enemies: 29
Bullets: 43

Collision speed at 50 FPS:

1 enemy vs 37 bullets
10 enemies vs 14 bullets
16 enemies vs 8 bullets

---

So it's just a small improvement, it can do 1 or 2 bullets more depending on case, but better than nothing.

And the HIT text is still drawn every frame, so maybe 1 bullet is lost this way.

But the key to understanding these figures is that checking all bullets against just one target is very fast. It's only the 10 vs 10 scenarios that cause serious slowdown.

So we can have a game with many aliens, like 16, and the aliens can easily shoot 10 bullets, if the only collision check needed for those bullets is against the player.

But when player shoots, this is which causes the slowdown, because now all bullets have to checked against all aliens, and there aren't any real way to avoid this.

And so I think that the key to achieve good speed is to handle player bullets vs aliens collisions with the fast Blitz sprite collision commands as much as possible. I'm pretty sure this is the way it's done in every Amiga shooter that runs at 50 FPS. So either aliens or the player bullets need to be sprites. If both are BOBs, then the collision check cant use the sprite collisions commands, and slowdown is unavoidable.

So with this engine we could maybe have a game with 16 BOB enemies + maybe 10 enemy BOB bullets + player as a sprite + at least 6 player bullets made with sprites + maybe some more bullets or aliens or other stuff made with the sprite multiplexing trick. And that would still surely run at 50 FPS.
Attached Thumbnails

Attached Files
 CollisionTestV71.zip (36.7 KB, 8 views)

Last edited by Master484; 19 June 2018 at 19:28.

 Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

 Similar Threads Thread Thread Starter Forum Replies Last Post Shatterhand Coders. Blitz Basic 1 12 January 2017 18:51 Galahad/FLT Coders. Asm / Hardware 10 01 January 2017 17:23 jman Coders. Tutorials 5 03 September 2011 00:07 Doc Mindie support.WinUAE 6 17 October 2007 21:15 DeAdLy_cOoKiE Retrogaming General Discussion 4 24 March 2006 17:56

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home News Main     Amiga scene     Retrogaming General Discussion     Nostalgia & memories Support     New to Emulation or Amiga scene         Member Introductions     support.WinUAE     support.WinFellow     support.OtherUAE     support.FS-UAE     support.Hardware         Hardware mods         Hardware pics     support.Games     support.Demos     support.Apps     support.Amiga Forever     support.Amix     support.Other Requests     request.UAE Wishlist     request.Old Rare Games     request.Demos     request.Apps     request.Modules     request.Music     request.Other     Looking for a game name ?     Games images which need to be WHDified abime.net - Hall Of Light     HOL news     HOL suggestions and feedback     HOL data problems     HOL contributions abime.net - Amiga Magazine Rack     AMR news     AMR suggestions and feedback     AMR data problems     AMR contributions abime.net - Home Projects     project.Amiga Lore     project.EAB     project.IRC     project.Mods Jukebox     project.Wiki abime.net - Hosted Projects     project.aGTW     project.APoV     project.ClassicWB     project.Jambo!     project.Green Amiga Alien GUIDES     project.Maptapper     project.Sprites     project.WinUAE - Kaillera Other Projects     project.Amiga Demo DVD     project.Amiga Game Factory     project.CARE     project.EAB File Server     project.CD32 Conversion     project.Game Cover Art         GCA.Feedback and Suggestions         GCA.Work in Progress         GCA.Cover Requests         GCA.Usefull Programs         GCA.Helpdesk     project.KGLoad     project.MAGE     project.Missing Full Shareware Games     project.SPS (was CAPS)     project.TOSEC (amiga only)     project.WHDLoad         project.Killergorilla's WHD packs Misc     Amiga websites reviews     MarketPlace         Swapshop     Collections     EAB's competition Coders     Coders. General         Coders. Releases         Coders. Tutorials     Coders. Asm / Hardware     Coders. System         Coders. Scripting         Coders. Nextgen     Coders. Language         Coders. C/C++         Coders. AMOS         Coders. Blitz Basic Off Topic     OT - General     OT - Technical     OT - Entertainment     OT - Sports     OT - Gaming

All times are GMT +2. The time now is 08:51.

 -- EAB3 skin ---- EAB2 skin ---- Mobile skin Archive - Top