This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Zelda FDS (and general disk-related questions)

Zelda FDS (and general disk-related questions)
by on (#98573)
I'm puzzling over some Disk System documentation and trying to wrap my head around a few hardware concepts, especially related to the Legend of Zelda. As I understand it, the RAM adapter generally functions as a writeable NROM (32K PRG-RAM, 8K CHR-RAM) and the BIOS coordinates shuttling data to and from the disk as needed. Also, unlike 3.5" floppy sectors, data blocks on disk can be of dynamic length. My question is whether the BIOS handles data retrieval like swappable banks in an MMC. In other words, when Link enters a new area, is the entire 8K of CHR-RAM swapped at once, or does the software swap tile blocks in and out as needed? The same question applies for game code.

Second, while searching the forums, I've found a few mentions of Zelda's 'bizarre' compression scheme (which was carried over to the cart version). Ditto for a post on romhacking.net. However, no one mentions precisely how the compression works. I assume the compression format is related to my question above, as a means to pack level data efficiently for disk-to-adapter transmission. (Also, does anyone have access to the partial disassembly mentioned in the romhacking forum? The link is dead now [no pun intended].)

I have also read that Zelda's dungeons (and overworld) fit like puzzle pieces into 16x8 screen matrices. How are these stored in memory and how are individual dungeons referenced during play (e.g. by coordinates within the screen matrix)?

I also found this partial disassembly interesting, for those who hadn't seen it.
Re: Zelda FDS (and general disk-related questions)
by on (#98578)
FDS has 32K of PRG-RAM at $6000 to $DFFF. The FDS BIOS is mapped at $E000-$FFFF. It also has 8K of CHR-RAM. All this memory (except the BIOS) can be written by the Disk Program if it wants. The BIOS has functions most games (though perhaps not all) use to load data from the disk. It works by calling a LoadFiles() function with parameters of what you want to load. Loading is FAR from instant. FDS has no bankswitching ability. Instead it loads data into RAM from whatever files it chooses to load off the disk. So you can think of the disk as being REALLY slow bankswitching in a way.

Unlike NROM, FDS supports nametable mirroring switching for vertical or horizontal mirroring. It also has a CPU IRQ Counter which can be used for raster effects.

The "compression" is because it would take alot more memory if you stored map data differently, like per 16x16 tile. This has nothing to do with disk transfer. It has more to do with the limited amount of PRG-RAM, and maybe to some extent the limited Disk capacity.

The BS-Zelda remake stores map data differently and takes up a whole lot more memory than the original. But they had alot more memory to work with.
Re: Zelda FDS (and general disk-related questions)
by on (#98585)
Thanks for the reply.

I get compression generally, but I was curious if there was anything disk-specific about Zelda's approach. In particular, I was thinking of this reply by tepples in an older thread regarding limited access to a disk's data.

In the same thread, qbradq calls Zelda's compression both 'extreme' and 'painful,' and was wondering if it was related to disk vs. cart constraints (seeing as the latter used MMC1/SNROM).

Is the mirroring switchable on the fly, i.e. when Link scrolls the screen vertically vs. horizontally?
Re: Zelda FDS (and general disk-related questions)
by on (#98600)
It's not "disk specific". It has more to do with how much PRG-RAM there was. With everything that needed to fit into that 32K, compressing the overworld and underworld in the way that they did was probably necessary. Keep in mind the cartridge version is a port. So just because it has free space doesn't mean they needed to use it all.

LoZ loads (after you start playing) whenever you switch "maps". Meaning movement from the overworld to the underworld. So it has to fit the entire overworld (16x8 screens) into whatever limited partition of the 32K PRG-RAM they had allocated for it. The way they chose to compress was as you probably know, having 1 byte per vertical strip for 16 bytes per screen making up the physical map. But there is still other screen data information, all of which you multiply by 128 (128 overworld screens) to get just how many bytes that map data take up. And remember you still need memory for the program code, including the sound engine.

I think the underworld was compressed even more by each dungeon room's physical shape being 1 single byte. They really did a good job with what they had I think.

And yes, mirroring is switchable anytime, just like other mappers including MMC1.
Re: Zelda FDS (and general disk-related questions)
by on (#98694)
I wasn't aware of the vertical strips, but I found a post where tepples references them (16x176 pixels each).
Re: Zelda FDS (and general disk-related questions)
by on (#98712)
I can't comment on anything FDS specific, but based on my experience with the NES version (which uses the exact same format as I understand it), I could explain the data format in excruciating detail.

There are three "worlds" in the game. The overworld, and two dungeon worlds. All nine dungeons are crammed into two "worlds" the same size as the overworld (check it out). (Correction: There are five maps. The second quest has its own pair of dungeon maps.) Each map has a number of "screen layouts" defined. These layouts are constructed from predefined vertical strips. The layouts are arranged, and heavily reused, to make the maps. Even the overworld re-uses a number of layouts.

Then, even the vertical strips are compressed. There is basically a stream of tile numbers, where each tile number is specified by the lower six bits. If bit six is set, the tile is doubled (sort of an RLE-ish thing). Bit seven marks the beginning of each vertical strip. But the strips overlap. The bottom half of one strip may use the same tiles as the top half of another. If you were to modify one, the other would be affected too.

But none of this stuff seems too out of the ordinary, be it for FDS or a cartridge.
Re: Zelda FDS (and general disk-related questions)
by on (#98731)
Snarfblam, thanks! I'm looking for excruciating details. :D

Let me see if I'm clear so far: each screen, whether overworld or dungeon, is comprised of 16 vertical strips of 16x176 pixels. Since Zelda uses 8x16 tiles, I assume metatiles are 16x16, meaning each strip is 11 metatiles tall. Each strip is encoded in a single byte, with bits 0-6 defining tile numbers and bit 7 acting as a flag to designate a new strip.

When you say 'predefined vertical strips,' do you mean that the basic background elements are 'hardcoded,' so levels may only be built using the existing strips? Or can someone with knowledge of the compression build their own strips (and thus, levels)? I know there are various ROM/ASM hacks of Zelda, but I don't know what techniques they use.

Would you mind providing an example of the compression/tile data? I'm still not clear how a strip can be defined by just seven bits (and the wraparound data seems really interesting). Does the compression put an upper limit on the number of terrain features (e.g. bushes, blocks, gravestones) within a single strip?

I'm asking all this because I worked through a lot of Super Mario's engine (mostly with doppelganger's assistance) and since Zelda was created by the same team at the same time, I was curious what techniques were shared/differed between games. I'm also looking at what type of changes (if any) had to be made in the transition from disk to cartridge. Fascinating stuff.
Re: Zelda FDS (and general disk-related questions)
by on (#98751)
I'd have gone into more detail, but I thought you were really after info about FDS hardware.

Dungeon layouts are smaller than overworld layouts. You're right, both use 16x16 metatiles. Overworld layouts are 16x11, dungeons are 12x7 (the walls and doors are handled separately).

Like I said, the strips are stored as a stream of tiles. Suppose you have two strips, one with mountain at the top and the rest is empty space, and then another that is mountain at the bottom and empty space up top. This is what your data stream would look like.

Code:
For demonstration, assume the empty metatile is 0 and mountain is 1.
Bits 0-5 identify a metatile between 0 and $3F
Bit 6 indicates tile is repeated (doubled)
Bit 7 indicates a column starts at this byte

Data   Metatile    Doubled   Start of column
----   --------    -------   ---------------
C1     01          X         X
C0     00          X         X
40     00          X
40     00          X
40     00          X
00     00         
41     01          X

This defines two columns composed of these metatiles:
1: 01 01 00 00 00 00 00 00 00 00 00
2: 00 00 00 00 00 00 00 00 00 01 01

The game actually has sixteen pointers into the column data: one for columns $00-$0F, one for $10-$1F, and so on. This way you don't have to walk the entire stream to find each column. Because there are actually only about 140 columns, they put 10 ($A) in each group, so if you list all the unique column numbers in hex, it would look like decimal. $20 is after $19. If you use $1A you'll get the same column as $20, $1B give you the same column as $21, so on. When they made the game, I'm sure they would have just stuck with the "canonical" column numbers.

As far as if you wanted to add your own new columns, they are really pretty poorly compressed. I re-compressed them by hand and got them down to 60%-70% of their original size, giving me room to insert a bunch of new columns without using any new ROM space, but I somehow corrupted the ROM in the process and never bothered making a second attempt.

I'm actually lending a helping hand to Infidelity, who is working on a pretty extensive hack of the game (NES version). He gutted the screen data and related code and replaced it with his own, giving himself complete freedom with screen layout. That's really the way to go if you want to extensively rework a game, but it's quite a bit of effort.
Re: Zelda FDS (and general disk-related questions)
by on (#98775)
OK, I'm still not clear how that data stream translates to the two resulting columns. We have seven bytes of data (C1, C0, 40, 40, 40, 00, 01) that will output two 11-metatile columns, or 22 metatiles total. Does each byte, at best, define two metatiles? Even with doubling, I don't see how seven bytes can fill in all the needed metatiles.

If the start of each column is defined first, how is the byte block parsed after that? One at a time? Alternating? How does it work for an entire screenful of data?

The pointers and column data make sense. Are those columns for both overworld and dungeons? Meaning, are there just around 140 unique strips that make up the entire game?

Thanks again. This is all really helpful.
Re: Zelda FDS (and general disk-related questions)
by on (#98785)
Maybe I should walk through how the game decodes the strips. I'll expand on the sample above. A screen layout consists of 16 column IDs. Imagine the first column ID is $01. The game takes the high nibble, and uses that as an index to a pointer table. Each pointer in the table references a group of up to sixteen columns (in reality, each group has ten at most). Our high nibble is 0, so we follow the first pointer in the table, which takes us to this data:

Code:
Data: C1 C0 40 40 00 C1 40 02 00 02 40 41

Byte   Metatile    Doubled   Start of column
----   --------    -------   ---------------
C1     01          X         X
C0     00          X         X
40     00          X
40     00          X
40     00          X
00     00         
C1     01          X         X
40     00          X
02     02         
00     00
02     02
40     00          X
41     01          X

Metatiles:
00 = Mountain
01 = Ground
02 = Bush


Now we take the low nibble, in our case, 1. This identifies which column in the group we want. Column 1 would be the second column (column 0 being the first, of course).

The game walks through the bytes, watching for bytes with the high bit set. Each byte with the high bit set marks the beginning of a column's data. So on the very first byte, the high bit is set. This is column 0. Not the one we want yet, so on to the next byte. The next byte has the high bit set. This is column 1. This is what we are looking for. Now it's time to decode a column. The first byte in the column is $C0. Bit five is set so it is doubled. The low six bits equal zero, so metatile 0 occurs twice (00 00). Next byte is $40. Again, doubled metatile 0 (00 00 00 00). The next two bytes are also $40, so two more doubled metatile 0's (00 00 00 00 00 00 00 00). Next byte is $00, so that's metatile 0, not doubled (00 00 00 00 00 00 00 00 00). Finally, $C1. Bit six is set, so it's doubled, and it's metatile 1: 00 00 00 00 00 00 00 00 00 01 01. Nine tiles of ground and two tiles of mountain.

Now, suppose we were looking for column $02 instead of column $01. We would start at the first byte, which has the high bit set. This is column $00. Move on the the second byte, which also has high bit set, which marks column $01. Not what we're looking for so on to the next byte: $40. The high bit is not set so we keep looking until we find a byte with the high bit set. Eventually we come upon the seventh byte: $C1. The high bit is set, thus we have column $03, which is what we want. Now we can decode eleven tiles, which will give us 01 01 00 00 02 00 02 00 00 01 01, or mountain at the top and bottom, with two bushes in between.

So, in the example data, column $00 uses bytes $0 - $5, column $01 uses bytes $1 - $6, and column $2 uses bytes $6 - $C. Twelve bytes defining three eleven-tile columns.

Hopefully that clears up how the columns work. And no, the overworld columns are not shared with the dungeon columns (that would be a problem since they are different sizes). Although the overworld and dungeons work the same exact way, all of their data is completely separate.