| |
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. |
|
... 20 posts hidden. Click here to view all posts....
|
| |
Krill
Registered: Apr 2002
Posts: 2940 |
Quoting chatGPZQuote: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? Interesting! Did it? If so, would certainly make such an approach a bad idea. |
| |
chatGPZ
Registered: Dec 2001
Posts: 11290 |
I vaguely remember something along those lines (but no details), and that it indeed caused odd behaviour in some of the old games. Perhaps TLR can tell when he is back from vacation :) |
| |
Oswald
Registered: Apr 2002
Posts: 5074 |
Quote: 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.
ah, well how about just drawing enemy bullets first, player bullets 2nd, so player bullets are always drawn infront of enemy bullets.
in case of player - enemy bullet collision no problem, player bullets are most of the time are born outside the player sprite |
| |
Oswald
Registered: Apr 2002
Posts: 5074 |
Quote: 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"
this got me thinking too, a 2x2 sized ball moving at 2 char steps can not tunnel through a 1 char boundary ;) |
| |
oziphantom
Registered: Oct 2014
Posts: 488 |
precalc all your entities collision box expanded by the bull et size.
i.e if you have a rect on the entity that is 16x8 and a 4x4 bullet if you make the rect 24x16 and the bullet 1x1 the collision test is the same.
Only now you have a point in rect which gives you a trivial discard. If you have a plexor you then have a Y sorted list which allows you to do a trivial discard and stop once the sprites get below.
i.e if bullet Y > bottom Y of sprite next sprite
if bullet Y < top Y then no collision
If you sort you bullets, they tend to have a fixed order depending on how your game works, so sorting frame to frame won't be much, you will be able to check the first bullet then move down the sprite list till you hit the first sprite in range for Y, then check and then advance bullets or sprites as needed based upon them potentially being range on the Y, then if so do a X range check. |
| |
cadaver
Registered: Feb 2002
Posts: 1159 |
Quote: ah, well how about just drawing enemy bullets first, player bullets 2nd, so player bullets are always drawn infront of enemy bullets.
in case of player - enemy bullet collision no problem, player bullets are most of the time are born outside the player sprite
True, that should be enough in 99% of the cases. Maybe when a player has an AI buddy who is also supposed to be hurting enemies, there can be rare problem cases, but usually it should be so that if player misses an enemy bullet rarely it's not that bad, but player bullets should never miss :) |
| |
Fungus
Registered: Sep 2002
Posts: 668 |
I was thinking the exact same thing, priority matters so order of operations would be to do positioning, then enemy bullets, then player bullets. That makes sense.
Yes I recall something about older vics not clearing the collision register except on vblank. Later it was changed to reading the register to clear it, or perhaps that's old wives tales? Old games do make use of the register, quite many of those synapse and sierra games I've been into lately from 82-83.
Precalculating is what I think I meant by keeping an offset table, essentially a static list of char positions to check which can just be offset by x,y position for fast lookup. |
| |
Martin Piper
Registered: Nov 2007
Posts: 698 |
Regarding the "some VICs don't reset the collision register" thing.
Page 145 of the PRM states the register bits are set by a sprite collision, at the screen position it occurs, and cleared by reading the register. Same for the sprite to background register.
So I doubt a version of the VIC broke that functionality. It wouldn't make sense to clear the register only once per frame since that would lead to previous collision events from previous frames being missed if the sprites moved. |
| |
Bansai
Registered: Feb 2023
Posts: 40 |
Quoting FungusYes I recall something about older vics not clearing the collision register except on vblank. Later it was changed to reading the register to clear it, or perhaps that's old wives tales? Old games do make use of the register, quite many of those synapse and sierra games I've been into lately from 82-83. I wonder if the old wives tales might have some basis in reality from a timing problem similar to sparkle.
https://forum.icomp.de/index.php?thread/1054-c64-compatibility/
Functionally, it makes no sense where a rev would violate the PRM as the read to clear behavior is straightforward, but if timing was an issue, all bets are off.
With respect to the vblank, maybe it was the only reliable area to clear the collision regs on some VIC revs and the story got distorted? |
| |
soci
Registered: Sep 2003
Posts: 478 |
Sounds like a mix up of lightpen position latching and sprite collision. The former is the one which is once per frame. |
| Previous - 1 | 2 | 3 - Next |
