Tuesday, July 30, 2013

Could the world of Doriath from C64 fit into the Coleco Vision? (Part 3)

The biggest challenge so far in this project seem to be how to store the entire maze? After all, looking back to games on Coleco Vision, many got less than 10 different screens (some games like Donkey Kong only display 3 screens)!

In my first post, I end up with a map of 256 rooms to adjust. Re-sizing them from 40 columns wide to 32. But, after spending a few hours on that task, I realize that it would take days and days!

I then start to look to other approach, I find out that each room are divided into 8 large tiles (as shown above). Before describing how these large tiles work, I need to explain the states of the dynamic elements found in this game.


Some elements in the maze has two different states. For example, a chest box can be either close or open. The state of these elements will determine how they will be draw on screen.

There are 7 different elements (illustrated above) which the player can encounter when entering a room: 
   - Chest Box;
   - Up to 2 Enemies (Enemy #1, Enemy #2);
   - Mushroom;
   - Flower;
   - Trap Door;
   - Door (Portcullis).

Looking at the entire maze, we will never have a mushroom and a flower in the same room. In fact, we will never have more than one enemy when there is a mushroom or a flower. We can now group the information as follows:
   - Chest Box;
   - Enemy #1;
   - Enemy #2 / Mushroom / Flower;
   - Trap Door;
   - Door (Portcullis).

There are 14 trap doors in the game. We can found a trap door with : a Chest Box + 1 Enemy, a Portcullis + 1 Enemy or 2 Enemies.

Knowing that, we can reduce it to 4 bits of information:
   - Chest Box;
   - Enemy #1;
   - Enemy #2 / Mushroom / Flower / Trap Door;
   - Door (Portcullis) / Trap Door.

Where, when there are 2 enemies, the state of the trap door will be located at the door state, otherwise at enemy #2. A value of 0 will represents the default state: chest box close, enemy alive, door close and so on.

ROOM States (Bits Description)

7 6 5 4  3 2 1 0
x x x x  x x x x
| | | |  | | | |
| | | |  | | | +--- -Chest Box  A, 1=Open 
| | | |  | | +----- -Enemy #1   A, 1=Killed
| | | |  | +------- -Enemy #2   A, 1=Killed / Mushroom  A, 1=Active /
| | | |  |           Flower     A, 1=Grown  / Trap Door A, 1=Open
| | | |  +--------- -Portcullis A, 1=Open   / Trap Door A, 1=Open
| | | |  
| | | |  
| | | +------------ -Chest Box  B, 1=Open 
| | +-------------- -Enemy #1   B, 1=Killed
| +---------------- -Enemy #2   B, 1=Killed / Mushroom  B, 1=Active /
|                    Flower     B, 1=Grown  / Trap Door B, 1=Open
+------------------ -Portcullis B, 1=Open   / Trap Door B, 1=Open

Where A is for the rooms numbers which are even (0, 2, 4, ...), while B is for the odd numbers (1, 3, 5, ...). The initialization of the maze (at least for the rooms) will consist of writing zeros at these 128 bytes RAM.

Note: When the player exit a room and all possible elements for that given room are set, all 4 bits should be set to 1. So, even if a room contain none of these element, when the player leave that room all bits should be set to 1.

The nibble corresponding to the current room will be store into a specific byte, which will simplify the reference to this information in our code (+ 1 byte RAM). The higher nibble of that byte RAM will specify if the element is present (set to one) or not.

A total of 129 bytes (RAM) will be use for the entire maze states.


In order to determine if a trap door will be draw open or close, we need to know if there will be one or two enemies.

Among the 256 rooms, 39 has two enemies while 73 has only one enemy. Enemies are described by their type, their initial coordinates on screen and their type of movement (stand still, short distance walk, long distance walk or move straight forward).

I compare these attributes (by taking out bytes from the original game) and found that the unique description needed for two enemies went down to 37. Doing the same for single enemy, the number went down to 60.

Enemies (Bits Description)

Byte 0:

7 6 5 4  3 2 1 0
x x x x  x x x x
| | | |  | | | |
| | | |  +-+-+-+--- - Enemy Type: 1=Plebata, 2=Plebata-Archer, 
| | | |               3=Roimort, 4=Wispith, 5=Cobron, 6=Magusaan,
| | | |               7=Quasilin, 8=Mingos, 9=Krakoli, 10=Draconis.
| | | +------------ - Position X (5th bit)
| +-+-------------- - Movement: 0=None, 1=Short, 2=Long,
|                     3=Straight Ahead.
+------------------ - Initial Direction: 0=Left, 1=Right.

Byte 1:

7 6 5 4  3 2 1 0
x x x x  x x x x
| | | |  | | | |
| | | |  +-+-+-+--- - Position: X (lowest 4 bits), from 0-31
+-+-+-+------------ - Position: Y, from 0-15

The enemy initial coordinates on screen is ( x*8, y*8+16 ) pixels.

The reference table to access these 2 bytes (or 4 bytes, if two enemies) will use 256 bytes, one byte per room. In fact, 7 bits out of 8 will be use because they will refer to less than 128 enemies descriptions.

The enemies descriptions will take 120 bytes for 1 enemy (60 x 2 bytes) and 148 bytes for 2 enemies (37 x 4 bytes).

A reference number equal to 0 will be reserved for 0 enemy. Then reference numbers from 1 to 60 will be use for single enemy and from 61 to 98 for two enemies.

Six bytes in RAM will be use per enemy :
   - Type (bit 0-3: type, bit 4-7: reserved)
   - Attributes (bit 0-3: color, bit 4: fire a spell?, bit 5-6: movement, bit 7: direction left/right)
   - Enemy X position (in pixel)
   - Enemy Y position (in pixel)
   - Spell X position (in pixel)
   - Spell Y position (in pixel)

I may use 2 additional bits (currently reserved) to allow X coordinates to be greater than 255.

Total size to store enemies information:
256 + 120 + 148 = 524 bytes (ROM) and 2 x 6 = 12 bytes (RAM).

Large Tiles

The main component of the maze are the 8 large tiles which I mention at the beginning of this article. When doing some analysis, I notice that each corner (2 x 2 characters) can have 3 patterns.

A corner can be either transparent (display whatever is on the tile), use a brick or a cave pattern. There are 4 cave patterns, each one match a specific corner.

Large Tile Corners (Bits Description)

7 6 5 4  3 2 1 0
x x x x  x x x x
| | | |  | | | |
| | | |  | | | +--- - Top-Left     Pattern : 0=Brick, 1=Cave
| | | |  | | +----- - Top-Right    Pattern : 0=Brick, 1=Cave
| | | |  | +------- - Bottom-Left  Pattern : 0=Brick, 1=Cave
| | | |  +--------- - Bottom-Right Pattern : 0=Brick, 1=Cave
| | | | 
| | | +------------ - Top-Left     Opaque : If set, Yes.
| | +-------------- - Top-Right    Opaque : If set, Yes.
| +---------------- - Bottom-Left  Opaque : If set, Yes.
+------------------ - Bottom-Right Opaque : If set, Yes.

When we ignore these corners, there are only 70 large tiles. 

On the other hand, we can count 142 different large tiles which required corners. These large tiles take 2 bytes for their description. The first byte being the pattern of the large tile (among the 70 we found). The 2nd byte is the byte described above (Large Tile Corners). 

Each room will use 8 bytes, one for each large tile. Also, since there are 5 different patterns of 2 x 2 characters for corners, we need to add 20 extra bytes.

Total size to store large tile references and corners: 
256 x 8 + 142 x 2 + 20 = 2,352 bytes (ROM)

Large Tiles - Type A      (0x00-0x1F)

The 70 large tiles can be grouped based on their design properties. In the first group, they are organized in a specific order which tell which wall to be draw based on the 4 lowest bits.

If you look closely, you will notice that bit 0 (set to 1) will draw the wall on the left, bit 1 the one on the right and so on. Bit 4 (#16 to 31) will draw a ladder in middle prior to the walls. Tile #31 is a special case where the two upper lines will be erase, then 2 brick corners will be draw. These tiles will be generated by code only, no data is required.

Large Tiles - Type B      (0x20-0x2D)

Large tiles of Type B are the one which required to be store as is (8 x 10 = 80 characters), except for the one which has a chest box. The Chest Box appear only when the large tile number is odd (35, 37, 39 and 41). The position of the Chest Box is equal to the 4 lower bits divided by 2. For example, large tile 35 which is 0x23 in hexadecimal: (0x23 & 0x0F)/2 =  0x03>>1 = 1. Using the same logic: 37 give x = 2, number 39 give x = 3 and number 41 give x = 4. Which is the position of the first character used to display the chest box. The vertical position being constant. These positions are relative to the tile, not to the screen.

To store the 7 large tiles design of Type B, I will need 7 x 80 = 560 bytes. To store the Chest Box open and close, I will need an additional 2 x 6 = 12 bytes.

The total size required to store large tiles of Type B is: 
560 + 12 = 572 bytes (ROM).

Large Tiles - Type C      (0x30-0x38)

Large tiles of Type C are the one using water patterns. You will notice in the original game that the water is animated. At this point in time, I have an idea how the water is animated but not entirely sure about its details. I would store the entire water pattern on the first water tile (#48). I think there is different characters used and the bitmap inside these character get updated at each frame.

Since the water fall on tile #48 is 4 characters wide and 10 characters tall, it will required 40 bytes. Water fall on pattern #49 and 50 is almost identical to #48. On pattern #49, I could store the last 2 lines (16 bytes). Pattern #50 may look like 2 cave corners, but they are not. They use a slightly different variation which make their slope look sharper. To store these 2 corners, I will need 8 bytes.

The water fall at #51 and 52 contain a water fall but also a lake which we see on tile #53 and 54. Specific code should be written to handle these two cases. We will need 16 bytes of data for the last two lines at #51 and 8 bytes for #52. Tiles #53 and 54 will required 16 bytes each, while tiles #55 and 56 which are 5 lines height, will required 40 bytes each.

The total size required to store large tiles of Type C is: 
40 + 16 + 8 + 16 + 8 + 2*16 + 2*40 = 200 bytes (ROM)

Large Tiles - Type D      (0x39-0x3E)

Large tiles of Type D are in fact the leftover ones! They have been moved here in order to reduce the numbers of indexes reserved. Leaving more indexes available for tiles which need corners patterns for their description.

Tile #57 and 58 had 2 columns wide and will required 20 bytes each. Tile #59 will required 40 bytes. The 3 others large tiles (#60 to 62) are 4 lines height and will required 32 bytes each.

The total size required to store large tiles of Type D is:
2 * 20 + 40 + 3 * 32 = 176 bytes (ROM)

Large Tiles - Type E      (0x40-0x46)

Large tiles of Type E contain a rope in its center. The rope will be draw first and then some part could be erased for #66 and 67. The corners on #67 and 68 are usual corners which can be add after the large tile has been draw.

The data required on tile #65 to 67 is : 3 x 16 = 48 bytes. And, the data required for tile #68 to 70: 4 x 20 = 80 bytes.

The total size required to store large tiles of Type E is: 48 + 80 = 128 bytes (ROM)

Large Tiles - Type F      (0x48-0x4E)

Large tiles of Type F could feature some interactive elements. The flower needs 2 and 14 bytes, for a total of 16 bytes. The mushroom needs 2 x 6 bytes (as there are 2 characters on the ground which differ from the pattern of tile #72). The torch needs 6 bytes (a character which display the fire on top of it will also be stored). Trap door needs 2 x 3 characters for open and close drawing. And portcullis will be generated because it's only one character.

The background of these tiles will need 16 bytes for the 2 lines on tile #72 to 74. Tile #75 will take 32 bytes.Tile number 77 will required 4 bytes (one corner which is repeat on both side), the extra character needed below the trap door close will be added in code. Large tile #78 will needs 4 bytes for the top and bottom parts of the portcullis.

The total size required to store large tiles of Type F is:
(16 + 12 + 6 + 6) + (16 + 32 + 4 + 4) = 96 bytes (ROM)

Large Tiles - Type G      (0x50-0x58)
Finally, large tiles of Type G feature some low-danger elements : lava (#80 to 82), water split (#83 to 85) and water drop (#86 to 88). Some information will be added to our game engine to manage these animation which could reduce player's stamina in some circumstance.

The lava tiles need 16 bytes each, the water split tiles need 24 bytes each, tile #86 needs 32 bytes, #87 needs 5 x 8 = 40 bytes and #88 need 6 x 8 = 48 bytes. 

The total size required to store the large tiles of type G is:
3 x 16 + 3 x 24 + 32 + 40 + 48 = 240 bytes (ROM).

Chest Boxes

A fixed length vector with room numbers will be use to determine the content of each chest box. Room numbers will be store grouped together. The order would be: Amulets (in amulet order), blue keys, white keys, scroll fragments, red potions and the green potion. Since stamina potions are the most common item, if the room number is not found in the list, it will be a stamina potion. The amulet ID would be directly taken from it's position in the list.

There are: 59 stamina potions (default value, not stored), 14 blue keys (portcullis), 11 white keys (trap door), 9 amulets (including Plebata and Quasilin), 8 scroll fragments, 4 red potions and 1 green potion. 

To store these information: 47 bytes will be required.

Note: There is 14 traps and 17 doors to open. So, there are a total of 6 keys missing?

Maze Conversion & Total Size
After re-sizing 70 large tiles, I was able to generate the maze adapted for Coleco Vision display (32 columns by 20 lines per room). You can see above the result for part of the maze: on left: original game on Commodore 64 and on right: Coleco Vision, but using the original charset and colors.  

The total size required to store the maze information (excluding charsets and sprites) is:

                                    ROM     RAM
Maze States...........................0     129
Enemies.............................524      12
Large Tiles References............2,352       0
Large Tiles A.........................0       0
Large Tiles B.......................572       0
Large Tiles C.......................200       0
Large Tiles D.......................176       0
Large Tiles E.......................128       0
Large Tiles F........................96       0
Large Tiles G.......................240       0
Chest Box (contents).................47       0
----------------------------------------   ----------
Total............................ 4,335     141 bytes

With less data, more code will need to be written. How much bytes will the code will be taken? These numbers are not final but it give you a good idea about how small things can get. How big 4,335 bytes is? If we take that number divided by the number of rooms we get 16.9 bytes. So, in average a room take less than 17 characters long to describe how it should be draw (excluding charsets and sprites).

If I would want to save even more bytes, I would study the references tables which describe the 8 tiles and also the 256 bytes that tell where to look at for the enemies description. Together, they represent 2,304 bytes (more than 53% of the total data described here). By using more code, CPU cycles and 9 extra bytes in RAM, I think the total size could be reduce below 4 Kb!

I will conclude this article (pretty long one)... with an example to illustrate the process.
And as always, Thanks for reading...

- - -

Room name 'Hall 01 of Cerim's Deep' or room #0x20.

1. Entering for the first time room #0x20, retrieving the states...
  • Look at offset 0x20>>1 = 0x10 in RAM, for the lowest nibble (even room number).
  • The binary value found will be 0000 which we will store to the current room state byte.

2. Getting Enemies Information
  • Read the enemies index from the enemy look-up table using the room number 0x20.
  • The index return will be between 1 and 60 because there is one enemy in this room.
  • Two bytes will be read from the enemy information: 83 F7.
  • In RAM, 12 bytes will be written for the enemies: 03 8A 38 88 00 00  00 00 00 00 00 00
  • If enemy bit is set, to indicated that the enemy is kill, the enemy type is set to 0. (e.g.: if Roimort is dead, the 12 bytes would then be: 00 8A 38 88 00 00  00 00 00 00 00 00).
  • Bit 5 on the current room state byte will be set (since there is one enemy).

3. Drawing the room

The large tiles reference values in decimal, for room 0x20 are: 
42, 88, *1, 44
39, 83, 77, *2

where *1 and *2 are numbers higher than 88 (the last tile), which mean they consist of large tiles + corner patterns byte.

*1 will point to the 2 following bytes: 64 (tile) and 0x33 (corners).
*2 will point to the 2 following bytes: 81 (tile) and 0x22 (corner).

Each large tiles will be draw. When drawing large tile #39, the Chest will be draw closed as the bit state in RAM is 0. When drawing large tile #77, the second byte for the enemy being 0x00 (color = transparent) indicate that there is only 1 enemy in that room. The bit for the 2nd enemy will be use to determine if the trap door is close or open.

When drawing large tile #39, the bit 4 for the current room state byte will be set. When drawing large tile #77, after looking for the 2nd enemy attribute byte, bit 6 of the current room state byte will be set.

4. When the player passes next to the chest box. 

A function will be call to know what is inside. The value 0x20 will be find in the chest box vector (unless the chest box contain a stamina potion) and it's position will determine the corresponding object type found.

5. When the player exit the room: Saving Room State.

The current room state byte will be read and a comparison will be made between the two nibbles (lower and higher 4-bits). If they are identical, the lower nibble will be set to 0xF. Then the lower nibble of current room state will be stored at the lower nibble of offset 0x10 in RAM. 

Note: I did not provide details about water and lava elements for now, they will be describe later.

No comments:

Post a Comment