Working with Maps, Tiles, Chars and Compression

cbmeeks edited this page Mar 3, 2016 · 10 revisions

About

My game programming typically leans towards platformer games like Metroid or Contra. Another personal favorite (in both style and fun) is the original Legend of Zelda. Zelda isn't a platformer, meaning, it's not a "run and jump" game but an overhead game.

One thing you will notice is that each game I mentioned is a Nintendo Entertainment System (NES) classic. Yes, I am a huge NES fan. I always felt the Commodore 64 was severely lacking in some of the block-buster titles the NES had. But that's a topic for a later date.

Anyway, it has been my mission to create some of these games for the C64. Not really port them, but to make games that are similar in style and play-ability. The focus of this document is to provide ideas I have for storing, drawing and compressing maps for the Commodore 64. At first, these are ideas on paper only. With a little pseudo code mixed in. I hope to eventually provide some real working code. So consider this a work in progress. Oh, and since I am in the US, I will be NTSC biased. :-)

Also, most of my documents are for a game I am working on called 51 Pegasus. I may never finish it. It's not like I make a living making Commodore 64 games. LOL (but that would be awesome!!!)

So, many of the things I talk about may not apply to your game but hopefully it will be helpful to some degree.

Characters (Chars)

The C64 has a screen resolution of 320x200 pixels. There are plenty of documents out there explaining the different screen modes so I won't go into those here. But it's safe to say that out of that resolution, we get 40x25 characters on screen. Each character being 8x8 pixels. A character, or char for short, is simply an image that represents what you see on screen. Such as the letter 'A' or 8. When you first power up your C64, you immediately see a blinking cursor and some text on the screen. Each letter and number you see represent one char.

Fortunately, we can change the appearance of all of the characters you see on screen. Doing so allows us to create virtual worlds to play in. We're all familiar with the built-in PETSCII character set which contains some really neat characters like a heart, diamond, etc. Even though there have been many games created with them, they aren't very appealing to more "professional" games. That's why most game developers change the way they look. So instead of the letter A looking like an "A", it can be changed to look like a small energy tank or missle. Or be a part of a larger set representing a large energy tank. It's still the letter A as far as the computer is concerned. It just looks different.

Unfortunately, however, we only have 256 characters we can change. Which limits how detailed our maps can be. We could always drop into a hi-res multi-color mode but doing so takes a large amount of memory (for the C64) and limits other things we can do. Such as making scrolling or different maps very difficult. Of course we can always load more character definitions from disk or other areas of memory. We can only work with 256 at one time. It's possible to have the VIC-II change the character set mid-screen to point to another set of characters. But this is beyond the scope of this document.

... more to come on chars ...

Tiles

Some of the earliest game programmers discovered that in order to make dynamic and large virtual worlds, you can combine chars together to form tiles. If you look at NES and C64 games, you will typically find that many of the screens (scrolling or not) tend to be made up of repeating blocks of images.

_ ... insert images here ..._

So while building a map for the C64 using 40x25 chars would allow some incredibly detailed worlds, you would quickly run out of memory and CPU time drawing such maps. Also, I wanted to point out that I say chars when referring to the characters of the C64 screen and tiles when referring to a group of C64 chars. However, in the NES world, tiles are the same as chars. So an 8x8 char on the C64 is the same as an 8x8 tile on the NES. It's really the same thing on both, just two different terminologies.

By creating tiles made up of smaller chars, we can reduce the amount of memory to draw our maps with only a slight loss in detail. A good artist (which I am not) can make these tiles appear to be very detailed while at the same time avoiding the appearance of repeating tiles. But hey, it's an 8-bit machine. If you want giga-textures then go play a PS4. ;-)

A tile can be virtually any size. If you wanted, you could represent a tile by combining 4 chars horizontally and 3 chars vertically. Giving you 12 chars for that one tile. However, 8-bit computers work better with even numbers. And it's considered best practice to make your tiles a multiple of 2 on both the horizontal and vertical sides. It's typically customary to make your tiles square. A 2x2 char tile is common, 4x4, etc. There are always exceptions and some games use 5x5 chars for their tiles. So it's up to you. There is no "right" or "wrong" way to represent your tiles.

