DOOM. Как в битвах с демонами закалялся новый жанр - Дэн Пинчбек

Вершины, лайндефы, сайддефы, сектора и все связанные с ними переменные вместе взятые образуют уровень. Все усложняется, когда дело доходит до прорисовки всего этого добра в режиме реального времени, и именно здесь проявляется настоящая гениальность движка Джона Кармака. Частота перерисовки всего, что видно на экране, называется FPS – frames per second, количество кадров в секунду. Высокая частота кадров дает вам более скоростные и управляемые бои, менее рваные анимации, а также плавный и быстрый игровой процесс. Это и был Скверный Грааль DOOM. Задача любого игрового движка – выдавать игроку необходимую картинку как минимум x раз в секунду, что бы ни происходило в игровом мире и как бы ни менялись его элементы. К этому нужно добавить фоновые вычисления, которые на экране никак не отображаются, все эти числа и алгоритмы – пока мы говорим только о графике. WAD-файл (файл со всеми ассетами DOOM – аббревиатура расшифровывается как Where’s All the Data, «Тут все данные») представляет собой набор инструкций, которые буквально диктуют игре, как отображать уровень: «Нарисуй точку здесь и здесь, соедини их вместе и прикрепи текстуру a высотой b пикселей; затем соедини все это вместе и накрой пол в этом секторе текстурой c, а потолок текстурой d, и затем наложи здесь свет e». А затем все это перерисовывается x раз в секунду. Очевидно, что процесс этот довольно сложный; к тому же дизайнеры добавляют в игру главного героя, который двигается по уровню, врагов, которые тоже ходят туда-сюда, летающие огненные шары, взрывающиеся бочки, лифты и так далее. Чтобы сократить количество нужных вычислений, нужно рисовать только то, что игрок видит на экране: таким образом, уменьшается количество данных, требующих обработки. Но прорисовка все равно требует много ресурсов, и именно из-за нее частота смены кадров может снижаться, создавая визуальные «тормоза», которые портят игровой опыт. По словам Ромеро, эта проблема «выявила ограничения того способа, которым Кармак рендерил сцены, потому что он для этого использовал списки секторов, а я создал какую-то штуку с рекурсивными секторами, и из-за этого игра работала очень медленно».

Ромеро говорит о списке, где каждому сектору WAD присваивается уникальный идентификатор, так что механизм рендеринга может точно определить, что и как он должен отрисовывать. Проблема в том, что если движок рендерит каждый сектор, то он делает ненужную работу. Классический способ отрисовать все объекты, находящиеся внутри поля зрения игрока (так называемый алгоритм художника), – это начать с рисования фона, затем нарисовать те объекты, что находятся дальше всего, и так далее вплоть до самого переднего плана. Другие примеры, с помощью которых можно представить себе этот процесс, – это набор слоев Photoshop или стопка прозрачных пластиковых листов. Следующая проблема заключается в том, что некоторые объекты, которые отрисовываются в результате этого процесса, на самом деле могут быть невидимы, если их закрывают другие объекты. Например, если яму с лавой не видно из-за низкой стены, но анимированная текстура лавы при этом перерисовывается сорок раз в секунду, то получается, что ресурсы, которые уходят на ее рендеринг, на самом деле тратятся впустую. Таким образом, процесс рендеринга замедляется, а частота кадров снижается. В поисках решения этой проблемы во время работы над портом Wolfenstein 3D для Super Nintendo Кармак решил реализовать алгоритм двоичного разбиения пространства, или BSP.

BSP – это, по сути, способ выяснить, как различные сектора связаны друг с другом, и таким образом избежать ненужного рендеринга. Этот алгоритм перемещает трудоемкие вычисления для расчета того, какие объекты видны из той или иной точки, на итоговую часть процесса создания уровня. Этот процесс завершается созданием BSP-таблицы, которая содержит данные для графического движка, чтобы установить, какие объекты и в каком порядке рендерить – таким образом, этим не приходится заниматься в режиме реального времени в процессе игры. BSP разбивает уровень на части, которые называются подсекторами – их составляют многоугольники, содержащиеся внутри секторов. У каждого подсектора имеется список связанных с ним секторов. Механизм рендеринга движется вниз по дереву, пока не найдет нужный подсектор, а затем проверяет связанные с ним сектора вместо того, чтобы при каждой перерисовке экрана всякий раз вычислять связанность секторов, так сказать, «обычным способом». По сути, BSP работает как предметный указатель в книге, позволяя быстро и легко находить связи, зависимости и иерархии. Таким образом, как и любой другой алгоритм индексирования, BSP весьма значительно сокращает время рендеринга и, следовательно, увеличивает частоту смены кадров. Считается, что Кармак узнал о BSP из работы Брюса Нейлора, который опубликовал ряд статей о BSP в начале 1980-х годов. Там он ссылался на концептуальную идею BSP, или «предварительную версию», которую Роберт Шумакер предложил за десять с лишним лет до того. Кармак, однако, говорит, что впервые он наткнулся на описание этого принципа в книге Computer Graphics: Principles and Practice («Компьютерная графика: принципы и практика») и уже какое-то время ломал над ним голову. О его опыте внедрения BSP полезно рассказать, потому что он в красках показывает, как компьютерные науки существовали в эпоху до интернета:

Кармак первым применил технологию BSP для игр, и с тех пор она прижилась в основе огромного количества игровых движков. Наряду со многими другими достижениями DOOM, использование Кармаком двоичного разбиения пространства стало исключительно важным наследием для игр в целом. Каковы были результаты? Как выразился Ромеро: «Именно тогда все заработало супербыстро и BSP переродилось для компьютерных игр». В отличие от остальных, Кармак говорит о своих прорывных достижениях намного скромнее: