Pac-Man Ghost AI Explained

Pac-Man's four

ghost

s seem to have their own rules about how to haunt the player. Because of this, they rarely travel in a single group and can also be exploited so Pac-Man can hide in plain sight. How is this possible? In this video we will explore the algorithms that determine the movement of

ghost

s and how to take advantage of them. Ghosts have four main behavioral states. You're probably familiar with three of them. They are known as dispersion, pursuit, fear and eating states. When Pac-Man eats a power pellet, the ghosts will enter his scared state, and if Pac-Man touches them in this state, they will enter his eaten state.

At any other time they are in scatter or chase mode. Instead of chasing Pac-Man throughout the level, they will sometimes run away during scatter mode. The amount of time ghosts spend scattering and in chase mode depends on the level the player is currently enabled. Generally, ghosts start in scatter mode and switch between it and chase mode four times per level. This pattern gives the player a break for a moment every once in a while when the ghosts aren't sitting in Pac-Man's queue. Unlike the first level, the third chase sequence is very long, while the fourth scatter sequence is essentially a single-frame kill.

After the final scatter sequence, the ghosts are stuck in chase mode. The timer that controls these stages resets when the level is completed and when Pac-Man dies. 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 still some points left in the maze. This starts at the first level when there are 20 points left and increases as the level increases. During scatter and chase states, 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 continue from this point.

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

This algorithm is used for every tile movement, not just at maze intersections. Because solid tiles are ignored and ghosts cannot turn back, once one enters a part of the maze, everyone will travel to the next intersection. As another example, let's say a ghost travels across this tile and this tile up here is the target. Going down properly is now out of the question, because that's a wall and you can't turn around and go back up. When going between left and right, the right minimizes the distance to the target. Likewise, traveling to this tile from the right results in choosing between left and up.

Going up here would be the decision to reduce the distance. If the ghost were to travel from the left side, the distances between up and right to the target are the same. However, up takes priority over right, so the spirit would go up. With the targeting system disabled, let's see how the ghosts interact with their respective states. During scatter mode, each ghost focuses on a specific tile in the maze. This target never changes during the spread state. The four objectives are located in the four corners of the maze, through which each ghost flows to a different area of ​​the map.

Blinky goes top right, Pinky top left, Inky bottom right, and Clyde bottom left. Usually the scatter phase is short enough that they don't stay in the corners for long, but if they could, they would continue running in circles near their respective target tiles. We can simulate this by placing tons of ghosts throughout the maze and see how they all eventually stick to their respective corners. Blinky would always go clockwise and Pinky would always go counterclockwise. Inky and Clyde can also get stuck depending on which part of the map they come from. Let's save the chase mode for last and look at the fear first.

All four ghosts go into spook mode at the same time when Pac-Man eats a power pellet in levels 1-16 and 18. They turn blue and Pac-Man can touch them to get points and send them back to the haunted house. When you touch a power ball, all ghosts will turn 180 degrees, regardless of whether they are scared or not. This is one of the exceptions to the rule of change. In scared mode, instead of minimizing the distance to a target 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 eat mode.

At this point, they empty their eyes and run back to the ghost house before continuing again. This is done by forcing the ghosts' goal token right in front of the door. Once they reach you, scroll 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 all turn around 180 degrees, as if going into fear mode. They also spin when they exit chase mode and enter scatter mode. These are the other two exceptions to the switching rule and you can use them to easily see when a mode switch occurs.

Unlike scatter mode, where the target token is constant, in chase mode, a new target token is calculated each time before making a move decision. 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 easiest way to determine a target token. It's just the tile where Pac-Man is located. Knowing this, if we drop Blinky and Pac-Man anywhere in the maze we can determine the path Blinky will take. Since the target 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 discover her target token, but there's a twist. The Pinky Goals tile is the four-tile Pac-Man tile. So, four tiles to the left if he looks left, four below if he looks down, or four to the right if he looks 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 to see why this happens. So the positions of the Pac-Man tiles 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 and counting towards 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 and falling. The first row of the maze is position Y $21 and the bottom is $3F. The game also stores 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): horizontally negative, vertically zero. Down and up would be ($00, $01) and ($00, $FF) respectively.

These unit vectors can be multiplied by a constant and added to obtain an arbitrary two-dimensional vector. For example, to guess four, we take the vector ($FF, $00) and multiply it by four to get ($3FC, $00). The positions are just 8-bit values, so output three is discarded and we get ($FC, $00) which corresponds to (-4, 0). But what causes the ascending vector to be incorrect? If we multiply ($00, $FF) by four, we get ($00, $3FC) which should 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 calculation treats the entire vector as one 16-bit value instead of two 8-bit values.

So instead of discarding all three, it flows into the X component of the vector. Instead, the result is ($03, $FC), which is equivalent 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 $FC add behavior is added to component X in addition to the three that are already present. This results in a final shift of four up and four to the left instead of the expected four up. This error does not occur in the correct direction, since any X coordinate overflow 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 a 16-bit value, -1 is added to the vertical component and 1 is also added to the horizontal component. Anyway, with that anomaly understood, let's look at Pinky's objective token again. We can do the same thing we did with Blinky and find out what path he will take if we know where Pac-Man is. Since the token is slightly in front of Pac-Man, Pinky tends to grab Pac-Man from the front while Blinky chases him from behind. Since the tile is not directly above Pac-Man, it is very possible that Pinky will never reach Pac-Man if he sits in certain spots.

