On Quora a games enthusiast asked the question “How did game developers pack entire games into so little memory twenty five years ago?” wondering how game developers could fit games in to the space a standard JPEG fits in nowadays. Dave Baggett, employee #1 at Naughty Dog, responded. He highlighted how Naughty Dog fit the whole of Crash Bandicoot into 2MB of RAM, leaving spare just 4 bytes.
How did game developers pack entire games into so little memory twenty five years ago?
That amount of space is equivalent to that of a single moderate-resolution compressed JPEG file – just one image. I’m wondering what development was like back then. They certainly didn’t write open software back then in a collaborative environment, as it was a very competitive space I’m sure with great financial reward.
But I’m wondering what kinds of expertise, techniques, ideas or insights might have been used back then to achieve that. Is it possible that some ideas may have been lost or gone unwritten? With such variety in game play it’s certainly a feat to be able to entertain millions of people for hundreds of hours and to do so in such an efficient way. The efficiency reminds me of the demo scene. Coupled to that I may ask a followup question on how to better understand the computer science principles and techniques used to, for example, encode 64k intros and demos.
But the primary focus of this question is on the expertise of the past: how the developers were so successful, a lost or hidden technique that they may have used, compromises or algorithmic tricks.
Dave Baggett’s Response
Here’s a related anecdote from the late 1990s. I was one of the two programers (along with Andy Gavin) who wrote Crash Bandicoot for the PlayStation 1.
RAM was still a major issue even then. The PS1 had 2MB of RAM, and we had to do crazy things to get the game to fit. We had levels with over 10MB of data in them, and this had to be paged in and out dynamically, without any “hitches”—loading lags where the frame rate would drop below 30 Hz.
It mainly worked because Andy wrote an incredible paging system that would swap in and out 64K data pages as Crash traversed the level. This was a “full stack” tour de force, in that it ran the gamut from high-level memory management to opcode-level DMA coding. Andy even controlled the physical layout of bytes on the CD-ROM disk so that—even at 300KB/sec—the PS1 could load the data for each piece of a given level by the time Crash ended up there.
I wrote the packer tool that took the resources—sounds, art, lisp control code for critters, etc.—and packed them into 64K pages for Andy’s system. (Incidentally, this problem—producing the ideal packing into fixed-sized pages of a set of arbitrarily-sized objects—is NP-complete, and therefore likely impossible to solve optimally in polynomial—i.e., reasonable—time.)
Some levels barely fit, and my packer used a variety of algorithms (first-fit, best-fit, etc.) to try to find the best packing, including a stochastic search akin to the gradient descent process used in. Basically, I had a whole bunch of different packing strategies, and would try them all and use the best result.
The problem with using a random guided search like that, though, is that you never know if you’re going to get the same result again. Some Crash levels fit into the maximum allowed number of pages (I think it was 21) only by virtue of the stochastic packer “getting lucky”. This meant that once you had the level packed, you might change the code for a turtle and never be able to find a 21-page packing again. There were times when one of the artists would want to change something, and it would blow out the page count, and we’d have to change other stuff semi-randomly until the packer again found a packing that worked. Try explaining this to a crabby artist at 3 in the morning. 🙂
By far the best part in retrospect—and the worst part at the time—was getting the core C/assembly code to fit. We were literally days away from the drop-dead date for the “gold master”—our last chance to make the holiday season before we lost the entire year—and we were randomly permuting C code into semantically identical but syntactically different manifestations to get the compiler to produce code that was 200, 125, 50, then 8 bytes smaller. Permuting as in, ”
for (i=0; i < x; i++)
Ultimately Crash fit into the PS1’s memory with 4 bytes to spare. Yes, 4 bytes out of 2097152. Good times.