Passing Through Ghosts in Pac-Man

This is an excerpt from my book Bug Voyage: A Tour of Classic Game Glitches, available in the current Rogue Souls Storybundle. The book also contains information on pseudorandom number generation, doing low-level math in binary and decimal, and how you can crash any Galaga machine without even putting money in.

If you have a Pac-Man, Ms. Pac-Man, or the like machine near you… well, if you do, lucky you, they're getting scarce. Even the "20 Year Reunion" machines with Ms. Pac-Man and Galaga in a single cabinet, which were everywhere for a time, aren't that common any more.

But for the purposes of this discussion, it's okay to load a YouTube video of one of the games and watch it for a minute:

Notice how Pac-Man and the ghosts smoothly coast through the maze? They glide so confidently, so cleanly.

This smoothness, as we shall see, is a lie, and that's not all. Here's another YouTube video:

It was uploaded by Jamey Pittman, author of The Pac-Man Dossier, the source of much of the information on Pac-Man in this book. It's cued up to a way in to save some time. Watch it for a little bit. Particularly watch Pac-Man and the Red ghost (as the annotation says, he's Blinky). Around the 40 second mark, watch what happens!

Did you see it? Pac-Man went clean through the red ghost! How did that happen? Can it be made to happen consistently?

Relax. I'll explain how, and yes, it's consistent. If you follow Pittman's pattern on the first level, exactly, it'll happen every time.

Pac-Man

What is a Sprite?

Some 2D graphics hardware of the time provided for those special graphic objects we talked about called sprites. You may have heard the term used lately to refer to a pixel art character graphic.

This usage is not historical; back in the day, the term was used to refer to an independently-movable graphic object that could be placed anywhere on-screen, either overlaid upon the rest of the graphics, sometimes called the background, or behind it. They work by setting X and Y coordinates, the image to be displayed and its color. Often they were used for play characters, but they could be also be used to supplement the background art or other purposes.

