A Few months ago I decided it was about time I write my own Pacman clone. I had it all figured out except for the AI. I wanted to make a good AI, and started looking for one. Diving more and more into the Pacman's world, I became obsessed with the AI, and trust me the Pacman AI deserves an article of its own. But it was that obsession, which led me to a decision. I'm gonna to reverse engineer the original Pacman. Yes, I know. I got it real bad.

So, there I was spending hours, late nights, trying to put the pieces together, placing break points, and playing tones of Pacman, where at one point I wanted to test something related to Pacman getting caught. I was running Pacman into ghosts, when suddenly; I just went through one of them.Skeptical, are you?! Look at the link from "The Pac-Man Dossier". It gives a pretty good explanation of the bug. I would like to elaborate a bit more, and put it in context of game programming and programming in general.

But first let me finish my story (It took me months of work,you can spare a few seconds). At one point while going through the code I found the collision detection procedure, and a few hours later, I found, yet another collision detection procedure. Weird. Here we a have, not one, but two ways to detect collisions and yet, we have a collision detection bug.

Let's look at the following game loop. I think it is pretty standard:

Do {
Get user input
Move characters
Detect collisions
Render
} While ( Player alive)

Here is how the first collision detection works:

For each ghost
If ghost.MAZE_POS == pacman.MAZE_POS Then Return collision detected
Next
Return no collision detected

The MAZE_POS are set at the [Move characters ] procedure, as follows
CHARCTER.SCREEN_POS.X = CHARCTER.SCREEN_POS.X + DIRECTION HORIZONTAL DELTA
CHARCTER.SCREEN_POS.Y = CHARCTER.SCREEN_POS.Y+DIRECTION VERTICAL DELTA
CHARCTER .MAZE_POS.X = CHARCTER .SCREEN_POS.X / 8
CHARCTER .MAZE_POS.Y = CHARCTER .SCREEN_POS.Y / 8

Now let's look at the following scenario:
PACMAN.SCREEN_POSITION.X = 100
GHOST.SCREEN_POSITION.X = 100
PACMAN.SCREEN_POSITION.Y = 7
GHOST.SCREEN_POSITION.Y = 8
PACMAN.DIRECTION = DOWN
GHOST.DIRECTION = UP

At the first iteration, the [Move characters ] will result
PACMAN.MAZE_POSITION.X = PACMAN.SCREEN_POSITION.X/8 // 100/8 = 12
PACMAN.MAZE_POSITION.Y = PACMAN.SCREEN_POSITION.Y/8 // 7/8 = 0
GHOST.MAZE_POSITION.X =GHOST.SCREEN_POSITION.X/8 // 100/8 = 12
GHOST.MAZE_POSITION.Y = GHOST.SCREEN_POSITION.Y/8 // 8/8 = 1

And in the collision detection we get:
PACMAN.MAZE_POSITION (12,0) != GHOST.MAZE_POSITION(12,1)
At the next iteration, the [Move characters ] will result
PACMAN. SCREEN_POSITION.X = PACMAN.SCREEN_POSITION.X +0 // stays 100
PACMAN. SCREEN_POSITION.Y = PACMAN.SCREEN_POSITION.Y +1 // now it is 8
GHOST. SCREEN_POSITION.X =GHOST.SCREEN_POSITION.X + 0 //stays 100
GHOST. SCREEN_POSITION.Y = GHOST.SCREEN_POSITION.Y +(-1) // now it is 7
PACMAN.MAZE_POSITION.X = PACMAN.SCREEN_POSITION.X/8 // 100/8 = 12
PACMAN.MAZE_POSITION.Y = PACMAN.SCREEN_POSITION.Y/8 // 8/8 = 1
GHOST.MAZE_POSITION.X =GHOST.SCREEN_POSITION.X/8 // 100/8 = 12
GHOST.MAZE_POSITION.Y = GHOST.SCREEN_POSITION.Y/8 // 7/8 = 0

And in the collision detection we get:
PACMAN.MAZE_POSITION (12,1) != GHOST.MAZE_POSITION(12,0)
D'oh!, indeed.

In this case if the programmers used the bounding rectangle collision detection based on the screen position it would of worked, but notice that even that won't always work for 2D games. Picture an asteroid game, where your spaceship advances more than a pixel on each frame and so is the asteroids.

Moreover, this is not the only bug in Pacman. One might even think that the Pacman's programmers were not such an elite coders. But when looking at the rest of the code, you get exactly the opposite impression. They were GREAT coders. So what exactly went wrong? How could they have missed that?

If we look at it chronologically, they were inventing the game industry. There were games prior to Pacman, but I believe it was one of the firsts to have more software based code than hardware.

Pong was, I think, mostly hardware. And the Atari games had a Hardware mechanism for detecting collisions. It does not mean that hardware programming is easier than software; in fact it is quite the opposite. But it does mean that there wasn't a lot of code to learn from. They were writing some of the first lines in computer games industry, so show some respect.

But there is also a timeless reason, I think, that programmers and QA everywhere, can relate to.

Think of a program you write that for some reason is simply hell to debug. You either cannot:

(A)Run it in a debugger.
Or (B) The bug occurs only at theclient site, and you are not allowed to halt the system.
Or ( C ) In cases like this where you don't even have a line to place a breakpoint.

You would have to look at the code and figure out the entire scenario. But there's more. If you wereQA-ing PacMan, what would you do? Would you spend most of your time escapingthe ghosts or trying to run into them?

And that leads me to the second collision detection procedure. It had more testing based on screen position. It subtracts Pacman screen position from the ghost's and tests if the result is lesser than 4 (but it does not test if it greater than -4).

Oh yea, one more thing. It does that ONLY when in scared mode, when Pacman IS chasing the ghosts.

So this is only speculating, but it is based on real life experience.

If the bug happens when you are running into ghosts, it would probably appear mainly when YOU chase the ghosts. Now this is, I think, classic.The first thing that comes to mind is "something is wrong in the scared mode,so let's add a scared mode collision detection patch!". If you programmed for long enough, you are probably nodding now.

So a nice conclusion would be, when testing, try to test NOTalways what is an expected behavior, try to test sometimes the unexpected. But a nicer conclusion would be, if you missed that one bug, well, you can still sale millions of copies. ka-ching!