Pac-Man Ghost AI Explained

The four

ghost

s in Pac-Man seem to have their own set of rules for how to process the player. Because of this, they rarely travel in a single group and 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 control the movement of

ghost

s and how to take advantage of them. Ghosts have four main behavior states. You are probably familiar with three of them. They are known as scatter, chase, blast, and meal states. When Pac-Man eats an energy pellet, the ghosts will enter his fear state, and if Pac-Man touches them in this state, they will enter his eaten state.

At any other time they are scattered or in pursuit mode. Instead of chasing Pac-Man throughout the level, they will sometimes run away during scatter mode. The amount of time the ghosts scatter and the chase mode depend on the level the player is on. Ghosts generally start in scatter mode and switch between it and chase mode four times per level. This pattern gives the player a breather for a moment now and then when the ghosts aren't sitting right on Pac-Man's tail. Unlike the first level, the third chase sequence is very long, while the fourth spread sequence essentially only removes a single frame.

After the last scatter sequence, the ghosts get stuck in chase mode. The timer that controls these stages is reset when the level is cleared and when Pac-Man is killed. Blinky has special cases that allow him to pretend that he is in chase mode when he is actually in scatter mode when there are a few dots left in the maze. This starts at the first level when 20 points remain and increases as the level increases. During the scatter and chase state, the ghosts use a guidance system to determine which direction to travel. Once they enter a new tile, they will immediately choose the next best tile to go from this point.

The decision is between three new tiles: the one directly in front, 90 degrees clockwise, or 90 degrees counterclockwise. Note that turning 180 degrees backwards at this point is not an option. This means that normally a ghost cannot turn while you are crawling. As you'll see later, it's certainly possible in some circumstances, but let's ignore that for now. Directions that would cause a ghost to travel on a solid tile are also taken into account. Of the remaining options to choose from, the one closest to the destination tile linearly is the tile the ghost will start moving to. If two or more tiles are the same distance from the destination tile, the tile directly above on the screen has the highest priority, then the left and bottom.

This algorithm is used for every tile move, not just at maze intersections. Because solid tiles are ignored and ghosts cannot go back, once one enters a section of the maze they will travel through it to the next intersection. As another example, let's say a ghost was traveling on this tile, and this tile up here was the target. Going down properly is already out of the question, because that's a wall and you can't turn around and go back up. Going between left and right, the right minimizes the distance to the target. Similarly, traveling to this tile from the right side results in choosing between going left or going up.

Going up would be the decision here to reduce the distance. If the ghost were traveling from the left side, the distances up and to the right to the target are the same. However, top takes precedence over right, so the ghost would go up. With the target system inactive, let's see how the ghosts interact with their respective states. During scatter mode, each ghost points to a specific tile in the maze. This target never changes during the spread state. The four targets are in the four corners of the maze, causing each ghost to flow towards 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. Usually the spread phase is short enough that they don't stay in corners for long, but if they could, they'd still run in circles near their respective destination tiles. We can simulate this by placing tons of ghosts throughout the maze and seeing how they eventually all get stuck in their respective corners. Blinky always rotated in a clockwise direction and Pinky in a counter-clockwise direction. Inky and Clyde can also get stuck depending on which part of the map they came from.

Let's save the chase mode for last and look scared first. All four ghosts go into fear mode at the same time when Pac-Man eats a power pill at levels 1-16 and 18. They turn blue and Pac-Man can touch them for points to send them back to the haunted house. Tapping an energy pellet will cause the ghosts to rotate 180 degrees, regardless of whether they are spooked or not. This is one of the exceptions to the investment rule. In scared mode, instead of minimizing the distance to a destination tile, they will simply randomly choose a suitable direction with the output of a random number generator.

If Pac-Man hits a scared ghost, he will go into eaten mode. At this point they empty out the eyeballs and take you back to the ghost house before coming back to haunt you. This is done by forcing the target token of the ghosts right in front of the door. Once they reach it, they drop down to enter and return to scatter or chase mode. And finally, we will see the chase mode. When all the ghosts go into chase mode, they turn about 180 degrees, as if they went into fear mode. They also flip when exiting chase mode and entering scatter mode.

