Donkey Kong Land III/Notes

The following article is a Notes Page for Donkey Kong Land III.

Japanese Version

Color Palettes

All color palettes, such as the sprite color palettes (0x1BE60-0x1BE67) and the level color palettes (0x84FFB-0x852FA) have four different colors (eight bytes) each and each color is a 15-bit value: 5 bits for blue, 5 bits for green, and 5 for red, in that order. Since each color has two bytes and there are 16 bits in two bytes, the first bit is unused. The bits for each color are then translated into a four-digit hex value, and the first two hex digits and the last two are switched because all Game Boy variants are little endian. Sprite palettes are constant and never change at all in the game, so each sprite can have one of eight different color palettes.

All sprite color values, from 0x1BEA0-0x1BF1E (?), is assigned a 3-bit value from 00-07. This number corresponds to the palette defined in the Sprite Color Palettes section (from 0x1BE60-0x1BE9F). Any number 08 or higher will cause the sprite to be invisible, which isn't used at all.

Most playable characters have different colors for various animations (such as jumping or swimming), especially Dixie and Kiddy (however, Ellie also has three and Squitter has two). Therefore, if you change the color of a character, it is important to change the color for every byte that relates to that character, otherwise a character can change color depending on his/her action.

When Kobble is defeated, his color becomes that of Skidda's. Therefore, if you make Skidda a different color from Kobble (Kobble's color is located in 0x1BEA1, Skidda's is 0x1BEA4), Kobble will turn into a different color when he is defeated.

For some reason, when trying to edit the color palette for cave levels (0x851FB-0x8523A), it completely screws up when playing the level Haunted Hollows (except the bonus stages in that level). It is likely because it is the only cave level with water in it. The same problem occurs with Ugly Ducting when trying to edit the color palette for tube levels.

(todo: add screenshots)

Level Header Data

Levels

This is the level header data, which controls different aspects of each level. In the English version, this data is located in 0x40065-0x4047E, and in the Japanese version, this data is located in 0x40067-0x40480.

In both versions, level headers have an array of $19 (25) bytes and is as follows:

aa bb cc dd ee ff gg hh ii jj kk ll mm nn oo pp qq rr ss tt uu vv ww xx yy

aa = Determines the level map that is used.
bb = Tileset pointer
cc = Sprite pointer
dd = Level properties. This determines water visibility, starting direction, and
     traction.
     Only bits 6, 3, and 0 have properties.
     Bit 6 = Water visibility. If this bit is 1, then water will be darkened. If
             this bit is 0, then it will be clear.
             Note: In the Game Boy Color version, this bit only has an effect on
               Tube and Cave stages, where it uses a raster effect to darken the
               palette during the middle of a frame using scanlines. Even if
               this bit is set as 1 on any other type of stage, the water will
               still be clear.
     Bit 3 = Starting direction. If this bit is 0, then Dixie/Kiddy will start
             the level facing right. If this bit is 1, then Dixie/Kiddy will
             face left at the beginning of the level.
     Bit 0 = Traction. If this bit is 0, then the level will not be slippery. If
             it is 1, then it will be slippery (like in snow stages).
ee = The music used in the level. See this for index numbers. After entering a
     level at least once, a flag is set so that when entering a level again
     (this affects bonus levels as well), the music played will be this value
     added by $14. This makes it so that you will hear slightly shortened music
     after this. For example, if this byte is $0B (Stilt Village) and you have
     been to at least one level, you will hear $1F (the same music, but shorter)
     instead. This flag resets when turning the game off.
ff = Water level. A lower value means the water will be higher up. If this value
     is 00, then the whole level will be submerged. Increasing the value by 01
     will lower the water by 32 pixels.
gg = This determines the precipitation.
     00 = Snow
     01 = Rain
     FF = Nothing
     Note: If a level has water in it, the bubbles floating from the water will
     cause sprite overload and cause precipitation to not show up properly, even
     if the bubbles are offscreen.
hh = X position from start, in increments of 32 pixels.
ii = Y position from start, in increments of 32 pixels.
jj = X position from Star Barrel, in increments of 32 pixels.
kk = Y position from Star Barrel, in increments of 32 pixels.
ll = X position from Bonus Barrel #1, in increments of 32 pixels.
mm = Y position from Bonus Barrel #1, in increments of 32 pixels.
nn = X position from Bonus Barrel #2, in increments of 32 pixels.
oo = Y position from Bonus Barrel #2, in increments of 32 pixels.
pp = X position from Warp Barrel, in increments of 32 pixels.
qq = Y position from Warp Barrel, in increments of 32 pixels.
rr = Bonus #1 map.
ss = Bonus #2 map.
tt = Warp map.
uu = ??? (This is either 00 or 01)
vv = ??? (This is either 00 or 01)
ww = ??? (This is either 00 or 01)
xx = If both this and byte yy are 00, then you will get an instant death upon
     entering the level. The purpose of this byte besides this is unknown.
