Target Tiles
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.
Looking
Ahead
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.
Intersections
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:
(click image for full size)
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.
Scatter Targets
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