Forums

Sega Master System / Mark III / Game Gear
SG-1000 / SC-3000 / SF-7000 / OMV
Home - Forums - Games - Scans - Maps - Cheats - Credits
Music - Videos - Development - Hacks - Translations - Homebrew

View topic - Collision Detection is Hard: The Story of Alf (blog)

Reply to topic
Author Message
  • Site Admin
  • Joined: 08 Jul 2001
  • Posts: 8644
  • Location: Paris, France
Reply with quote
Collision Detection is Hard: The Story of Alf (blog)
Post Posted: Tue Jul 27, 2021 9:21 am
Nice read by Nicole Express about use of the hw collision detection flag:
https://nicole.express/2021/remember-alf.html
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 14691
  • Location: London
Reply with quote
Post Posted: Tue Jul 27, 2021 10:03 am
I was a bit disappointed that it doesn’t find the actual bug (presumably something in the software collision detection that tries to determine what set the hardware collision flag).

This is sort of why hardware collision detection is a problem: you can use it to avoid running the software collision code when there’s no pixel-perfect collision, but then (1) you are running that code only on some frames, so either it is fast enough to run on every frame or your frame rate will suffer when things do collide; and (2) any approximation (or bugs) in the software collision detection will be unfairly applied depending on whether any sprites overlap, whether or not they are the relevant ones.
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 08 Jul 2001
  • Posts: 8644
  • Location: Paris, France
Reply with quote
Post Posted: Tue Jul 27, 2021 10:41 am
I think that was the main point, using the HW filter promotes not exercising the software code very well (but then, Alf is generally glitchy so it's no surprise).

With the bats spawning on both sides I guess it's easy to get a collision on the edge of screen if the game doesn't clip the sprites properly?
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 14691
  • Location: London
Reply with quote
Post Posted: Tue Jul 27, 2021 2:59 pm
I assumed that the sprite collision is only over drawn pixels so a bat on the edge of the screen - or even one on each side - will not collide. Perhaps what is happening here is that two bats are spawned at once?
  View user's profile Send private message Visit poster's website
  • Joined: 30 Jul 2021
  • Posts: 13
Reply with quote
Post Posted: Fri Jul 30, 2021 8:52 pm
So the impression I was getting was that while spawning a sprite on screen a collision was being created, but I wasn't sure where... honestly yes I could've kept going in detail but I was feeling really burned out by that point-- I certainly didn't expect the post to get as much attention as did!
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 14691
  • Location: London
Reply with quote
Post Posted: Fri Jul 30, 2021 10:00 pm
Well, we are by nature super-nerding the details. The bigger picture is like I said above, how a hardware pixel-perfect sprite collision gating a simpler software collision is generally not a good idea because it leads to inconsistent behaviour and even masks bugs in the latter.

Also maybe interesting to note is that even today, collision is often approximated by AABB (albeit perhaps more than one per entity) and very often more “generous” (including in 3D) than true pixel-perfect collision detection, trading off correctness for making the game more forgiving and fun.
  View user's profile Send private message Visit poster's website
  • Joined: 05 Sep 2013
  • Posts: 3763
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Wed Aug 04, 2021 5:46 pm
I read it yesterday and I didn't get if there's some software collision check routine that gets used when there's a hardware collision

if there's one, that's the one is to blame

(I guess I missed your point)
  View user's profile Send private message Visit poster's website
  • Joined: 30 Jul 2021
  • Posts: 13
Reply with quote
Post Posted: Sat Aug 14, 2021 6:42 pm
I wrote a follow-up that goes into more detail. It looks like differences between the Genesis and the Master System do end up mattering beyond just timing. I can't link it because I'm too new though... but it's on the same site.

The issue seems to be that the Genesis marks the hardware collision bit when a sprite is colliding with the masked region of the screen in Master System mode. The Master System does not.
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 14691
  • Location: London
Reply with quote
Post Posted: Sat Aug 14, 2021 7:53 pm
That’s an interesting, and I think previously unknown, discovery.

The link: https://nicole.express/2021/alf-2-alf-harder.html
  View user's profile Send private message Visit poster's website
  • Joined: 28 Sep 1999
  • Posts: 1197
Reply with quote
Post Posted: Thu Aug 26, 2021 10:25 pm
That detail about collisions happening in the leftmost column is really interesting, thanks for the great in depth write-up. I wonder if it relates to where collision detection happens.

On the TMS9918 and related systems the sprites are implemented as shift registers that clock out pixels in real time with the display. In the patent these signals go into a "color - priority - multiplexer and collision detect" block that drives the color bus and VDP status flags. We can reasonably assume that collision and pixel color are therefore computed at the same time.

It would seem likely this block also inputs the blanking signals (V-Blank, H-Blank, and forced full-screen blanking from the control register) as these are needed to pick the backdrop/overscan color that gets driven onto the color bus. The logical OR of those signals could be used to mask off the sprite collision result to prevent collisions in blanked screen areas.

On the SMS this functional block, if it exists, would likely also input the left column blanking signal to mask the collision bit too. So here collision is being evaluated on a pixel by pixel basis and that result can be inhibited by any of the blanking signals such as left 8 pixels and anywhere in the active or inactive display regions.

But on the Genesis it's different, Mode 5 sprites are rendered into double buffered line buffers ahead of when they're displayed so collision detection is produced with a scanline granularity instead of a pixel granularity. This would make it difficult for the hardware to differentiate between collisions on the leftmost 8 pixels vs anywhere else without extra complexity added. If we assume SMS games on the PBC using Mode 4 re-use this same sprite rendering hardware which seems to be the case, it could explain why collision detection can happen in the left column.
  View user's profile Send private message Visit poster's website
  • Joined: 30 Jul 2021
  • Posts: 13
Reply with quote
Post Posted: Thu Aug 26, 2021 11:40 pm
I should have been more clear; this isn't a matter of an invisible collision happening in the left column, it's that the mere presence of sprites in the masked region counts as a "collision" for the purpose of software collision detection.
  View user's profile Send private message Visit poster's website
  • Joined: 28 Sep 1999
  • Posts: 1197
Reply with quote
Post Posted: Fri Aug 27, 2021 12:13 am
Nicole Express wrote
It's that the mere presence of sprites in the masked region counts as a "collision" for the purpose of software collision detection.


Ah I understand now. Maybe it could be useful for homebrew software to check if it's running on the Genesis? (among the other techniques)
  View user's profile Send private message Visit poster's website
Reply to topic



Back to the top of this page

Back to SMS Power!