I personally prefer 2x2 char tiles on the C64. But 4x4 char tiles are also popular. 2x2 char tiles means each tile will be 4 bytes in size. The larger your tiles are, the fewer of them you can fit onto a screen at one time. However, larger tiles also mean less memory required for each screen. Smaller tiles allow much more detail per screen at the cost of more memory.

Going back to the resolution of the C64, we again have 320x200 pixels. Which gives us 40x25 chars. So if we assume a 2x2 char tile, that means we can get 20x12.5 tiles on the screen. 12.5? Yeah, 25 characters tall / 2 chars would give us 12 1/2 tiles. I don't like half-tiles so I would limit it to a resolution of 40x24 chars yielding 20x12 tiles. What do we do with the extra row of chars? That can be used for status information, scores, energy, etc.

Now, instead of taking 960 bytes per screen (40 x 24 chars), we now have 240 bytes (20 x 12 tiles). 240 bytes is much less than 960 but on the C64, even 240 bytes is a lot of memory.

If your game is only going to have a few screens you can probably just live with this. But a project I am working on will have many screens. So I want to reduce that even further. The first thing I recommend is to lower the number of chars you are drawing. Instead of drawing 40x24 chars, I will be using 40x20 chars. 40x20 chars yields 20x10 tiles. Now we're down to 200 bytes per screen. This leaves us 5 rows for our status bar. This status bar is a little large because I want to put a real-time map, graphics representing weapons, etc. So the sacrifice of screen real estate won't be that bad. Especially if you can make it engaging and useful.

Meta Tiles

I don't know who coined the term "meta tile", but in my opinion, a meta tile is a collection of tiles. Which is a collection of chars. So, a 2x2 char block would be one tile. A meta tile could be a 2x4 block of TILES. So that 2x4 object (meta tile) would represent 4x8 chars. This is useful for things that tend to repeat or large sections such as statues. For example, check out this screen in Metroid. Notice that we have certain patterns that repeat.

_ ... insert pics of Metroid meta tiles ... _

And that's what a meta tile can be viewed as. A pattern of tiles. The advantage? Look at the floor and ceiling of Metroid below.

_ ... insert pic of Metroid floor and ceiling ... _

Notice how it repeats certain tiles. Now we can store that in our map using our 2x2 tiles. But a similar floor would take 20x2 tiles (40 bytes) on the C64 (not exactly because the resolutions are different on the NES and the C64 but you get the idea). So what if we created a meta tile that represented 4x2 tiles then repeated that meta tile 5 times across the screen? We then have 5 bytes vs. 40. Because each meta tile could be represented as one byte. This of course means we have a maximum of 256 meta tiles but I think that's a practical limit. And, our drawing just got a little more complicated. But with some planning and mixing of tiles with meta tiles, you can create a lot of maps with a lot less memory.

For example, we could have a room that contains that meta tile on the floor and ceiling. So our 20x10 char screen would have the top two tiles and bottom two tiles drawn with the meta tiles. It would be something like:

M M M M M
T T T T T T T T T T T T T T T T T T T T 
T T T T T T T T T T T T T T T T T T T T 
T T T T T T T T T T T T T T T T T T T T 
T T T T T T T T T T T T T T T T T T T T 
T T T T T T T T T T T T T T T T T T T T 
T T T T T T T T T T T T T T T T T T T T 
M M M M M

T = 20 x 6 = 120 bytes
M (ceiling) = 5 x 1 = 5 bytes
M (floor) = 5 x 1 = 5 bytes
130 bytes representing a screen of 40x20 chars (20x10 tiles).

130 bytes for that screen is a pretty good savings over 200 for the normal 20x10 tiles. Granted, we now have a meta tiles table. But the top and bottom meta tiles would only cost 8 bytes of memory (which represents 4x2 tiles). So one byte to represent 32 chars. :-)

