| |
cadaver
Registered: Feb 2002
Posts: 1159 |
De-facto fast bullet collision detection in games
Anyone have studied typical bullet <-> enemy collision detection methods used in games with high bullet count, like Salamander, Enforcer, Turrican?
Turrican appears to have the enemies checking chars underneath them for bullet chars, and index into a table which contains the damage value for each type of bullet char.
This avoids typical O(n^2) bounding box overlap checks (each bullet vs each enemy), though a large enemy would need to check many chars under it.
A side-effect of this method is that enemy bullets hitting the player usually cannot be chars, but rather sprites, which would check the collision differently. |
|
| |
Fungus
Registered: Sep 2002
Posts: 668 |
Hrm, large enemies only need to check chars around their perimeter I would think, there could be a offset lookup table for that?
I have noticed in many older games the sprite collision is only used with the player, but it isn't entirely accurate when multiple things are colliding which is very annoying. Some games use an IRQ and it clears the register immediately so it can be used many times a frame, but that's not very useful if your game has tight timing for the raster. Phobia is pretty fast, enough to work on NTSC, I cannot remember what technique it used though.
Have you asked Dan Phillips what he used in Armalyte? |
| |
Martin Piper
Registered: Nov 2007
Posts: 698 |
It really depends on a few factors, like how accurate you want the sprite collision, if the bullets/enemies/player are sprites, if you're scrolling the screen, if you can allocate a certain character range to be bullets/sold background, etc.
SEUCK does pixel accurate sprite to sprite collision, using the hardware collision register, for example.
Other games have an off-screen collision map (blob of memory), which might or might not be the same resolution as the screen. It might be half resolution for example. Some games plot their sprite enemies into this map along with their bullets.
Other game use a simple bounding rectangle (or "circle" or "diamond") check for their sprites.
Some games used the actual chars on screen, but look-up those chars up into another table that denotes the collision type of enemy/bullet/background.
Some use a mixture of these methods depending on if they are enemy to bullet, enemy to enemy, enemy to player etc.
There are many many variations on how to do this depending on data format/layout, accuracy, and sprites or not.
Sometimes you can spot where the collision map is by inspecting a live memory view, like in ICU64. Like in this video: https://youtu.be/3SvsElGt3Hc?t=2480 |
| |
Jetboy
Registered: Jul 2006
Posts: 265 |
Quoting cadaverA side-effect of this method is that enemy bullets hitting the player usually cannot be chars, but rather sprites, which would check the collision differently.
Not a problem if enemy bullets use different char than player bullets do. |
| |
cadaver
Registered: Feb 2002
Posts: 1159 |
Thanks for suggestions! Very true that the enemy doesn't necessarily need to check its inside area, though it also has to take into account the maximum velocity of bullets (e.g. a 2x2 faster moving "bounce" bullet in Turrican) and itself to not miss collisions due to "tunneling" |
| |
tonysavon
Registered: Apr 2014
Posts: 25 |
For sure not the best method, but I want to report my experience with Guy in a vest,a project that is indefinitely on hold :-).
I hit CPU limits quite soon there, because I have colour scrolling plus soft-sprite bullets with sub-char positioning (each bullet is pixelled on top of the BG and takes 2 chars in the charmap, so you don't see the char fame around it, i think ikari warriors does that). Initially I was using the bounding box approach, so for each one of the N bullets I was testing collision with the M enemies on screen, so NxM comparisons. I started to have some slowdowns when I added digi. The solution for me was to blend bullet positioning / collision detection with the sprite multiplexer.
Say you have 4 raster splits with sprites and bullets equally spread, I'd do 4*(N/4)*(M/4) tests, which is 4 times faster, at the cost of making the multiplexer more complicated.
Guy in a vest is horizontal only scrolling, which makes things much easier but I suppose this approach could be used also for 4 ways scrolling. Just don't ask me how :-) |
| |
Krill
Registered: Apr 2002
Posts: 2940 |
With sprite multiplexing and such, is there anything that would make spr-spr hw collision detection interleaved with the multiplexer logic a bad idea? :) |
| |
Oswald
Registered: Apr 2002
Posts: 5074 |
"A side-effect of this method is that enemy bullets hitting the player usually cannot be chars"
why ? |
| |
cadaver
Registered: Feb 2002
Posts: 1159 |
Quote: "A side-effect of this method is that enemy bullets hitting the player usually cannot be chars"
why ?
For avoiding a pathological case where a player char bullet overlaid on an enemy char bullet (or vice versa) would create a missed collision. That assuming the char bullets are drawn first, and all collisions are checked afterward. |
| |
chatGPZ
Registered: Dec 2001
Posts: 11290 |
Quote:With sprite multiplexing and such, is there anything that would make spr-spr hw collision detection interleaved with the multiplexer logic a bad idea? :)
didnt one of the old VICIIs clear the collision latch only once per frame? |
| |
Martin Piper
Registered: Nov 2007
Posts: 698 |
Quote: With sprite multiplexing and such, is there anything that would make spr-spr hw collision detection interleaved with the multiplexer logic a bad idea? :)
Well SEUCK uses the hardware collision with its multiplexor. I also have the option of using hardware collision with my multiplexor, also used in the SEUCK redux games. As long as a "last 8 sprites" to real multiplexed sprite index map is maintained then it seems to work fine for detecting multiplexed hardware collision. |
... 20 posts hidden. Click here to view all posts....
|
| Previous - 1 | 2 | 3 - Next |
