Retrospective development of Crash Bandicoot, or how the developers packed the whole game in 2MB RAM
Here's a joke from the late 90s. I (Dave Baggett) was one of two programmers (along with Andy Gavin) developing Crash Bandicoot for the PlayStation 1.
RAM was a major problem even in those days. PS1 had only 2MB of RAM, and we had to do crazy things to fit the game. We had levels containing more than 10MB of clean data, and these 10 megabytes had to be loaded page by page and unloaded into memory dynamically, without any visible delays for the player, with frame rates of 30 frames per second.
This basically worked by the fact that Andy wrote an awesome swap system, which was supposed to load and unload pages into 64K memory as Crash passed the level. This system was a true work of art, involving the entire range of available tools, ranging from high-level memory management, ending with direct work with memory and programming in opcodes. Andy also had to control the location of the bytes on the CD-ROM so that even at a speed of 300KB / s, the PS1 could have time to load the data for all the details of the level by the time Crash reached it.
')
I wrote a packer who took the game’s resources — sounds, art, lisp code to control creatures, and so on. and pack them into 64K pages for the swap system written by Andy. (By the way, the task of packing into fixed-size pages of a set of arbitrary data sizes is NP-complete, and almost impossible to solve in polynomial, that is, whatever acceptable time. Knapsack problem. ).
Some of the levels barely fit, and my packer used a whole set of algorithms (first-fit, best-fit, etc.) to try to get the best packaging option, including stochastic search, similar to the gradient descent process used in the simulation algorithm annealing. Essentially, I had a whole bunch of different packaging strategies, and I tried them all and used the best result.
The problem with using random directional search was that you could never be sure that you could get exactly the same result again. Some levels of Crash Bandicoot fit into the maximum allowed number of pages (21, if I'm not mistaken) just because the packer was lucky and he found this option. Also, this meant that as soon as you received a packaged level, you could change the code for some turtle and never get a package that fits into 21 pages. There were cases when the designer wanted to change something and it inflated the number of pages, and we had to change something in other, almost random, places, until the packer finds a working version again. Try to explain this to irritable designers at 3 am :)
The best episode of this retrospective and the worst period of time was the packaging of the kernel code in C and assembler. We literally had a couple of days to release the “gold master” version - our last chance to hit the holiday season, before we lose another year. And we sat, rearranging the C code into semantically identical, but syntactically different constructions, to force the compiler to issue a code that was 200, 125, 50, and then 8 bytes less. Rearranged, for example: “for (i = 0; i <x; i ++)” - but let's try to rewrite it in a while loop and use the variable that was used somewhere before for iteration? This was all done after we had tried standard tricks, such as putting data into the last two bits of the pointer (and this only worked because the addresses of the R3000 were 4 byte aligned).
Ultimately, Crash fit into PS1 memory, and even 4 free bytes are left! Yes, 4 bytes from 2097152. Good luck.
RAM was a major problem even in those days. PS1 had only 2MB of RAM, and we had to do crazy things to fit the game. We had levels containing more than 10MB of clean data, and these 10 megabytes had to be loaded page by page and unloaded into memory dynamically, without any visible delays for the player, with frame rates of 30 frames per second.
This basically worked by the fact that Andy wrote an awesome swap system, which was supposed to load and unload pages into 64K memory as Crash passed the level. This system was a true work of art, involving the entire range of available tools, ranging from high-level memory management, ending with direct work with memory and programming in opcodes. Andy also had to control the location of the bytes on the CD-ROM so that even at a speed of 300KB / s, the PS1 could have time to load the data for all the details of the level by the time Crash reached it.
')
I wrote a packer who took the game’s resources — sounds, art, lisp code to control creatures, and so on. and pack them into 64K pages for the swap system written by Andy. (By the way, the task of packing into fixed-size pages of a set of arbitrary data sizes is NP-complete, and almost impossible to solve in polynomial, that is, whatever acceptable time. Knapsack problem. ).
Some of the levels barely fit, and my packer used a whole set of algorithms (first-fit, best-fit, etc.) to try to get the best packaging option, including stochastic search, similar to the gradient descent process used in the simulation algorithm annealing. Essentially, I had a whole bunch of different packaging strategies, and I tried them all and used the best result.
The problem with using random directional search was that you could never be sure that you could get exactly the same result again. Some levels of Crash Bandicoot fit into the maximum allowed number of pages (21, if I'm not mistaken) just because the packer was lucky and he found this option. Also, this meant that as soon as you received a packaged level, you could change the code for some turtle and never get a package that fits into 21 pages. There were cases when the designer wanted to change something and it inflated the number of pages, and we had to change something in other, almost random, places, until the packer finds a working version again. Try to explain this to irritable designers at 3 am :)
The best episode of this retrospective and the worst period of time was the packaging of the kernel code in C and assembler. We literally had a couple of days to release the “gold master” version - our last chance to hit the holiday season, before we lose another year. And we sat, rearranging the C code into semantically identical, but syntactically different constructions, to force the compiler to issue a code that was 200, 125, 50, and then 8 bytes less. Rearranged, for example: “for (i = 0; i <x; i ++)” - but let's try to rewrite it in a while loop and use the variable that was used somewhere before for iteration? This was all done after we had tried standard tricks, such as putting data into the last two bits of the pointer (and this only worked because the addresses of the R3000 were 4 byte aligned).
Ultimately, Crash fit into PS1 memory, and even 4 free bytes are left! Yes, 4 bytes from 2097152. Good luck.
Source: https://habr.com/ru/post/260637/
All Articles