The four ghosts in Pac-Man seem to have their
own rules about how to persue the player. Because of this, they rarely travel in a single
group, and they can also be exploited so that Pac-Man can hide in plain sight. How is this possible? In this video, we'll explore the algorithms
that govern the ghosts' movement and how to take advantage of them. The ghosts have four main behavior states. You're most likely familiar with three of
them. They are known as the scatter, chase, frightened,
and eaten states. When Pac-Man eats a power pellet, the ghosts
will enter their frightened state, and if Pac-Man touches them while in this state,
they'll go into their eaten state. At any other time, they are either in scatter
or chase mode. Rather than chasing Pac-Man the entire duration
of the level, they will sometimes run away during scatter mode. The amount of time the ghosts spend in scatter
and chase mode depend on which level the player is currently on. In general, the ghosts start in scatter mode
and alternate between this and chase mode four times per level. This pattern gives the player a breather for
a moment every once in a while when the ghosts aren't right on Pac-Man's tail. Other than the very first level, the third
chase sequence is very long while the fourth scatter sequence is only a single frame, essentially
eliminating it. After the last scatter sequence, the ghosts
are stuck in chase mode. The timer that controls these phases is reset
when the level is cleared and when Pac-Man dies. Blinky has special cases which will allow
him to act like he is in chase mode when he is actually in scatter mode when there are
few dots left in the maze. This starts to happen on the first level when
there are 20 dots remaining, and this increases as the level number increases. During the scatter and chase states, the ghosts
use a targeting system to determine which direction to travel. As soon as they step into a new tile, they
will immediately figure out the next best tile to move into from this point. The decision is between three new tiles: the
one directly in front of it, 90 degrees clockwise, or 90 degrees counter-clockwise. Notice that at this point, turning around
backwards 180 degrees is not an option. This means that a ghost can not normally turn
around while crusing around. As you'll see later it is possible in certain
circumstances, but for now let's ignore that. Directions that would make a ghost travel
into a solid tile are also removed from consideration. Of the remaining options to choose from, the
one that is the closest to the target tile linearly is the tile the ghost will start
moving to. If two or more tiles are the same distance
from the target tile, the tile directly up on the screen is given the highest priority,
then left and down. This algorithm is used for every tile movement,
not just at the intersections of the maze. Because solid tiles are ignored and ghosts
can't turn around backwards, once one enters a section of the maze, they will travel all
the way through it to the next intersection. As another example, suppose a ghost were travelling
downwards into this tile, and this tile up here was the target. Well moving down is already out of the question,
since that's a wall, and he can't turn around and go back up. Between going left and right, right minimizes
the distance towards the target. Similarly, travelling into this tile from
the right side results in choosing between left and up. Going up would be the decision made here to
reduce the distance. If the ghost were travelling from the left
side, the distances between going up and right to the target are the same. However, up is given priority over right,
so the ghost would go up. With the targeting system down pat, let's
look into how the ghosts handle their respective states. During scatter mode, each ghost targets one
specific tile in the maze. This target never changes during the scatter
state. The four targets are in the four corners of
the maze, causing each ghost to flock to a different area of the map. Blinky goes to the top right, Pinky to the
top left, Inky to the bottom right, and Clyde to the bottom left. Most of the time the scatter phase is so short
that they don't stick around in the corners for too long, but if they could, they would
continue running around in circles near their respective target tiles. We can simulate this by placing tons of ghosts
throughout the entire maze and see how eventually they all bunch up in their respective corners. Blinky would always end up going in a clockwise
cycle and Pinky in a counter-clockwise cycle. Inky and Clyde can get stuck going in either
direction depending on what area of the map they arrived from. Let's leave chase mode for last and look at
frightened mode first. All four ghosts will enter frightened mode
simultaneously when Pac-Man eats a power pellet on levels 1-16 and 18. They will turn blue and Pac-Man can touch
them for points and send them back to the ghost house. Upon touching a power pellet, the ghosts will
also all turn around 180 degrees, regardless of if they enter frightened mode or not. This is one of the exceptions to the turn-around
rule. When in frightened mode, instead of minimizing
distance to a target tile, they will just pick an eligbile direction at random using
the output from a random number generator. If Pac-Man does touch a frightened ghost,
they will go into eaten mode. At this point they will turn into a blank
set of eyeballs and scurry back to the ghost house before persuing again. This is done by forcing the ghosts' target
tile to be right in front of the gate. Once they reach it, they move down to go inside
and revert to scatter or chase mode. And finally we will look at chase mode. When all the ghosts enter chase mode, they
will all turn around 180 degrees, just like entering frightened mode. They also turn around when leaving chase mode
and entering scatter mode. These are the other two exceptions to the
turn-around rule, and you can use this to easily tell when a mode switch occurs. Unlike scatter mode where the target tile
is constant, in chase mode, a new target tile is calculated every time before a decision
to move is made. Each ghost has a unique way of determining
this active target tile, which is what ultimately leads to the ghosts' unique habits. Blinky has the simpliest way of determining
a target tile. It is simply just the tile where Pac-Man is
located. Knowing this, if we plop Blinky and Pac-Man
anywhere in the maze, we can trace out the path that Blinky will take. Because the target tile is directly on top
of Pac-Man, Blinky will pretty much always find his way to Pac-Man one way or another. There are a few exceptions which we'll look
at more later. Pinky has the next simpliest way to figure
out her target tile, but it comes with a twist. The tile Pinky targets is the tile four tiles
in front of Pac-Man. So, four tiles to the left if he's facing
left, four below when facing down, or four to the right when facing right. But when Pac-Man is facing up, the target
tile is four tiles above and four tiles to the left. Let's go off on a tangent for a moment to
look at why this happens. So, the tile positions of Pac-Man and the
ghosts are stored as two bytes next to each other. The first byte is the horizontal position,
starting from way off the right side of the screen, counting up leftwards. The right side of the screen is X position
$20, and the left is $3B. The second byte is the vertical position,
starting from way off the top the screen, going down. The first row of the maze is Y position $21,
and the bottom is $3F. The game stores directions as unit vectors
in this format as well. So left is the pair ($01, $00)--horizontally
positive one, vertically zero. Right would then be the pair ($FF, $00)--horizontally
negative one, vertically zero. Down and up would be ($00, $01) and ($00,
$FF) respectively. These unit vectors can be multiplied by a
constant and added together to get an arbitrary 2-dimensional vector. For example, to get four to the right, we
take the vector ($FF, $00) and multiply it by four to get ($3FC, $00). The positions are only 8-bit values, so the
carried three is discarded and we get ($FC, $00) which corresponds to (-4, 0). But what causes the up vector to be incorrect? If we multiply ($00, $FF) by four we get ($00,
$3FC) which should be truncated to ($00, $FC) just like the right vector. The problem is that although these are 8-bit
values, the code that handles this calculation treats the entire vector as one 16-bit value
instead of two 8-bit ones. So instead of the three being discarded, it
overflows into the X component of the vector. The result is instead ($03, $FC), which corresponds
to (3, -4). This overflow error occurs one more time when
the vector is added to the position of the object of interest, Pac-Man in this case. The carried one from adding $FC gets added
to the X component in addition to the three that is already present. This results in the final offset being four
up and four to the left instead of the expected four directly up. This error doesn't occur in the right direction,
since any overflow of the X coordinate does get discarded since it is in the upper half
of the 16-bit value. Because the two 8-bit components of the vector
are treated as one 16-bit value, any time -1 is added to the vertical component, 1 is
also added to the horizontal component. Anyway, with that anamoly understood, let's
look back at Pinky's target tile. We can do the same thing as we did with Blinky
and trace out any path she will take if we know where Pac-Man is. Because the tile is slightly in front of Pac-Man,
Pinky tends to catch Pac-Man from the front as Blinky chases from behind. Also, since the tile isn't directly on top
of Pac-Man, it is easily possible that Pinky won't ever actually reach Pac-Man if he sits
in certain places. This is even easier to do when Pac-Man faces
up, since the target tile is fairly disjoint with his position. Inky has an interesting target tile calculation,
mainly because it is not only dependent on Pac-Man's position, but also Blinky's current
position as well. First, an intermediate tile is found, which
is two tiles in front of Pac-Man. Again, just like with Pinky, if Pac-Man is
facing up, the tile is two in front and two to the left instead. Then, the vector from this tile to Blinky's
position is rotated 180 degrees on its end. This is Inky's target tile. This peculiar method of targetting results
in Inky working with Blinky to flank Pac-Man when the two of them are far apart. But if Blinky is right on Pac-Man's tail,
Inky will come in close too. These paths assume Pac-Man stays stationary,
which isn't normally the case, and also assumes that Blinky stays stationary, which definitely
isn't true. Therefore it's relatively difficult to predict
Inky's movement due to the secondary dependance on Pac-Man's position. Then there's Clyde. With a name that sticks out from the others,
you just know that he's the odd one out. Clyde's target tile is identical to Blinky's,
which is directly on top of where Pac-Man is currently located. However, this is only the case when Clyde
is eight or more tiles away from Pac-Man. If he is less than eight tiles away, the target
tile he choses is the same one as in scatter mode. This means there are actually few spots where
Pac-Man can idle and Clyde will catch him. Most of these spots are down in the bottom
left corner near Clyde's scatter target, but there are a couple other areas in the maze
that have long tunnels without escape routes to the bottom left where Clyde has no choice
to but run into Pac-Man. Now, earlier I said that Blinky will usually
always find Pac-Man, but there is actually an exception to this thanks to some special
cases. There are two areas of the maze where ghosts
in scatter or chase mode will not attempt to update what direction they are facing. That is, they cannot turn at an intersection. One area is right at the exit of the ghost
house, and the other is right where Pac-Man starts in the maze. This effectively means that the ghosts cannot
turn up at these four intersections. Because of this, there is at least one tile
where Pac-Man can hide forever and pretty much never get caught. In the case of Blinky, suppose he is right
here travelling upward. He goes left, but then is forced to continue
moving left until this intersection where he goes down. He goes right and up at the bottom of the
maze and now he's completed a cycle, which means he will be stuck in this loop until
Pac-Man moves. Blinky can get stuck here going clockwise
or counter-clockwise. Pinky can also get stuck here going clockwise
only, or she'll get stuck circling the ghost house in either direction. Clyde will also get stuck in one of two cycles
nearby as well. Inky is difficult to track down here because
his movement depends on where Blinky is in his pattern, but generally he gets stuck cycling
around the ghost house or one of these T-shaped walls. Inky's target tile ends up moving around in
a cycle due to Blinky moving around in a cycle pattern himself. The number of tiles it takes for Blinky to
run around this T-shaped wall is equal to the number of tiles it takes for Inky to run
around another T-shaped wall, as well as the ghost house. Therefore, once Inky falls into a cycle around
one of these things, he's stuck there indefinitely. Pac-Man will never get caught once the ghosts
all fall into their endless cycles, but that doesn't mean it's incredibly easy to get into
this position. Just entering this tile facing up doesn't
grant invincibility, since Blinky can still easily find Pac-Man from about half of the
positions on the map. Luckily, Blinky doesn't travel on much of
this part of the map on his own, since he is usually near the top right during scatter
mode, and somewhere near Pac-Man during chase mode. Pinky and Clyde can really only find Pac-Man
when they are near the bottom right of the maze. The easiest way to trigger the safe spot is
to lure the ghosts to the bottom left and enter from the bottom intersection. Inky is the ghost you'll need to look out
for the most, since it can take much longer for him to get caught up in a cycle somewhere. This hiding spot isn't the only way to take
advantage of the ghost's behavior, but it is the most silly. There are many smaller and more practical
ways to use this knowledge of the movement algorithm to avoid the ghosts during gameplay. Just understanding how the ghosts greedily
minimize distance between them and their target tile is a good start. For example, when in the bottom tunnels, Blinky
and Pinky will go up or inward to get closer to Pac-Man, even though neither of these directions
are the best way to reach him. This leaves the rest of the tunnel empty,
thanks to this U-shaped bend. Pinky's offset targetting can be abused by
turning around quickly after passing through an intersection. If Pinky is within four tiles of Pac-Man and
Pac-man turns around right as Pinky enters the intersection tile, the target tile will
be behind the intersection, making Pinky make a 90-degree turn one way or the other, since
continuing straight forward would increase the distance between the two. This works even better being chased downward
because of the left-offset bug. This bug also leads to other ways of tricking
Pinky, such as idling in this position in the maze. The target tile is across and against a completely
different wall to the one Pac-Man is touching, so Pinky will want to go up and left instead
of down or right. You may be wondering if these types of strategies
are used in order to play perfect games, where the maximum score possible is acheieved. The answer is yes, but more likely the movement
is just memorized. See, since all of the ghosts' movement patterns
are ultimately based on Pac-Man's movement, and therefore the player's input, a consistent
movement pattern of Pac-Man will result in the exact same ghost movement every time. The only thing to fight against then is the
random number generator output when the ghosts are in frightened mode. But, after level 19, the ghosts don't even
enter frightened mode anymore. At this point, you only have to memorize exactly
where the ghosts will move given that you control Pac-Man the exact same way each time
you play. Before ending the video, I'd like to share
one final animation showing off the ghost's target tiles and projected travel paths during
gameplay. I think it's just fun to sit and watch, and
think about how some fairly simple math results in such a great game experience. Thank you for watching! If you are new to the channel, and/or haven't
seen the video explaining the kill screen in Pac-Man, be sure to check it out. Maybe after mastering the ghosts' movement
patterns you'll be able to make it to that level yourself!
