Why does Ms. Pac-man turn upside down?

Question

Ms. Pac-man is a game where you navigate a small yellow circle around a maze, collecting dots and fruit whilst avoiding brightly-coloured monsters, or ghosts. This time, however, the yellow dot has an eye, a red bow, some lipstick and a "beauty spot". Apart from a few minor visual glitches, there was nothing really wrong with the game; at least until you got to level 130 or so. Then this happened:

Surely this can't be a simple overflow glitch; it must have taken organised sabotage to produce such an error.

Why, out of all things that could happen, would this occur?

Answer 1

The reason for this glitch is rather obscure; it's not surprising that the developers didn't catch it. It all starts with the tunnels on the sides of the screen. These tunnels allow Ms. Pac-man and the ghosts to move from one side of the screen to the other. But, somewhere in development, somebody decided that the ghosts were moving too quickly through them. Their solution? Create "slow tiles" on the tunnel spaces.

In this image, squares with black borders represent the "slow tiles". These had the otherwise unused bit 6 of their bytes on the colour grid set, causing the ghosts to slow down slightly whilst moving going over them. This itself didn't cause the glitch; the main fault was elsewhere.

To store the "slow tiles", the game uses a very sophisticated compression algorithm; it stores the distance to the next "slow tile" as a single byte value, where a 00 byte marks the end of the table. Although there are three layouts in the game, the first two have tunnels in the same places and so can use the same "slow tile" table. The algorithm the game uses to paint the "slow tiles" is as follows:

1. LD A,(#4E13): Load the current level number into A.
2. CP #03: Is A < 3?
3. JP P,#2534: If not, jump elsewhere (return).
4. LD HL,#95DF: Load the "show tiles" table address.
5. CALL #94BD: Loads a pointer to either the first or second table into BC depending on level type.
6. LD HL,#4400: Loads the start of colour memory into HL.
7. LD A,(BC): Set A to the memory value pointed to by BC.
8. INC BC: Increment BC.
9. AND A: Is A == 0x00?
10. JP Z,#2534: If so, jump elsewhere (return).
11. RST #10: Increment HL by A and set A to the memory value pointed to by HL + A.
12. SET 6,(HL): Set bit 6 of the memory value pointed to by HL - paint the "slow tile".
13. JR #95D4: Jump back to instruction 7.

If you are observant you may have noticed some "slow tiles" along the outside of the top maze border. These are there because the maximum distance between two "slow tiles" is 0xFF, or 255, due to the way that their positions are compressed in memory. In order to reach from the right-hand side to the left-hand side of the screen, the pointer needs to span some 0x0300 memory values. This number is clearly larger than 0xFF, so the developers bridged this gap in a series of 0xA0-sized jumps along the outside of the maze, where the "slow tiles" would not affect the ghosts.

There is, however, a flaw in this algorithm. In the third instruction, the developers checked the "Positive" bit (JP P,#2534) instead of the "Carry" bit (JP NC,#2534) (note that it would have to check if the carry bit was not set). This means that the value of A is treated as a signed integer during the comparison, and so values 128 and above are treated as if they are negative. Negative numbers are, indeed, less than three.

As a result of this, an invalid, or "garbage", pointer is loaded into the register in instruction 5. This in turn causes the following loop to process something that is not a table. For example: on level 134, this is the "table" read:

7F 7F 7F 7F 7F 7F 7F 7F C9 C9 C9 C9 C9 C9 C9 C9
C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9
C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9
C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9
C9 C9 C9 C9 C9 C9 C9 C9 00 00 00 00 00 00 00 00

As you might have guessed, this causes the pointer to go significantly past the colour memory, overwriting the sixth bit of every 201st memory value as it goes. Notably it writes to memory value 5D2B, which causes the majority of the screen to flip upside down.

Eventually, enough arbitrary memory values are written to to cause the game to reset. It is possible to fix this programming error, but that uncovers a whole other set of errors and it is not in the scope of this answer to explain those. For that, you will have to ask another question.

^{I have made up the term "slow tiles" for this answer; I do not know what these are actually called. A lot of information was sourced from donhodges.com.}