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.

Thursday, July 11, 2013

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

I might have started my journey on the hard way! But that doesn't mean I am not exploring other avenues. After all, I got no intention to extract the sprites by playing the game and taking screen shots.

I saw a few years ago a video of ICU64 and I was amaze by it. I never though to create nor need such a tool. But when I saw it, I felt that is quite useful for software development in general. I think even Microsoft should get inspired by it and add a tool within their VisualStudio to monitor the memory in real-time. If you have never seen that tool, go watch the video below!

ICU64: Real-time Hacking of a C64 Emulator, video from mathfigure on YouTube.

I try ICU64 version 0.1.2 for Vice 2.3, I got a few crash here and there but worked about 99% of the time. I activated the graphic component in ICU64 and saw all the sprites at the last memory range address.

I also took some time to discover a couple of things in the game:

  • how to activate the spells;
  • how to increase the number of stamina, keys and other elements;
  • where are stored the flags to mention that an enemy has been killed;
  • and so on...

Knowing that kind of stuff would be very useful for me. As they could be use to answer specific questions related with the game logic. 

One of those question I asked myself was... how the dragon move? I know he is moving at the direction of the player, but after... what he will do? 

Well, I find the answer...

He is leaving the screen and never comeback, as long as you stay in the room! lol... The dragon might be big, but he is quite shy for a dragon! 

But in normal mode (without cheating) the player will get killed before the dragon reach the background with his head. 

Among all sprites in this game, two objects pose problems for the Coleco Vision. They are the Dragon and the Sea Serpents (Krakoli). On Coleco Vision only 4 sprites can be display in a row. The sprites can be 16x16 or 8x8 pixels and they can also be magnify by 2 (in both direction) or not. However 1 bit control each of these settings (i.e. 1 for sprite size, 1 for magnify). Which mean that all sprites get affected by these attributes.

In the image above, I merge all 4 sprites used to display the animation. The grid is 8x8 pixels. This way I can see how many background tiles I would need. I would like to make him HD (well retro-HD style) by increasing his resolution. I could use sprites to get the colors elements (eyes, nose, wings and toes). Also, I would like the dragon to move smoothly (not block by block). So, for now this object present a challenge of memory-size and cpu-cycles.

The image above show the Sea Serpents in the same way. This object does not move in X nor Y. But, the water in which he live is animated. To see how the object will look like I need to first convert screen backgrounds for Coleco Vision hardware. I think special water tiles will be required.

It is interesting to deal with big animated objects like that. Before the 16-bit video games console, animated sprites were most of the time restrict to be 32x32 or less. Seeing a giant enemy was really impressive!

Unused Sprites?

If you know the game well and you saw the ICU64 screen shot I took, you might wonder about a couple of sprites. There are few sprites which as never been seen in this game (as far as I know/remember). They might be there as an attempt to do something during development. Or, there might be something that still need to be discover.

Unused Sprites, Normal Size

Unused Sprites, Taller Size

Unused Sprites, Wider Size

 Unused Sprites, Bigger Size

The C64 can display sprites in normal, taller, wider or bigger (taller+wider) mode. Each of the sprites on the C64 can be set within one of these mode. In Doriath, the player get the attribute : taller. The snake take the attribute wider. The dragon and the sea serpents use bigger and the ghost (Wispith) use normal size attribute.

I think the spider should be taller. What I think it's a worm should be set wider and the bat should be normal size. They put the bat animation next to the weapons... could it be the one used against the ICE dragon?

Sprites Optimization

I mention the limit of 4 sprites on the same horizontal line. NewColeco has a video on his YouTube channel about it. In fact, I am using many of his videos to understand the limit of the Coleco Vision. I admit it's more entertaining than reading specification. The C64 has a limit of 8 sprites on screen. There are tricks on the C64 to handle more sprites, but that's another topic.

In Doriath, the sprites on screen are: the player (+ his weapon), up to 2 enemies (+ one/two firing something) and water drop / fire ball or a water splash. The water splash is fix on screen and could be render using background tiles instead.

It is important to keep the hardware limits we have and try our best to cope with them. Another case we can deal with involve the snakes. In some rooms, you got 2 snakes and they are often on the same line. Each snake require 2 sprites to be display. Snakes also fire something which I believe is their tongues (I put an 's' because they must have more than one as they keep firing them).

