English Amiga Board Fast (bounding box?) Collision detection
 Register Amiga FAQ Rules & Help Members List  /  Moderators List Today's Posts Mark Forums Read

 09 March 2019, 01:09 #41 Photon Moderator   Join Date: Nov 2004 Location: Eksjö / Sweden Posts: 4,765 I'm sure most of the methods have already been mentioned, but this made me write an article on Coppershade on the topic. Good collision detection definitely enhances a game I think, and this was good inspiration (Edit: Well, apparently I have to write flawless articles for some silly reason, so I just wasted four hours making this "The ultimate power in the Universe". (Translation: article updated. ) It now explains how to apply the hitbox check code appropriately, and the exact criteria to check for the Skip Issue (with illustration) in your game. Onwards, to games better than those of yore!! Last edited by Photon; 10 March 2019 at 00:03.
 08 April 2019, 01:58 #42 ReadOnlyCat Code Kitten   Join Date: Aug 2015 Location: Montreal/Canadia Age: 48 Posts: 1,143 The fastest collision tests are the ones you do not do. Organizing your objects hierarchically allows to avoid unnecessary tests. The grid approach is just an example of that which is quite expensive to maintain but there are simpler hierarchical schemes which work well: Do the enemy objects move a lot relative to one another (if at all)? For example, if all enemies of a wave have the same horizontal speed, you can sort them for a negligible cost at creation time along the X axis. This way, as soon as you have established that player.X < enemy.X you can stop testing: the remaining ones do not collide. That works vertically as well. If enemies move in a group that keeps the same shape, compute the bounding box of that group, and test that bounding box before testing each element of that group. I would generally recommend sorting moving objects horizontally and vertically and updating the sorted lists/arrays as needed. You can even spread the update of these sorted lists over several frames. If you add some tolerance (say max_enemy_speed * nb_frames_update pixels) to your tests, then you will never miss a collision.
 10 April 2019, 13:28 #43 DanScott Lemon. / Core Design   Join Date: Mar 2016 Location: Sunny Bournemouth, UK Posts: 430 Have to agree, a sorted list of objects isn't going to change dramatically from frame to frame, and is very quick to re-sort...usually one quick pass is enough
10 April 2019, 20:48   #44
Photon
Moderator

Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 4,765
Quote:
 Originally Posted by ReadOnlyCat The fastest collision tests are the ones you do not do.
And also the only cause of missing when you hit, or falling through the map. Happens to this day, and is a great source of frustration.

Quote:
 Originally Posted by ReadOnlyCat Organizing your objects hierarchically allows to avoid unnecessary tests. The grid approach is just an example of that which is quite expensive to maintain but there are simpler hierarchical schemes which work well:
Grid doesn't save time (tested by me). (And is not hierarchical.)

Quote:
 Originally Posted by ReadOnlyCat Do the enemy objects move a lot relative to one another (if at all)? For example, if all enemies of a wave have the same horizontal speed, you can sort them for a negligible cost at creation time along the X axis. This way, as soon as you have established that player.X < enemy.X you can stop testing: the remaining ones do not collide. That works vertically as well. If enemies move in a group that keeps the same shape, compute the bounding box of that group, and test that bounding box before testing each element of that group.
Sorting is good if you want to have them sorted for another reason. Moving at the same speed is then not a requirement for sorting them in at creation. (And is not hierarchical either.)

I think you just have to tell us what case you have in mind I can't conjure it up in my mind. (A cloud of spaceships? That won't help for testing a bullet tearing through them. Well I mean, group them all you want but it costs time too, and as soon as it enters the cloud it reverts back to worst case which is checking which one it hit.)

Quote:
 Originally Posted by ReadOnlyCat I would generally recommend sorting moving objects horizontally and vertically and updating the sorted lists/arrays as needed. You can even spread the update of these sorted lists over several frames. If you add some tolerance (say max_enemy_speed * nb_frames_update pixels) to your tests, then you will never miss a collision.
Quote:
 Originally Posted by DanScott Have to agree, a sorted list of objects isn't going to change dramatically from frame to frame, and is very quick to re-sort...usually one quick pass is enough