Now, that of course means our map just got pretty narrow with only 6 tiles (12 chars) of usable game space. But this could work in some maps. And with a good map drawing routine, you can mix and match all you want.

Rooms of 51 Pegasus

If you had a game like Zelda where each screen is static and only scrolled when going to the next screen, you could probably stop with just tiles and meta tiles. You could make large areas of grass or mountains in meta tiles and make each screen very small. So the 128 screen Over World of Zelda could probably easily fit into memory at once. With good planning.

But I want 51 Pegasus to be a game similar to Metroid where the screen scrolls in either a horizontal or vertical direction. In Metroid, you start off in a "room". Then you run right until you find a bubble door. Blast the door and you enter a vertical shaft. Which has a collection of doors. So basically, each vertical or horizontal area in Metroid can be considered small maps called rooms. If you look at Metroid in detail, you will find rooms are repeated frequently. Sometimes just the colors change but the rooms are the same. The Metroid programmers were very clever. The NES has much less memory than the C64. What they did was draw a set of reusable rooms that were one screen in size (16x15 tiles in NES). Then they could chain rooms together. So if you had 200 rooms, a VERY large virtual room could be represented with 20 bytes (20 screens wide). This was very clever but doesn't quite fit with the C64 because the NES has the ability to change the screen location up to 255 pixels. C64 can only do 7 and the C64's screen location is limited to a 1k boundary. On the NES, you can pan the screen left and right, for example, up to 255 pixels and during that time you draw new tiles on the left/right side. The Amiga can do something similar. However, on the C64, you can only pan up to 7 pixels. Which means you must be clever in how you scroll maps on the C64 using techniques such as double-buffering.

But, that doesn't mean we can't find a way to store many rooms and chain them together. But first, I want to talk about a compression algorithm I came up with. I may not have invented it, doubtful actually, but I haven't seen it used anywhere. If anyone knows of prior use, please let me know. I will talk about this compression in a bit but I wanted to mention how 51 Pegasus will be (hopefully) designed.

_ ... more detail on 51 Pegasus rooms ... _

Compression

Meta tiles are a form of compression if you think about it. So are tiles. With a tile, you are representing 2x2 chars with only one byte (not counting the tile lookup table). While there are many types of compression algorithms in the world, most are complex and not designed for the limited power of the 6502 CPU. I want to state for the record that I am NOT a compression expert. I just want to make my maps smaller. :-)

One popular compression format is RLE (Run Length Encoding).

https://en.wikipedia.org/wiki/Run-length_encoding

RLE works like this...say you have a stream of data (map, tiles, etc.) that was:

$10 $10 $10 $10

Notice that $10 is repeated 4 times taking 4 bytes of RAM. RLE would replace that with:

$10 $04

Meaning "take the number $10 and repeat it 4 times". Now, we only have 2 bytes instead of 4. A savings of 50%. Pretty impressive and very easy to implement.

But RLE suffers from a major flaw. Checker boards. How would RLE encode this data?:

$A0 $10 $10 $88 $10 $10 $10 $FE

That's 8 bytes. But RLE would produce:

$A0 $01 $10 $02 $88 $01 $10 $03 $FE $01

Now we're at 10 bytes. When compression algorithms produce LARGER files then we have failed. So RLE can be very useful but you have to test it on your maps. If your maps get larger, then don't use it. If they get smaller then use it. But then you now have complexity in your drawing. You now have to check if you are compressed or not.

One thing I propose is a mixture of RLE and no compression. Basically a way to turn RLE on and off IN the map and on-the-fly. Let's take the same data above:

$A0 $10 $10 $88 $10 $10 $10 $FE

Now this time, let's designate a certain byte as a flag, a way of telling the drawing routine if we are in compression mode or not. For simplicity, let's use the byte $FF. So when the drawing routine encounters an $FF, it switches mode and goes into RLE drawing. We loose one byte in our tiles doing this. Meaning we can't have a tile number $FF. But it's only one tile and there are ways around that.

