DScraft - это адаптация убер-популярной компьютерной игры Minecraft для Nintendo DS. Хотя DScraft даже близко не так популярен, как оригинальная игра, ему всё равно удалось собрать большое комьюнити, которое существует и сегодня, а саму игру загрузили более 500.000 раз только с одного моего сервера. Мне нравится думать, что это хотя бы частично из-за реализации тех вещей, которые обычно не предполагались возможными на платформе. Вся разработка заняла примерно полтора месяца. В основном было две вещи, которые раньше заставляли людей думать, что Minecraft на DS почти невозможен: GPU консоли и нехватка памяти.

Для начала, так как у DS были очень ограниченные возможности рендеринга (2048 треугольников за кадр; для сравнения, средний компьютер может потянуть в сотни раз больше), для рендеринга достаточно большого мира могли потребоваться хорошо оптимизированные алгоритмы отсечения, чтобы отрисовывалась только видимая геометрия. Кроме этого у DS было всего 4 Мегабайта (основной) оперативной памяти. Если предполагать, что один блок будет занимать один байт (это разумное предположение), то после быстрых подсчётов любому станет очевидно, что даже маленький мир (128x128x128 блоков) отнимет половину оперативной памяти. Это, конечно же, ведёт к осознанию того, что если вы вообще хотите мир приемлемого размера, то вам придётся стримить этот мир из другого места, скорее всего с microSD карты в вашем флэш-картридже. К сожалению, стриминг данных довольно медленный, не говоря уже о записи. И, конечно же, процессор DS тоже очень слаб.

Эти две проблемы ведут к тому, что для хранения миров необходимо придумать подходящую структуру данных, с которой стриминг информации будет быстрым, при этом позволяя отсечению геометрии работать эффективно. Быстро стало очевидно, что для ускорения этих процессов блоки нужно группировать: использование трёхмерного массива для хранения загруженной части мира приводило бы к тому, что каждый раз после стриминга новой информации приходилось бы проходить через весь массив (так как весь мир в памяти приходилось бы перемещать в нужном направлении, чтобы освободить место для загруженных данных). Аналогично, проходить через каждый блок в алгоритме отсечения было бы неэффективно, когда такой медленный и точный алгоритм не нужен. Таким образом, мир стал разделён на «кластеры» блоков размером 4x4x4 (этот размер показался разумным, хотя можно было использовать и любой другой размер). После этого, в попытке сделать стриминг ещё безболезненнее, кластеры блоков были соединены в колонны. Основанием для этого было то, что поскольку высота мира фиксирована, а вертикальный стриминг не был обязателен, это убрало бы целое измерение из стриминга, делая его гораздо более эффективным. Потом эти колонны кластеров блоков (BCC, block cluster column) были сгруппированы в супер кластеры, которые по сути были 2D массивами, содержащими кучу BCC.

Стриминг

С этой структурой данных стриминг мира в память становится относительно безболезненным: учитывать движение игрока так же просто, как и перемещать BCC в супер кластерах, загружая при этом новые BCC с SD карты. Например, если игрок переместится на один BCC влево, то всё, что нужно сделать - это переместить содержимое супер кластера вправо и загрузить самую левую полосу BCC с SD карты. Перемещение содержимого супер кластера можно производить довольно быстро, поскольку супер кластер - это относительно небольшой массив. Остаётся только найти эффективный способ загрузки BCC.

Другое преимущество этой структуры данных в том, что с её помощью сжатие большого мира станет проще. По большей части данные, хранящиеся в файле мира Minecraft - это гигантский трёхмерный массив, каждая клетка которого представляет атрибуты блока. Благодаря тому, как структурированы миры, эти данные очень хорошо сжимаются; такой массив обязательно будет содержать большие участки одинаковых блоков (таких как воздух, земля, камень), и поэтому даже простой RLE алгоритм будет очень эффективным. Конечно, простое хранение мира в виде большого сжатого 3D массива затруднило бы чтение небольших частей по отдельности. Однако с нашей структурой данных возможно сжимать/декодировать BCC по отдельности, делая хранения мира в сжатом виде жизнеспособным вариантом. Однако, такой вариант добавит ещё одну переменную - размер каждого отдельного BCC. При хранении несжатых BCC длина данных не играет никакой роли, потому что она всегда одинаковая. Однако при сжатии длина данных становится важной, так как у каждого BCC она будет разной. Это усложняет эффективное хранение BCC: если BCC пришлось изменить, и длина его данных изменилась, то что с этим нужно делать? Простым способом решения проблемы было бы добавление новых BCC к концу файла и принятие старой локации BCC «открытой» для записи. Однако, это создаёт проблему в виде фрагментации, с которой сложно справиться со слабым железом DS.