Collision checks are similar to sorts in that you want to cut down on comparisons. Checks are of an order, in both cases. Sorts have swaps tho costing extra without checking the box. That's the problem.

Continuous-sorting methods are also thwarted by a few objects moving in the opposite direction of others (or standing still while the others move in any direction). A game that doesn't have that would be some special case game, it's just hard to see.

I wouldn't recommend sorting every frame to someone making a game, because I would need to know if the case is special enough. If speeds are slow, correctly calculated every-nth-frame checks with knowledge of the skip issue saves much more time.

Generally I of course agree that you should remove unnecessary collision checks from your code. It's just that you're aware so you don't remove necessary checks. If you want to cut down on collision checks, the best way to avoid the order of many-to-many is to know that it is a bullet, or an enemy, or the player, or a collidable.

So knowing more about the objects is the only way to cut down on checks. Simplest case, a new bullet is added to the bullet list and not to the general list of objects. So I'm challenging these suggestions because they don't decrease the order. And that makes the difference between a routine that takes 20 scanlines and one that takes 2 frames, that just how it is.

Last edited by Photon; 10 April 2019 at 20:59.

06 June 2019, 02:45   #45
Code Kitten

Join Date: Aug 2015
Age: 48
Posts: 1,143
Quote:
 Originally Posted by Photon And also the only cause of missing when you hit, or falling through the map. Happens to this day, and is a great source of frustration.

Obviously, one should only remove the unnecessary collision tests.

Quote:
 Originally Posted by Photon Grid doesn't save time (tested by me). (And is not hierarchical.)
(yup, clearly not hierarchical, not sure why I categorized it as such )
That does not surprise me, grids are used by PhysX in the Unreal Engine but are only efficient when there are a large number of objects per grid square otherwise the overhead is just too high.

Quote:
 Originally Posted by Photon Sorting is good if you want to have them sorted for another reason. Moving at the same speed is then not a requirement for sorting them in at creation. (And is not hierarchical either.)
Sorting has indeed nothing to do with object hierarchy indeed but I was not implying that it had.

Quote:
 Originally Posted by Photon I think you just have to tell us what case you have in mind I can't conjure it up in my mind. (A cloud of spaceships? That won't help for testing a bullet tearing through them. Well I mean, group them all you want but it costs time too, and as soon as it enters the cloud it reverts back to worst case which is checking which one it hit.)
Yup, a cluster of objects which stay close to one another.
No need to tests the individual objects in that cluster if the bounding box of the cluster does not collide.

Quote:
 Originally Posted by Photon Collision checks are similar to sorts in that you want to cut down on comparisons. Checks are of an order, in both cases. Sorts have swaps tho costing extra without checking the box. That's the problem. Continuous-sorting methods are also thwarted by a few objects moving in the opposite direction of others (or standing still while the others move in any direction). A game that doesn't have that would be some special case game, it's just hard to see.
This is why I mentioned that this depends on the behaviour of the game objects.
In shoot'em ups it is frequent for enemy waves to stay coherent, that is, enemies in the wave stay in the same order and thus do not need to be re-sorted.
Tagging waves with this information permits to know that their members do not need to be re-sorted and that they should be tested in order (based on the position of the player).

Quote:
 Originally Posted by Photon I wouldn't recommend sorting every frame to someone making a game, because I would need to know if the case is special enough. If speeds are slow, correctly calculated every-nth-frame checks with knowledge of the skip issue saves much more time. Generally I of course agree that you should remove unnecessary collision checks from your code. It's just that you're aware so you don't remove necessary checks. If you want to cut down on collision checks, the best way to avoid the order of many-to-many is to know that it is a bullet, or an enemy, or the player, or a collidable. So knowing more about the objects is the only way to cut down on checks. Simplest case, a new bullet is added to the bullet list and not to the general list of objects. So I'm challenging these suggestions because they don't decrease the order. And that makes the difference between a routine that takes 20 scanlines and one that takes 2 frames, that just how it is.