yy = If both this and byte xx are 00, then you will get an instant death upon
     entering the level. The purpose of this byte besides this is unknown.

The levels in this group of data are ordered as follows:

Total Rekoil
Liftshaft Lottery
Miller Instinct
Black Ice Blitz
Polar Pitfalls
Tundra Blunda
Bleak Magic
Red Wharf
Ford Knocks
Jetty Jitters
Koco Channel
Riverbank Riot
Surface Tension
Seabed Shanty
Coral Quarrel
Deep Reef Grief
Barbos Bastion
Minky Mischief
Redwood Rampage
Simian Shimmy
Arich Attack
Vertigo Verge
Rockface Chase
Clifftop Critters
Rocketeer Rally
Footloose Falls
Rickety Rapids
Stalagmite Frights
Haunted Hollows
Ghoulish Grotto
K. Rool's Last Stand
Jungle Jeopardy
Tropical Tightropes
Rainforest Rumble
Karbine Kaos
Bazuka Bombard
Kuchuka Karnage
Barrel Boulevard
Krazy Kaos
Ugly Ducting
Whiplash Dash
K. Rool Duel

Bonuses/warps

Bonus stages and warps use a different format. This time, each header is only 0xE (14 decimal) bytes long. The format is as follows:

aa bb cc dd ee ff gg hh ii jj kk ll mm nn

aa = Determines the level map that is used.
bb = Tileset pointer
cc = Sprite pointer
dd = Level properties. This determines water visibility, starting direction, and
     traction.
     Only bits 6, 3, and 0 have properties.
     Bit 6 = Water visibility. If this bit is 1, then water will be darkened. If
             this bit is 0, then it will be clear.
             Note: In the Game Boy Color version, this bit only has an effect on
               Tube and Cave stages, where it uses a raster effect to darken the
               palette during the middle of a frame using scanlines. Even if
               this bit is set as 1 on any other type of stage, the water will
               still be clear.
     Bit 3 = Starting direction. If this bit is 0, then Dixie/Kiddy will start
             the level facing right. If this bit is 1, then Dixie/Kiddy will
             face left at the beginning of the level.
     Bit 0 = Traction. If this bit is 0, then the level will not be slippery. If
             it is 1, then it will be slippery (like in snow stages).
ee = The music used in the bonus level. See this for index numbers. Since the
     flag used to indicate whether a level has been entered will always be set
     by the time a bonus level is entered, this value ends up being added by
     $14, so you should subtract $14 from the original music ID when editing
     this.
ff = Water level. A lower value means the water will be higher up. If this value
     is 00, then the whole level will be submerged. Increasing the value by 01
     will lower the water by 32 pixels.
gg = This determines the precipitation.
     00 = Snow
     01 = Rain
     FF = Nothing
     Note: If a level has water in it, the bubbles floating from the water will
     cause sprite overload and cause precipitation to not show up properly, even
     if the bubbles are offscreen.
     Note 2: Unlike regular levels, snow and rain tiles will glitch randomly, so
     using this byte is not recommended.
hh = Bonus level type
     00 = Find the Token!
     01 = Collect the Stars!
     02 = Bash the Baddies!
     03 = (Warp stage)
ii = Bonus time
     This is in seconds, and is stored in a binary coded decimal.
jj = Number of enemies to defeat/stars to collect
kk = X position from start, in increments of 32 pixels.
ll = Y position from start, in increments of 32 pixels.
mm = If both this and byte nn are 00, then you will get an instant death upon
     entering the level. The purpose of this byte besides this is unknown.
nn = If both this and byte mm are 00, then you will get an instant death upon
     entering the level. The purpose of this byte besides this is unknown.

Music Index Numbers

Here are index numbers for the music in the game.

00 - (Silence)
01 - (Silence)
02 - Dixie Beat
03 - Crazy Calypso
04 - Northern Kremisphere
05 - Brothers Bear
06 - Bonus Time (screen)
07 - Bonus Time (stage)
08 - Bonus Win
09 - Bonus Lose
0A - (Silence)
0B - Stilt Village
0C - Enchanted Riverbank
0D - Nuts & Bolts
0E - Treetop Tumble
0F - Rockface Rumble
10 - Water World
11 - Mill Fever
12 - Hot Pursuit
13 - Jungle Jitter
14 - Rocket Run (Unused theme!)
15 - Cascade Capers
16 - Cavern Caprice
17 - (Silence)
18 - (Silence)
19 - Death
1A - Level Complete
1B - Big Boss Blues
1C - Wrinkly Refuge
1D - Baddies on Parade
1E - Game Over