После запуска нескольких тестов стало понятно, что для поддержания приемлемой частоты кадров (которую всё равно нужно было установить в 30FPS для работы двухпроходной отрисовки, но мы вернёмся к этому позже) во время стриминга мира с SD карты необходимо избегать операции поиска(seeking) любой ценой, так как FAT таблицы по сути являются связными списками. В другом контексте такую проблему можно было бы легко преодолеть. Однако, долгое время чтения, сложность кеширования данных, когда доступно так мало ОЗУ и, конечно же, нехватка мощностей процессора делают эту проблему менее тривиальной, чем она должна быть.

Невозможность поиска означала, что чтение данных через обычные интерфейсы не стоит рассматривать: операции чтения были бы непоследовательными, что ясно указывало на необходимость чтения секторов с SD карты напрямую для достижения наибольшей эффективности. Конечно, для чтения данных напрямую из секторов необходимо знать, какие сектора содержат нужные данные. Таким образом кажется логичным сопоставить части файла мира, ассоциируя смещение в файле мира с секторами SD карты. Такое сопоставление было бы нужно выполнять после каждой загрузки мира, так как файл мира хранится на SD карте пользователя и нет никаких гарантий, что сектора не переместятся между игровых сессий, однако это относительно быстро, если учитывать, что это загрузка перед началом игры, а не операция, которую нужно выполнять в реальном времени.

Реализация этого дала ещё один фрагмент информации: для поддержки приемлемой производительности нужно читать не более одного сектора за кадр (поскольку это всё ещё довольно дорогая операция, и было необходимо учитывать некую погрешности при тестировании, чтобы учесть различные скорости чтения SD карт). Это означало, что куски данных для чтения должны были быть меньше размера сектора, и в идеале быть выровнены по секторам. Из-за этого даже думать о данных переменной длины стало сложно.

Решение этих проблем, которое было реализовано в оригинальном DScraft, было простым: по сути, файл мира был огромным двухмерным массивом, содержащим несжатые BCC. Таким образом каждый BCC мог быть выровнен по сектору (по факту, каждый BCC заполнял ровно один сектор), и чтение/запись BCC было бы таким же быстрым, как чтение/запись сектора, так как в карте, созданной во время загрузки, хранилось расположение секторов всех BCC.

Однако, это решение не использовало сжатие и было очень неэффективным, если говорить о размере файлов мира (вес мог доходить до 128Мб для миров в 1024x1024x64 блоков). Из-за упомянутых выше ограничений сжатие данных было бы несколько сложной задачей. Упуская, что алгоритм сжатия должен был быть невероятно быстрым, а куски данных должны были быть меньше размеров секторов (обе из проблем довольно легко решить), реальная проблема заключалась в том, что данные должны были быть выровнены по секторам. Учитывая, что идея была в том, чтобы иметь данные переменной (априори неизвестной) длины, такое условие было бы сложно соблюсти. Тривиальным решением было бы добавить паддинги к каждому куску данных, чтобы один кусок данных помещался в одном секторе, но это идёт в разрез с целью сжатия. Другим, более разумным решением, было поместить как можно больше кусков данных в один сектор, пока они не перестанут помещаться; таким образом получится обеспечить расположения данных в границах одного сектора, делая возможным быстрое чтение. Проблемы фрагментации были бы ограничены пределами отдельных секторов, и с ними было бы очень легко справиться. Для этого потребовалось бы создание секции «карты» ассоциаций в начале файла, связывающей смещения в мире со смещениями в файле, хотя это было бы низкой ценой за уменьшения размера файла примерно на 90%.

