只为找到最好的打包方案

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

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

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

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

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

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

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

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

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

　　Dave Baggett 的回答

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

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

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

　　英文原文：How did game developers pack entire games into so little memory twenty five years ago?

这里有新鲜出炉的精品教程，程序狗速度看过来！

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

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

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

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

　　问题描述