1F-2A is the same as 0B-16, but with shorter beginnings.
2F is the same as 1B, except with a slightly slower tempo.

Level Index Numbers

Here are the index numbers for the levels. In-game, the current level is stored in RAM address FFA6 in the English version, and FFA5 in the Japanese version. Pointer tables, such as the ones for level maps, use this order. Note that the level headers are ordered differently.

00 - Seabed Shanty
01 - Coral Quarrel
02 - Deep Reef Grief
03 - Total Rekoil
04 - Liftshaft Lottery
05 - Miller Instinct
06 - Koco Channel
07 - Riverbank Riot
08 - Surface Tension
09 - Black Ice Blitz
0A - Polar Pitfalls
0B - Tundra Blunda
0C - Red Wharf
0D - Ford Knocks
0E - Jetty Jitters
0F - Minky Mischief
10 - Redwood Rampage
11 - Simian Shimmy
12 - Vertigo Verge
13 - Rockface Chase
14 - Clifftop Critters
15 - Rocketeer Rally
16 - Footloose Falls
17 - Rickety Rapids
18 - Stalagmite Frights
19 - Haunted Hollows
1A - Ghoulish Grotto
1B - Jungle Jeopardy
1C - Tropical Tightropes
1D - Rainforest Rumble
1E - Karbine Kaos
1F - Bazuka Bombard
20 - Kuchuka Karnage
21 - Barrel Boulevard
22 - Ugly Ducting
23 - Whiplash Dash
24 - Barbos Bastion
25 - Arich Attack
26 - Krazy Kaos
27 - Bleak Magic
28 - K. Rool Duel
29 - K. Rool's Last Stand

Level Maps

The compression data is unchanged from DKL. However, as with DKL2, there are some minor changes in the overall data:

• The level's width and height are stored right before the compressed map data, which is then multiplied by 32x32 pixels. In DKL, the width was stored elsewhere, and the height was not stored at all.
• Any tiles that contain sprites are initialized to 0x80.
• After the end of the compressed map data, the sprite data follows. This data consists of relative pointers. It replaces any byte in the decompressed map data whose byte value is 0x80 or greater with values in this sprite data. This sprite data always consists of values of 0x80 or greater.
  • After this process, the game uses a sprite table which consists of a background tile (one byte), and a sprite (two bytes). The sprite table is shared among all levels with the same setting (stilt, etc.). During this process, the game takes the lower seven bits of any byte value of 0x80 or greater, and uses this value to find the right entry in the sprite table to assign the tile the correct background tile and sprite.
• The decompressed map data shows up in a different part of RAM. In DKL, it showed up starting at 0xCC00. In DKL2 and DKL3, there is a big-endian pointer table starting at 0xC600 in RAM. The pointers depend on the width of the level (so there is one pointer for every row), and the number of pointers depend on the height of the level (in addition, the last pointer is copied 4 additional times). This pointer table did not exist in DKL.

To find the starting address of the decompressed map data, read the big endian pointer at 0xC600-0xC601 in RAM -- this will tell you where the decompressed map data starts. Alternately, it can be calculated with this formula: 0xC600+(height+4)*2.

Animations

0x1BEA0: (GBC version only) A list of the 8-bit sprite palette indices used by each Animation. It's indexed using an animation ID.

0x18001: A list of 24-bit pointers (bank first, big endian) to Animation structures. It's indexed using an animation ID.

Animation Structure

Animation:
    - The first byte is the number of frames in the animation.
    - Following that is a list of AnimationFrame structures- one for each frame in the animation.
    - Following that is a list of SignedPoint structures that define the relative locations of every sprite for
      every frame of the animation.
        - The first 'n' items in this list are for frame 0 where 'n' is the number of sprites used by frame 0.
            This pattern continues for every frame of the animation.
        - For each frame of the animation, each consecutive SignedPoint is relative to the one before it.

AnimationFrame Structure

AnimationFrame:
    0x0: The number of sprites used by this frame of animation.
    0x1-2: A 16-bit pointer (big endian) to the first tile pattern used by this animation frame.
           The pointer uses a special format (detailed below).
           These tile patterns are uncompressed.
           
           Pointer format:
               0x00-01:
                   Bits B-F: The bank.
                   Bits 0-A: Bits 5-F of the address.
 
               Bits 0-4 of the address are all 0.
 
               Due to the way the pointer is formatted, the address must be a multiple of 0x20 and
                 the bank must be in the range 0x00-1F.

