Как сделать игру типа doom

Пишем клон движка Doom: чтение информации карт

Введение

Цель этого проекта — создание клона движка DOOM, использующего ресурсы, выпущенные вместе с Ultimate DOOM (версия со Steam).

Он будет представлен в виде туториала — я не хочу добиваться в коде максимальной производительности, а просто создам работающую версию, и позже начну её улучшать и оптимизировать.

У меня нет опыта создания игр или игровых движков, и мало опыта в написании статей, поэтому можете предлагать свои изменения или даже полностью переписать код.

Вот список ресурсов и ссылок.

Книга Game Engine Black Book: DOOM Фабьена Санглара. Одна из лучших книг по внутреннему устройству DOOM.

Требования

Необязательное

Мысли

Не знаю, смогу и я завершить этот проект, но приложу для этого все силы.

Моей целевой платформой будет Windows, но поскольку я использую SDL, будет просто заставить движок работать под любой другой платформой.

А пока установим Visual Studio!

Проект был переименован из Handmade DOOM в Do It Yourself Doom with SLD (DIY Doom), чтобы его не путали с другими проектами под названием «Handmade». В туториале есть несколько скриншотов, на которых он всё ещё называется Handmade DOOM.

Файлы WAD

Прежде чем приступать к кодингу, давайте поставим перед собой цели и продумаем, чего мы хотим достигнуть.

Для начала давайте проверим, сможем ли мы считывать файлы ресурсов DOOM. Все ресурсы DOOM находятся в файле WAD.

Что такое файл WAD?

«Where is All my Data»? («Где все мои данные»?) Они в WAD! WAD — это архив всех ресурсов DOOM (и игр на основе DOOM), находящийся в одном файле.

Разработчики Doom придумали этот формат, чтобы упростить создание модификаций игры.

Анатомия файла WAD

Файл WAD состоит из трёх основных частей: заголовка (header), «кусков» (lumps), и каталогов (directories).

Формат заголовка

Формат каталогов

Архитектура

Примечание: такая архитектура может быть и неоптимальной, и при необходимости мы будем её изменять.

Приступаем к коду

Давайте добавим два новых класса: WADLoader и WADReader. Начнём с реализации WADLoader.

Реализовать конструктор будет просто: инициализируем указатель данных и храним копию передаваемого пути к файлу WAD.

Теперь давайте приступим к реализации вспомогательной функции загрузки OpenAndLoad : просто попробуем файл открыть как двоичный и в случае неудачи выведем ошибку.

Если всё будет хорошо, и мы сможем находить и открывать файл, то нам понадобится знать размер файла, чтобы выделить память для копирования в неё файла.

Теперь мы знаем, сколько места занимает полный WAD, и выделим нужное количество памяти.

Скопируем содержимое файла в эту память.

Давайте вкратце проверим код и убедимся, что всё работает. Но прежде нам нужно реализовать LoadWAD. Пока LoadWAD будет вызывать «OpenAndLoad»

И давайте добавим в функцию main код, создающий экземпляр класса и пытающийся загрузить WAD

Нужно будет ввести правильный путь к вашему файлу WAD. Давайте запустим!

Ой! Мы получили консольное окно, которое просто открывается на несколько секунд! Особо ничего полезного… работает ли программа? Идея! Давайте взглянем на память, и посмотрим, что в ней! Возможно, там мы найдём что-нибудь особенное! Для начала разместим точку останова, дважды щёлкнув слева от номера строки. Вы должны увидеть нечто подобное:

Я поместил точку останова сразу после чтения всех данных из файла, чтобы посмотреть на массив памяти и увидеть, что в него загружено. Теперь снова запустим код! В автоматическом окне я вижу несколько первых байтов. В первых 4 байтах написано «IWAD»! Отлично, работает! Никогда не думал, что этот день настанет! Так, ладно, нужно успокоиться, впереди ещё много работы!

Считывание заголовка

Общий размер заголовка составляет 12 байт (от 0x00 до 0x0b), эти 12 байт разделены на 3 группы. Первые 4 байта — это тип WAD, обычно «IWAD» или «PWAD». IWAD должен быть официальным WAD, выпущенным ID Software, «PWAD» должен использоваться для модов. Другими словами, это просто способ определить, является ли файл WAD официальным релизом, или выпущен моддерами. Заметьте, что строка не NULL terminated, поэтому внимательнее! Следующие 4 байта являются unsigned int, в котором содержится общее количество каталогов в конце файла. Следующие 4 байта обозначают смещение первого каталога.

