How Naughty Dog Fit Crash Bandicoot into 2MB of RAM on the PS1

“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 Simulated annealing. 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++)

“—what happens if we rewrite that as a while loop using a variable we already used above for something else? This was after we’d already exhausted the usual tricks of, e.g., stuffing data into the lower two bits of pointers (which only works because all addresses on the R3000 were 4-byte aligned).

Ultimately Crash fit into the PS1’s memory with 4 bytes to spare. Yes, 4 bytes out of 2097152. Good times.”

The Last Of Us: Review

Hiding behind a desk you frantically attempt to craft a weapon that can increase your chances for what is to come. You listen intently for what danger lies in the dark. Confronting your enemies won’t always work. Sometimes you just have to accept the fact that survival is the only real goal. The Last of Us is a game about survival, friendship, and the acceptance that in this phenomenal  universe there is nothing either good or bad. The story of  The Last of Us is a huge departure from Naughty Dog’s previous titles.

Where the Uncharted serious is known for its amazing set pieces, action sequences, witty dialogue, and Raiders of The Lost Ark type characters-TLOU goes for the complete opposite. The story is paced deliberately and slowly. The world is extremely grim at times with small segments of humor but it is constantly overshadowed by the characters of the game. Who are basically only in it for one thing; Themselves. TLOU spans about a year traveling across the U.S. Joel and Ellie the main characters of the game are fantastic contrast to each other. Joel only talks when he really needs to. Ellie can’t seem to stop talking. She is a curious and brash kid who was born into the horrible world.  Ellie meets Joel and and they soon find themselves on an expedition across vast dangerous lands.

The game-play in TLOU is truly a masterpiece. Never has a game felt so right while being so incredibly lopsided. The infected in the game can kill you in seconds. Every decision you make is vital to your survival. Where most games give you a certain sense of invulnerability. TLOU forces you to quickly react to a situation or meet a gruesome and gory death. Bullets are  scarce and you have to manage your resources. The suspense I felt from every encounter was nothing I’ve felt in a long time. The sound in this game incredible. Every gunshot ripped through the darkness of the world with an authentic punch.

Ambiance in the environment and sound effects for things such as footsteps was top notch.  Listening for clickers(type of infected in the game) or bandits was stressful and a legitimate real tactic, I’ve never seen done so effectively before. When game-play mechanics revolve around the sound design you know you have something special. The voice actors did an incredible job and you actually care about these characters. Not to mention the downright mind blowing soundtrack. The story of The Last of us draws you in, the game-play continually impresses over and over, and the characters stay with you long after your done. All we can do now is hope the series continues in some form on PS4.