I agree and was under the impression that this was more or less what I was saying but it looks I will have to work on making myself clearer.

 06 June 2019, 09:28 #46 buzzybee Registered User   Join Date: Oct 2015 Location: Landsberg / Germany Posts: 238 Thought you guys might be interested how the player-bullet-to-object collission system works in RESHOOT R. Here is my quick roundup All player bullets are made of sprites 2,3,4,5 CLXCON determines if further checks are useful If yes -> conventional bounding box comparisons against other objects No sorting or whatever. Did some testing and I could not really see any benefit, instead it seemed more efficient to implement an optimised object data list and a separate collidable objects list generated each frame from the object data structure, while preparing objects for blitting Hence player bullets are excluded form this list, as there is no need to check these vs. other player bullets. So are explosions, particles, extra symbols and most enemy bullets (got upto 60 of them in some scenes) The remaining objects are coll-checked, which takes up not too much rastertime
08 June 2019, 21:26   #47
Photon
Moderator

Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 4,765
Quote:
 Originally Posted by ReadOnlyCat I agree and was under the impression that this was more or less what I was saying but it looks I will have to work on making myself clearer.
Don't worry It's just in the context of recent conversation, it seemed like you hoped sorting and special-casing would help and it doesn't. I stress this to prevent coders from wasting time, both rastertime and coding time. F.ex. grouping = bounding box = pretty much the same as checking each of the objects for box collision.

And if you sort the objects, you still have to find the start/stop X/Y for comparison, and now you've wasted time sorting and searching for no real benefit.

This is the problem; there are no smart time shortcuts, because to not miss one you must make sure you don't, and this is comparable in time to the check itself. The exceptions are planning this in early in the game and adapt the game idea, and taking advantage of free hardware collision detection.

Anyway I think we both have the same goal in mind, games with no frustrating collision misses

 11 August 2019, 11:44 #48 zero Registered User   Join Date: Jun 2016 Location: UK Posts: 333 Have a look at this video of Gradius on the PC Engine: [ Show youtube player ] The collision detection is "loose" to say the least. The level 1 boss (volcanoes) at 2:30 are a great example. Note how some of the rocks thrown out explode well above the ship and the laser beams. The PC Engine has an 8 bit CPU running at around 8MHz, and there are a lot of sprites on screen. Sprites are nearly free on the PC Engine but the collision detection isn't. My guess is that the hit box is massive and tile based. So for example a enemy might occupy the tile at \$12,\$17. That can be combined into a single 16 bit number \$1217 and then checked very quickly to see if a bullet also occupies the same tile. No bounding box. If you look at enemy movements they tend to stick to a grid so that these tile based hit boxes are more accurate. The larger enemies maybe have multiple tile hitboxes.
 11 August 2019, 15:04 #49 Shatterhand Warhasneverbeensomuchfun   Join Date: Jun 2001 Location: Rio de Janeiro / Brazil Age: 36 Posts: 3,341 I also believe sorting for a shoot'em up isn't really that useful, at least if you never want to miss a frame. Everytime I try to optimize some code I always want it to work as fast as possible at the worst case scenario. Sorting objects on an axis to stop doing unnecessary is great up until you get the worst case scenario and the code have to do all of them anyway. So if the collision checking makes me miss a frame at the worst case scenario, it's not going to work for me. This is a subject that really sparks me a lot of interest. I am coding a shoot'em up too (but not in Asm, I see all this code in Asm and all I get is a headache ). Player vs Enemy is done simply with a sprite X playfield collision done in the hardware and it works wonders for me. But player bullets vs enemies is the real culprit here. I am already using the "only test half of frames" with "expanded hitbox" and I'd still like to get new ideas to make stuff faster. The grid idea always looks good on paper but, when I try to implement it, I am still doing basically the same number of comparisions on code so still no banana. When I see a game like Swiv on the Amiga running at 50 fps with a shitload of player bullets testing against a shitload of enemies, I know there's gotta be some smarter way to do it.
11 August 2019, 15:31   #50
roondar
Registered User

Join Date: Jul 2015
Location: The Netherlands
Posts: 1,287
Quote:
 Originally Posted by Shatterhand When I see a game like Swiv on the Amiga running at 50 fps with a shitload of player bullets testing against a shitload of enemies, I know there's gotta be some smarter way to do it.
