With some basic Googling It looks like that the max size was around 512 KB. How is this even possible to fit games of this size onto such little memory? What is this magic?
In: Technology
[removed]
While some of these explanations are alright, it doesn’t explain Final Fantasy, Dragon Quest, or a few other larger NES games.
Normal NES carts are limited to a ROM of 40KB. For small games like Super Mario Bros., this is pretty easy by just reusing the same pictures. But what if you wanted to make something *bigger* that needed *more storage*?
Bank switching.
With bank switching, the cartridge has a larger storage than 40KB. This larger size is divided into 40KB chunks, and when something outside of the chunk currently being read is needed, the cartridge switches to another chunk and loads that information for the system to read.
Upsides are great, with more complex games!
Downside is that the cartridges are more expensive to produce.
EDIT: Grammar.
EDIT 2:
Man I should have read the OP more closely.
The maximum storage size for an NES cartridge was 1MB.
Along with this, programming techniques to save space were used. Reusing the same graphics information, programming directly in assembly to optimize space saving, and much more.
It’s a trick called indexing. I think the best way to explain is with an example.
I have a very long number. Specifically, the number is 55555555522333333344444776666677.
Now, I could represent the number like that, or I could say
9-5,2-2,7-3,5-4,7-7,5-6,2-7
This takes up a bit less space (33 vs 28 characters). And so long as you knew that the commas separate this into a list, and that the hyphen separates the number of occurrences from the value of those occurrences, you would be able to take this list and get the original number. All I have to do is tell you (the NES) ahead of time to interpret whatever info I give you in this manner, so that when I put the shortened version on the cartridge, you can get the original no matter what it is.
But 33 vs 28 isn’t a lot of saved space, right? 5 characters. Big deal. That’s only 15% saved.
But in fact, that was actually pretty poor compression. We can go deeper.
If you look at all the numbers, both for the number of occurrences and for the value of the digit, you’ll notice that each of them is single digit. So we can actually shorten it to
95227354775627
Just by slightly altering the rule we give you – that every two digits is a pair where the first is the number of occurrences and the second is the value. Since this eliminates all commas and hyphens, this shortens the first compression by an additional 50%, for a total of 57% overall.
But we can get even more aggressive. You see, up until now, each character has taken up an entire byte (this is how strings were encoded as of 1981’s 8-bit “Extended ASCII”, which doubled the number of available characters from 1963’s original 7-bit ASCII encoding). So far we’ve been focusing on just reducing the number of bytes. However, when you get into what the NES sees, our starting number looks more like this (represented in hexadecimal):
35353535353535353532323333333333333334343434343737373737373736363636363737
Our first compression looks like this:
392D352C322D322C372D332C352D342C372D372C352D352C322D272C
And our second compression looks like:
3935323237333534373735363237
You’ve probably already noticed that in the uncompressed number and the second compression, every other digit is 3. That’s because the digits 0-9 are stored in the values 30-39 in ASCII. If you look at that and say, “can’t we just get rid of those alternating 3s?” You’d be 100% correct, and you’re catching on to how this works.
In hexadecimal, each written character takes up 4 bits, not 8 – so a pair of two makes a full bit. Each set of 4 bits can have a value of 0 to 15 (when it goes above 9, it switches to letters, where A is 10, B is 11, up to F at 15).
Since each digit is under 15, we can effectively cut the length in half one more time. What we end up with looks identical to the second compression
95227354775627
Except we know under the hood that it requires half as much information. To prove it, we can convert this back from hexadecimal to ASCII and get:
ò”sTwV’
And our total compression is just shy of 79% – basically, 5 times as efficient.
=============================
Now, this has all been about compression, but the method I mentioned was *indexing*. Compression is the basic idea behind indexing. However, indexing ups the ante – it’s the next level.
To explain indexing, the best example I can give is showing approximately how a game like Zelda is actually put together.
Let’s start with the lowest level: tiles. In NES architecture, a tile is 8 pixels wide by 8 pixels tall, for a total of 256 pixels.
Now, if you’ve ever worked with a color picker in a program like Photoshop or GIMP, you might be aware that modern red-green-blue digital coloring is represented in hexadecimal! FFFFFF is white, 000000 is black, FF0000 is red, 00FF00 is green, 0000FF is blue, and any values in between FF and 00 can be mixed to make a total of 256^3, or 16,777,216, different colors. If you used a computer in in the late 90s or early 2000s, you might recall the computer saying it switched its color mode to “millions of colors” upon entering or exiting a game. This is the color mode it was talking about.
If you’ve been doing the math, a color system that represents white as FFFFFF in hexadecimal is taking up 3 bytes for every single pixel. Multiply by the 256 pixels in our tile, and it’s taken up 3/4 of a kilobyte. If the NES screen size is 256×240 pixels, or 32×30 tiles, then a single screen is 720 kilobytes – it doesn’t even fit on the cartridge. One single screen!
However, the NES can’t display 16 million different potential colors. It can’t even display the 32 thousand colors that the gameboy color was capable of with 15-bit rgb. No, actually, the NES had a curated list of 54 usable colors (if someone wants to lawyer me, it’s 432, but for reasons I won’t go into, those extra colors come with some deal breaking strings attached and weren’t useful very often. They’re also not listed out – they’re potential tints of the base 54 colors).
This list of colors is stored on the console itself – the game gets it for free. However, even if we did have to store it on the cartridge, we’d be sacrificing 1/20th of a a kilobyte in order to reduce the color data by 75% (3 bytes vs 6 bits). Why 6 bits? Because a 6-bit number holds values between 0 and 63, making it the smallest number of bits that can reference 54 different colors.
This is what indexing is – by listing out a number of specific items we expect to use and ignoring all the possible combinations we will never use, we can significantly improve how efficient it is to call on the one we need. In this case, we don’t need 16 million different colors, we only need 54. So rather than make each pixel choose from 16 million, we spend a bit of space giving it a list of just 54 to choose from. That list is our “index”.
But we can keep going. Because as you probably know, NES sprites are actually 16×16 pixels. This is because a sprite is actually a tilemap – a 2×2 group of tiles. This serves two purposes – first, since certain 8×8 tiles get reused between 16×16 sprites (especially on the background layer where terrain repeats frequently) a fair amount of data is saved there, though I’d have to go through all the sprites one by one to tell you how much it saves. The second is that, because the choice of palaette is tied to the sprite and not the tile, we eliminate 3/4 of the number of times we have to specify which palette we’re using.
Palettes, you say? Yes. In fact, each pixel does not pick directly from the NES list of 54 colors. The game cartridge defines a list of palettes, containing 4 colors each, that sprites can choose to apply. This means that, by spending a couple bits at the start of each sprite to specify a palette, each pixel only needs 2 bits to take its pick of the 4 colors. This brings the size of each tile down to 64 bytes. This also means that each sprite is just barely over 256 bytes. Even less if it uses the same tile multiple times, like the bridges and raft launch sprites, which are the same two tiles repeated on the left and right side.
Now we’re at sprites. The overworld of Zelda 1 seems to have 50 possible sprites as far as I can tell, meaning as it often winds up, we need 6 bits to reference them with. So for the purposes of the overworld, it’s .75 bytes times the total size of the overworld.
Well, for each board, we’ve got 32 tiles or 16 sprites across, and 28 tiles or 14 sprites high. Wait, 28? We had 30 earlier, what gives? Well, remember that the top 16 pixels are our HUD and don’t contribute to the size of the overworld.
16 by 14 sprites is 224 total background sprites per board. Multiply by our .75 bytes per sprite, and each board now only takes up 168 bytes.
The overworld itself is 8 maps high and 16 wide, for a total of 128 boards. Multiply that by 168 bytes per board, and our entire overworld fits comfortably within about 4% of our cartridge. Once you add our palettes, tiles and tilemaps, maybe it’s closer to 6 or 7%. But even if that’s a bit conservative, the indexing I’ve listed here is definitely not all nintendo did. If it were me, I’d index all water sprites as a single sprite, since the coast can be derived logically from surrounding squares. If a similar thing could be done with cliffs, the index could be reduced from 6 bits to 5. And obviously, not every board is custom. Many have similar baseline features that might be called on and added to after the fact.
Either way, I didn’t intend to spend hours gushing about this. I’m going to let both our brains rest like the freshly seared steaks that they are, and hope no one notices that this explanation doesn’t quite qualify as an ELI5 simply for sheer length.
Latest Answers