$A0 $FF $10 $02 $88 $FF $10 $03 $FE

OK, now we are 9 bytes instead of 10 but still more than the original 8 bytes. When drawing, we first see the byte $A0. $A0 is not $FF so we just draw that tile and move on. Then we see $FF. Now we switch to RLE mode. We take the next byte, $10 and use that as our tile number. Then, we take the next byte again, $02 and use that as the number of times we repeat the tile. After we repeat, we take the next byte, $88 and determine it's not $FF so we just draw it and move on. We continue on until the map is drawn.

This is pretty cool but how can we solve the problem of it being larger than the 8 bytes? I feel the best way is not during the drawing routine, but in your compression routine. See, I would suggest that we take a modern computer, running a modern language like C# or Ruby and compress our maps. This compression program should detect that $10 is only used twice the first time. So if it takes 3 bytes to represent we're drawing two tiles, then we are being wasteful. Also, the second group of $10 is repeated three times. So technically, we break even because the $FF byte means turn on RLE. $10 is what we are repeating and $03 is the number of times we repeat. That's three bytes ($FF $10 $03). The same as just drawing $10 $10 $10. The compression program should detect repeating tiles of FOUR or more before utilizing the algorithm. So using the original data, the compression program would not compress it at all. It would simply save the map as it was:

$A0 $10 $10 $88 $10 $10 $10 $FE

Then the drawing routine would never detect an $FF and never switch to RLE mode. So my algorithm wouldn't be very useful for that data. However, let's look at this data:

$67 $88 $10 $10 $10 $10 $10 $10 $10 $10 $10 $10 $99 $10 $10 $10 $55 $99

That's 18 bytes. How would conventional RLE encode this?

$67 $01 $88 $01 $10 $0A $99 $01 $10 $03 $55 $01 $99 $01

That's 14 bytes. Better than 18. RLE actually worked this time. But let's try my method:

$67 $88 $FF $10 $0A $99 $10 $10 $10 $55 $99

That's 11 bytes. Even better. ;-) So I beat RLE and will every time. However, the compression program now has to be a little more complex. But this isn't a problem because I wouldn't put this on the 6502. This would be a C# or Ruby (or whatever) program that would read your map files and produce this. Of course, your drawing routine (in 6502 ASM) needs to be able to switch between repeating and non-repeating. But this can be handled later. Notice that the second set of $10 repeated three times. We could have used $FF $10 $03 but it's not worth the effort because we now switch to RLE and take a little hit for that to yield the same effect. This is where your compression program comes in. You could even tweak it so that maybe you don't switch to RLE mode unless you have 5 or 6 tiles repeating. Doing so reduces the effectiveness of the compression, though.

I think this is a good balance between RLE and no compression. If your compression program is good, then your maps will never get larger. They might stay 200 bytes per screen, but at least they won't grow.

Now, how can we take this further?

Compression and Meta Tiles

Oh, this is getting good. What if we sacrificed another byte, say $FE, to represent switching to meta tiles?

For example, say we have the following data. This represents a ceiling of one tile (2x2 chars).

$10 $1B $10 $1B $10 $1B $10 $1B $99 $A0 $10 $1B $10 $1B $10 $1B $10 $1B $99 $A0

Notice we have a repeating pattern of $10 $1B and $99 $A0. More accurately, we could say we are repeating $10 $1B $10 $1B $10 $1B $10 $1B and $99 $A0. So $10 $1B $10 $1B $10 $1B $10 $1B would be a good candidate for a meta tile. Now, if we use $FE to represent a meta tile, then our compression program could generate:

$FE $01 $99 $A0 $FE $01 $99 $A0

8 bytes now represents the top ceiling which is down from 20. Not too shabby. Granted, we now introduce a meta tile table (no big deal) and our drawing method now much switch from single tiles, RLE repeating tiles, and now single meta tiles.