In case it makes you feel better, SWIV does not run at 50FPS. It runs at 25FPS and sometimes slows down to 17FPS.

As for collisions, the easiest optimisations are to check the player using hardware collision detection (which you already do) and splitting up collision checks into separate groups of objects that don't interact.

For instance:
• Check player using hardware
• Check player bullets only vs enemies that are 'alive' and on screen (i.e. don't check vs enemy bullets or enemies that are exploding)
• Check bonus items separate from the above
• Program/script the enemy movement so it never needs to check for collisions vs walls.
This is faster than the simplest approach where you simply check all objects vs all objects. Another approach is to try and get the code that does the actual checking as optimal as possible, though it tends to be hard to save much time this was as the algorithm isn't very complicated. Other optimisations are harder to do and often end up costing as much in preparation time as you save during the checking.

12 August 2019, 10:23   #51
zero
Registered User

Join Date: Jun 2016
Location: UK
Posts: 333
Quote:
 Originally Posted by Shatterhand The grid idea always looks good on paper but, when I try to implement it, I am still doing basically the same number of comparisions on code so still no banana.
Then you are doing it wrong ;-)

Bounding box looks like this:

Code:
`if (x >= box_left) && (x <= box_right) && (y >= box_top) && (y <= box_bottom)`
Where as grid looks like this:

Code:
`if (player_grid == bullet_grid)`
So it's one test instead of four. One trick you can do is to use this to eliminate most of the bullets, which will be far away from the player, and then do a more accurate test on just the ones that are very close. It helps if the player has a tiny hit box like typical Japanese shooters.

Edit: I forgot another classic example of grid collision detection: PacMan! In PacMan collisions happen when PacMan and a ghost occupy the same tile. It actually make the game more exciting because the ghosts can get really close to the player, actually touching, and the player can still get away sometimes. Doesn't feel janky at all.

 12 August 2019, 12:35 #52 NorthWay Registered User   Join Date: May 2013 Location: Grimstad / Norway Posts: 608 Can't you do bounding box with min(abs(x_center-x_box_center),abs(y_center-y_box_center)) < (radius+box_radius)
12 August 2019, 12:59   #53
DanScott
Lemon. / Core Design

Join Date: Mar 2016
Location: Sunny Bournemouth, UK
Posts: 430
Quote:
 Originally Posted by NorthWay Can't you do bounding box with min(abs(x_center-x_box_center),abs(y_center-y_box_center)) < (radius+box_radius)
assumes your box is a regular square shape ?

 12 August 2019, 15:41 #54 Shatterhand Warhasneverbeensomuchfun   Join Date: Jun 2001 Location: Rio de Janeiro / Brazil Age: 36 Posts: 3,341 I don't code in asm, all my Amiga code is done on Blitz Basic. So first let me bow before all you Gods who code in Asm, as I am just a small learning peasant. :P :P The boundbox approach Northway suggests is freaking slow on Blitz Basic because the ABS function is slow as hell there. All the enemies on my games have square hitbox so that would work great. As for the grid approach... I don't remember what I was doing, but I remember in the end I didn't gain anything by doing it. But yeah, probably doing it wrong. I'll try it again.
12 August 2019, 16:38   #55
zero
Registered User

Join Date: Jun 2016
Location: UK
Posts: 333
Quote:
 Originally Posted by NorthWay Can't you do bounding box with min(abs(x_center-x_box_center),abs(y_center-y_box_center)) < (radius+box_radius)
You can, but that's still

2 x subtractions
2 x sign check
2 x sign change
1 x comparison/branch

compared to

1 x comparison/branch

Even with heavy asm optimization it's going to be several times slower.

Another interesting trick in Gradius is that when there are too many sprites on screen it drops the player's bullets first. They still get hit detection but flicker.

I'm wondering about the laser weapon too. Probably not necessary to check the whole length of it, just the start and end points. Nothing moves fast enough to pass through the middle and at worst it's death will only be delayed by a few frames.

