19 ноября 2010

Введение

Меня зовут Майкл Гудфеллоу. Первый раз я дотронулся до компьютера где-то в 1971, и мне сразу захотелось знать как его программировать. Я работал в индустрии ПО с 1975 по 2005, когда вышел на пенсию по инвалидности. И да, я все еще пишу код. Кто знает зачем?

Я учился программировать, создавая компьютерные игры (в которые мы играли на похожих на печатные машинки терминалах, подключенных к большим мейнфреймам), но я не написал ни одной профессионально. Я много лет хотел написать игру. Я много раз застревал с этим. Но, перед тем, как мне удалось найти на это время, игры стали слишком хорошо выглядеть. Для человека без художественных способностей, это выглядит слишком сложно. Half-Life2 (или даже Half-Life) – это не то, что вы делаете в свободное время, днем занимаясь работой. Мои друзья, корпоративные программисты как и я, согласились. Когда я упомянул о написании игры (даже MMO!) они долго смеялись.

Но теперь вышел и стал хитом Minecraft - и это проект одного человека. Очевидно, для игр, которые не выглядят на миллион (или 20 миллионов) долларов все еще есть ниша. Так что я попробую.

Когда я работал над проектами раньше, это был только я, компьютер и полная тишина, так как никто из моих друзей не был заинтересован в таком невозможном проекте. На этот раз я могу позволить себе сделать грязь. Я буду писать публично для вашего развлечения. И чтобы вы могли следовать за мной, я опубликую все исходники. Даже если я выдохнусь, возможно, там будет какой-нибудь полезный фреймворк для кого-нибудь из вас.

Наконец, я знаю, что есть много других открытых проектов с богатыми фреймворками. И поэтому разработка чего-либо с нуля вроде этого - пустая трата времени. Плюс есть всевозможные стандартные форматы и интерфейсы, которые вы должны поддерживать, и стандартные инструменты, которые вы можете использовать. Не лучше ли повторно использовать чужой код, чтобы получить преимущество? Но... Эй, смотрите! Документ с требованиями! Устроим 10-часовую встречу по этому поводу?

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

Ну, займемся кодингом!

Часть 1: Маленький Мир

Так как Minecraft так популярен, давайте начнем с мира, сделанного из кубиков. Я захочу вернуться к этому позже, но пока у него есть ряд преимуществ. Во-первых, его легко закодировать. Во-вторых, вы можете легко модифицировать мир, добавляя и убирая кубы. Когда мы напишем сервер и позволим всем людям собраться вместе, мы захотим модифицируемый мир. И, наконец, если Minecraft может иметь успех с кубами, можно написать много других игр в том же стиле графики (посмотрите CGI Lego анимации на YouTube), так что кто-то может найти применение даже этому простому коду.

Если вы собираетесь строить из кубов, то первая структура данных, которая приходит на ум, это Octree. Оно делит все ваше пространство на 8 кубов. Если в кубе ничего нет, или в нем все те же самые кубы (например, объем воды или почвы), то вы закончили. Если куб не является однородным, то вы делите его на 8 меньших кубов. Вы делаете это несколько раз, пока не достигнете кубиков размера 1, которые на самом деле составляют мир. Смотрите Рис. 1 для примера мира, в котором удален только верхний угловой куб. На Рис. 2 вы можете видеть дерево более сложного объекта - сферу с вырезанным срезом.

Рис. 1: Простое Octree

Рис. 2: Сферическое Octree

Мы можем сделать пейзаж таким же образом. Мы генерируем некоторые высоты по шаблону из Perlin Noise. Мы используем дерево размером 128 на 128 на 128 (7 уровней), так что потенциально в нем может быть 2 097 152 отдельных куба. Этот ландшафт сплошной внизу, и земля не очень далеко простирается по вертикали. Также под поверхностью нет слоев грязи, гравия или руды. Но из-за сжатия Octree у него всего 35 057 узлов. Смотрите на Рис. 3.