These are the other two exceptions to the change rule, and you can use this to easily see when a mode change occurs. Unlike scatter mode, where the fate token is constant, in pursuit mode, a new fate token is calculated each time a move decision is made. Each ghost has a unique way of determining this active target tile, which is what ultimately leads to the unique habits of ghosts. Blinky has the easiest way to determine a target tile. It's just the tile where Pac-Man stands. Knowing this, if we blow up Blinky and Pac-Man anywhere in the maze, we can see the path Blinky will take.

Since the destination tile is directly above Pac-Man, Blinky will almost always find his way to Pac-Man one way or another. There are some exceptions that we will see later. Pinky has the next easiest way to find out the target tile for her, but she has a twist. The Pinky Goals tile is the four-tile tile for Pac-Man. So four tiles to the left when facing left, four down when facing down, or four to the right if facing right. But when Pac-Man points up, the target tile is four tiles up and four tiles to the left. Let's go on a tangent for a second and see 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 the right side of the screen, counting to the left. The right side of the screen is position X $20 and the left side is $3B. The second byte is the vertical position, starting at the top of the screen, it crashes. The first row of the maze is position Y $21 and the bottom is $3F. The game also saves addresses as unit vectors in this format. So on the left is the pair ($01, $00) - horizontally positive, vertically zero.

On the right would then be the pair ($FF, $00) - negative horizontally, zero vertically. Down and up would be ($00, $01) and ($00, $FF) respectively. These unit vectors can be multiplied by a constant and added to get an arbitrary two-dimensional vector. For example, to get four on 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 output three is discarded and we get ($FC, $00) which is equivalent to (-4, 0). But what makes the up vector wrong? If we multiply ($00, $FF) by four, we get ($00, $3FC) which must be shortened to ($00, $FC) as the correct vector.

The problem is that even though these are 8-bit values, the code that handles this computation treats the entire vector as one 16-bit value instead of two 8-bit values. So instead of discarding all three, it spills over into the X component of the vector. Instead, the result is ($03, $FC), which is equal to (3, -4). This overflow error occurs again when the vector is added to the position of the object of interest, Pac-Man in this case. The add $FC behavior is added to the X clause in addition to the three already there. This results in a final offset of four up and four to the left instead of the expected four straight up.

This error does not occur in the correct direction, since any overflow of the X coordinate is discarded because it is in the upper half of the 16-bit value. Because the two 8-bit components of the vector are always treated as one 16-bit value -1 is added to the vertical component, 1 is also added to the horizontal component. Anyway, with that anamoli in mind, let's look back at Pinky's target tile. We can do the same thing we did with Blinky and find the path he will take if we know where Pac-Man is. Since the tile is slightly in front of Pac-Man, Pinky tends to grab Pac-Man from the front while Blinky chases after him from behind.

Since the tile is not directly on top of Pac-Man, Pinky may very well never reach Pac-Man if he sits in certain spots. This is even easier to do when Pac-Man is face up, since the fate token is quite inconsistent with his position. Inky has an interesting calculation of target tiles, especially since it depends not only on Pac-Man's position, but also on Blinky's current position. First, he meets an intermediate tile, which is two tiles before Pac-Man. Again, just like with Pinky, if Pac-Man is face up, the tile is two in front and two to the left. The vector of this tile then goes to the Blinky position and is rotated 180 degrees at the end.

This is Inky's target tile. This particular method of aiming causes Inky to team up with Blinky to flank Pac-Man when the two are far apart. But if Blinky is right behind Pac-Man, Inky is coming up too. These paths assume that Pac-Man remains stationary, which is normally not the case, and they also assume that Blinky remains stationary, which is definitely not true. Therefore, it is relatively difficult to predict Inky's movement due to his secondary reliance on Pac-Man's position. Then there's Clyde. With a name that stands out from the rest, you just know he's the odd one out.

