Collision Detection in Amiga GamesCollisions matter. It's why you smashed your joystick! This article details three of the methods of collision detection along with their efficiency, and provides a fast bounding box collision function.
Many-to-Many, One-to-Many, and One-to-OneThis is a thought that occurs naturally to the coder or designer while developing the game: "Which objects should damage which other objects?"
If damage is a vital factor for the gameplay, the number one factor is to plan detection so that one important object is matched against only the objects that can damage it. After that, apply any combination of these methods that fits the game.
Hardware Collision DetectionYou should poll CLXDAT when possible, typically at end-of-frame ("VERTB the next frame"). DBLPLF+Sprites (as per the example in the Hardware Reference Manual) was implemented in the Amiga custom chips precisely to off-load collision detection from the CPU completely - and will also detect things like missiles hitting the ground, well - any object overlapping another ("Many-to-Many") - at zero cost.
It's extremely powerful! Maybe your game wasn't or can't be designed to fit this mode, but definitely consider adapting a part of it to use this freebie... Else, consider the other methods.
The Other MethodsBriefly mentioning simple pixel-testing (btst) and math-based methods (such as using circles to approximate object contours to get an angle out for physics), below is a bounding box collision check that should be optimal* for 68000 - Scc is not useful in-loop, and tables increase the cycle count, so Bcc.
It will tell you if the bounding boxes of two objects intersect - but not if the actual pixels of the objects do!
BoxCollision: ;d0-d5=srcx,srcy,dstx,dsty,src box width/2+dst ;box width/2,src box height/2+dst box height/2 sub.w d2,d0 bpl.s .nondx neg.w d0 .nondx: cmp.w d4,d0 ;this will early-exit if bullets travel up or down. bhi.s .nohitx ;for left or right, change the x/y order. sub.w d3,d1 bpl.s .nondy neg.w d1 .nondy: cmp.w d5,d1 .nohitx:rts ;flags set to either hi or ls. or use Sls, -1=hit.
* Note the half width/height to minimize cycles, i.e 2px precision - hi/ls is inclusive rounding for false positives rather than a missed hit. For 1px precision, just double the deltas and sizes and use hs/lo.
Bitmap Collision DetectionThe Blitter has a result bit, BZERO, that will give an exact answer to whether pixels overlap. If you use an AND minterm and BZERO is 1, they don't collide.
These checks can be done in an off-screen, 1-bitplane buffer, checking just the contours ("masks" or filled outlines) of any two graphics that should be considered.
This means that you get a processing overhead of two 1-bitplane blits and a clear, but the blit only has to be as big as the union of the overlapping bounding boxes (so check with the code above first!) As with the hardware option, it gives a definite and unambiguous answer, and provides quality collision detection.
I recommend this for bullets against player ship, fighting game moves, and similar life-or-loss-of-life situations.
Most games didn't ever use proper collision detection, and if detection is too forgiving, the game is bad, and if it kills you when you didn't get hit, the game is evil, unfair, and bad. :)
Masking and Missed Collisions
The Color ZeroSometimes, the graphics artist or coder might use color 0 in playfields or sprites as background color. This will in some cases, just by sheer accident, make pixels simply not overlap. Then, the Hardware and Blitter collision detection methods will say that they don't collide.
To avoid this, assign a color other than 0 for 'black' or whatever (and use Stencil to fix all the graphics), and then in conversion, the contours will automatically be correct.
It can also be fixed by making custom contours separately, which will not waste a color, and allows for things like a part of the object being uncollidable (spaceship shield, fighting game clothing...)
The Skip IssueThis happens when objects move fast, and when they move towards each other the speed is "doubled"!
In essence, this issue occurs when small objects moving fast (e.g. bullets) might skip over the target, whether it is the player sprite - or the enemy that actually got hit by your bullet before he shot you!
In some cases, such as when bullets travel in a constant speed and direction, this can be fixed by giving the too-small object graphic an overlarge contour or hitbox (e.g. Hybris shots moving straight up). For all other cases, the correct fix is to interpolate the in-between position(s) and test for collisions at each position, i.e. "check more often", so that an object doesn't skip over another.
This issue becomes more urgent as your framerate drops. In other words, the issue (and fix) scales up with lower framerate!
Should I check only every Nth Frame??It's a good idea to divide work over several frames - if you can get away with it! It depends fully and solely on the speed and size of the objects you're checking.
The Skip Issue applies, and if a group of objects is checked only every Nth frame, it's exactly the same as lowering (dividing) the framerate.
Hitboxes will skip past each other when the relative speed between them is >= width1+width2 (or height1+height2,respectively). See Figure 1.
Figure 1: Bullet (red hitbox) and ship (green hitbox) moving towards each other at some random combined speed. Speed = width of target is not enough; it must move by the width of the bullet further, in order to cause the Skip Issue.
"So how do I know if I can get away with it?"
You can check if you're safe by calculating the relative speeds vX and vY between a main object and each object it should be checked against. Select the absolute maximum, e.g. if min(vX)=-9, max(vX)=8, and min(vY) is -7 and max(vY) is 6, an object could move 9 horizontally and 7 vertically in a frame. The sum of the two hitboxes is normally larger than this, but if you check every Nth frame, you must multiply vX and vY by N - while the hitbox sizes stay the same!