English Amiga Board


Go Back   English Amiga Board > Coders > Coders. Asm / Hardware

 
 
Thread Tools
Old 09 March 2019, 01:09   #41
Photon
Moderator

Photon's Avatar
 
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.
Photon is offline  
Old 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.
ReadOnlyCat is offline  
Old 10 April 2019, 13:28   #43
DanScott
Lemon. / Core Design

DanScott's Avatar
 
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
DanScott is offline  
Old 10 April 2019, 20:48   #44
Photon
Moderator

Photon's Avatar
 
Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 4,765
Quote:
Originally Posted by ReadOnlyCat View Post
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 View Post
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 View Post
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 View Post
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 View Post
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.
Photon is offline  
Old 06 June 2019, 02:45   #45
ReadOnlyCat
Code Kitten

 
Join Date: Aug 2015
Location: Montreal/Canadia
Age: 48
Posts: 1,143
Quote:
Originally Posted by Photon View Post
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 View Post
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 View Post
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 View Post
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 View Post
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 View Post
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.
ReadOnlyCat is offline  
Old 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
buzzybee is offline  
Old 08 June 2019, 21:26   #47
Photon
Moderator

Photon's Avatar
 
Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 4,765
Quote:
Originally Posted by ReadOnlyCat View Post
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
Photon is offline  
Old 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.
zero is offline  
Old 11 August 2019, 15:04   #49
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
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.
Shatterhand is offline  
Old 11 August 2019, 15:31   #50
roondar
Registered User

 
Join Date: Jul 2015
Location: The Netherlands
Posts: 1,287
Quote:
Originally Posted by Shatterhand View Post
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.
roondar is offline  
Old 12 August 2019, 10:23   #51
zero
Registered User

 
Join Date: Jun 2016
Location: UK
Posts: 333
Quote:
Originally Posted by Shatterhand View Post
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.
zero is offline  
Old 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)
NorthWay is offline  
Old 12 August 2019, 12:59   #53
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Sunny Bournemouth, UK
Posts: 430
Quote:
Originally Posted by NorthWay View Post
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 ?
DanScott is offline  
Old 12 August 2019, 15:41   #54
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
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.
Shatterhand is offline  
Old 12 August 2019, 16:38   #55
zero
Registered User

 
Join Date: Jun 2016
Location: UK
Posts: 333
Quote:
Originally Posted by NorthWay View Post
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

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.

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.
zero is offline  
Old 12 August 2019, 18:16   #56
touko
Registered User

touko's Avatar
 
Join Date: Dec 2017
Location: france
Posts: 93
Quote:
Originally Posted by zero View Post
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 .
touko is offline  
Old 12 August 2019, 18:27   #57
roondar
Registered User

 
Join Date: Jul 2015
Location: The Netherlands
Posts: 1,287
Quote:
Originally Posted by zero View Post
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 ;)
roondar is offline  
Old 12 August 2019, 19:15   #58
Retro1234
Boo

Retro1234's Avatar
 
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.
Retro1234 is offline  
Old 12 August 2019, 23:38   #59
Photon
Moderator

Photon's Avatar
 
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.)
Photon is offline  
Old 12 August 2019, 23:54   #60
NorthWay
Registered User
 
Join Date: May 2013
Location: Grimstad / Norway
Posts: 608
Quote:
Originally Posted by DanScott View Post
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.
NorthWay is offline  
 


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

Similar Threads
Thread Thread Starter Forum Replies Last Post
Games with collision detection disabling cheat? alkis21 Retrogaming General Discussion 9 03 January 2018 04:54
Fast(est) method for bounding box collisions? MickGyver Coders. Blitz Basic 2 02 October 2017 21:17
Possible problem with Collision detection ! amilo3438 support.WinUAE 5 11 January 2017 18:35
Collision Detection sandruzzo Coders. General 5 10 June 2016 12:50
Collision detection: 2 doubts 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 Jump


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


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.
Page generated in 0.09436 seconds with 13 queries