Вершины, лайндефы, сайддефы, сектора и все связанные с ними переменные вместе взятые образуют уровень. Все усложняется, когда дело доходит до прорисовки всего этого добра в режиме реального времени, и именно здесь проявляется настоящая гениальность движка Джона Кармака. Частота перерисовки всего, что видно на экране, называется 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, Брюс Нейлор приехал к нам и подарил мне копии своих статей. Так интересно разговаривать с людьми о прошлом. Конечно, теперь у вас есть интернет. Сейчас вы можете найти все что угодно. Но в те годы найти перепечатки старых научных статей было большой удачей. Раньше я пользовался услугами справочных служб: вы платили им где-то двадцать пять долларов, а они высылали вам ксерокопии старых исследовательских работ. Это был совершенно другой мир. Большую часть своих знаний о программировании я извлек где-то из трех справочников, потому что других книг у меня не было. Приходилось доходить до всего самому. Поэтому оказалось, что в свое время я переизобрел много классических вещей, таких как код Хаффмана
[48] или LZW
[49]. Я так гордился своими открытиями, а потом узнавал, что все эти вещи уже давно придуманы, причем придуманы гораздо лучше».
Кармак первым применил технологию BSP для игр, и с тех пор она прижилась в основе огромного количества игровых движков. Наряду со многими другими достижениями DOOM, использование Кармаком двоичного разбиения пространства стало исключительно важным наследием для игр в целом. Каковы были результаты? Как выразился Ромеро: «Именно тогда все заработало супербыстро и BSP переродилось для компьютерных игр». В отличие от остальных, Кармак говорит о своих прорывных достижениях намного скромнее:
«Людям нравится искать особый, волшебный ингредиент. Им нравится искать такие истории. Но почти любого результата можно достичь несколькими способами. И работа над DOOM начиналась с другого подхода, который был не таким быстрым, как мне хотелось. Впервые я использовал BSP в порте Wolfenstein 3D для Super Nintendo, и скорость получилась выше, чем при рейкастинге
[50]. А потом, когда я вернулся к работе над DOOM, я продолжил использовать этот метод, потому что он оказался эффективным и здесь. И наоборот, движок Build (Duke Nukem 3D) не использовал BSP и был настолько же быстрым, насколько и технологии DOOM. Но, безусловно, благодаря успеху нашей игры тысячи людей узнали, что такое BSP, и даже начали изучать его с научной точки зрения».
