Collision Detection Is Hard: The Story of Alf

Today we’re talking about ALF. It’s a surprising move for Nicole Express; we do not condone cat-eating. But neither did Alf, eventually. In any case, we’re not here to talk about the television show (which I’ve never seen) or the pogs; we’re here to talk about ALF for the Sega Master System. By request!

This post is dedicated to the memory of my good friend Near, author of the Higan emulator, a good friend of mine, and the person who taught me debugging techniques I used in this post, who sadly passed away a month ago. You deserve a better tribute than an ALF post. Rest in peace.

Remember Alf? He’s back!

ALF for the Sega Master System, released in 1989, stars the furry alien on a quest to fix his space ship. It’s a platformer-adventure that would almost be good, but wow, it’s pretty hard, and not always in a good way. The game has that same “jank” people attribute to Micronics (though it was actually developed by Nexa, a San Francisco-based company eventually bought by Spectrum Holobyte), with flickery characters and awkward collision detection. Which is a shame because an ambitious title; almost reminds me of E.T. in that way.

In any case, we’re not here to talk about how great or not ALF on the Sega Master System is. I’m sure some 80’s kids had a fun time with it, and it’s an odd-ball title that I can respect. It’s also one of the few Master System games that was only released in North America. I guess the Europeans just don’t like Alf?

The history lesson

So I was perfectly content to live my life not caring about ALF for the Sega Master System. Gong Xian on Twitter, though, let me know of an interesting bug. Then Bob from RetroRGB was having a stream with Tianfeng and the issue came up again, and now I’m writing an article about ALF.

So I’d like to link to my Master System overview here, but that’s not done yet. So time for fast mode.

The Sega Mark III, known as the Master System in America, Europe, and eventually Japan, got its name from being the third revision of the Sega SG-1000 console. The SG-1000 has never shown up on this blog, but its computer version, the SC-3000 has.

The main feature the Mark III has over the SG-1000 is in its graphics chip. The SG-1000 used the TMS9918A, a common chip developed by TI in 1979 for its TI-99/4A computer, and used by machines like the MSX standard and the ColecoVision. The Mark III’s graphics processor, known as the VDP (Video Display Processor) and seemingly not as anything else, takes that as its core, and builds a new system on top of it.

	TMS9918A	Master System VDP
Color palette	16 pre-set colors	64 colors (6-bit RGB)
Tilemap colors	2 per 8x1 cell	16 per 8x8 cell
Sprites	32, 4 per scanline	64, 8 per scanline
Sprite colors	1	15
Simultaneous colors	16	31
Resolution	256x192	256x192
Scrolling	No	Yes, 256x256 tilemap
VRAM	16kiB	16kiB
VRAM bus width	8 bits	16 bits

So I don’t know about you, but what this tells me is that the TMS9918A was incredibly functional for 1979. 32 simultaneous sprites is nothing to sneeze at, even if they are one-color and with a 4-per-scanline limit. (Note, however, that the TI-99/4 and TI-99/4A had to share that 16kiB of video RAM with things like BASIC programs)

This TMS9918A heritage also brought along a feature that was at one point synonymous with hardware sprites, but would become less and less common over the 1980s: hardware collision detection.

Hardware collision detection

Collision detection in video games can be a pretty complicated topic, especially on a console with limited resources. For example, imagine player-enemy collision. My old Javascript game Aspect Legend treats everyone as circles; if your dot gets within another circle’s radius, you die.

This is a little more complicated on an 8-bit console, though, where you don’t have access to Math.pow, or a modern CPU to run those calculations every 1/60 of a second. (Or, in the case of Aspect Legend, every 1/120 of a second.) So Aspect Star “N” takes a different approach, using overlapping boxes. Space Ava 201 is grid-based, which is an entirely different way to solve the problem. (Note: when I link to my code, it’s just because that’s the code I’m most familiar with, not to imply that it’s the best way)

Notice, however, that all of these methods don’t have the sprite aligned with the collision. For example, take a look above. The red box over the lower mouse represents a collision area; notice that it includes blank pixels, but excludes some of the mouse’s feet and body. Meanwhile the player is just treated as a point. This isn’t a big deal in Aspect Star “N”, but if the sprites and collision boxes get too divergent, a game can quickly become unplayable.

Hardware collision detection solves that problem, and the problem of having to waste CPU cycles on this, by just having the video processor do it. The Atari 8-bit systems, including the 2600 and the computers, can do this, for example.

The video processor is in charge of drawing sprites, perhaps using something like a line buffer. Therefore, all it needs to do is when it realizes it’s drawing one sprite on top of somewhere is set a flag. And so the TMS9918A does just that.

Hardware collision detection is therefore perfect. It will only report when two sprites actually overlap, not when a box overlaps. It’s so perfect that when a sprite “flickers”, the hardware collision detection will not register a collision when the sprite isn’t visible; this is what makes the famous Adventure easter egg possible.

But for TI, there was a problem. The TMS9918A has 32 sprites. Each could collide with the other 31 sprites. Therefore, you wouldn’t just need one flag: you’d need 992. And remember, pretty much everything in 8-bit home console and computer design comes down to one simple phrase: memory is expensive.

Therefore, the TMS9918A just has a collision flag. Programs have two options once they see this flag is set:

1. Run a software collision detection routine to determine which two sprites collided.
2. “Race the beam”, constantly check the collision flag while the screen is being drawn and detect when it is. This takes more CPU time than just running a software routine every frame.

The Master System inherited this single-bit hardware collision detection from the TMS9918A. This made it a bit unique; the Nintendo Entertainment System and, as far as I can tell, the Atari 7800, both eschewed the feature. And the vast majority of games on the Master System didn’t bother using it; if you have to have software collision detection anyway, why bother?

But guess what game does use it!

Finally, the bug

The lead programmer of ALF, Kevin Seghetti, was only on his second game for the console, and his first was Monopoly, which wasn’t exactly an action game. Plus, I mean, it’s ALF for the Sega Master System. I think you can be forgiven for not bringing the A-game.

Here, you can see that Alf has been injured by a bat. Unfortunately, Alf is quite fragile, and dies on the spot. But something’s odd. Alf died without any overlap between his sprite and the enemy. In most games, you’d just say the collision was bad. But I just said that hardware collision detection was perfect.

We can confirm this is how it’s supposed to work by opening up the source code of an emulator, and then building it with hardware collision detection disabled. Here is where you’d do that in the Higan emulator, for example. There’s no real reason to go that far, but if you do, you’ll find that Alf can not die.

The plot thickens

However, this bug has an interesting component: I took that screenshot running on a Genesis 1 using a Power Base converter. That’s my preferred way to take Master System screenshots, as it has a good video quality.

However, I also have a Japanese Master System. Because of some peculiarities of the Japanese Master System’s output (its sync is at a different voltage level, as far as I know), I don’t have a high-quality cable, and use a cheap SCART cable that syncs on composite video and gives a darker picture with faint jailbars.

But surprisingly, it’s a darker picture of a living Alf.

What gives?

So, the Japanese Master System has the same VDP as the Mark III and the first-run American Master System; its only standout feature is its use of FM sound. So while I don’t have an American Master System (yet), I think it’s safe to assume they’re equivalent in this regard.

The Sega Genesis is backwards compatible with the Master System. However, it is not backwards compatible with the SG-1000. All those TMS9918A modes are not available. This wasn’t a huge deal; the only western-released Master System game that actually used an SG-1000 mode was F-16 Fighting Falcon.

F-16 Fighting Falcon is often described as "basically an SG-1000 game", but that's not accurate! The game will not run on an SG-1000 (or at least, not on an SC-3000) even if you bypass the title screen, which does use the Master System's graphics mode. This is because it uses all 8kiB of RAM the Master System has. (By comparison, the SG-1000 has only 1kiB and the SC-3000 2kiB built-in)

F-16 Fighting Falcon is actually somewhat relevant to ALF. While the developers are not the same people (in fact, Mobygames claims the Master System version was developed by famed Sega developer Yuji Naka), both games were developed by Nexa. Just make sure to play your Nexa games on the real Master System, apparently they had something against the Power Base Converter.

This basically means that the Sega Genesis is missing some legacy features. You might, therefore, assume that sprite collision is one of those legacy features; and indeed, I notice that if I modify the emulator to always have hardware collision detected, objects have larger hitboxes, showing that there is a software routine that’s a bit sloppy.

You don’t actually need a modded emulator, or in fact, to press a button to show how sloppy ALF’s software collision detection is. Here’s an unmodified emulator letting the demo run. This is the last frame, and a collision has been detected between Alf and the speargun scuba diver. Why? Notice in the top left; a sprite (the catfish) is colliding with the oxygen bar. Since this is the demo, no death animation plays; instead, it resets back to the title screen.

So, is collision detection broken on the Mega Drive?

No! I made a simple test program using some Space Ava 201 graphics, and confirmed that the Sega Genesis in Master System mode does in fact support hardware collision. In this case, I just changed the background color.

This actually makes sense; this legacy feature managed to make its way into the Mega Drive mode as well. Hugues Johnson went into an article describing it, but be careful with your testing, as even the Higan emulator doesn’t bother implementing it for Mega Drive games. No commercial games used it, it seems, and it’s easy to see why.

So if collision detection works, then there must be a collision detected. Let’s take a look at the two frames of the crime. First, the Master System game, where Alf doesn’t die. Second, the game running on a Genesis, the frame before he does. I tried to match them as close as possible.

What’s the difference? There’s a bat spawning off on the left side of the screen. And how can we tell if bats accidentally cause a collision when they spawn?

One way is to use a trace logger.

Debugging ALF, because I’ve lost control of my life

A trace logger is quite simple theoretically. An emulator is constantly running code instruction after instruction. On a system like the Sega Master System, with a single CPU that controls everything, the game state could just be logged after each instruction. This could allow you to step through the state.

In practice, there is a problem, which is that there are a lot of instructions. The Sega Master System CPU clock runs at 3.5MHz. Considering it has 8kiB of RAM and 16kiB of VRAM, logging the constant state of everything would take up a huge amount of disk space. So instead, each instruction just gets a line like this:

0097  bit  5,a            AF:8053 BC:00be DE:7f80 HL:d135 IX:cfeb IY:c02d SP:dfd0 IFF:00 IM:1

That might seem intimidating! But it’s not too bad. First off is the address that’s being read from. Then, there’s the instruction at that address. The AF, BC, DE, HL, IX, IY, SP, IFF, and IM are the state of the Z80 processor’s internal registers.

So, why did I choose a bit 5,a instruction? It’s because I’m looking for checks to collision detection. If we look at SMS Power’s documentation of the Master System VDP, we see that it is the fifth bit when reading from the control port. So the idea that the bit instruction, which checks a bit within the byte of a, would be used is just an educated guess.

How do we confirm this is the right place? Let’s look at where a came from by looking at the instruction right before this one.

0094  ld   a,($c009)      AF:7f53 BC:00be DE:7f80 HL:d135 IX:ba18 IY:c02d SP:dfec IFF:00 IM:1

So a comes from address $c009. This is in the Sega Master System’s RAM space. We continue to work backwards; where is the last code that touches $c009? A simple search backwards will tell us.

0074  in   a,($bf)        AF:1010 BC:0006 DE:cfac HL:cfb9 IX:ba18 IY:c02d SP:dfec IFF:00 IM:1
0076  ld   ($c009),a      AF:8010 BC:0006 DE:cfac HL:cfb9 IX:ba18 IY:c02d SP:dfec IFF:00 IM:1

in a,($bf) uses the Master System’s IO ports; these are a convenient feature of the Z80, unlike the 6502-based systems I’m more familiar with, you don’t need to have IO pretend to be RAM and take up space in the available memory map. And the SMS Power article above points out that $3f is exactly the source of VDP registers.

Tracing

So the big problem with tracing is that even a short time will produce a huge number of instructions. I went to the cave in question, and ran just enough time that a bat spawned, being careful to never see two objects collide. This was only a few seconds; the log created is 70MB. That’s why we need to be able to know what to look for going in.

In this case, I can look at the bit 5 on line 0097, and then look at the next few lines to see what it does with that check.

0097  bit  5,a            AF:8053 BC:00be DE:7f80 HL:d135 IX:ba18 IY:c02d SP:dfec IFF:00 IM:1
0099  call nz,$377e       AF:8055 BC:00be DE:7f80 HL:d135 IX:ba18 IY:c02d SP:dfec IFF:00 IM:1
009c  call $083c          AF:8055 BC:00be DE:7f80 HL:d135 IX:ba18 IY:c02d SP:dfec IFF:00 IM:1

call nz,$377e will call the routine at $377e only if the zero flag is clear, which generally means the prior instruction had a non-zero result. Therefore, the jump will only be taken if a collision was detected. Since the next line is the instruction at $009c, we can realize that the branch was not taken.

Since my trace had no visible object collisions, you’d expect that it’d have no cases where that branch is taken. But that’s not true. Later on, we see this:

0097  bit  5,a            AF:e053 BC:00be DE:7f80 HL:d135 IX:85ed IY:c02d SP:dfec IFF:00 IM:1
0099  call nz,$377e       AF:e031 BC:00be DE:7f80 HL:d135 IX:85ed IY:c02d SP:dfec IFF:00 IM:1
377e  ld   a,($c254)      AF:e031 BC:00be DE:7f80 HL:d135 IX:85ed IY:c02d SP:dfea IFF:00 IM:1

So collision did happen! For just two frames (this code runs every frame; I was able to trace it back to the frame interrupt handler, so once every 60Hz). You’d expect a real collision to last more than two frames. (Of course, I confirmed this with more logging)

And that’s why the sloppy algorithm is used.

But why is the bat there?

That’s a harder question to answer. What I will say is that ALF is very timing-heavy; it’s always running code on the main thread, while the interrupt runs. In fact, I tried using SMS Examine to read through the code, and while it didn’t fully work (sadly it wasn’t able to catch the main game logic, though it did catch our interrupt handler with its bit 5,a), it did reveal that the game goes through a long delay loop only on Japanese systems. Given the game wasn’t even released outside of the US one has to wonder the point, but it definitely implies that timing was crucial.

If you use an emulator like MEKA, you can switch between PAL and NTSC timings, which are much more dramatic than the difference between a Genesis and a Master System. And the intro demo’s enemy positions differ quite a bit! Consider the undersea screenshot above; on a Master System, Alf is killed by a spearman. Here, Alf is killed by a spear, not by a spearman. (Plus, the cat hasn’t collided with the object yet.)

I don’t have a PAL Master System to check this. And of course, in the real world, ALF was only released in the United States.

That’s ALF, folks

A video game having glitches is not at all surprising. But it’s fun to see how even relatively subtle differences can be noticed, and the chain of events. Having gone through all this, it’s hard to blame anyone at Nexa for not noticing this. I mean, the Genesis hadn’t even had its US launch yet, let alone the Power Base Converter.

Plus, I mean, it’s ALF. Why did I spend so long on this?

from Hacker News https://ift.tt/3i4QFGk