Есть одна вещь, которой нет ни в одном из этих решений - это бесконечные миры. Если рассмотреть второе решение, то добавить бесконечные миры на самом деле довольно просто, идея заключается в том, чтобы грузить BCC из файла мира, если они существуют, и генерировать их на лету, если их нет. Таким образом, если BCC модифицируется игроком, он сохраняется и добавляется к файлу, чтобы во время следующей игровой сессии изменения сохранились. Если данные BCC не менялись, то их не нужно сохранять, поскольку их можно сгенерировать заново и получить идентичный результат. Конечно, это создаёт некоторые проблемы. Для начала, если опираться на прошлое решение, то необходимо сделать что-то с картой ассоциаций смещений в начале файле, так как теперь она должна поддерживать бесконечные миры, которые очевидно невозможно хранить в карте ассоциаций фиксированного размера. Решением этого является перемещение информации из неё в хранимые BCC, вместо того, чтобы централизовать их в этой карте. Таким образом, если в заголовке каждого BCC будет храниться позиция колонны в мире, то игра сможет построить свою карту ассоциаций при загрузке мира. Это само по себе несколько проблематично; это не только сделает загрузку дольше (хотя, по общему мнению не так уж и невыносимо), но ещё и добавит новых кусок данных неизвестной длины, который необходимо хранить в ОЗУ: карту ассоциаций. При достаточно большом мире (или скорее при мире с большим количеством пользовательских изменений) карта ассоциаций станет слишком большой для обработки игрой, что сделает мир только полубесконечным.

Ещё одна проблема этой идеи в том, что контент должен генерироваться приставкой на лету. Чтение с SD карты может занять много времени, но и генерация процедурного контента может быть долгой. Конечно, генерацию можно сделать относительно быстрой при помощи эффективных методов (например, предпочитая шум симплекс вместо шума Перлина), но факт остаётся фактом: для этого необходимо много подсчётов (особенно с учётом предподсчётов для ускорения рендеринга, о которых я расскажу ниже). К счастью, DS имеет не один, а два процессора. Как объяснено в статье об Aperture Science DS (web.archive.org), основной процессор DS - это ARM9, а ARM7 процессор (который работает на частоте вдвое меньше частоты ARM9 процессора) обычно используется только для передачи данных (он используется для передачи информации о сенсорном экране в ARM9, для связи со звуковым оборудованием...). С помощью некоторых усилий, должно быть возможным перенести процессы стриминга мира на ARM7. Это могло бы освободить ARM9 процессор, позволяя создать более сложные схемы генерации/стриминга контента и гарантировало бы, что благодаря асинхронности, стриминг не замедлял бы игру. Конечно, могут возникнуть какие-то проблемы. Во-первых, DLDI драйвера (которые используются для доступа к содержимому SD карты на различных флэш-картриджах через общий интерфейс) были скомпилированы для работы на ARM9; нет гарантии, что они будут совместимы с ARM7 (хотя различия между между ARM7 и ARM9 минимальны), и так как код большинства драйверов закрыт, рекомпиляцию под архитектуру ARM7 не стоит рассматривать как вариант (чего бы это не стоило, но я смог абсолютно нормально запустить DLDI драйвер картриджа R4 на ARM7 какое-то время назад, используя fatFS для доступа к FAT). Во-вторых, ARM7 процессор имеет очень ограниченный объём памяти, с которой было бы нужно работать. И наконец, было бы необходимо разработать хороший способ передачи больших объёмов данных между процессорами. Все эти проблемы можно решить, но могут быть и другие проблемы, о которых я не подумал.

Отрисовка

Другой большой проблемой, возникшей при создании DScraft, был рендеринг. DS имеет довольно ограниченный GPU, который ограничивает максимальное число блоков на экране. Поэтому я решил, что DScraft должен работать с двухпроходным рендером. По сути, идея была в том, чтобы поднять лимит треугольников в кадре с 2048 до 4096, просто отрисовав не одну сцену, а две, затем соединяя их в одну. Конечно, это сократило бы частоту кадров вдвое, до 30FPS. но это было бы вполне приемлемо. Для того, чтобы достичь этого я использовал аппаратную функцию захвата экрана DS. которая позволяется записать изображение из главного экрана в главный VRAM банк. Этот процесс довольно легко реализовать, но в случае с DScraft это означало отдать два из четырёх главных VRAM банков (те. 256Кб из ~650Кб DS). К счастью, поскольку используемые в DScraft текстуры имеют очень низкое разрешение, это не оказалось большой проблемой. Идея была в том, чтобы как-то отрисовать передний и задний план каждой сцены отдельно, чтобы их можно было соединить просто отрисовав на отдельных отсортированных BG слоях. С этого было два уровня отсечения, которые нужно было выполнить: отсечение блоков (для отрисовки блоков только в поле зрения) и отсечение поверхностей (для отрисовки только тех поверхностей, что могут быть видны).