SignedPoint Structure

SignedPoint:
    0x0: A Y coordinate (signed)
    0x1: An X coordinate (signed)

Drawing an AnimationFrame

• Each consecutive sprite forming an animation frame is drawn relative to the previous one based on the offsets defined in the AnimationFrame's matching Animation structure.
• Only 8x16 sprites are used.
• Tile pattern indices increase by 2 for every consecutively drawn sprite.
• Each sprite forming the animation frame uses the same sprite palette.
• When flipping the animation frame horizontally, negate the X offset of each sprite before adding it. Additionally, the animation frame should be drawn 7 pixels to the left.

Graphics Compression

Most background graphics are compressed using the same Huffman coding derivative found in Donkey Kong Land and Donkey Kong Land 2.

Format

Compressed graphics take the form of a bitstream of variable-bit-length code words. Each code word describes a path through a binary tree which starts at branch 0xFE and ends at a leaf node. Each leaf node has an associated literal which gets written to the output. Once enough bytes have been written, the decompression stops.

• A bitstream value of 0 indicates that a left turn should be made.
• A bitstream value of 1 indicates that a right turn should be made.
• The bitstream is read starting from the most significant bit of every byte.

The binary tree is split into three tables:

• 0x3D00-3DFF: Table LT

Contains 8-bit values for the left-side nodes in the binary tree. It's indexed using a branch ID.

• 0x3E00-3EFF: Table RT

Contains 8-bit values for the right-side nodes in the binary tree. It's indexed using a branch ID.

• 0x3F00-3FFF: Table TT

Contains 8-bit values describing the type of each node in tables LT and RT. It's indexed using a branch ID.

Each byte follows this format:

• Bits 0-2: Unused
• Bit 3: The type of the node in table LT with the same index.
• Bits 4-6: Unused
• Bit 7: The type of the node in table RT with the same index.

Node types:

• 0: A leaf node whose value is a literal
• 1: A branch node whose value is the branch ID of its children

The same binary tree is shared by all compressed graphics.

Decompressor

A decompressor, implemented in Python 2:

"""
Decompresses graphics.

@param tables - A tuple containing the 3 graphics decompression tables (left, right, and type).
@param tileCount - The number of tile patterns to decompress.
@param input - A stream of compressed graphics.

@return The uncompressed graphics.
"""
def decompress(tables, tileCount, input):
    bitReaderInput = BitReader(input)
    
    output = bytearray()
    leftTable, rightTable, typeTable = tables
    
    # The size of a tile, in bytes.
    SIZE_OF_TILE = 0x10
    # The ID of the binary tree's root branch.
    ROOT_BRANCH_ID = 0xFE
    
    # The size of the uncompressed data.
    uncompressedSize = tileCount * SIZE_OF_TILE
    
    currentBranchId = ROOT_BRANCH_ID
    
    while len(output) < uncompressedSize:
        if bitReaderInput.readBit() == 0:
            # Take a left branch.
            nodeValue = leftTable[currentBranchId]
            nodeType = getBit(3, typeTable[currentBranchId])
        else:
            # Take a right branch.
            nodeValue = rightTable[currentBranchId]
            nodeType = getBit(7, typeTable[currentBranchId])
        
        if nodeType == NodeType.LEAF:
            # Write the leaf's value to the output and start over from the root branch.
            output.append(nodeValue)
            currentBranchId = ROOT_BRANCH_ID
        elif nodeType == NodeType.BRANCH:
            # Follow the branch.
            currentBranchId = nodeValue
        else:
            raise Exception("Unknown node type.")
    
    return output

class NodeType:
    LEAF = 0
    BRANCH = 1

class BitReader:
    def __init__(self, stream):
        self.stream = stream
        self.currentByte = 0
        self.bitPosition = 7
    
    def readBit(self):
        if self.bitPosition == 7:
            self.currentByte, = unpack("<B", self.stream)
        
        result = getBit(self.bitPosition, self.currentByte)
        
        self.bitPosition -= 1
        if self.bitPosition == -1:
            self.bitPosition = 7
        
        return result

def getBit(b, n):
    if b < 0: raise Exception("b must be positive.")
    return (n >> b) & 1

def unpack(fmt, file):
    import struct
    return struct.unpack(fmt, file.read(struct.calcsize(fmt)))