View Single Post
Old 21 January 2019, 14:39   #5
roondar
Registered User

 
Join Date: Jul 2015
Location: The Netherlands
Posts: 1,364
There are several hardware based ways to speed up collision detection, but they all carry significant drawbacks (not in the least that they tend to be 100% pixel perfect, which is not usually what you actually want).

Generally, I'd split collision detection into two (or more) distinct phases: one for player vs objects, one for player bullets vs enemies. You might even split off the player vs scenery from the rest as well. The reason this can help is that it allows you to skip a bunch of checks.

A 'normal' bounding box collision detection algorithm (as well as the absolute distance method mentioned by NorthWay) would check every object vs every other object, but this can clearly be improved since not all collisions are relevant. Splitting the collision detection up in multiple different groups also lowers the object count per test and potentially allows you to check only one object vs all objects rather than the worst case of checking all vs all. These notions combined will speed up the checking compared to the standard algorithm by (potentially) quite a bit.

I'd go for a split something like:
  1. player vs scenery*
  2. player vs objects (one check for the player against all objects that it should collide with)*
  3. bullets vs enemies (obviously only checking bullets vs enemies and not also bullets vs bullets)
This way only the bullets vs enemies group requires you to check a large number of objects, though even here many collisions are not checked for. Compared to the worst case scenario of all objects vs all objects (which would essentially run in O=n^2), the above is a massive improvement that leaves out a large number of pointless checks.

Edit: I noted I left out player bullets and enemy objects vs scenery. This might best be solved using a tilemap lookup IMHO.

All this said, collision detection does normally get slower with more objects to check quite rapidly.

*) If you can live with pixel perfect collisions, or don't mind creating a custom collision mask for the player, this can probably be done with the Blitter by doing a blit with channels A&C active (D disabled) and the minterm set for AND. When done, check the BZERO bit in DMACONR (bit 13) for the result. This can be quicker than doing bounding box checks if the number of objects is large enough.

Note that this method does require either a mask bitplane (i.e. one more bitplane that isn't shown but contains the mask you wish to collide against) or requires collisions to be checked vs specific bitplanes only (otherwise any pixel set will cause the mask to fire, including 'harmless background' pixels)

If the player is made up of Sprites, this can also be done through hardware but will either be fully pixel perfect or requires specific bitplanes to be set as collision 'sources'.

Last edited by roondar; 21 January 2019 at 15:34. Reason: Ellaborated on hardware collision detection a bit, fixed the 'how many checks do we need' part
roondar is offline  
 
Page generated in 0.07319 seconds with 11 queries