Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > De-facto fast bullet collision detection in games
2024-07-09 21:21
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....
 
2024-07-11 18:11
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
2024-07-11 18:29
Krill

Registered: Apr 2002
Posts: 2875
Quoting DanPhillips
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.
That's a very collaborative way for enemies to die. =)
2024-07-11 19:14
cadaver

Registered: Feb 2002
Posts: 1159
DanPhillips: very clever, thanks for the answer!
2024-07-11 22:10
Fungus

Registered: Sep 2002
Posts: 639
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
2024-07-12 04:02
ChristopherJam

Registered: Aug 2004
Posts: 1393
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.
2024-07-13 02:17
Fungus

Registered: Sep 2002
Posts: 639
In what way would you use the sort list? Just the index list for quick x,y lookup or what?
2024-07-13 05:35
ChristopherJam

Registered: Aug 2004
Posts: 1393
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.
2024-07-13 16:50
Oswald

Registered: Apr 2002
Posts: 5038
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...
2024-07-13 22:42
Fungus

Registered: Sep 2002
Posts: 639
Yeah I don't think sorting the bullets by Y in a list is very optimal compared to Dan's method.
2024-07-14 08:32
Martin Piper

Registered: Nov 2007
Posts: 659
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
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
csabanw
Codey/Second Dimension
Guests online: 109
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.7)
5 Edge of Disgrace  (9.7)
6 Uncensored  (9.6)
7 Comaland 100%  (9.6)
8 No Bounds  (9.6)
9 Wonderland XIV  (9.6)
10 Bromance  (9.5)
Top onefile Demos
1 Layers  (9.6)
2 Cubic Dream  (9.6)
3 Party Elk 2  (9.6)
4 Copper Booze  (9.6)
5 Rainbow Connection  (9.5)
6 It's More Fun to Com..  (9.5)
7 Dawnfall V1.1  (9.5)
8 Onscreen 5k  (9.5)
9 Morph  (9.5)
10 Daah, Those Acid Pil..  (9.5)
Top Groups
1 Nostalgia  (9.4)
2 Oxyron  (9.3)
3 Booze Design  (9.3)
4 Censor Design  (9.3)
5 Offence  (9.3)
Top Fullscreen Graphicians
1 Joe  (9.7)
2 Veto  (9.6)
3 Facet  (9.6)
4 The Sarge  (9.6)
5 Carrion  (9.5)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.119 sec.