This is even easier to do when Pac-Man is face up, as the target token is quite inconsistent with his position. Inky has an interesting calculation of target tokens, especially since it not only depends on Pac-Man's position, but also on the flow of Blinky's position. An intermediate tile is found first, which is two tiles ahead of Pac-Man. Again, similar to Pinky, if Pac-Man is face up, the token has two in front and two on the left. Then the vector from this tile to Blinky's position is rotated 180 degrees at the end. This is Inky's target token. This particular method of aiming results in Inky partnering with Blinky to flank Pac-Man when the two are far apart.

But when Blinky sits right behind Pac-Man, Inky comes over too. These paths assume that Pac-Man remains stationary, which is usually 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 dependence on Pac-Man's position. Then there's Clyde. With a name that stands out from the rest, you know he's the odd one out. Clyde's target token is identical to Blinky's, which is currently located directly above Pac-Man. However, this is only the case when Clyde is eight or more tokens away from Pac-Man.

If he is less than eight tiles away, the target tile he chooses is the same as for extended mode. This means that there are actually few places where Pac-Man can remain idle and Clyde will catch him. Most of these points are in the lower left corner 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 corner where Clyde has no other option to meet Pac- Man. Now, I said earlier that Blinky will generally 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 do not attempt to update which direction they are facing. That is, they cannot turn at an intersection. One area is located right outside the ghost house and the other is right where Pac-Man starts in the maze. This effectively means that ghosts cannot appear at these four intersections. This means that there is at least one tile where Pac-Man can hide forever and beautifully, many of which are never caught. In Blinky's case, let's say he's right about this trip. He goes left, but then is forced to continue left until this junction where he goes down.

He goes to the right and goes up to the bottom of the maze and has now completed a cycle, meaning he's trapped until Pac-Man moves. Blinky can get stuck here clockwise or counterclockwise. Pinky can also get stuck here by going clockwise only, or she can get stuck around the ghost house in either direction. Clyde also gets stuck in one of the two nearby cycles. It's hard to track Inky here because his movement depends on where Blinky and his boss are, but he usually gets stuck while riding his bike.around the haunted house or one of these T-shaped walls.

Inky's target token eventually starts moving in a cycle because Blinky moves in a cyclical pattern. The number of tiles needed for Blinky to run around this T-shaped wall is equal to the number of tiles needed for Inky to run around another T-shaped wall as well as the haunted house. Therefore, once Inky falls into a cycle around one of these things, he is stuck there indefinitely. Pac-Man will never be caught once the ghosts attack them all in their endless cycles, but that doesn't mean it's incredibly easy to get into this position. Only not entering this tile grants invincibility, because Blinky can still find Pac-Man easily from about half the positions on the map.

Fortunately, Blinky doesn't roam much of this part of the map alone, as he is usually found in the top right during scatter mode and somewhere near Pac-Man during chase mode. Pinky and Clyde can only find Pac-Man when they are at the bottom right of the maze on the screen. The easiest way to activate the safe place is to lure the ghosts at the bottom left and enter from the bottom intersection. Inky is the ghost to watch out for, especially since he can take a lot longer to get caught in a loop somewhere. This hiding is not the only way to take advantage of the behavior of the mind, but it is the stupidest.

There are much smaller and more practical ways to use this knowledge of the movement algorithm to avoid ghosts while playing. Simply understanding how greedy ghosts are and minimizing the distance between them and your target tile is a good start. For example, in the lower tunnels, Blinky and Pinky will go up or in to get closer to Pac-Man, although neither direction is the best way to get to him. This leaves the rest of the tunnel empty, thanks to this U-shaped bend. Pinky's offset orientation can be abused by turning quickly after passing an intersection. If Pinky is four squares away from Pac-Man and Pac-Man turns around as Pinky enters the crossed square, the target square will be behind the intersection, causing Pinky to make a 90-degree turn since going straight would increase the distance between the two. .

This works even better when she chases herself due to the shift left error. This mistake also leads to other ways to trick Pinky, such as remaining idle in this position in the maze. The target tile is opposite and completely against the wall that Pac-Man is touching, so Pinky wants to go up and to the left from below or to the right. You may wonder if these types of strategies are useful for playing perfect games, where the highest possible score is achieved. The answer is yes, but the move is most likely simply remembered. See, since all of the ghosts' movement patterns are ultimately based on Pac-Man's movement and therefore player input, Pac-Man's consistent movement pattern results in exactly the same movement of the ghost every time.

The only thing you can fight against is the output of the random number generator when the ghosts are scared. But after level 19 the ghosts don't even activate anxious mode anymore. At this point, all you have to do is remember exactly where the ghosts will move, since you control Pac-Man in exactly the same way every time you play. Before I end the video, I want to share a final animation showing the ghost objective tiles and travel routes projected during the game. I just like to sit back 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 death screen in Pac-Man, be sure to watch it. Maybe after mastering the movement of ghost patterns you can create that level yourself!