Most systems supported several, or even (as in Galaga's case) lots of sprites. There were other names for them as well: Atari first called them Player-Missile Graphics, and on the Commodore some early documentation referred to them as M.O.B.s, or "Movable Object Blocks." Before long though, pretty much everyone called them sprites.

Arcade Pac-Man's hardware supports sprite graphics. It can display up to eight on-screen at a time without the use of scanline-based tricks. The Pac-Man graphic itself is one of them, and the ghosts are four more. When Pac-Man eats a ghost, its eyes fleeing back home reuse the ghost sprite.

Not everything that changes on the screen is a sprite. Another kind of graphic that hardware of the time used was a tiled background. This was just a grid of individual graphics held in memory. If you change the contents of a spot of memory, a small part of the screen, the part represented by that part of the grid, immediately changes too as a consequence. This makes them easy to work with.

The dots in Pac-Man are tiles on the background that are erased as Pac-Man eats them. The blinking of the "Energizers" that power Pac-Man up is done by coloring those cells black, then white, every few frames. But these objects don't move, they're just removed or replaced.

The problem with tiled character graphics is that they can't move smoothly. They're laid down on a grid, so a background object that moves won't move smoothly across the screen as do Pac-Man and the ghosts, but "jump" around as it moves between grid spaces. You can't just move part of a grid space, it's all the way or not at all.

Well that's interesting. So what?

The Basis of Pac-Man's World

Years ago as a kid I made little games in Microsoft BASIC on my Commodore 64. This implementation of BASIC had some unfortunate problems. It ran slowly, and made almost no use of the system's then-prodigious audio-visual assets. If you wanted to do anything with graphics or sound at all, you had to do it yourself using weird and technical direct memory access commands called POKEs, or else learn some machine code yourself to do it for you.

One workaround was, instead of using the system's sprite graphics capability, to use character objects like I described above. They jerk around in tile-sized jumps, but they're a bit easier to mess with. What you could do is start in on your game using character graphics, then, when you got closer to something you'd want people other than your doting mother to see, you'd switch to using hardware sprites.

The object in memory might still conceptually jerk around in those eight pixel increments, but the player wouldn't see that, he or she'd see that flashy sprite image, which could be larger than a character tile anyway and so obscure what was going on. With some clever programming, you could interpolate the sprite's position so it appeared to glide more smoothly. If you did it well enough, the player would never notice the difference. Only you would know the truth.

You may have already guessed where I'm going with this. Because the interesting thing is, this is exactly how Pac-Man is programmed.

In effect, both Pac-Man and the ghosts have two positions. There is the position of their sprite graphics on-screen that you see, that glides across the screen. This is the information you're given with which to play the game, but it's just a shadow, a charade. If you want to understand how Pac-Man really works, you'll have to look past that.

Behind the scenes, the Pac-Man game program also notes which character cell Pac-Man and the ghosts each occupy. No on-screen trace of these coordinates is used. I suspect that at some point in Pac-Man's early development, when they were hashing out the basic game and doing rapid-turnaround play experiments, they may have been used to draw tiles directly to the screen. Jamey Pittman discovered that these coordinates are used for all of the game's AI, and they're also used for all of the game's collision detection.

The game goes through some effort to maintain this illusion. It tracks how far Pac-Man and the ghosts have moved out of their current cell on a sub-pixel level, and switches them to their new location when they've gone far enough. A slightly faster object will have a speed which causes it change cells a tiny bit more often.

These different elements, the grid coordinates, the between-cell tracking, and the position of the sprite on the screen, work together to present the illusion of smooth movement. But in game terms, the movement is exactly the same as it was back when I programmed character cell graphics on my Commodore 64.

The Payoff

We now have the information needed to understand how Pac-Man can move through the ghosts.

Pac-Man's collisions are detected by comparing those grid coordinates with that of the ghosts. If they're the same, it's a collision, and one eats the other. If they're different, there's no collision. That is all; there is nothing more.

One may see that one reason it's done this way is that makes collision detection very quick in terms of processor cycles. It compares Pac-Man's X and Y numbers to each of the four ghosts every frame. This way it doesn't have to worry about ranges or close calls. Only exact hits, in this coarse-grained system, count.

This grid is (roughly) aligned with the tile coordinate system that represents game actors' true positions.
All collision detection uses this grid. The game only registers a collision if both entities' tile coordinates are the same.
That means they have to occupy the same space on the grid.

The problem arises when the movement pixel counts for both Pac-Man and a ghost, moving towards each other, click over into the next cell in the same frame. The check for a collision occurs after all the objects have moved this frame. If Pac-Man clicks over into Blinky's space, and Blinky clicks over into Pac-Man's old space, in the same frame, then the collision check will fail. They will have swapped positions!

Since this is the only level of reality that really means anything in the game, it doesn't matter what appears to have happened. Pac-Man and the ghost will just slide through one another, ships passing in the night.

Because of the deterministic nature of the AI in the game, you can devise a pattern to reproduce this behavior, and although the timing of the pass-through bug has to be frame-perfect to work, you don't have to be frame-perfect to do it, so long as you obey the rules to performing Pac-Man patterns, which is how the show in Jamey Pittman's video works.

I go through all this description to impress upon you an important fact. It is easy to think of the objects in a video game as having a kind of reality. Pac-Man is this thing on screen, the ghosts are things, a spaceship, Mario, Sonic, Solid Snake, your soldier in Call of Duty, they're all things. This is illusory.

In fact, they're all just there to give you a glimpse into an inner, deeper system, one in which it can take serious effort by the machine just to tell if two objects are even touching. What you see on the screen is a depiction of an abstract world, and part of game design is communicating that world, through the display, to the player in a way that reflects his experience of reality.

It is easy to forget how tenuous this connection is. How do you know which thing on-screen is yours? It's the one that looks different and responds to your controls. What if a second thing like that appeared on screen? Or, what if your thing randomly moved in a different direction sometimes, or lagged behind your control movements, or turned invisible once in a while, or split in two, or turned to look like one of the enemies?

It's a job of the designer to make the connection between the inner world of the game and what you see on the screen as simple and direct as possible, unless he or she is seeking some special effect. That is what the word immersion really means, or should.

Extra Credit

On the 20 Year Reunion arcade machines, put in a coin, then, on the Player 1 joystick, enter: Up, Up, Up, Down, Down, Down, Left, Right, Left, Right, Left. If the ghost on the Game Select screen turns pink and a sound plays then you did it right. Then choose to play Ms. Pac-Man, and the game will instead be original Pac-Man.

Scanline tricks can be used to perform great magic on dedicated graphics hardware, like taking a system that supposedly can only display eight sprites and getting many more out of it, at the cost of some processor time and flexibility.

The Atari VCS/2600 console is especially notable in that most of the systems graphics had to be done using scanline tricks. See the book Racing The Beam for more information on these techniques.

Sources:
The Pac-Man Dossier: http://www.gamasutra.com/view/feature/3938/the_pacman_dossier.php?print=1
Jamey Pittman's YouTube channel: https://www.youtube.com/user/jameypittman/videos