25年前，開發者如何將游戲塞進內存？
Crash Bandicoot 游戲封面
英文原文：How did game developers pack entire games into so little memory twenty five years ago？
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 磁盤上字節的物理布局，這樣一來，即使磁盤的速率是 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 字節。那真是美好時光啊。
---------------------------------------------------------
如果您發現這篇譯文的任何問題，可隨時與杰微刊聯系。我們水平有限，但理想高遠。杰微刊旨在分享優質的內容。杰微刊也同樣期待理想的您對這個世界的貢獻。歡迎任何目的的聯系。杰微刊的有償投稿郵箱是：weikan@jointforce.com。我們的 QQ 是：3272840549。
譯者：杰微刊--張帆