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
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.
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.
[removed]
[removed]
[removed]
All graphical information was stored in 16KiB of memory. This area of memory was divided into sections.
The first was a pattern table. The table was 8KiB in size and divided into 8×8 tiles. The table was usually split vertically, half for backgrounds, half for sprites. A pixel was stored in 4 bits, meaning the NES could display 16 colors. The pattern table only stored the lower 2 bits of each pixel. The other two bits were looked up in one of the other two tables.
The next table was the “name table”, of which there were typically 2 but up to 4. A name table is 960 bytes. This corresponds to a 32×30 grid of 8×8 tiles from the pattern table. The top and bottom 8 scanlines weren’t rendered on a CRT television, so that memory could be used to hold game data. You can see the effect along the top and bottom edges of Tecmo Super Bowl.
A name table has an attribute table 64 bytes in size that maps the upper two bits of every pixel to the lower two bits in the pattern table.
There was also a sprite table, or sprite RAM, that used 4 bytes to map the x and y location, upper color bits, the tile index (meaning the x and y location is relative to a given tile in the background), horizontal or vertical flip, and foreground/background. This table was 256 bytes so there could be 64 sprites on the screen at any given time.
There were two color pallets of 16 colors each, and the color bytes split between the pattern table and the name or sprite tables indexed into these pallets. One was for the background, the other for the sprites. These two 16 color pallets mapped into a 256 color pallet built into the hardware.
If you don’t understand all that, don’t fret. The whole thing works out like a relational database, where one table maps into another. The data is down to packed bits, so while you have addressable bytes, you had to mask and pick out bits and combine them in registers to get complete values out. The hardware was built around all of this and could do it for you, which is how the system was fast enough to actually render this much data onto a CRT. A cartridge was ROM that basically plugged into this memory space, so the data was already laid out and good to go, the video hardware mapped right onto the cartridge data.
Short version: *insanely* talented coders doing everything they could to maximize space. I’m gonna blow your mind right now. Take a look at the [intro to SMB1.](https://cdn02.nintendo-europe.com/media/images/10_share_images/games_15/virtual_console_nintendo_3ds_7/SI_3DSVC_SuperMarioBros.jpg) We’ll ignore for a moment the fact that that screenshot takes up more memory than the entire game did.
Anyway, take a real hard look at it. Check out everything – the bricks, Mario, the Goomba, the hill, the clouds, the bushes… the clouds, the bushes… *the clouds, the bushes*…
Yeah. They’re the same icon, just with a new color palette swapped in. All sorts of little tricks like that in old-school programming.
And it’s not totally dead either! There’s still a (mostly European) subculture devoted to slick programming, called the [Demoscene](https://en.wikipedia.org/wiki/Demoscene). I’m gonna date myself here, but when I was a College Freshman I was introduced to a Demo called “[The Product](http://theproduct.de/)” – it’s a several minute long music video, all 3d generated graphics, made in under **64Kb**. I just downloaded it and checked – still runs on my fully updated Windows 10 machine, but I know for a while there it wasn’t playing nice with new computers so YMMV.
So coders are still out there that are capable of doing, frankly, ridiculous shit like that (even though that’s nearly 20 years old at this point, it’s still ongoing) — just they don’t *have* to anymore because it’s assumed most people will have reasonable stats on their computer. If everyone has 16 gigs of ram, who cares if you lose a couple kilobytes? Guys who are programming for efficiency, that’s who.
A lot of reused assets. If you look at the dungeons in the game they all look the same, but just rearranged and maybe with different colors. The different colors aren’t even separate files, they are changed programmatically.
For that matter there’s other tricks like using black space. The areas that are black in the game are actually just the absence of any assets being loaded.
For both Zelda and Final Fantasy they even reused sprites for enemies. So you could have a variety of enemies that just have maybe the color changed about them to differentiate them.
[removed]
Old games are like storing a brick and the plan of the house, then tell the processor to copy the brick according to the plan to build the house. Most of the size gain is because the graphics are done using repeating patterns and only storing a little square and telling the processor to repeat it.
Modern games are like storing the whole house and its 500 000 bricks. Often even the parts of the bricks you never see because they don’t care about size anymore.
Latest Answers