How Deep Can You Dig Dug?
A Complete Analysis and Patching of Dig Dug's Kill Screen
Project started 12/17/2007
Last update 10/21/2011
Updated 7/25/2008: Fixed a minor problem with the patch that was pointed out by "
Dig Dug has a "kill screen" on round 256, which is counted by the game as round 0. The round starts with an enemy Pooka directly on top of Dig Dug, causing the player to lose all of his remaining lives very quickly. We want to know why this bug occurs and try to develop a patch for the code to fix the problem.
First we do some research to see if the problem has already been addressed.
As it turns out, at least one of the various versions of Dig Dug have a built in fix. According to the MAME source code project: http://mamedev.org/source/src/mame/drivers/galaga.c.html
This is an interesting observation and provides a starting point for the search for clues. Using a debug build of MAME to disassemble Dig Dug, we can analyze the fix that was apparently not implemented in one version of the game:
0018: C0 RET NZ ; Return if not zero 0019: 3E 9C LD A,$9C ; Else load A with #9C (156 decimal) 001B: 77 LD (HL),A ; Store into round memory 001C: C9 RET ; Return
This subroutine is called immediately after the round has been increased and checks to see if it has just rolled over to zero. If it hasn't, it returns immediately. If it has, then it sets the round back to #96 (156 decimal). It works by keeping the rounds between 156 and 255 for the rest of the game.
However, we would like to fix the code so that round 0 is actually playable. In the Atari version, we can trace back the code that calls this subroutine reveals the places where the game round is incremented. This immediately gives us the memory location used to store the round: #840D.
The main problem we see from the kill screen is that a Pooka is drawn right on top of Dig Dug. We also observe that no tunnels are drawn, and the rocks seem misplaced.
Presumably, the tunnel patterns and locations of rocks and enemies are dependent on the round number. After lots of digging (no pun intended) around in the code and making extensive use of the debugger in MAME, we discover the source of Dig Dug's kill screen bug.
There is a subroutine that is called right before drawing the tunnels and before drawing the locations of the enemies. The purpose of this subroutine is to take the round number and produce as output a number between #00 and #0E (14 decimal) for the 15 different screen patterns that this game employs.
1BDE: 3A 27 86 LD A,($8627) ; Load A with round number 1BE1: FE 10 CP $10 ; Is this round < #10 (16 decimal) ? 1BE3: 38 04 JR C,$1BE9 ; Yes, skip ahead 1BE5: E6 03 AND $03 ; No, mask bits to make between 0 and 3 1BE7: C6 0C ADD A,$0C ; Add #0C (12 decimal) 1BE9: 3D DEC A ; Subtract 1 1BEA: C9 RET ; return
For rounds #01 through #0F, the result is just one less than the round number. For example, on round 1, the result returned is #00. For round 2, the result is #01, and so on. Rounds that are #0F (15 decimal) or higher give answers between #0B (11 decimal) and #0E (14 decimal).
The output is then multiplied and added to an offset in memory to vector into the memory location where the game holds the data for the locations of the tunnels, rocks, and enemies.
For example, on round 1, the offset is computed as #00, which is added in a later subroutine to point to a table of data that holds the locations of the Pookas and Fygars.
The game uses a simple number coding system to determine where to draw the various objects in the game at the start of the round. A screen shot of the grid of numbers is overlaid with round 1, seen below. Note that numbers which end in 0 and F are not shown; they are not used.
Locations of enemies are found in memory for round 1 at location #3258:
3258: 32 3C DA 00 00 B4 00 00
Locations of rocks for round 1 are at location #30F0:
30F0: 00 45 AB C4 00 00
We can see the subroutine takes the values stored in the table and places the Pookas and Fygars according to it. Up to four of each enemy can be drawn. If the value is #00, no enemy is drawn. The first four values are the locations of the Pookas and the last four values are the locations of the Fygars. We can see that if the table were to contain a value of #87, an enemy would be drawn right on top of DigDug.
Back to the subroutine. The subroutine is expecting input between #01 and #FF (255 decimal). When round 256 is reached, the round counter wraps around to #00, and this subroutine is NOT expecting the input to be #00. Since the round is less that 16, the subroutine subtracts one from it and returns that as a result. So when the input is #00, this is decremented, wrapping back around to #FF (255 decimal) , which is garbage output. This causes a chain reaction later in the code when the tunnels are drawn and the enemies placed.
The locations of the enemies for the various rounds are stored in tables. The enemies' initial locations are represented each by a single byte. If the location specified is #87 (135 decimal), an enemy is drawn right on top of Dig Dug at the start of the round. It turns out that one of the memory locations used when the bug occurs has a #87 in it, which causes a Pooka to be drawn on top of Dig Dug on this round.
The start of the enemy location table data for round 0 erroneously gets computed as #3350. This section of memory is actually program code and is not expected to be used as data for anything.
3350: 89 87 81 ED B0 21 A3 89
The 2nd data byte above, #87, is the one that causes a Pooka to be drawn where Dig Dug starts. The fifth data byte above, #B0, does not get drawn to the screen because #B0 is "off the grid". The first and the last are the same location, but one is a Pooka and the other is a Fygar.
The start of the rock location table data for round 0 erroneously gets computed as #31E8. This address happens to be used for the locations of the tunnels for round 9. These are encoded in an entirely different way, and are not supposed to represent locations of rocks.
31E8: 88 82 8C 80
The fourth data byte above, #80, does not get drawn to the screen because #80 is "off the grid".
The Fix, Part 1
We can fix the logic of this subroutine to allow for round #00 to produce a valid output. Here is the fix, which fits exactly into the same confines of the original code space:
1BDE: 3A 27 86 LD A,($8627) ; Load A with round number 1BE1: 3D DEC A ; Subtract 1 1BE2: FE 0F CP $0F ; Is this round < #0F (15 decimal) ? 1BE4: D8 RET C ; Yes, return 1BE5: 3C INC A ; Else restore A to its original value 1BE6: E6 03 AND $03 ; Mask bits to make between 0 and 3 1BE8: C6 0B ADD A,$0B ; Add #0B (11 decimal) 1BEA: C9 RET ; Return
The trick here is to change the subroutine to do the subtraction at the beginning of the subroutine instead of at the end. We make some adjustments to the rest of the routine to account for this. Instead of checking against #10 (16 decimal), we check against #0F (15 decimal), and add #0B at the end instead of #0C. It turns out this fix is very similar to the fix that Pac-Man received to fix its split-screen level.
With this patch, when the round is #00, it is first subtracted which wraps it back around to #FF (255 decimal), then it gets caught in the trap that is set for all rounds that are above 16 (now 15). This code has been tested and does work. Here is what round 256 then looks like after patching. It is playable (it is quite easy) and can be finished.
A New Problem Emerges
However, another problem appears when arriving at this round. The subroutine which draws the fruit is also dependent upon the round number, and another bug causes a very strange fruit to be drawn after two rocks are dropped:
We can immediately see that the "fruit" that appears on this round is incorrect. It turns out it is a part of the graphic of a Fygar that is shown on the splash screen.
Some other weird things happen here. The "fruit", when eaten, awards 10,000 points, but shows the graphic for 00 points. Also, part of the "fruit" graphic then appears in the lower left corner.
The next step is to fix this bug so that a proper fruit is drawn on this round. After lots of looking we find the code that we are looking for. This section of code happens to run on the game's 2nd Z80 CPU. There is a subroutine very similar to the previous one that converts the round number into a code that is then used as an offset to point to a table of data that has information about the fruit. The subroutine is supposed to produce an answer between 0 and #12 (18 decimal).
1B2D: 7E LD A,(HL) ; Load A with round number 1B2E: 21 E8 87 LD HL,$87E8 ; Load HL with address where subtotal is stored 1B31: FE 12 CP $12 ; Is the round number > #12 (18 decimal, pineapple) ? 1B33: 38 02 JR C,$1B37 ; No, skip next step 1B35: 3E 12 LD A,$12 ; Yes, load A with #12, pineapple is the final fruit 1B37: 77 LD (HL),A ; Store subtotal answer into #87E8 1B38: D6 01 SUB $01 ; Subtract 1
The answer is then further processed and added to a pointer to the fruit table. The first two values in the fruit table are
1B57: 53 0E 04 5D ; carrot 1B5B: 55 10 06 5E ; turnip
The first byte is used for the graphic, the 2nd byte is the color code, third byte is used for the score (how many hundreds in Binary Coded Decimal) and the fourth byte is the graphic used for the score onscreen after the fruit has been eaten.
On round 0, the answer gets erroneously computed as #FF instead of inside the expected range. This results in the fruit drawing subroutine to use memory location of #1C53 which contains the following bytes:
1c53: 96 96 9A 9F
The third byte value is used for the score is #9A and explains why 10,000 points are awarded.
The Fix, Part 2
This subroutine is a bit trickier to patch within the confines of the original code space, because a subtotal is saved right before the answer is finally decremented by one. However, close analysis of the code reveals two places where one byte can be saved. The first is within the following two instructions:
1B2E: 21 E8 87 LD HL,$87E8 ; Load HL with address where subtotal is stored ... 1B37: 77 LD (HL),A ; Store answer into #87E8
There is no point in using two instructions that take up four bytes when a single instruction that takes only three will do. This way of coding might make sense if the same value of HL was used again later on, but it isn't. We can condense these two instructions into a single one:
1B37: 32 E8 87 LD ($87E8),A ; Store answer into #87E8
The second place where a byte can be saved is in this instruction from the above subroutine:
1B38: D6 01 SUB $01 ; Subtract 1
The subtract command only makes sense to use when the number being subtracted is NOT equal to one. In this case, the simpler command DEC A will do exactly the same thing with one byte instead of two. So we can modify that line to read:
1B38: 3D DEC A ; Subtract 1
Now, we have two extra bytes that can be used when we fix this subroutine to allow round 0 to have a correct fruit. It turns out it is just enough and a fix is possible within the confines of the original code space:
Fixed code follows:
1B2D: 7E LD A,(HL) ; Load A with round number 1B2E: 3D DEC A ; Subtract 1 1B2F: FE 11 CP $11 ; Is the round number > #11 (17 decimal) ? 1B31: 38 02 JR C,$1B35 ; No, skip next step 1B33: 3E 11 LD A,$11 ; Yes, load A with #11 1B35: 3C INC A ; Add 1 1B36: 32 E8 87 LD ($87E8),A ; Store answer into #87E8 1B39: 3D DEC A ; Subtract 1
After applying this second patch, round 0 is treated as a round greater than 17, so a pineapple is now computed for this round and the game can now be played through round 0 with no apparent problems.
All that is left is to fix the checksums so that the game will load properly after being patched, we do this and continue to write a cheat code for MAME that will implement these fixes:
:digdug:A1700000:1B2E:3DFE1138:FFFFFFFF:Fix Kill Screen :digdug:A1710000:1B32:023E113C:FFFFFFFF:Fix Kill Screen (2/9) :digdug:A1710000:1B36:32E8873D:FFFFFFFF:Fix Kill Screen (3/9) :digdug:20710000:1BE1:3DFE0FD8:FFFFFFFF:Fix Kill Screen (4/9) :digdug:20710000:1BE5:3CE603C6:FFFFFFFF:Fix Kill Screen (5/9) :digdug:20010000:1BE9:0000000B:000000FF:Fix Kill Screen (6/9) :digdug:A1010000:1FFC:00000088:000000FF:Fix Kill Screen (7/9) :digdug:A0010000:3FF9:00000029:000000FF:Fix Kill Screen (8/9) :digdug:A0010000:3FFD:00000028:000000FF:Fix Kill Screen (9/9)
Alternately the ROMs can be written to directly. Write to ROM dd1a.2:
0BE1: 3D FE 0F D8 3C E6 03 C6 0B
Write to ROM dd1a.6:
0B2E: 3D FE 11 38 02 3E 11 3C 32 E8 87 3D 0FFC: 88
Write to ROM dd1a.4:
0FF9: 29 0FFD: 28
The fix is implemented by changing 21 bytes, plus 3 bytes for checksum fixes, for a total of 24 bytes.
Below is a Youtube video of me playing round 0 after being patched.
Comments and Conclusions
Dig Dug, like Donkey Kong, has a true killscreen, where the player is forced to die no matter what he may try to do. This problem and fix was overall a fun project to work on. I especially liked squeezing two bytes out of the second subroutine to make room for two new commands which were needed for the patch.
|In accordance with Title 17 U.S.C. Section 107, some of the material on this site is distributed without profit to those who have expressed a prior interest in receiving the included information for research and educational purposes. For more information go to: http://www.law.cornell.edu/uscode/17/107.shtml. If you wish to use copyrighted material from this site for purposes of your own that go beyond 'fair use', you must obtain permission from the copyright owner.|