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

Example:

Assume the sprite use the following 4 tiles:

A C

B D

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!

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

Everyone need to relax sometime. We usually play or do one of our favorite activity. Could be your best video game on your latest iPhone or a puzzle like SUDOKU. For me, my real puzzle I have are rated: Expert! In fact, they often cannot even be solved without some specialized assisting tools!

Back in June 2010, I went to a Coleco Vision/Adam convention near my place where I did a speech. Having not follow what was going on since then, I look back on YouTube last week-end and watch one presentation made last year. CollectorVision was there presenting a brand new Arcade Joystick and also new games. I am amaze to see that hobbyist produce what was the cutting-edge technologies back in 1984! Also, they promise more games to come for 2012.

Thinking about games... On my first computer, there is 1 game I play seriously in my childhood: Doriath. Back then, we (me and my brother) got dozens of diskettes with games. Most of the time, we just LOAD them, try and go to the next one. But, that one seemed easy if you are patient enough. It's an adventure game which look more like a puzzle. You have to find new amulets that allow you to kill a specific type of enemy. And when you kill an enemy in a room, it's gone forever! Plus, don't be impress by the fire or water, they do almost nothing.

Wow, Great, playing this game to the end will be a piece of cake!

But there are a lot's of rooms... the maze consist of a 16 by 16 rooms map (256 rooms). And after playing for more than 3 hours, we were still looking to the QUASILIN's amulet. 

Me and my brother got really serious about it! Let's draw each room to monitor the places we already visited and what was there! We end up with many many pages with room diagrams... But based on our maps, the QUASILIN amulet was missing in the game!!!

We may not have reached the end of the game but it was a good team effort for us. Both tie together to reach a single goal! Just to say, the ending of this game is even more strange than this...

Hum, I think it's on purpose that this game seem easy, but the reward you keep looking at cannot be achieve. I think the author probably design it as a lesson of life.

But, back then we felt bad about it and though: it's nonsense, must be a bug in his game!!!

Back to the Coleco Vision, were deception could also be found. That was our very first (and last) video games system we got together. We bought a lot's of cartridges and when looking to the system box or game guide that come with it, there was some games which we never found in store. We though, maybe it's our stores!? But end up that those games (like Side Trak) where vaporwares!

However, Collector Vision's guys are working hard to make them real! Including the cartridge box and instruction manual! They released it in 2011. They design this game on what they believe the game would have been. Because that game never got released on any other system!

---

Then, I was thinking... if Doriath could have been made for the Coleco Vision? Probably, yes? 

I knew someone already did a map capturing all 256 rooms into one big .GIF file. I will just need to extract the common tiles (8x8 pixels on C64) and get a way to display them on screen, and you could get the 256 rooms!

A long week-end, a rainy day or two... a not too busy schedule. As I work on some home tasks, I kept thinking about it and though, I knew I already have coded functions to LOAD and SAVE image files somewhere. All I need is a modified version of the map (where I will remove the enemies and a couple of adjustment here and there). Then I will code something to parse the image to get those tiles within one image file.

Some people still familiar with the C64 might think: or just use a C64 emulator memory viewer to view the tiles directly? Bah, I don't like cheating... got to find the solution from reverse engineering things.

I started to clean up the map by removing the enemy. I clean up the water (removing white dots and waves effects) and I remove the fire flames tiles. Also, I put back the colors of the chest box which was colored in the map I find to identify what are in. But, in the actual game they are all the same brown color. 

Did I mention there are 256 rooms? Well, yes... it took some time.

Once the map was cleaned, I convert it into .BMP format. Within couples of minutes, I got a first program loading and saving the image into a different name, just to verify that the LOAD and SAVE were working properly.

Tile Extracting Information File

I though to extract the tiles but also keep note for each tiles where in the image they were first taken from. This is to help validating what is going on. After all, maybe the clean-up process did left some pixels here and there.

The answer... 91 tiles! How much I was hoping for? Well, it has to be less than 256. I was hoping for half or less than half. I know more tiles need to be added for graphic effects and giant enemy.

This result is good. My puzzle solved? Well, not exactly... there are 256 rooms and each room contain 40 columns by 20 rows of tiles. If you store each room as they appear on screen, it will take 200 Kb to store them. The C64 has only 64 Kb and the ColecoVision only has up to 32 Kb ROM.

The tiles are assembled together to form objects which are used to draw each room. How many of those meta-tiles are needed?

This question is harder to answer than the previous one. First, the meta-tiles has different sizes. I also don't know how they were assembled to form the final layout. Maybe some were placed partially on top of other meta-tiles?

Our eyes can easily see and recognize patterns. But there are just too many graphical elements to extract them one by one. First, let's see how the rooms look like by generating text output using the tiles index  from my extracted tile bitmap.

Here, the letter W represents water (a blue tile).

To make a short story of how I extracted the meta-tiles, I create a system which deconstruct every room into the biggest meta-tile which can be find elsewhere in the map. The system take as an input a series of meta-tiles which are use to clean the map before processing it. This way, I can take out objects which are obvious or target those which I want to be separated anyway. The more meta-tiles I add in the input directory and less content are left on the map.

The answer... 95 meta-tiles. So, would the game be feasible on Coleco Vision? Well, 256 rooms it's a lot and 32 Kb it's small! This give 128 bytes per room... and at 128 bytes you are not getting a game but just a useless piece of data. Hum, so this problem is a quest of size-efficiency!

Another problem ahead... The graphic resolution on a Coleco Vision is 256 pixels by 192 (32 tiles by 24), while the C64 is 320 pixels by 200 (40 tiles by 25). Both system use the same tile size (8 x 8), but the Coleco Vision has 8 columns less than what we need. Also, rooms need to fit together on the map to stay consistent, so part of it as to be remove carefully.

To develop an automatic tool, first you need to know all the rules. Here, I just don't know until  I visit each room more than once and list those rules out. The solution I came up with is to generated an image which can be easily read by human and computer to visualize the meta-tiles. I will then modify each room by starting with the one I know what to do. Placing those modified room into a new map like the one generated. This new map will then be read back by the computer which will be replacing the old one.

The visualization read by the computer consist of a green (I pick up green color has no tiles contain green) rectangle around each meta-object but where RED and BLUE are equal to the meta-object ID.

Note: map color has been modified, to show as blueprint. Normal color are black (background) & green (lines).

Here you see just a portion of the map. But, the giant blue print is really impressive by it's complexity and it's size.

But to be human readable, we need to see the actual map. I need to know what I will be removing or changing and how it will look like.

Here I am back to Step 1. With a map to modify and with another long week-end ahead!

But...  would it rain?