12 August 2019, 18:16   #56
touko
Registered User

Join Date: Dec 2017
Location: france
Posts: 93
Quote:
 Originally Posted by zero The PC Engine has an 8 bit CPU running at around 8MHz, and there are a lot of sprites on screen. Sprites are nearly free on the PC Engine but the collision detection isn't.
I coded a bounding box detection routine on PCE which takes 80 cycles if collision .

12 August 2019, 18:27   #57
roondar
Registered User

Join Date: Jul 2015
Location: The Netherlands
Posts: 1,287
Quote:
 Originally Posted by zero You can, but that's still 6 x memory reads 2 x subtractions 1 x addition 2 x sign check 2 x sign change 1 x comparison/branch compared to 2 x memory reads 1 x comparison/branch Even with heavy asm optimization it's going to be several times slower.
This is a flawed comparison.

In order for the grid system to work, every object needs to know where in the grid it is. Setting aside the obvious problem of objects potentially falling into multiple grid coordinates (and yes, that even happens if the grid is huge and can cause issues if not accounted for), you still need to calculate which grid coordinate each object belongs too. This is not needed for bounding box collisions.

That cost is missing in your comparison.

Furthermore, most properly coded bounding box algorithms will exit as soon as possible. The version Northway shows is one of the exceptions here. Using a simple set of comparisons and exiting on the first 'fail' tends to have most objects leave the comparisons on the first or second test.

Last edited by roondar; 12 August 2019 at 20:29. Reason: Clarified my response a bit, Northway's algorithm is a different one from what I was comparing to ;)

 12 August 2019, 19:15 #58 Retro1234 Boo   Join Date: Jun 2006 Location: 5150 Posts: 4,348 A Grid System is probably a good idea, the grid has to be as small as you smallest object Your Grid/Boxes all have a Variable As you display each object/Bob you calculate what grid/box it's in, your variable you add 1 to that grid/box if the Variable reads 2+ you've got a hit. To save Variables going into crazy numbers when a Vertical line of the Grid goes off screen it wraps backs round. Last edited by Retro1234; 12 August 2019 at 20:52.
 12 August 2019, 23:38 #59 Photon Moderator   Join Date: Nov 2004 Location: Eksjö / Sweden Posts: 4,765 A grid is very special case. Furthermore, it must not round coordinates to the grid, or it will be more inaccurate even than mere box collision detection. If there are many objects to test, they are normally the same size, so it's nowhere near as extreme a special case. For the objects that are the same size, you can do a one-to-many collision test with 2 tests instead of 4, with an early exit in most cases, as demonstrated in my code. This brings it close to this (character mode?) grid collision detection with none of the drawbacks - apart from it being mere box collision detection, of course. As I write, I recommend planning hardware collision detection into a game as much as is possible with a given game idea. (This may well affect screen mode and size, so it's very valuable to decide this beforehand, if framerate is important.)
12 August 2019, 23:54   #60
NorthWay
Registered User

Join Date: May 2013
Posts: 608
Quote:
 Originally Posted by DanScott assumes your box is a regular square shape ?
I wasn't meant to assume anything much - you can muddle the radius for objects if you want to allow some overlap without triggering as hitting each other.

Also, on a grid any object can occupy 4 entries (or more if your object is larger than the size per grid space), and _then_ you need to do a check if someone occupy the same grid.

It all depends on what the logic demands. If you run into n*n checks then I'd put my money on a grid.

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

 Similar Threads Thread Thread Starter Forum Replies Last Post alkis21 Retrogaming General Discussion 9 03 January 2018 04:54 MickGyver Coders. Blitz Basic 2 02 October 2017 21:17 amilo3438 support.WinUAE 5 11 January 2017 18:35 sandruzzo Coders. General 5 10 June 2016 12:50 nandius_c Coders. Asm / Hardware 6 30 November 2014 00:53

 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         project.AmigaLive     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     Kinky Amiga Stuff     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         Coders. Entries Off Topic     OT - General     OT - Entertainment     OT - Sports     OT - Technical     OT - Gaming

All times are GMT +2. The time now is 04:42.

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