The Pac-Man Dossier
February 23, 2009 Page 5 of 10
Chapter 3: Maze Logic 101
We need to take a look at how ghosts are able to move through the maze in pursuit of a goal. All pathfinding logic described in this chapter is shared by the four ghosts - it is important to understand what they have in common before we get into what makes them different.
Before we proceed, let's see how the game tracks the location of Pac-Man and the four ghosts (herein referred to as actors for brevity's sake). The visible game screen should be thought of as a regular grid of tiles, each eight pixels square.
The actual pixel dimensions of the screen are 224 x 288, so dividing each value by eight yields a grid that is 28 x 36 tiles in size.
Each tile is either in legal space or dead space. In the picture above, legal space is shown as the gray-colored tiles; all other tiles are considered dead space.
Actors only travel between the tiles in legal space. Each dot sits in the center of a tile, meaning they are exactly eight pixels (one tile) apart-this is useful for estimating distances during gameplay:
What Tile Am I In?
As the actors move through the maze, the game keeps track of the tile each one occupies. An actor is only associated with a single tile at a time, although its graphic will overlap into the surrounding tiles. The location of the actor's center point is what determines the tile it occupies at any given time. As the actors can move at pixel-level precision, they are often not centered directly on top of the tile they are in. Consider the following example:
The transparent red ghost is moving left-to-right across a row of tiles in legal space. In frame one, its occupied tile (shown in bright red) is near the left side of the picture. It does not matter that some of the ghost's graphic is not in the tile-what matters is that the ghost's center point is in the tile.
By frame two, it has moved far enough for its center point to be in the adjacent tile to the right and its occupied tile is updated accordingly. The ghost continues to be associated with the same tile until frame six where its center point has now crossed over into the next one.
The underlying concept of tiles is essential for understanding the ghosts' pathfinding logic as it only cares about the tile an actor occupies-not its per-pixel location within that tile. To the logic routines, the five actors look very much like the picture below.
Each actor is defined by the tile it presently occupies along with its current direction of travel. Distances between actors are also measured in tiles (the pink ghost is five tiles away from Pac-Man horizontally and one tile away vertically, for example).
Just Passing Through
It wasn't too long after the release of Pac-Man when word began to spread of players occasionally passing straight through a ghost unharmed, seemingly at random. This rumor turned out to be completely true as most die-hard Pac-Man players can attest.
If you play the game long enough, you will eventually see Pac-Man run into one of the ghosts and come out unscathed on the other side-it doesn't happen very often so enjoy it when it does! Some players have even gone so far as to incorporate this mysterious pass-through oddity into their patterns.
The root cause of this elusive peculiarity lies in the way the game detects collisions between Pac-Man and the four ghosts. Any time Pac-Man occupies the same tile as a ghost, he is considered to have collided with that ghost and a life is lost.
It is irrelevant whether the ghost moved into Pac-Man's tile or Pac-Man into the ghost's-the result is the same either way. This logic proves sufficient for handling collisions more than 99% of the time during gameplay, but does not account for one very special case:
The above picture illustrates the conditions necessary to produce this curious behavior. There are five consecutive frames showing Blinky and Pac-Man passing through each other. Below each frame is the same scene represented by the tiles they currently occupy and the per-pixel location of their center points. Pac-Man and Blinky are at just the right position and speed relative to one another to cause them to swap tiles with each other simultaneously.
In other words, Pac-Man's center point moves upwards into Blinky's tile in the same 1/60th of a second that Blinky's center point moves downwards into Pac-Man's tile, resulting in them moving past each other without colliding. Note that Pac-Man's origin point is centered on the top edge of his tile in frame four; this is still considered to be inside the bottom tile, but moving up one more pixel will push him over the edge into the next one.
Pac-Man and Blinky have now swapped tiles with each other in frame five, and Pac-Man can go on his merry way because he never "collided" (i.e., shared the same tile) with Blinky at all! Click on the YouTube video below to see an example of the pass-through bug (it happens 40 seconds after playback begins):
Page 5 of 10