This week I'm looking at more modifications to Pac-Man's frightened ghost movement algorithm. In the video I just released last week, we found that the random number generator that the game uses is not super great, and the process to handle what to do if a ghost tries to turn into a wall causes the distribution of ghosts to favor the bottom left corner of the maze over time.
I suggest watching that video if you haven't already before reading on, since it might not make much sense without it!
It's a good one, I promise!
So in the video, I showed what the distribution would look like if the RNG output was perfectly uniform, if the ghosts chose directions in balanced way, and both of these combined. Of course the perfect setup with a uniform RNG and balance directions resulted in a perfectly uniform distribution of ghosts across the maze.
Implementing such an algorithm would take more than a trivial amount of effort to program, so here are some options that are relatively simple to code up. Most of these came from various commenters from the video!
Counter-Clockwise
Instead of rotating a failed direction clockwise, what if it were rotated counter-clockwise instead? Maybe that would work better.
Or maybe not.
Unfortunately all that does is flip the distribution horizontally. Now the ghosts favor the bottom right instead.
50/50 Rotation
Maybe, half the time the ghost rotates the direction clockwise, and the other half of the time it rotates it counter-clockwise. Sort of balance out between the two.
Still not so great.
With this you get the intermediate position between each of the two options. It's a mix of favoring the bottom left and favoring bottom right, which results in just favoring the bottom in general. The top half of the maze was under-represented in each case, so it doesn't magically get better when we combine the two.
Use the Index
Some people were curious why the RNG index value just wasn't used directly without looking up a byte from the game's ROM.
The recurrence T' = 5 * T + 1 mod 8192 produces a decent pseudorandom sequence of 13-bit numbers. However, if you look at just the bottom three bits (equivalent to using mod 4 instead of mod 8192), you'll find that the sequence just repeats 0, 1, 2, 3, 0, 1, 2, 3 over and over. That's not very random at all!
Using the index directly would indeed give each of the four directions an equal probability of being picked, but it becomes slightly easier to predict. (Now, since ghosts call the RNG even when in a tunnel and not turning, I don't think this is actually much of an issue in practice.)
ROM Plus/XOR Index
The next best thing though is to add or XOR the RNG index with the value read from ROM. This could possibly help with flattening the distribution a bit. Let's see how that does:
| Direction | Index | ROM | XOR | Add |
|---|---|---|---|---|
| Right | 2048 (25.00%) | 2064 (25.20%) | 2076 (25.34%) | 2046 (24.98%) |
| Down | 2048 (25.00%) | 2338 (28.54%) | 2052 (25.05%) | 2052 (25.05%) |
| Left | 2048 (25.00%) | 2452 (29.94%) | 2020 (24.66%) | 2050 (25.02%) |
| Up | 2048 (25.00%) | 1338 (16.33%) | 2044 (24.95%) | 2044 (24.95%) |
Wow, that actually works quite well! It would have only taken a few extra instructions to do it this way, and it greatly improves the uniformity of the RNG output. Let's see how it affects the ghost distribution:
Looks promising!
Actually, if you compare this to the version in the video with the perfect 25% split for directions, it's almost identical. That makes sense, since the distribution is within 0.05% of being spot on.
Finally, I'd like to share the heatmaps for the mazes in Ms. Pac-Man and Jr. Pac-Man. They use the same exact method for determining where frightened ghosts go, so it was as simple as building a Markov chain in the shape of each of the mazes and doing the same simulation.
The first maze in Ms. Pac-Man. You can find the others here: 2 3 4
Ms. Pac-Man has four different mazes. The first and second heavily favor the bottom left just like in Pac-Man, but the fourth has a hot spot near the bottom right of the ghost house. I would say maybe it's because there are two tunnels that wrap around the screen, but the first two mazes do too, so who knows.
The first maze in Jr. Pac-Man. You can find the others here: 2 3 4 5 6 7
Jr. Pac-Man has seven massive mazes, and none of them have tunnels that wrap around the sides of the screen. Both of these factors mean that the left side of the maze is extremely over-represented, as there's no shortcut from the left all the way to the right. I think the first maze is actually the best out of all of them.
You can support Retro Game Mechanics Explained on Patreon here! Any and all support is greatly appreciated!