Если мы сделаем несколько типов блоков и раскрасим их по высоте, добавив слой воды внизу, мы получим что-то, больше похожее на пейзаж. (См. Рис. 4). Так как различных типов блоков несколько (что означает больше отдельных кубов, которые не могут быть объединены в более крупные кубы), то узлов 47 297.

Рис. 3: Ландшафт из Perlin noise

Рис. 4: Ландшафт из кубов

Теперь мы должны кое-что оптимизировать. Я нарисовал это самым тупым способом. Я просто пересекаю Octree, рисуя каждый из 8 верхних кубов. Они рекурсивно рисуют своих 8 детей и так далее, пока не нарисуется все дерево. Для листовых кубиков, просто рисуются все 6 сторон куба, с разной текстурой на каждой стороне. Это ужасно медленно!

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

Во-вторых, мы не должны рисовать кубы, которые находятся позади нас или за пределами того, что называется view frustum. Смотрите на Рис. 5, чтобы получить представление о том, как графика рисуется. У вас есть объем, который проецируется на ближнюю плоскость обзора (ваш экран), находящуюся перед точкой камеры. Все кубы вне этой усеченной пирамиды не будут видны, поэтому нам не следует их рисовать. Для проверки, я строю сферу вокруг каждого из кубов, и проверяю, находится ли эта сфера справа от каждой из шести сторон фрустума. Это немного дорогой тест для каждого куба, но, к счастью, мы не должны тестировать их по отдельности.

Самое приятное в Octree то, что мы можем сделать этот тест на узлах дерева по мере того, как мы его проходим. Например, если один из восьми верхних кубов находится вне поля зрения, то нам не нужно заглядывать внутрь. Все его дочерние кубы также будут снаружи. Смотрите Рис. 6. Я сместил края вида на 25% от истинного края экрана. Вы можете видеть, какие кубы все еще рисуются. Большие кубы - это те, что выше в дереве, у которых нет дочерних.

Рис. 5: Что видит камера

Рис. 6: Обрезка дерева

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

Наконец, мы все еще рисуем кубики, которые зарыты в землю и не видны. Нам нужно пропустить кубики, которые не соприкасаются с воздухом. Есть пара способов сделать это. Мы можем просто спросить, прежде чем рисовать каждую грань куба. Мы вычислим положение блока перед этой гранью и спросим дерево, есть ли там блок. Это не так медленно, как кажется. Поскольку Octree - это дерево, то для нахождения блока требуется всего 7 сравнений (потому что мы сделали дерево 7 уровней глубины, или 2⁷=128 кубов по горизонтали). Однако для больших блоков будет особый случай. Если, например, у нас есть блок 4 на 4 на 4, который весь состоит из почвы, то нам придется спросить о каждом из 16 блоков, которые могут коснуться одной из его граней (см. Рис. 7). Большую сторону блока можно увидеть, если на ней есть открытые места.

После того, как алгоритм "закопанного" был применен ко всем кубам, мы, в основном, только раскрашиваем внешние блоки. Мы также рисуем стены любых пещер или дыр. Подавляющее большинство блоков просто не видны, и мы не тратим на них время. Смотрите на Рис. 8, чтобы увидеть вид из-под земли. Все внутреннее пространство больше не рисуется.

Рис. 7: Когда сторона открыта

Рис. 8: Все, что под землей больше не рисуется

Если спрашивать соседа каждой грани каждого куба слишком медленно (и это так), то можно оставить набор из шести флагов на каждом кубе. Эти флаги покажут, обнажена сторона куба или нет. По мере того, как мы добавляем или удаляем кубы в мире, нам нужно будет обновлять всех шести соседей измененного куба, устанавливая флаги, открыты они или нет. Также нам понадобится установить флаги нового куба, исходя из того, какие соседи у него есть. С помощью этих флагов мы можем быстро решить, какие грани рисовать по мере того, как мы рисуем все дерево.

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

Update: Один из комментаторов, Florian Bösch, написал свою статью про проблемы рендеринга блочного мира. Это выше головы любого, кто не глубоко разбирается в программировании графики (включая меня!), но взгляните на видео.Я унижен!