Collision Detection Is Hard: The Story of Alf | Hacker News Reader

Collision Detection Is Hard: The Story of Alf

nicole.express

160 pointszdw30 comments

Darbian (of Super Mario Bros speedrun fame) has been speedrunning this game on Twitch recently, on an actual Master System console. Previously he had played on the Genesis, which had different strategies due to the collision detection differences. His world record on it is just a bit under 5 minutes. Most of the runs die on that (very frustrating) bat section due to collision detection. I wonder if he has seen this article yet.

Maybe I missed it, but what was the actual cause of the bug?

Wondering the same thing!

Hehe, I don't think it's actually solved in this article. The article is kind of rambly right, so it's hard to tell for sure.

> 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.

It happened but was too fast for a human eye.

But what collided?

As per the next header there "But why is the bat there?".

But that bat is miles away from the Alf character, so it's still missing an explanation of why it counts as a collision. (Plus, that section "But why is the bat there?", doesn't appear to answer that question.)

From my understanding the position of the objects are different between NTSC and PAL. So if you set it to display NTSC you see the enemies in the wrong positions and the collisions are calculated on PAL.

Note: I'm not 100% sure I understood the article correctly

I found the article quite confusing I have 3 possible understandings:

1. The one stated above

2. Collision is extremely fast and not displayed on screen ( if was displayed in screen it will be easy to spot by going frame by frame )

3. Something else collided with something else. In the article it talks about the fish with the health bar

I thought the issue was that there were multiple collisions on the same frame and the software detection was off.

I think it came down to a single flag that gets set by the video chip for any two objects that collide. Once the flag is set, the game code needs to figure out which two sprite objects in the scene could have possibly collided. Some time elapses between the flag being set, and the code checking for the collision, allowing for other things to happen in the game (even if only briefly). Ultimately this creates a lot of room for errors because the software is analyzing the game in a slightly different state than when the collision actually occurred, and it may infer a collision between two objects that did not actually collide, due to some other limitations on resources and using object boundary boxes that do not perfectly map to the actual pixels occupied by an object.

The article doesn't say. In the mini-animation of when the fault occurred, after the momentary blank, you can see the bat does actually get partially concealed by something associated with the ALF sprite; it's possible that that counts as a collision. That would seem to indicate three possibilities:

1. The top of the ALF sprite is wider than it looks and has some non-transparent black in it.

2. There's another (non-transparent black) sprite there that's colliding.

3. There's a sprite multiplexing limitation that somehow counts as a collision.

My reading was that the 2nd off-screen bat caused a collision to trigger when it spawned. Sloppy collision detection registered this as a kill.

Ah, this sort of brings back memories.

When I was making my own extremely crappy and derivative games on the TI-99 4/A, the agony of doubly-interpreted BASIC meant that my pre-programmed walls and pits and such were painful to check for. I hit upon the idea of just checking the video array for where my sprite was going to move. Which wasn't bad for a tween.

To you young folks: hands up who had never heard of "Alf" before? (The character I mean, not the game.)

Once upon a time, the TV only had 3 apps on it and you had to get up to swipe between them.

Or turn the tuning dial

That was the joke

Oh ok!

Alf was pretty big all over the world, we even had a dubbed version here in South Africa. It was no fun as an adult to see the movie version and have him sound so weird.

A more suitable title is perhaps "Collision Detection In Videogames Is Hard: The Story of Alf"

There are many more areas that the HN crowd would be interested in where "collisions" are a thing. Self-driving cars, hash functions, lock-free data structures, etc.

"The Story of Alf" does not make this more specific either. "Alf" could easily be the nickname of some self-driving project or the acronym for some lock-free data structure or so.

Perhaps, but according to the rules of this site you are supposed to use the title of the linked article.

"unless it is misleading" which could be considered to be the case here.

It’s not misleading, it’s vague. It is in fact about collision detection, maybe just not the kind you assumed at first. It’s also not clickbait.

I’m not sure how many people here share my view, but when I see “collision detection” I think about video games first, not self driving cars.

Collision detection in cars is very easy, I'd say. Collision prevention is the hard part.

"Collision Detection" is a term of art: https://en.wikipedia.org/wiki/Collision_detection

Collision shouldn't be a thing for self driving cars.

Yet, you should still have code that handles them.

Eg something that automatically calls the police and ambulance.

Reply on news.ycombinator.com