25年前，开发者如何将游戏塞进那么小的内存中？

25年前，开发者是如何将游戏塞进那么小的内存中的？Quora上，这个问题获得了50万人的阅览，Dave Baggett对问题的回答也获得了六千多的点赞，其中不乏游戏大师。 

问题描述

家庭游戏系统软件采用了64K~128K的磁卡（cartridge），然而却能够提供玩好几个小时的各式各样的图形、精灵鬼怪和声音。游戏系统好像要提供大量的功能（功能性的函数、库、硬件加速和图形指令等等）似的，大量的图片、音乐和音效、动画效果、游戏算法能放入如此小的存储空间中，是多么得令人吃惊，更别提是25年前！

上面提到的存储空间大小目前看来也就等同于一个采用中等分辨率压缩（moderate-resolution compressed）的JPEG文件——一张图片而已。我十分好奇，在那个年代软件开发究竟是怎么一回事。我坚信在当时，开发者肯定没有一个所谓编写开源软件的协作开发环境，更别提在那样一个软件开发能收获巨大经济回报的时代。

我十分好奇，那个年代的开发者究竟基于哪些知识、技术、想法或者洞察力完成了这样的开发。有没有可能一些想法已经丢失或者没有被记录下来？曾经的电子游戏种类如此丰富，并且使数以百万的人花费数百小时在上面获得快乐，更别提游戏开发采用了这样高效的方式——这显然是一项壮举。这种效率让我想起了录制音乐demo。结合这些，我想提出下列的问题：如何更好理解计算机科学的原则和技术的使用方式，比如，如何将64K的demo进行编码。

这个问题的重点是那个时候的专业技能：那时的开发者为何如此成功？他们使用了哪些已经失传的技术、解决办法，或者算法技巧？

Dave Baggett的回答

下面是20世纪90年代末的一个相关轶事。当时，我和Andy Gavin共同为PS1编写游戏“古惑狼”(Crash Bandicoot)。

《古惑狼》游戏封面

在当时，RAM依然是最主要的问题。PS1只有2MB的RAM，然而我们不得不做一些疯狂的事情使游戏适配硬件。我们的游戏数据大约有10MB大小，所以我们不得不进行动态的分页输入输出（paged in and out dynamically），虽然加载滞后帧速率就会下降到30Hz，但是我们并没有任何故障。

之所以能成功运行，是因为Andy写了一个令人难以置信的分页系统，可以将64K数据页进行交换，从而作为古惑狼这款游戏的数据遍历水平。这就是当时的 “全栈”能力，在这个分页系统中，运行了上至高级内存管理，下至操作码级别的直接内存访问系统（DMA）的全部代码。Andy甚至控制了CD-ROM上字节的物理布局，这样一来，即使CD-ROM的速率是300KB/s，PS1还是能在游戏执行到某个位置时加载到相应的数据。

我当时主要负责编写打包工具，这个工具的功能是将资源文件，比如声音、图形图像、小动物的声音控制代码（译者注：lisp control code）等打包为64K的数据分页，塞进Andy的系统当中去。（顺带一提，这个问题——将任意大小的对象打包成固定大小的数据分页，生产数据包——是一个NP完全问题，所以看起来在合理的时间或者线性复杂度下得到最优解是不可能的。）

然而有些时候算法并不合适，我的打包工具采用了各种各样的算法（如最先适配、最好适配(first-fit,best-fit)等等），只为找到最好的打包方案，包括使用随机搜索类似于Simulated annealing中用到的梯度下降的过程。基本上，我写了一大堆不同的打包策略，一一尝试，并择优选择。

像那样使用随机指导搜索（a random guided search）的问题在于，你永远不知道你能否再次得到同样的结果。有些古惑狼的关卡只能靠“碰碰运气”来进行随机打包，并放入最大允许页数（我印象中是21）。这意味着，一旦你将这个关卡打包，可能更改了一个乌龟的代码，就永远不会再找到这个21-分页的数据包了。有几次，一个艺术家修改一些内容，就会毁掉现行的分页计数，所以我们不得不半随机似的改变其他内容，直到打包器能再次找到可用的数据包。并且我还要在凌晨3点给这个倔强的艺术家解释清楚。

现在回忆起来，到目前为止最好的部分，也是当时最糟糕的部分，正是使核心的C/汇编代码（C/assembly code）适配。那时距离“最终测试版”的发版期限没有几天了，而这几天是我们抓住假期发行游戏的最好机会，在此之前，我们失去了整整一年的时间。当时我们正在将语义上相同，而语法上具有不同表现（semantically identical but syntactically different manifestations）的C语言代码进行随机排列（permute），以此希望编译器能够生成200字节、125字节、50字节然后是小于8字节的代码。

作为当时排列所采用的方法“for (i=0; i < x; i++)”——如果我们采用上面用到的变量，并使用while循环来重写这段方法，以用作他用，那么会发生什么呢？这是我们尝尽各种一般方法——比如像将数据塞进指针的最低两位（这个方法只能在R3000上生效，因为所有的地址都是4字节对齐的（4-byte aligned））——之后的解决之道。

最终，古惑狼成功了的适配了PS1的内容，还多出了4字节的空闲空间。是的，2097152之外的4字节。那真是美好时光啊~