Clyde's destination tile is identical to Blinky's, who is currently directly above Pac-Man. 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 chooses is the same as for spread mode. This means that there are very few places where Pac-Man can be idle and Clyde will catch him. Most of these locations are in the lower left near Clyde's scattered objective, but there are a few other areas in the maze that have long tunnels with no escape routes in the lower left where Clyde has no choice but to run into Pac- Man.

Now, I said earlier that Blinky will always find Pac-Man, but there's 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 which way they are facing. That is, they cannot turn at an intersection. One area is right outside the ghost house and the other is right where Pac-Man starts out in the maze. This effectively means that ghosts cannot spawn at these four intersections. Because of this, there is at least one tile where Pac-Man can hide forever and many never get caught.

In Blinky's case, let's assume he's right here on the ride. He goes left but then he is forced to continue going left until this intersection where he gets off. He goes to the right and up at the bottom of the maze and has now completed a loop, which means he's stuck until Pac-Man moves. Blinky can get stuck here clockwise or counterclockwise. Pinky can also get stuck here only clockwise, or she'll get stuck around the ghost house in both directions. Clyde also gets stuck in one of two near loops. Inky is hard to track here, as his movement depends on where Blinky is his pattern, but most of the time he gets stuck biking around the haunted house or one of these T-shaped walls.

Inky finally movesa cycle due to Blinky walking in a cycle pattern itself. The number of tiles Blinky needs to run around this T-shaped wall is equal to the number of tiles Inky needs to run around another T-shaped wall, as well as the haunted house. Therefore, once Inky falls into a loop around one of these things, he is stuck there indefinitely. Pac-Man will never get caught once the ghosts attack them all in their endless cycles, but that doesn't mean it's incredibly easy to get to this position. Just don't enter this tile to grant invincibility, because Blinky can still easily find Pac-Man from about half the positions on the map.

Fortunately, Blinky doesn't travel alone for much of this part of the map, as he's usually in the upper right during scatter mode and somewhere near Pac-Man during chase mode. Pinky and Clyde can only really find Pac-Man when they are in the bottom right of the maze. The easiest way to activate the safe place is to lure the ghosts in the bottom left and enter from the bottom intersection. Inky is the ghost to watch out for, especially since it can take him much longer to get caught in a loop somewhere. This shelter isn't the only way to take advantage of ghost behavior, but it's the dumbest thing to do.

There are much smaller, more practical ways to use this knowledge of the movement algorithm to avoid ghosting during gameplay. Just understanding how greedy ghosts are to minimize the distance between them and their destination tile is a good start. For example, in the lower tunnels, Blinky and Pinky will go up or down to get closer to Pac-Man, although neither direction is the best way to reach him. This leaves the rest of the tunnel empty, thanks to this U-shaped curve. Pinky's targeting offset can be abused by quickly turning around after passing an intersection. If Pinky is four tiles away from Pac-Man and Pac-Man turns around when Pinky enters the crossover tile, the target tile will be behind the intersection, causing Pinky to do a 90 degree turn, since going in a straight line the distance between the two would increase. .

This works even better when she gets chased due to the left offset bug. This bug also leads to other ways to trick Pinky, such as staying idle in this position in the maze. The target tile is opposite and completely against the opposite wall that Pac-Man is touching, so Pinky wants to move up and left from below or to the right. You may wonder if these types of strategies are used to play perfect games, where the maximum possible score is achieved. The answer is yes, but the movement is most likely simply remembered. See, since all of the ghosts' movement patterns are ultimately based on Pac-Man's movement, which is why player input is consistent, Pac-Man's movement pattern results in the exact same thing. ghost move every time.

The only thing you can fight against is the random number generator output when the ghosts are in scared mode. But after level 19, ghosts don't even activate fear mode anymore. At this point, all he needs to remember is exactly where the ghosts will move, since he controls Pac-Man the exact same way every time he plays. Before I wrap up the video, I want to share a final animation showing the ghost target tiles and projected travel paths during gameplay. I just like to sit and watch and think about how some pretty simple math results in such a great gaming experience.

Thanks for watching! If you're 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 you master the movement of the ghost patterns you can get you to level up!