Because the head of the snake is located above what we need to display in the 2nd sprite used, there is a way to modify the sprites to reduce the flickering impact. The blue and red squares in the drawing above represents the sprite positions. If the player was not there, the limit of 4 sprites per line would be respected. Otherwise, one part of the snake need to be sacrificed. Here, I choose to flicker the tail of the two snakes. However, maybe it will look better if the snake located further to the player will be the one flashing?

The limit of 4 sprites per line may sound stupid. But, the hardware has to keep track of 32 objects! Somehow sorting 4 among the 32 per scan line where decision has to be taken at every pixel on the screen to know which color to use. I am not familiar enough with the hardware of the Coleco Vision to know if we can change video registers while the screen get draw and do fancy tricks like the C64.

I extracted all sprite-objects which I plan to use (see above some of them). In total that is 85 files. Each sprite in this list are either: 16x16, 16x32 or 32x16.

This represents a total of 139 sprites of size 16x16. A total of 4,448 bytes (139 * 16x16 / 8 pixels per byte) to store in the ROM (13.6% of 32 Kb). 

But, not all of these 139 sprites are unique, in fact there are 128 unique sprites. For example: some sprites feature a character with the same head and chest as another but different leg positions. With 128 sprites we are now down to 4,096 bytes (12.5% of 32 Kb).

Sprites can be store compressed in ROM and be restored in video memory at the initialization of the game. As a first step, I divided the 128 sprites to get char tiles of 8x8 pixels. Sprites are not charset, but their size of 16x16 make them easy to be divided in 4 tiles of 8x8. I retouch some sprites (e.g.: weapons) so their positions in the 16x16 sprite can reduce the number of tiles being generated.

Also, I output some statistics and information to validate what is going on. I also made a special case where a tile flipped along the Y-Axis and matching a previous tile should be referenced to that previous tile. Of course, I keep track of those which are identify in the image above by an asterisk (*).

Finally, this is where the fun begin! How would I code the information to reduce the size needed to store the sprites?

For the tiles, storing them as is: 252 tiles x 8 bytes/tile = 2,016 bytes. 

The encoding I end up is base on the statistics I extracted, which is:

0         +0b: New Char (1 bit)
               Count : 252              Size (bits) : 252
10        +4b: Flip Short Ref. (6 bits)
               Count : 121              Size (bits) : 726
110       +0b: Empty (3 bits), 
               Count : 73               Size (bits) : 219
111       +5b: No Flip Ref. (8 bits)
               Count : 54               Size (bits) : 432
111 00000 +4b: Flip Long Ref. (12 bits)
               Count : 11               Size (bits) : 132
111 11111 +0b: Flip XLong Ref. (8 bits)
               Count : 1                Size (bits) : 8


Assume the sprite use the following 4 tiles:

Where tiles are process in the order: A, B, C and D.

Where A and B are new tiles, C is the same tile as 5 tiles before B but flipped and D is an empty tile.

What will be the coding vector and how many bits is required to store that sprite?

Answer: The coding vector in binary will be: 0, 0, 10 0101, 110 which is: 11 bits long.


The total length for the coding vector to generate the 128 sprites using the 252 tiles is 1,769 bits or 222 bytes.

The total size is now : 2,016 + 222 = 2,238 bytes. (ROM : 6.8% of 32 Kb)

Compare to storing the raw 128 sprites, here I save 1,858 bytes. Each sprite take in average 13.8 bits to store the reference information and 15.75 bytes in tile data. A total average equal to : 17.475 bytes / sprite (instead of 32).

I plan to improve the sprites which are stretched on C64, to make them look better on Coleco. This should not impact the result I get here.

After looking closer to the data generated I noticed that I could explore a modified version of my algorithm which could deal with 1 Kb of RAM and include compressed tile data while still having the ability to use previous referencing tiles.

Decompression will surely take more time than copying raw data to the video memory. But so far this process need to be done only once at initialization... And for this game the only compressed data I can think of are the sprites and charsets.

One thing I know now is that the sprites can fit in 32 Kb ROM!