But with some clever planning on meta tiles and a good compressor, we can now start having some really large maps without much RAM.

But Wait! There's More!

Let's take our repeating tiles (using $FF) logic and apply it to meta tiles as well. So let's say we have a meta tile that is composed of the following tiles:

$10 $1B $AA $55 $66     (meta tile $01)

That meta tile is 5x1 tiles. So to draw a ceiling, we could designate byte $FD for repeating meta tiles. Now we have:

$FD $01 $04

See what just happened? Our map drawing routine detected $FD which means RLE for meta tiles. Next byte, $01, represents meta tile $01 and $04 means how many times we repeat it. That would draw out:

$10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 

Yeah we just repeated $10 $1B $AA $55 $66 four times but we just rendered our ceiling and it only took 3 bytes.

I feel this compression method will allow some very large maps and many rooms. But unfortunately, our drawing routine just got a lot more complicated. The meta tiles are a great idea if properly planned out, but they are an extra layer on top of tiles. And tile rendering itself is a layer on top of chars. So two layers deep with a mixture of RLE. Complicated.

So when will this work out best? I feel a good way to use this method is to "decompress" rooms into a small working buffer before rendering to screen. This could be done during a "slow scroll". What would be a slow scroll? In Zelda, a slow scroll could be when Link touches the edge and the screen starts to shift. The drawing routine could afford to take a second or two to render the next page from the compressed maps. It could render that into the temporary buffer and scroll from there. In Metroid, this would work the same. When Samus runs through the door, we have a second or two to decompress the map into a buffer.

This buffer will have to be planned out. In Zelda, it could be the size of one screen since we only page one screen at a time. In 51 Pegasus, I will probably decide a maximum "room" size beforehand and decompress into that. Say, a buffer of 100x10 for 5 screens of 20x10 (horizontal). That would be 1,000 bytes. And maybe 20x50 for vertical shafts. So basically, when the hero walks through a door into the next room, decompress the map into that room and use that room as your source for scrolling.

This seems more logical than trying to render a line of chars on each screen location (top/bottom/left/right) when we are scrolling and then having the draw routine deal with that complexity then. So, we sacrifice 1,000 bytes or so for a temporary room map, some RAM for our meta tiles (dependent on the game) and of course our tile buffer.

I'm hoping this logic will win in the end. Having very large worlds to explore is why I want to make games in the first place. :-)

Meta Tiles Part Deux

Another idea I have been toying with is what Metroid actually does. Each room in Metroid starts off empty (all black) and contains only the meta tiles that the room needs. The difference is that the meta tiles in Metroid contain a little more logic. They are basically RLE mini-maps (or objects) that contain a position byte.

I may get this format slightly wrong (going from memory), but it's something like:

$A3 $10 $03 $XX $XX

Here, $A3 is the position of the meta tile (in tiles) on screen. $A3 converted to binary is 1010 0011. Bits 0-3 represent the Y position and bits 4-7 represent the X position. So 1010 is a nybble and would be 12. Then we take 12 and multiply by 16 (the size of a tile in Metroid...which is actually 2x2 chars/tiles) and you have an X position of 192. But since we are talking chars (NES tiles) then the X position is 12. The 0011 is 3 in decimal. Which gives us a Y position of 3 * 16 = 48 pixels. This was a pretty clever way of specifying a screen position in one byte. But this won't work with the C64 because the NES resolution is 256x240 pixels. The NES can only show 16x15 2x2 tiles. So the math works out great. But the C64 is 320x200. It would work for the Y position but not the X because X can go over 256 pixels.

Anyway, going back to our example, the next byte is $10. This is the tile to repeat and the $03 is how many times to repeat it. Now, the $XX's are not real bytes. I just can't remember what they are. But basically, if the forth byte is not a certain value ($FF, I think) then drop down a row and continue the repeat again.

So, like I said, that's not exactly how it's done but pretty close. This Metroid/NES version of meta tiles is more dynamic. But the beauty is that you could fill an entire screen with only one meta tile. So only 4, or maybe 5 bytes and you have an entire screen. Now that's compression!

