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: 326
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: 326
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,943
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: 573 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,943
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,943 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: 573
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: 326
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, 9 views)

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

22 June 2018, 14:55   #113
Master484
Registered User

Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 326
I found a way to dramatically speed up the collisions: The Blitz command BlitColl.

I simply put that before the bullet QBlits, and if it returns true, then a collision variable is set to -1. And the collision routines for that bullet are not done unless this collision variable is set.

I actually tested Blitcoll before, but I did it in the wrong way and placed it after the QBlit, in which case it always returned a collision, because it saw the bullet graphics that the QBlit just draw a moment before, and therefore I thought that the command was too slow. But when placed before the QBlit, everything suddenly worked as intended.

So I made a new demo version again, the ADF with source code is in the attachment of this post.

Collision performance now at 50 FPS is this (A500, no Fast, Cycle Exact) :

1 enemy vs 32 bullets
10 enemies vs 20 bullets
16 enemies vs 14 bullets

So in the cases of many enemies vs many bullets speed is about 6 bullets better. Only in the case of 1 enemy vs many bullets performance is worse; this is caused by the BlitColl that is now done for every bullet.

Although now it's harder to determine where the slowdown starts, because now the collisions themselves trigger the slowdown, rather the amount of objects. So I think the performance is actually 8 bullets better, but when the screen is full, there are collisions all the time, and so for example in 16 enemies vs 16 bullets the speed is constantly altering between 50 FPS and 25 FPS.

But in a real game the collisions would last only 1 frame, because usually bullets are deleted when they hit something, and enemies explode, and so on.

---

And about the BlitColl command, it is actually a pixel-perfect collision method, that checks if any of the pixels locations that are about to be drawn to already contain some graphics. So it returns a collision if the Bitmap contents in the drawing locations are anything else than color 0. So this command does a sort of a "BOB vs Playfield" collision detection.

One slightly faster way would be to check just one pixel with Point (X,Y) at the bullet center, and activate collisions if color is greater then 0. But that is somewhat inaccurate, and because BlitColl is so fast, I used it. But the Point command was some 10 scanlines faster, so if more speed is still needed, then that is one way.

I just feel so stupid now when I realize that Blitz already had a command like this to do fast BOB collisions, but I just couldn't figure out how to use it properly until now.

Although of course BlitColl just tells if a collision (graphics overlap) has happened or not, so the 4 IF method is still used to determine what collided with what. But the difference now is that this check is no more done every frame for all bullets, but only in those frames when a collision has happened, and only for the bullet that caused the collision.

And also the bullets are still divided into 2 groups, that check their collisions in alternating frames.

---

So, now things look much better. The "all bullets vs all enemies" collision code now consumes only some 17 % of the "theoretical maximum drawing power". In all likelyhood this is the fastest that BOB vs BOB collisions can be in Blitz.

And remember that these type of "all bullets vs all enemies" collisions are only needed for player bullets. Enemy bullets only need to check one object: the player. So use this "BlitColl + 4 IF" method for player bullets vs enemies collisions, and have a separate Sprite command based collision routine for enemy bullets vs player sprite.
Attached Files
 CollisionDemoV96.zip (37.0 KB, 5 views)

 22 June 2018, 16:10 #114 idrougge Registered User   Join Date: Sep 2007 Location: Stockholm Posts: 3,367 I never mentioned BlitColl because it tests a blit against any pre-existing graphics, which means that it only works on a clear background like in your test program. The only way to make this useful is if you do a 1982-style space game or use dual playfield with all bob activity on the front playfield.
23 June 2018, 10:56   #115
Master484
Registered User

Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 326
Quote:
 I never mentioned BlitColl because it tests a blit against any pre-existing graphics, which means that it only works on a clear background like in your test program. The only way to make this useful is if you do a 1982-style space game or use dual playfield with all bob activity on the front playfield.
That's right, in a single playfield 16 or 32 color mode game BlitColl would be hard to use.

An alternative command for those games would be the Point(X,Y) which can be used in the same way as BlitColl, although with less accuracy because it checks the color of only 1 pixel. But of course using Point to check collisions in a 16 color game would mean that the enemies and background couldn't use any same colors, and so the resulting graphics might be end up looking like 8+8 dual PF graphics, but without any of the benefits of real dual PF.

So I think this makes 8+8 dual playfield the best choice for a shmup that needs to check lots of collisions.

---

Although there is a way to make BlitColl work on single playfield too, and that would be to have most of the screen in background color 0. For example the first levels of Turrican mostly have only clear sky in the background, and in many places only the ground tiles contain graphics. So BlitColl could maybe be used.

And also in many 16 color shmups there screen is mostly space, with stars made of sprites, such as in Sirius 7:

In a game like this BlitColl could be used. Even if the stars in the background would be bitmap graphics, it still might not matter so much, because the stars vs bullets collisions would be relatively rare. Only when the background is totally filled with graphics BlitColl becomes useless.

Also by the way, Sirius 7 runs in 50 FPS and the bullets seem to be BOBs, and so are the enemies, so it has to do bob vs bob collisions. And tried to count the maximum object amounts in screen, and this was the result: 16 enemies + 14 player bullets + 5 enemy bullets. So it does better than my demo, but the object amounts are quite close. Although the bullet sizes in Sirius 7 are 5*5 and 8*3, while in my demo they are 8*8.

 Yesterday, 01:40 #116 idrougge Registered User   Join Date: Sep 2007 Location: Stockholm Posts: 3,367 It's quite feasibly to treat bullets as points instead of bodies, so you only need four IFs without any addition or subtraction involved, thereby reducing the number of cycles required for a collision test quite radically.
 Yesterday, 18:37 #117 Paulso Registered User   Join Date: Jan 2016 Location: Ireland Posts: 12 Would ShapesHit work if you only need to check the rectangular shape? I'm doing a bit of research on Blitz & there was a earlier post on BlitColl & Bitplane use here http://eab.abime.net/showthread.php?t=85218 Page 12 Blitz user magazine issue 2 has some example of BlitColl use inside a While Wend: https://ia601709.us.archive.org/35/i...oftware_NZ.pdf

 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     Coders. Contest Off Topic     OT - General     OT - Technical     OT - Entertainment     OT - Sports     OT - Gaming

All times are GMT +2. The time now is 10:20.

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