| |
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. |
| |
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. |
| |
DanPhillips
Registered: Jan 2003
Posts: 31 |
Armalyte uses a slightly different approach.
Enemies check the chars underneath them, if they detect a bullet they can stop they then write a "die" blank character, The char bullet processing reads the screen at the previous position if its the special die char it erases it with a normal blank char and dies.
Advantage of being in space and the starfield twinkling for up to 8 frames (while waiting for a screen flip) isn't really noticeable.
This allowed us to have a lot of bullets, without taking up space in the charset (like IO for instance where every bullet is unique, making a lookup faster, but taking char space away from the background)
Cheers
Dan |
| |
Krill
Registered: Apr 2002
Posts: 2940 |
Quoting DanPhillipsEnemies check the chars underneath them, if they detect a bullet they can stop they then write a "die" blank character, The char bullet processing reads the screen at the previous position if its the special die char it erases it with a normal blank char and dies. That's a very collaborative way for enemies to die. =) |
| |
cadaver
Registered: Feb 2002
Posts: 1159 |
DanPhillips: very clever, thanks for the answer! |
| |
Fungus
Registered: Sep 2002
Posts: 668 |
Thanks Dan, that's a wonderful solution.
Now that you mention that... I'm thinking of keeping a table of all active bullets in an array, to avoid having to bother checking the screen at all... hrm! or perhaps using the color only? hrmm |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1402 |
Nice solution, Dan.
Some scattered thoughts:
I too have considered using the sprite multiplexer sortlist to limit the number of tests required; never got around to implementing it though.
As for enemy bullets overwriting player bullets - you could write enemy bullets to the screen, then check player position, then write player bullets, then check if enemies have hit them?
But TBH you only have one or two players, an alternate solution for enemy bullet to player position checks would just be to inline a fast check against the current player(s) position into the enemy bullet update code - it's only O(number of bullets), and you could self modify some immediate operands in the comparison code too. |
| |
Fungus
Registered: Sep 2002
Posts: 668 |
In what way would you use the sort list? Just the index list for quick x,y lookup or what? |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1402 |
Fungus, check oziphantom's comment (#16). You keep your bullet list and the sprite list sorted by Y, then you can walk down both lists in parallel, and most bullets need checking against at most eight sprites. |
| |
Oswald
Registered: Apr 2002
Posts: 5074 |
Quote: Thanks Dan, that's a wonderful solution.
Now that you mention that... I'm thinking of keeping a table of all active bullets in an array, to avoid having to bother checking the screen at all... hrm! or perhaps using the color only? hrmm
checking the screen is faster, as you dont have to check every bullet against every sprite if there is hit. just check for bullets under sprites. I think whole sprite scan is probably faster or on par with checking one bullet against sprite rectabgle x1 x2 y1 y2... |
| |
Fungus
Registered: Sep 2002
Posts: 668 |
Yeah I don't think sorting the bullets by Y in a list is very optimal compared to Dan's method. |
| |
Martin Piper
Registered: Nov 2007
Posts: 698 |
Sometimes the bullet char on screen cannot be replaced with a kill char, it might be visible as a wrong character for example.
A good optimisation can be related to sprite background collision. Usually the sprite X/Y coordinates (or X/2) can fast lookup into a couple of tables to reduce it to address and lda(addr),y checks. If an offset is applied to the lookups then Y-40 and Y+40 Y-1 and Y+1 etc can be used to read the screen chars around the sprite middle. Useful for checking a few characters for background collision.
If the bullets store their index into an off screen buffer, which doesn't need to be cleared, then that off screen buffer can be read quickly by the sprite-background lookups just by adjusting the address. If the buffers are page aligned then the hi address only needs adjustment. Then the bullet can be killed by reading its index and setting the relevant flag in its animation table entry.
This means the sprite to background and sprite to char bullet collision can reuse a lot of the calculation effort. |