Следует начать с отсечения блоков; для работы двухпроходной отрисовки было необходимо создать алгоритм, который позволял бы быстро и эффективно отсечь блоки вне поля, зрения при этом сортируя их по расстоянию от камеры. По сути последнее требование сделало классические алгоритмы, использующие quad-деревья и oct-деревья, малоподходящими. Вместо них я выбрал простой алгоритм трехмерного распространения, основанный на позиции игрока. Он заполнял бы конус зрения, и при правильной реализации был бы естественный способ узнать, какие блоки на переднем плане, а какие на заднем.

Однако для того, чтобы это работало, всё ещё было необходимо найти эффективный способ узнать, находится ли блок в поле зрения. Во-первых, вместо того, чтобы применять распространение видимости непосредственно на блоках, я применял его на кластерах блоков. Во-вторых, вместо того, чтобы самому выполнять вычисления для определения, виден ли кластер, я использовал аппаратную функцию BoxTest встроенную в GPU DS. И хотя обычно это хорошая идея, по возможности использовать специализированные функции, в нашем случае это особенно хороший выбор, поскольку он понижает потребление процессора в тестах практически до нуля. Действительно, использование BoxTest позволило реализовать тесты асинхронно, и это означает, что пока GPU проводит какие-то подсчёты, процессор мог делать что-то другое. Таким образом, используя эту асинхронность, было возможно сделать алгоритм отсечения ещё более эффективным. Кроме того, алгоритм распространения имел ещё одно преимущество - он позволял иметь максимально высокую дальность прорисовки, так как алгоритм останавливался только после только, как он собирал максимальное число блоков, которое можно было отрисовать.

Разобравшись с отсечением по полю зрения нужно было разобраться и с другой важной функцией - с отсечением перегороженных блоков, т.е. нужно было найти способ не рисовать блоки, которые были скрыты другими блоками. В такой игре, как DScraft, эта функция особенно важна, потому что в мире было много слоев - в буквальном смысле. В основном, occlusion culling позволяет не рисовать пещеры, если игрок над землёй, и наоборот. Это имеет больше значение, когда вы и так ограничены в количестве блоков, что можете отрисовать за кадр. К сожалению, настоящий occlusion culling обходится дорого и его сложно собрать. Поэтому я прибегнул к небольшому хаку, или, как мне нравится это называть, эвристике. Идея заключалась в том, что если невозможно «смотреть через» кластер в определенном направлении, то, если алгоритм распространения попытается «пройти через» этот кластер в этом направлении, то распространение должно остановиться. Это была простая идея, но она показала хорошие результаты в большинстве ситуаций. И конечно же она была чрезвычайно дешёвой с точки зрения процессорного времени.

Кроме этого, единственной действительно важной вещью касающейся отрисовки было отсечение поверхностей: по сути, нужно было рисовать только те стороны блоков, которые можно было увидеть, и не рисовать поверхности между двумя соседними блоками. Эта довольно простая проблема, однако и критическая по очевидным причинам. В случае с DScraft я решил, что поверхности для отрисовки будут подсчитаны заранее. Это было сделано довольно просто, при помощи создания связного списка видимых поверхностей для каждого кластера в памяти. Таким образом, отрисовка кластера блоков была сделана простым проходом по вышеупомянутому списку. Добавление или удаление блоков повлечёт за собой просто изменение списка. В дополнение, информация о том, какие стороны блоков должны были отрисовываться, или нет, хранилась вместе с данными блоков в BCC в файле мира.

Официальный сайт (web.archive.org)

Упоминания в прессе:

• Kotaku

• Joystiq (web.archive.org)

• Pocket Gamer

• Tiny Cartridge