The point to take from this is that all rooms would be empty and take 0 bytes. Then, we add only the objects that are needed to make it not empty. So a room with only a floor would be extremely small. Especially if you used a large meta tile. But this reduces flexibility.

I would like to play on this idea a little. Warning, entering brainstorm mode here!

I like the idea of a mini-map in a meta tile. What if I applied my algorithm to meta tiles? Take this sample room:

$10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 
$10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 
$10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 
$10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 
$00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 
$00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 $00 
$10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 
$10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 
$10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 
$10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 $10 $1B $AA $55 $66 

Again, we have a repeating pattern of $10 $1B $AA $55 $66. So we define meta tile $01 as:

$10 $1B $AA $55 $66    (meta tile 1)

But notice our thick ceiling/floor is four tiles in height. Leaving us with a tiny 2 tile passageway. Not very useful unless you are rolled into a ball. ;-) But you get the point. Or, the $00 tiles could be grass and Link is walking down a very narrow path.

Anyway, using our original compression, we would come up with:

$FD $01 $04
$FD $01 $04
$FD $01 $04
$FD $01 $04
$FF $00 $14
$FF $00 $14
$FD $01 $04
$FD $01 $04
$FD $01 $04
$FD $01 $04

That room would only be 30 bytes. Now this is assuming our drawing routine is row based and doesn't wrap. If we could change it to wrap to the next line, which we probably should, then it would be:

$FD $01 $10
$FF $00 $28
$FD $01 $10

Wow. 9 bytes. $FD tells us we are in RLE meta tile mode, $01 is the meta tile and $10 is 16 in decimal. So 16 meta tiles of 5 tiles each yields 80 tiles drawn from upper left to the middle. Then we repeat tile $00 40 times ($28 = 40 decimal) and then do the floor like the ceiling.

So is it worth altering our simple, static meta tiles? Can we really beat 9 bytes? I think at this point, it really comes down to the game.

Let's look at this map ($ omitted):

01 01 05 01 05 01 01 01 01 01 01 01 01 01 01 01 01 04 04 01 
00 00 00 00 00 00 00 00 01 05 01 04 01 01 01 04 01 04 01 01 
00 00 00 00 00 00 00 00 00 01 01 01 01 04 04 01 04 04 03 01 
00 00 00 00 00 00 00 00 00 01 01 01 01 01 01 02 02 02 02 01 
05 01 01 00 00 00 00 00 00 00 00 01 01 01 01 04 01 04 03 05 
01 01 04 04 01 00 00 00 00 00 00 00 00 00 01 01 01 01 01 01 
01 04 01 04 01 00 0A 0B 00 00 00 00 00 00 00 00 00 00 00 00 
05 01 01 01 01 01 04 01 01 01 05 01 05 00 00 00 00 00 00 00 
01 01 01 04 01 01 01 04 01 04 01 01 01 04 01 01 01 01 01 01 
01 04 01 01 01 01 01 01 01 01 01 04 01 01 01 01 04 01 01 05 

With no meta tiles and no wrapping, we get:

01 01 05 01 05 FF 01 0C 04 04 01                            11
FF 00 08 01 05 01 04 01 01 01 04 01 04 01 01                15
FF 00 09 FF 01 04 04 04 01 04 04 03 01                      13
FF 00 09 FF 01 06 FF 02 04 01                               10
05 01 01 FF 00 08 FF 01 04 04 01 04 03 05                   14
01 01 04 04 01 FF 00 09 FF 01 06                            11
01 04 01 04 01 00 0A 0B FF 00 0C                            11
05 FF 01 05 04 01 01 01 05 01 05 FF 00 07                   14
01 01 01 04 01 01 01 04 01 04 01 01 01 04 FF 01 06          17
01 04 FF 01 09 04 FF 01 04 04 01 01 05                      13

Which is 129 bytes. Not bad. Way less than 200.

_ ... more coming soon ... _