The Pac-Man Dossier
February 23, 2009 Page 6 of 10
Whenever a ghost is in chase or scatter mode, it is trying to reach a target tile somewhere on (or off) the screen. A target tile is merely a way to describe the tile a ghost would like to occupy at any given moment.
This tile can be fixed in place or change location frequently. Whenever the ghosts scatter to the corners of the maze, for example, each ghost is striving to reach a fixed target tile located somewhere near its home corner.
In chase mode, the target tile is usually (but not always) related to Pac-Man's current tile which changes often. Although it may not be obvious at first, the only difference between chase and scatter mode to a ghost is where its target tile is located. The same pathfinding logic applies in either case.
Ghosts are always thinking one step into the future as they move through the maze. Whenever a ghost enters a new tile, it looks ahead to the next tile along its current direction of travel and decides which way it will go when it gets there.
When it eventually reaches that tile, it will change its direction of travel to whatever it had decided on a tile beforehand. The process is then repeated, looking ahead into the next tile along its new direction of travel and making its next decision on which way to go.
When a ghost looks ahead into the upcoming tile, it must examine the possible exits from that tile to determine a way to proceed. In the picture below, the red ghost has just arrived at tile A and is moving right-to-left. It immediately looks ahead to tile B (the next tile along its direction of travel).
Each tile has four potential exits to be considered: right, left, up, and down. In the case of tile B, the up and down exits are blocked by walls and must be discarded as potential candidates. The right exit is also discounted because it would only take the ghost back to tile A again, and ghosts never voluntarily reverse direction. With three of the four possible exits eliminated from tile B, moving left is the only remaining choice.
This example is the most simple to explain as the ghost has but one way it can legally move. As such, we did not have to worry about where its target tile was located. The majority of game tiles in legal space are similar to this one, but things get more interesting when a ghost approaches a tile with more potential exits to choose from.
When a ghost arrives one tile away from an upcoming intersection, it must choose between several possible directions in which to proceed. Consider the following example:
In the first picture, the red ghost has just reached tile A and is seeking its target (shown as the green tile). It immediately looks ahead to the subsequent tile along its present direction of travel (up). In this case, that tile is a four-way intersection. As this intersection tile has no walls blocking off any of the exits, the ghost can only discard his reverse direction (down), leaving three exits open for travel.
It looks one tile beyond the intersection in each of the three remaining directions, collecting "test tiles" (shown as the tiles with dashed, white lines). In the middle picture, the ghost triangulates the distance from each of these test tiles to its target tile.
Whichever direction's test tile has the shortest distance to the target becomes the direction the ghost will take upon reaching the intersection tile. In this case, the right test tile has the shortest distance to the target, and the ghost updates its chosen direction for the intersection tile accordingly.
Sometimes a ghost is presented with two or more test tiles that have the same distance to the target tile. In the example below, the red ghost must choose between moving down or left at the upcoming intersection tile. Unfortunately, both test tiles have the same distance to the target (bottom left).
To break the tie, the ghost prefers directions in this order: up, left, down, right. Up is the most preferred direction; right is the least. Therefore, the ghost chooses to go left at the intersection because left precedes down in the preference list. Although it may seem obvious to a person that going down was the better choice to reach the target, ghosts are not that smart. They cannot see more than a few tiles ahead and, as a consequence, cannot recognize the disparity between these two options.
As mentioned before, each ghost has a fixed target tile it is trying to reach in scatter mode. The picture below shows the actual tile used by each ghost. Notice each target tile is in dead space on either the top or bottom edge of the screen. As such, the ghosts will never be able to reach them.
Luckily, a ghost does not care if its goal is attainable or not-the A.I. routines are very short-sighted. All a ghost cares about is following the pathfinding logic described above to make the best choice it can on which way to turn at the next tile.
As a result, it will simply make circles in the area of the maze nearest its target tile until the target is set to some other location. That's all scatter mode really is. The only reason a ghost has a "favorite corner" of the maze at all is due to the location of a target tile it will never reach.
Page 6 of 10