Давайте добавим структуру, которая будет хранить информацию. Я добавлю новый файл заголовка и назову его «DataTypes.h». В нём мы будем описывать все нужные нам struct.

Теперь нам нужно реализовать класс WADReader, который будет считывать данные из загруженного массива байтов WAD. Ой! Тут есть хитрость — файлы WAD имеют формат big-endian, то есть нам нужно будет сдвинуть байты, чтобы сделать их little-endian (сегодня в большинстве систем используется little endian). Для этого мы добавим две функции, одну для обработки 2 байт (16 бит), другую — для обработки 4 байт (32 бит); если нам нужно считать только 1 байт, то делать ничего не надо.

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

Давайте соединим всё вместе, вызовем эти функции и выведем результаты

Запустим программу и посмотрим, всё ли работает!

Отлично! Строку IWAD хорошо заметно, но правильны ли другие два числа? Попробуем считать каталоги при помощи этих смещений и посмотрим, получится ли!

Нам нужно добавить новую struct для обработки каталога, соответствующего представленным выше параметрам.

Теперь давайте дополним функцию ReadDirectories: считаем смещение и выведем их!

В каждой итерации мы умножаем i * 16, чтобы перейти к инкременту смещения следующего каталога.

Запустим код и посмотрим, что получится. Ого! Большой список каталогов.

Судя по названию lump, можно предположить, что нам удалось правильно считать данные, но возможно есть способ получше, чтобы проверить это. Мы взглянем на записи WAD Directory при помощи Slade3.

Похоже, что название и размер lump соответствуют данным, полученным при помощи нашего кода. Сегодня мы проделали отличную работу!

Другие примечания

DOOMReboot: полностью несогласен. 15 МБ ОЗУ в наши дни — совершенная мелочь, и считывание из памяти будет значительно быстрее, чем объёмные fseek, которые придётся использовать после загрузки всего, необходимого для уровня. Это увеличит время загрузки не меньше, чем на одну-две секунды (у меня всё время загрузки занимает меньше 20 мс). fseek задействуют ОС. У которой файл скорее всего находится в кэше ОЗУ, но может быть и нет. Но даже если он там, это большая трата ресурсов и эти операции запутают множество считываний WAD с точки зрения кэша ЦП. Самое лучшее, что можно создать гибридные методы загрузки и хранить данные WAD для уровня, которые помещаются в кэш L3 современных процессоров, где экономия окажется потрясающей.

Исходный код

Базовые данные карт

Научившись считывать файл WAD, давайте попробуем использовать прочитанные данные. Будет здорово научиться считывать данные миссии (мира/уровня) и применять их. «Куски» данных миссий (Mission Lumps) должны быть чем-то сложным и хитрым. Поэтому нам нужно будет двигаться и нарабатывать знания постепенно. В качестве первого небольшого шага давайте создадим нечто наподобие функции автокарты (Automap): двухмерного плана карты с видом сверху. Для начала посмотрим, что находится внутри Mission Lump.

Анатомия карты

