| |
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....
|
| |
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: 697 |
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. |
| Previous - 1 | 2 | 3 - Next |
