Разработка игры. Бродилка. [Лог#5]

Концепты локаций – это для меня что-то новое.
Теперь же нужно их изобразить, дабы представить публике моё виденье игрового мира. И тут небольшая проблема, дело в том, что вид в игре планируется сверху с небольшим углом, думаю, такой вид не очень удобен для концептов, но зато был бы достаточно точным, однако, удобнее изображать какие-то детали или «пейзажи» используя разные ракурсы (относительно игрового вида), так было бы проще для моделей (если мы говорим о статичных элементах уровня, вроде, их называют пропсы (англ. props)).

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

Локация: Лес \ Джунгли \ Заброшенное место

Вообще суть практически всех локаций должна заключаться в следующем: заброшенные здания, лаборатории, возможно заводы, заброшены на столько, что все покрылось мхом (в прямом смысле), честно говоря, я не знаю как такие изображения правильно гуглить, дабы показать вам «вот видите? Вот так, только по мультяшнее». Куда делись люди? Что с ними случилось в этих местах и почему главный герой остался? – это вопросы сюжета, который я пока не могу раскрыть ( а есть ли он, этот сюжет ).

Главная идея этой локации – «победа» природы над техногенными штуками. Основной дух локации в том, что главный герой не понимает, что «вот это старый заброшенный завод» т.е. постройки и техника, и любые следы жизни людей не основные в этом месте т.е. среди хвойных деревьев можно найти завалявшийся «бульдозер», но в такой мини-сценке основной упор был бы не на этом бульдозере, а скорее на ель, например. То есть локацию скорее можно описать как ЛЕС с руинами, нежели заброшенное здание в лесу.

Брошенный погрузчик?

Это по моему и называется пропсами.

Локация: пещеры, около скалистые места
Что скрывается в пещерах? Возможно, это будет сюжетным поворотом, если вы не читали диздок. В пещерах – лаборатории и всякие помещения, которые «пострадали» от природы меньше. Собственно примерно в этих местах и начинают появляться мутанты, и количество роботов возрастает.

К сожалению ничего показать не могу, но думаю отличными референцами могут послужить некоторые локации из игры Portal 2 (именно из второй части, а не первой).

О генерациях «подземелий» много писать не буду, возможно, это будет даже целый отдельный лог.
Как генерировать и что – это сложная тема, могу лишь сказать, что подземелья будут собираться из 3Д тайлов (насколько мне известно в WarCraft III используется подобная техника для горных возвышенностей ). Имеем набор из, например, 16 таких тайлов, а программа, на основе генерированных данных (карта проходимости и высот) «подставляет» тайлы в локацию (локация изначально пустая конечно).

Вообще, если локации будут достаточно большими, то есть большая вероятность того, что появятся тормоза. Повысить производительность помогут различные деревья – QuadTree, OctTree или BSP.
Игровая механика предполагает больше действия по плоскости, а следовательно и локации, уровни и подземелья – будут «распластаны» по плоскости и отсюда следует, что можно выбрать QuadTree т.к. он по большей части для 2Д игр, но может и применяться и для 3Д ( если высота, как в нашем случаи, сильно не меняется ).
Можно было бы использовать обыденный QuadTree, однако, это лог велосипедописания и изобретения колеса! Следовательно, можно экспериментировать во всём и организация деревьев – не исключение. Эксперимент заключается в скрещивании QuadTree и BSP, вот в чём его суть:
Мы делим нашу «большую коробку локации» (изначальный лист для дерева – корень) не на квадраты, а пополам, ось деления чередуется — при первой итерации мы поделим, например, по горизонту, а вторая уже по вертикали. Примерные просчёты были и они говорят о том, что QuadTree и наше дерево практически одинаковы по сложности для нахождения точки в листьях.
Но игровые объекты – не точки, они ведь имеют, например, 3Д модель – какой-то объём, поэтому каждому объекту надо задать или рассчитать радиус.
Точка в пространстве и радиус – вот что является входным параметром для расчета того, в каком узле находится объект.
Идея BSP в разделении пространства пополам используется в играх типа Half-Life, Quake и Doom, для определения относительно чего же делить пространство выступают статичные полигоны (геометрия уровня).
В моей же реализации вместо полигонов сцены берутся фиксированные (рассчитанные) плоскости т.е. не зависит насколько сложная геометрия уровня, всё равно разделяться будет по правилу деления ограничивающей коробки ( Bounding box ).

Вот как будет делиться пространство:

Красная точка — объект который нужно найти (определить в каком узле).
Желтая линия — плоскость деления.
Оранжевый крест означает «пропуск» узла т.к. он не подходит под условия.

И какая же примерная структура узла такого дерева? Вот некий Си подобный псевдокод:
struct sQBSPLeaf
{
sPlane *plane; // Вообще, все плоскости, которые могут быть, можно рассчитать
sQBSPLeaf *leafs[2]; // в каждом узле может быть только два потомка

TArray<CGObject*> objects; // Объекты, которые находятся в текущем узле
TArraygeometryIndexes; // Индексы геометрии? Что?
// Вообще можно ещё добавить и массив вершин, но это если у вас просто гигантские локации
};

Зачем там какие-то индексы для геометрии? Что это вообще? Дело в том, что при больших локациях тормоза могут вызывать не только многочисленные объекты, но и количество отправляемых на обрисовку треугольников. Если вы понимаете как устроены 3Д модели ( а геометрия локации по сути одна большая модель ), то скорее всего знаете, что она состоит из вершин и индексов. Важной частью являются эти самые индексы – они указывают, какие вершины пойдут на обрисовку из этого можно сделать такой вывод, что хранить все вершины можно в каком-нибудь контейнере (буфере), а индексы вершин в другом месте, например, узлах дерева и использовать индексы только видимых узлов, что по идее должно дать прирост производительности.

Как же раскидать индексы по этим узлам? Вот что я предлагаю:
Скопировать (хотя можно и не делать этого) изначальный набор индексов.
Начать проходить наше дерево, при этом брать 3 индекса ( 3 вершины полигона ) и проверять, если хотя бы одна вершина находится в узле, то добавляем эти 3 индекса в список узла и удаляем их из изначального списка, а иначе идём дальше и проверяем следующие 3 индекса.
Такое повторить для каждого узла.

Выглядит вроде нормально, но есть узкое место – один большой полигон. Что если одна вершина в узле А, а другая в узле Б, а третья вообще, например, в Д. И как быть? Ведь этот полигон записан в узел А, если этот узел не будет виден (если мы находимся в узле Д, например ), то и рисоваться он не будет – нужно решит эту проблему, а вот как решить – немного другой вопрос, нельзя просто добавлять два треугольника к разным узлам, ведь если мы видим и А и Б, то такой треугольник нарисуется два раза, что может вызвать графические артефакты ( Z-fighting ), можно конечно добавить какую-нибудь проверку на подобные полигоны, вроде «в данном кадре этот полигон уже рисовался?» и если ответ да, то мы не рисуем его снова, но такой подход требует дополнительных затрат. Есть ещё одно решение, но оно увеличивает количество полигонов в сцене и требует пересчёта всех индексов – разрезание полигонов, кстати, именно так и работает BSP от Quake, Doom и Half-Life – берётся плоскость полигона и по ней разрезаются другие полигоны ( Кто работал с Hammer Editor скорее всего поймут о чём я, хотя в редакторе это не отображается )

Об определении видимости могу посоветовать почитать про Frustum culling, конечно его реализовать я тоже постараюсь ( в плане логов ).

Проблема «я не вижу своего игрока за этим лесом\стеной\горой!» — серьезной недоделкой может оказаться, но это можно решить, главное понять, что должно быть на выходе, например, подсветка силуэтов или «удаление» преграждающей геометрии, возможно прозрачность уменьшить у неё. Если решение прибегает к изменению визуальных данных геометрии( как отображается уровень ), то должен напомнить, что весь уровень – одна большая 3Д модель и «выключить» её небольшую часть будет проблематично, однако, мы же «распихали» большую модель по различным наборам индексов( для дерева ), почему же нельзя использовать подобное решение? Мой ответ такой: это будет некрасиво, да-да, всё дело в красоте отображения, согласитесь, если вдруг у вас пол локации на экране становится прозрачной, даже пол! Это не очень хорошо, поэтому я думаю, что решение кроется где-то в пост-эффектах т.е. мы действительно можно «обрезать» локацию, но потом снова рисовать её полной, а в пост-эффекте смешивать эти два результата по определённому правилу.

Собственно вот так примерно должна будет выглядеть игра, по крайней мере вид камеры:

Что дальше?
Скорее всего стоит ожидать «Думы о движке игровом», там я постараюсь описать, что же из себя будет представлять игра с точки зрения кода, конечно, в логе этого кода будет минимум. Больше будет размышлений и описания как это должно работать, возможно, будут диаграммы какие-нибудь для лучшего понимания.
Есть вероятность бонус-лога, где будут исключительно концепты локаций, ведь я обещал передать атмосферу, а тут ничего атмосферного и нету вовсе, поэтому возможно будет некий «Лог #5+».