Начнём сначала: описание уровней DOOM очень похоже на 2D-чертёж, на котором стены обозначены линиями. Однако для получения 3D-координат каждая стена берёт высоты пола и потолка (XY — это плоскость, по которой мы движемся горизонтально, а Z — это высота, позволяющая двигаться вверх и вниз, например, поднимаясь на лифте или спрыгнув вниз с платформы. Эти три компоненты координаты используются для рендеринга миссии как 3D-мира. Однако для обеспечения хорошей производительности движок имеет определённые ограничения: на уровнях нет расположенных одна над другой комнат и игрок не может смотреть вверх-вниз. Ещё одна интересная особенность: снаряды игрока, например, ракеты, поднимаются по вертикали, чтобы попасть в цель, расположенную на более высокой платформе.

Эти любопытные особенности стали причиной бесконечных холиваров по поводу того, является ли DOOM 2D- или 3D-движком. Постепенно был достигнут дипломатический компромисс, спасший множество жизней: стороны сошлись на приемлемом для обеих обозначении «2.5D».

Чтобы упростить задачу и вернуться к теме, давайте просто попробуем считать эти 2D-данные и посмотреть, можно ли их как-то использовать. Позже мы попробуем отрендерить их в 3D, а пока нам нужно разобраться в том, как работают совместно отдельные части движка.

Проведя исследования, я выяснил, что каждая миссия составлена из набора «кусков». Эти «куски» (Lumps) всегда представлены в файле WAD игры DOOM в одинаковом порядке.

Показанная выше демо-карта имеет следующие характеристики:

Формат вершин

Как и можно ожидать, данные вершин очень просты — всего лишь x и y (точка) каких-то координат.

Формат Linedef

В Linedef содержится больше информации, он описывает линию, соединяющую две вершины, и свойства этой линии (которая позже станет стеной).

Значения флагов Linedef

Не все линии (стены) отрисовываются. Некоторые из них имеют особое поведение.

Архитектура

Для начала давайте создадим класс и назовём его map. В нём мы будем хранить все данные, связанные с картой.

Пока я планирую только хранить как вектор вершины и linedefs, чтобы применить их позже.

Также давайте дополним WADLoader и WADReader, чтобы мы могли считывать эти два новых элемента информации.

Кодинг

Код будет похож на на код чтения WAD, мы только добавим ещё несколько структур, а затем заполним их данными из WAD. Начнём с добавления нового класса и передачи названия карты.

Теперь добавим структуры, чтобы считывать эти новые поля. Поскольку мы уже несколько раз это делали, просто добавим их все сразу.

Далее нам понадобится функция для считывания их из WADReader, она будет близка к тому, что мы делали ранее.

Думаю, для вас здесь нет ничего нового. А теперь нам нужно вызвать эти функции из класса WADLoader. Позвольте изложить факты: здесь важна последовательность lumps, мы найдём название карты в lump каталога, за которым в заданном порядке будут следовать все lumps, связанные с картами. Чтобы упростить себе задачу и не отслеживать индексы lumps по отдельности, мы добавим перечисление, позволяющее избавиться от магических чисел.

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

Ого, мы почти закончили! Теперь давайте просто считаем VERTEXES! Повторюсь, мы уже делали такое раньше, теперь вы должны разбираться в этом.

Хм, похоже, что мы постоянно копипастим один и тот же код; возможно, в дальнейшем его придётся оптимизировать, но пока вы реализуете ReadMapLinedef самостоятельно (или посмотрите на исходный код по ссылке).

Финальные штрихи — нам нужно вызвать эту функцию и передать ей объект карты.

Теперь давайте изменим функцию main и посмотрим, всё ли будет работать. Я хочу загрузить карту «E1M1», которую передам в объект карты.

Теперь давайте всё это запустим. Ого, куча интересных чисел, но верны ли они? Давайте проверим!

Посмотрим, сможет ли slade помочь нам и в этом.

Мы можем найти карту в меню slade и посмотреть на подробности lumps. Давайте сравним числа.

А как насчёт Linedef?

Также я добавил это перечисление, которое мы попробуем использовать при отрисовке карты.

Другие примечания

В процессе написания кода я ошибочно считывал больше байтов, чем нужно, и получал неверные значения. Для отладки я начал смотреть на смещение WAD в памяти, чтобы понять, нахожусь ли я на нужном смещении. Это можно сделать при помощи окна памяти Visual Studio, которые оказываются очень полезным инструментом при отслеживании байтов или памяти (также в этом окне можно устанавливать точки останова).

Если вы не видите окно памяти, то перейдите в Debug > Memory > Memory.

Теперь мы видим значения в памяти в шестнадцатеричном виде. Эти значения можно сравнить с hex-отображением в slade, нажав правой клавишей на любой lump и отобразив его как hex.

Сравниваем их с адресом загруженного в память WAD.

И последнее на сегодня: мы увидели все эти значения вершин, но есть ли простой способ визуализировать их без написания кода? Я не хочу тратить время на это, просто чтобы выяснить, что мы движемся не в том направлении.

Наверняка уже кто-то создал графопостроитель. Я загуглил «draw points on a graph» и первым результатом оказался веб-сайт Plot Points — Desmos. На нём можно вставить числа из буфера обмена, и он нарисует их. Они должны быть в формате «(x, y)». Чтобы получить его, достаточно немного изменить функцию вывода на экран.

Ого! Это уже похоже на E1M1! Мы чего-то добились!

Если вам лениво это делать, то вот ссылка на заполненный точками график: Plot Vertex.

Но давайте сделаем ещё один шаг: немного потрудившись, мы можем соединить эти точки на основании linedefs.

Источник

Клон Doom в 13 килобайтах JavaScript

В прошлом году я участвовал в соревнованиях JS13K 2019, на которых людям предлагается разрабатывать игры в менее чем 13 КБ кода на JavaScript. Я участвовал с клоном Doom, который назвал… «Ещё один клон Doom» (Yet Another Doom Clone).

Поиграть в него можно здесь. Исходный код выложен сюда.

Зачем создавать клон Doom?

Зачем писать FPS на JavaScript всего в 13 КБ (с учётом сжатия)? По нескольким причинам. Но лучше всего на этот вопрос отвечает раздел FAQ соревнований JS13K «Можно ли использовать WebGL?»:

«Да, но может быть сложно уместить его в 13 килобайта, если вы планируете писать FPS».

Кроме того, в то время я как раз написал 3D-рендерер и хотел поработать над ним ещё. К тому же мне нравится создавать сильно сжатый код. (Например, много лет назад я создал язык и написал компилятор для нового языка, предназначенный специально для использования в код-гольфинге.)

Именно поэтому я выбрал FPS. Остаётся вопрос: «Почему Doom?» На него ответить проще: если вы хотите написать FPS, и чтобы он при этом был небольшим, то Doom — практически самый минималистичный вариант.

Причина, по которой Doom настолько прост (по современным стандартам) понятна: Doom должен был работать на «железе» на пять порядков более медленном, чем сегодня. За ту же цену сейчас можно собрать машину, которая способна выполнять в сотню тысяч раз больше работы, чем Pentium 1994 года. Поэтому я решил, что будет интересно попробовать воссоздать нечто наподобие Doom, но вместо ограничений производительности использовать ограничения объёма кода.

Фундамент: 3D-рендерер на JavaScript

Движок игры я начал строить на основе написанного ранее 3D-рендерера, который я хотел реализовать как можно более простым. Оказалось, что благодаря своей простоте он к тому же довольно мал: ядро движка 3D-рендеринга заняло всего примерно 5 КБ сжатого JavaScript, то есть на игру осталось всего 8 КБ. Я решил, что ситуация не так уж и плоха. Если я не будут использовать большие спрайты или файлы объектов, то всё должно получиться.

Движение игрока

Для перехода от 3D-рендерера к движку 3D-игры, по сути, требуется только одно изменение: управляемое игроком движение камеры и повторный рендеринг после каждого движения. Для реализации этого я поместил игрока внутрь параллелепипеда и работал над движком, пока движение не стало правильным. Doom имел очень характерный стиль движения, который я стремился воссоздать.

Первый шаг к этому — реализация ускорения движения игрока в направлении его взгляда до какой-то (высокой) максимальной скорости. Я добавил больше ускорения, чем в оригинальном Doom, потому что сегодня это ощущается привычнее. Важнее для воссоздания ощущения Doom было добавление раскачивания камеры при движении игрока.

В состоянии постоянного движения это просто синусоида, но при переходе от неподвижности к ходьбе я добавил обязательные детали, чтобы перемещение казалось естественным.

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

Также я добавил одну особенность, которой не было в Doom — небольшую величину поворота камеры вдоль продольной оси на каждом шаге. (В Doom его не было, потому что движок позволял выполнять поворот только по оси Z, то есть игрок даже не мог взглянуть вверх.)

Затем я добавил ограничение движения. Нет никакого смысле создавать сложные лабиринты в стиле Doom, если игрок может проходить сквозь стены. Для «правильной» реализации ограничений нужно сделать игрока сферой, стены — плоскостями и вычислять пересечения сферы с плоскостью. Я беспокоился, что это займёт слишком большую часть наших 13 КБ.

Поэтому вместо этого игра испускает восемь лучей из текущей позиции игрока и определяет, пересекается ли какой-нибудь из этих лучей со стеной. Если да, то я отталкиваю игрока назад, чтобы он оставался не менее чем в пяти единицах от этой стены. Так я реализовал распознавание коллизий сферы «для бедных», на что мне понадобилась всего сотня байтов.

Реализовать эту систему было довольно сложно, особенно обработать случаи одновременного пересечения лучей с несколькими стенами. Во некоторых ситуациях система даёт сбои, поэтому при создании дизайна уровней я вручную тестировал их на баги и проектировал их так, чтобы баги распознавания коллизий не возникали. (Главное ведь, чтобы работало. )

Object Lathing

Поэтому вместо него я решил написать минималистичный метод «точёных» объектов (object lathe):
мы задаём 2D-контур, представленный в виде ряда точек, обтачиванием вращаем точки по кругу для генерации 3D-объекта. Это позволяет создавать красивые объекты, занимающие мало пространства. Например, для описания показанного выше кувшина потребовалось примерно двадцать байтов.

Задолго до разработки игры я также создал тщательно минимизированную до 300 байт реализацию подразделения поверхностей (surface subdivisioning) (которую ранее использовал для 3D-рендерера). Но в конечном итоге мне не хватило места и от неё пришлось отказаться. Однако я особо не жалею, потому что она не добавляла в игру ничего важного.

Игровой цикл

Всё описанное выше было довольно статичным, по миру перемещалась только камера. Однако для создания игры требуется интерактивность. И здесь нам пригодится игровой цикл.

Мы будем использовать совершенно стандартный игровой цикл. Изначально в коде он выглядел так:

Да, это красивый и удобный код, но каждая из функций вызывается только один раз. Поэтому они превратились во встроенные функции, и цикл стал некрасивым.

Оружие и враги

Распознавание попаданий реализовано как простое сканирование испускаемым лучом (в нём используется тот же код, что и в распознавании коллизий со стенами при движении игрока). При попадании создаются частицы взрыва с небольшой вспышкой.

Для сканирования попаданий пришлось внести в систему испускания лучей несколько изменений. Во-первых, поскольку первая версия проверяла коллизии только по горизонтали, мне нужно было теперь проверять, произошла ли коллизия на нужной высоте по Z. Это сделать было не особо сложно: вычисляем, насколько далеко объект от игрока, из наклона игрока по поперечной оси определяем, какой должна быть высота пули, и если она находится в пределах ограничивающего параллелепипеда объекта, то коллизия произошла.

После этого я сортирую все потенциальные коллизии и выбираю ближайшую.

Для стрельбы также требуется тряска экрана, и, поскольку в игре нет боеприпасов, замедление движения игрока. Важно, чтобы у игрока была причина не держать всю игру палец на спусковом крючке.

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

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

Сначала блоки, из которых состоял враг, просто разлетались сквозь стены и пропадали с экрана. Это сбивало с толку, поэтому я добавил эффект отскакивания блоков от стен. Если говорить кратко, то отскоки совершенно физически недостоверны. Коллизии снова реализованы при помощи пересечения лучей. Если ближайшая стена полностью находится на плоскости xz, то объекты меняют знак свой скорости по y. Если стена полностью на плоскости, то меняется знак скорости по x. Во всех остальных случаях меняются знаки скоростей по x и y.

Когда позиция объекта меньше, чем высота пола текущей комнаты, скорость по z меняет свой знак и уменьшается на 20%. Каждую секунду объект замедляется на 50% (как будто к нему применяется какое-то гипотетическое трение).

ИИ врагов

Несмотря на то, что я изучал и имел дело в работе с ««ИИ»» (со множеством кавычек), враги в игре довольно неинтеллектуальны. У врагов есть позиция и поворот. Они постоянно ходят туда и обратно, пока не пробудятся по одной из двух причин:

(а) игрок находится в поле их зрения

(б) игрок подстреливает врага, находящегося в поле зрения.

Определение поля зрения тоже реализовано при помощи испускания лучей. Чтобы не тратить впустую такты ЦП на испускание лишних лучей, враг проверяет других врагов всего раз в секунду.

После пробуждения враг начинает двигаться к игроку по прямой. Если на его пути что-то встаёт, то он выбирает новое случайное направление и делает несколько шагов, а затем снова начинает двигаться к игроку. Иногда движущиеся враги стреляют по игроку.

Кроме того, в момент смерти враг запрашивает помощь у других врагов, которых может видеть (снова при помощи испускания лучей). Благодаря этому сложно устранять врагов по одному из-за угла, потому что это скучная механика, и не стоит её поощрять.

Текстуры

Пока картинка выглядит очень скучной, ведь используется всего одна текстура. Я знал, что никак не смогу уместить в игру нарисованные от руки текстуры, даже самые маленькие, поэтому сгенерировал их процедурно. Я решил использовать всего три текстуры: плитки пола, кирпичный паттерн для стен и простой шум Перлина для лавы и взрывов.

Генерация кирпичей довольно тривиальна. Отрисовываем горизонтальные линии через каждые N шагов, а затем вертикальные линии через каждые N со смещением на N/2 в чётных строках. Код выглядит так:

С генерацией плиток всё чуть сложнее. Сначала я создал шестиугольную решётку, а затем для каждого пикселя плитки я вычисляю расстояние до ближайших двух точек решётки. Если расстояние до ближайшей точки равно удвоенному расстоянию до второй по близости, то рисуем линию. Так мы получаем стандартный паттерн из плиток.

Шум Перлина визуально гораздо красивее, чем другие типы шумов. Его случайность выглядит намного естественнее, чем простой белый шум. Генерация шума Перлина довольно сложна, поэтому я просто дам ссылку на Википедию и скажу, что сделал так же. Также я добавил небольшое количество шума Перлина к кирпичному паттерну, чтобы он был менее скучным.

Анимации врагов

Простое скольжение врагов по карте выглядит не особо интересным, поэтому я добавил анимацию ходьбы. Она заняла на удивление мало места и заключалась в движении конечностей как маятников.

Один тип врагов — это слишком скучно, поэтому затем я добавил небольшого летающего врага, он быстрее движется и в него сложнее попасть. Внешний вид его опять-таки очень минималистичен: это просто две похожие на крылья трапецоида и прямоугольное тело. Чтобы показать, что он как будто летает, враг немного машет крыльями и раскачивается вверх-вниз; здесь снова используется код анимаций шагающего врага.

Казалось очевидным, что для добавления звука нужно использовать JSFXR, однако на этом этапе места уже начинало не хватать. Взглянув ещё раз на код, я увидел, что ещё многое можно оптимизировать.

Благодаря последовательности небольших изменений мне удалось сократить его почти в два раза. Самая большая экономия получилась благодаря удалению map из массива в воспроизводимый файл WAV и замене его на вызов функции WebAudio, получающей непосредственно массив float. Ещё одна серьёзная экономия получилась благодаря замене куче операторов case на операции поиска в массиве. То есть я реализовал принцип мультиплексора и вычислил все возможные случаи внутри массива, а затем просто выбирал индекс нужного значения. Это медленнее, зато код короче. После замены циклов for на map и создания вспомогательной функции clamp код оказался достаточно коротким, чтобы можно было написать красивые звуковые эффекты.

Затем я захотел сделать так, чтобы аудиосистема реагировала на то, где находится игрок в 3D-пространстве. Я думал, что эта часть потребует много усилий, но оказалось, что это довольно просто, и теперь в коде есть функция createStereoPanner, выполняющая эту задачу.

В качестве фоновой музыки я переписал среднюю часть токкаты и фуги ре минор. Она просто повторяется бесконечно.

Описание карты

Одной из уникальных особенностей Doom были уровни. Каждая карта больше напоминала лабиринт, по которому игрок бегал в поисках выхода. Для создания клона это был обязательный компонент.

Однако для простого хранения карт потребовалось бы слишком много места: при наивном задании (т.е. при сохранении позиций всех стен) даже несколько простейших уровней занимали более килобайта. Поэтому карты записываются как набор многоугольников (которые могут быть и вогнутыми). У каждого многоугольника есть высота пола и потолка, а если два соседних многоугольника имеют общее ребро, то игрок может пройти из одного в другой (иногда спускаясь ниже или поднимаясь).

Для создания кода, превращающего многоугольники в трёхмерные комнаты, потребовалось довольно много усилий. Хоть и легко разместить стены вокруг каждого многоугольника, основной сложностью стало определение того, когда стены быть не должно из-за двух соседних рёбер. Чтобы упростить процесс, проём создаётся только тогда, когда у двух стен обе координаты совпадают точно.

Изначально я создавал карты, вручную задавая координаты многоугольников, но у такого подхода было две проблемы: во-первых, они занимали много места, и, что более важно, на создание тратилась куча времени. Если я хотел успеть спроектировать достаточное количество карт, то нужно было придумать что-то получше.

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

Я даже добавил функции, позволяющие создавать циклы for и вызовы/возвраты, чтобы можно было, например, изготавливать лестницы, а затем многократно применять функцию make-stairs там, где мне были нужны лестницы.

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

Поэтому код черепашки стал таким:

Чтобы упростить создание карт, я избавился от большей части языка и создал гораздо более простой язык. Я убрал циклы, вызовы функций, повороты и реализовал всего два опкода: make-polygon и goto. Опкод make-polygon получает количество вершин и последовательность байтов, где старшие 4 бита определяют сдвиг по оси x, а младшие 4 бита — сдвиг по оси y. После достижения последней вершины цикл завершается и черепашка создаёт многоугольник. Опкод move просто перемещает черепашку в новое место для создания нового многоугольника.

После создания нескольких карт я посмотрел, какие части моего языка turtle занимают больше всего места. Я понял, что трачу много места на перемещение черепашки от многоугольника к многоугольнику. Как можно сократить этот процесс? Обратим внимание, что обычно многоугольники не изолированы: они соединяются с другими многоугольниками вершиной. Поэтому я добавил ещё одну функцию backtrack. При каждом движении черепашки она добавляет своё местоположение в стек. Backtrack извлекает позицию черепашки определённое количество значений назад. Это очень эффективно: более 95% перемещений черепашки было заменено командами backtrack.

Редактор карт

Для удобства создания карт я быстро набросал WYSIWYG-интерфейс. Этот редактор компилирует карты на язык turtle, чтобы их можно было использовать в игре.

Обновление карты в редакторе в реальном времени обновляет рендерящуюся игру, чтобы я сразу видел, что происходит. В видео показан процесс создания новой карты.

Так как этот редактор не будет находиться в составе игры, я мог не волноваться о качестве кода или удобстве редактора. Он невероятно уродлив и некрасив, в нём используются непонятные горячие клавиши. (Хотите добавить новый многоугольник? Выберите созданную вершину и нажмите Shift-A для выделения соседнего ребра, а затем E (для экструдирования). Хотите добавить вершину к уже существующему ребру? Shift-A и S (для разбиения). Нужно удалить многоугольник? Shift-Q. Если знать, что делать, то всё вполне логично, но не особо интуитивно понятно.)

Мысли об экономии пространства

Для успешного создания полной игры в 13 килобайтах сжатого JavaScript требуется постоянно помнить о занимаемом кодом пространстве.

Основная цель заключается в том, чтобы всегда понимать размер кода. Я загрузил скрипт на Python для отслеживания каждого изменения файла исходников и пересборки пакета. Он показывал количество свободных байтов, оставшихся для самой игры, чтобы они всегда были видимы и я мог понять, стоит ли внесённое изменение повышения сложности.

Пригодилось и то, что я написал множество вспомогательных функций, которые использовал во многих частях программы. Вот некоторые из них, которые я считаю наиболее полезными:

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

В самом некрасивом моём коде я сделал так, что умножения матриц 4×4 стали и очень эффективными, и одновременно очень короткими; для этого пришлось потрудиться:

Для постоянного отображения текущего размера сборки требовался автоматизированный процесс сборки. Сначала скрипт сборки просто запускал uglifier, за которым выполнялся стандартный zip, чтобы я мог отслеживать занимаемое пространство. Вскоре я осознал, что есть оптимизации, которые позволят мне автоматизировать процесс, чтобы ещё больше сжать код. Я написал короткий скрипт, определяющий все имена переменных webgl и заменяющий их короткими однобуквенными именами (потому что uglify этого не делал). Затем я модифицировал эту программу так, чтобы она переписывала длинные имена функций WebGL, например, framebufferTexture2D, коротким трёхсимвольным кодом вида e2m (я брал восьмой символ с конца, второй символ с конца и третий символ с начала). Ближе к концу разработки я узнал о advzip, который ещё больше помог мне с улучшением сжатия.

Источник