Ретроспектива розробки Crash Bandicoot, або як розробники упаковували цілі гри в 2MB RAM

Ось вам анекдот з кінця 90-их. Я (Dave Baggett) був одним з двох програмістів (разом з Andy Gavin), розробляють Crash Bandicoot для PlayStation 1.



Оперативна пам'ять була головною проблемою навіть у ті часи. У PS1 було всього 2MB RAM, і нам доводилося робити божевільні речі, щоб вмістити в них гру. У нас були рівні, містять більше 10MB чистих даних, і ці 10 мегабайт повинні були посторінково завантажуватися і вивантажуватися в пам'ять динамічно, без будь-яких видимих затримок для гравця, при фреймрейті в 30 кадрів в секунду.

В основному це працювало за рахунок того, що Andy написав потрясну систему підкачки, яка повинна була завантажувати і вивантажувати сторінки в пам'ять розміром 64K, по мірі того як Crash проходив рівень. Ця система була справжнім витвором мистецтва, яка задіяла весь діапазон доступних інструментів, починаючи від высокоуровневного менеджменту пам'яттю, закінчуючи прямою роботою з пам'яттю і програмуванням в опкодах. Andy також довелося контролювати розташування байтів на CD-ROM, щоб навіть при швидкості 300KB/сек PS1 могла встигнути завантажити дані для усіх деталей рівня до того часу як Crash добирався до нього.

Я ж написав пакувальник, який брав ресурси гри — звуки, арт код на lisp для управління істотами, і т. д. і упаковував їх в сторінки по 64К для системи підкачки, написаної Andy. (Між іншим, завдання упаковки сторінки фіксованого розміру набору довільних розмірів даних — NP-повна, і, майже не піддається розв'язанню за полиномиальное, тобто скільки-небудь прийнятний час. Задача про рюкзак.).

Деякі з рівнів ледь вміщалися, і мій пакувальник використав цілий набір алгоритмів (first-fit, best-fit, і т. д.), щоб пробувати отримати наилучшый варіант упаковки, включаючи стохастичний пошук, схожий на процес градієнтного спуску, використовуваний в алгоритм імітації відпалу. По суті, у мене була ціла купа різних стратегій упаковки, і я пробував їх всі і використовував найкращий отриманий результат.

Проблема використання випадкового спрямованого пошуку полягала в тому, що ти ніколи не міг бути впевнений, що зможеш ще раз отримати такий же результат. Деякі рівні Crash Bandicoot вміщалися в максимально допустиму кількість сторінок 21, якщо не помиляюся) лише з-за того, що упаковщику пощастило і він знайшов цей варіант. Так само, це означало, що як тільки ти отримав упакований рівень, ти міг поміняти код для якої-небудь черепашки і вже ніколи не отримати упаковку, помещающуюся в 21 сторінку. Були випадки, коли дизайнер хотів що-небудь поміняти і це роздувало кількість сторінок, і нам доводилося міняти що-небудь у інших, майже випадкових місцях, до тих пір, поки пакувальник знову не знайде робочий варіант. Спробуй пояснити це дратівливим дизайнерам в 3 години ранку :)

Самим кращим епізодом цієї ретроспективи і найгіршим періодом часу тоді була упаковка коду ядра на З і асемблері. У нас було буквально пару днів щоб выпусть «gold master» версію — наш останній шанс встигнути до сезону свят, до того, як ми втратимо ще один рік. І ми сиділи, переставляючи C код в семантично однакові, але синтаксично різні конструкції, щоб змусити компілятор видати код, який був на 200, 125, 50, а потім і 8 байт менше. Переставляли, наприклад: «for (i=0; i < x; i++)» — а давайте спробуємо переписати в while-цикл і використовуємо для ітерації змінну, яка вже використовувалася десь раніше? Це все робилося вже після того як ми перепробували стандартні трюки, такі як приміщення даних у два останніх біта вказівника (і це працювало тільки завдяки тому, що адреси R3000 були вирівняні по 4 байти).

У кінцевому рахунку, Crash вмістився в пам'ять PS1, і навіть залишилося вільних 4 байта! Так, 4 байта з 2097152. Удачі.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.