Источник

Игра «Тарас Бульба и платформы Хулиона» многих удивила своим генерируемым миром. Эта игра победила в конкурсе лабиринтов-платформеров. В статье рассказывается, как делаются игры с подобными лабиринтами, как сделать красивые пещеры, и про то, как их запутать.

1. Палитра.
2. Топология
3. Форма пещер
4. Текстуры
5. Предметы и освещение

1. Палитра.

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

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

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

Есть очень избитый приём, я не знаю как он называется, но я очень часто его замечаю. Посмотрите на эту картинку:

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

Для выпускников вуза удобна оранжево-голубая цветовая плоскость:

То есть это все цвета, для которых:

G=(R+B)/2;

Ну можно немного от неё в стороны уходить, но недалеко.

Любая некрасивая картинка становится удивительно стильной, если её цвета спроецировать на эту плоскость. Наверное, у художников этот приём имеет название, типа «цветовая компрессия» или что-то такое, но я не в курсе.

Смотрите, вот чудный оригинал:

А теперь я беру и проецирую её на эту оранжево-голубую плоскость:

Шикарно же! Возьмите любой фотоконкурс, наверняка в призёрах будет такая оранжево-голубая поделка. Короче, отличный приёмчик для выпускников вуза. Я тоже не побрезговал. 🙂

Можно другой фильтр применить, тоже стильно выходит:

Короче, одна из причин милой картинки в игре — это обрезанная палитра. Вообще 8-битный фон был вынужденной мерой, потому что фон является огромной картинкой на 14 мегабайт, и если бы не 8 бит, он был бы намного больше. Ну и ограниченный набор пришлось как-то придумывать, как получше разметить. Я как раз применил такую вот почти плоскую палитру:

  // первые 11 цветов служебные
  for (int i=11; i<256; ++i)
  {
    const int r = (i-11)%7;
    const int g = (i-11)/7%5;
    const int b = (i-11)/35;
    colorTable[i] = tbal::Color (r*28+g*8+b*3+37, r*14+g*18+b*13+21, r*6+g*10+b*29+5); 
  }

Наглядно вот так:

Цветов хоть завались, выбирай любой. Ну да, она не совсем плоская, но рядом.

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

Тот же страшный скрин, но в этой палитре, будет таким:

Мутновато, но тут контрастность надо как-то поправить, и ни разу не заметно, что 8 бит.

2. Топология

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

Для зерна-по-умолчанию (15071987) генерируется такая топология:

Треугольнички — это однонаправленные стрелочки, то есть можно пройти только в одну сторону. При этом горизонтальные односторонние переходы на самом деле становятся двусторонними после первого же прохода с нужной стороны (дверь открылась и так и осталась), но генератор это не учитывает. Односторонние проходы наверх в генераторе запрещены.

Цветные линии — это двери, требующие ключ соответствующего цвета (буква «К»). Цветные клетки — это до которых можно добраться только зайдя за соответствующую линию.

Итак, как такую картинку сгенерировать? Для начала надо построить один кольцевой маршрут. План такой: Мы выходим из клетки (0,0) и идём «куда глаза глядят». Приоритетное направление — на новые пустые клетки.

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

Условие конца: дойти до клетки (0,0), либо до другой клетки, где мы были до первого необратимого хода (это клетка (0,0) и ещё две следующие). В алгоритме стоит ограничение на число попыток, и через N шагов мы попали черт знает куда, а вовсе не в начало:

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

Некоторые проходы стали обратимыми, плюс добавились два новых прохода, за счёт рандома один из них стал односторонним, один стал двусторонним.

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

Но нам этого мало. Давайте к этой петле новую прикрепим. Берём произвольную посещённую точку и идём из неё в случайную сторону, приоритетно выбирая путь в сторону пустой клетки. Через N шагов, если мы не вернулись на старый маршрут, идём назад кратчайшим путём к клетке, начинающей новый маршрут, избегая предыдущих маршрутов.

Итак, добавили вторую петлю:

Я покрасил в цвет клетки второй петли. Уже сейчас можно ставить дверь-на-ключе перед жёлтыми клетками, как видите. При этом жёлтый ключ ставится на любую чёрную клетку.

Повторять, пока не надоест:

Я ещё один новый маршрут покрасил цветом.

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

Осталось повесить двери-на-ключах (угадайте куда) и расставить сами ключи. Алгоритм расстановки ключей простой: жёлтый ключ можно ставить на любую чёрную клетку, красный — на любую жёлтую, зелёный — на любую красную и т.д. Но я ставлю не на любую. Я выбираю самую дальнюю клетку от предыдущего ключа. В итоге получается та картинка, что вы видели изначально.

Дальше мы каждой клетке назначаем номер, в каком порядке её проходить. В зависимости от номера выбирается, какие бонусы в эту клетку размещать и каких монстров. Для клеток, расположенных в стороне от кратчайшего пути, слегка понижается вероятность напороться на кучу монстров и повышается до 100% вероятность найти бонус. То есть боковые отростки и тупички, как правило, хранят хорошие вещи. Так делаются «секретики».

Алгоритм подходит и для 3Д, нетрудно придумать, как адаптировать алгоритм для многоэтажного 3Д-уровня.

3. Форма пещер

Настало время генерировать тот самый огромный битмап.

Прежде чем нагенерировать пещеры, надо порезать уровень на сегменты. Сегмент — это горизонтальная часть уровня от стены до стены. Итак, режем уровень на сегменты, вот я все сегменты нарисовал:

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

Для туннелей выбор формы пещеры простой — прямоугольник, высота случайная в небольших пределах. Для пещер хитрее. Форма пещеры задаётся двумя линиями y(x), одна линия для пола, другая для потолка. Линии можно генерировать Перлином, наверное, попробуйте им. Но я сделал иначе. Я генерирую координаты последовательно. Сначала генерируется пол. Потом аналогично потолок, только он прибавляется к полу и у краёв сегмента делается наклонный потолок.

Самый простой способ — это:

y[x+1] = y[x] + random(-1..1)

Но это приведёт к отсутствию длинных наклонных участков, это не очень красиво.

Я сделал так, чтобы рандом как бы запоминал профиль последнего участка. Я запоминаю профиль в отдельной переменной. Этот профиль случайно меняется на random(–1..1) при переходе к следующей координате, при этом он ограничено диапазоном –3..3

Приращение берётся как

(профиль + random(-2..2)).clamp(-1..1)

То есть к профилю прибавляем этот рандом, результат урезаем между –1 и 1, и это и есть то, на сколько надо изменить координату при переходе к следующему пикселю.

Так я генерирую кривую линию, идущую из точки x1 вправо. Аналогично генерирую линию из x2 влево. А потом смешиваю их, причём с разным весом. Вблизи точки x1 вес первой линии единичен, вблизи точки x2 вес второй линии единичен.

Сгенерировался такой сегмент (хранится как два массива y[x]):

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

Раскидав сегменты, получаем такую картинку:

То есть просто берём и кидаем сегменты друг на друга, это просто.

Теперь ещё надо заполнить вертикальные проходы. Форма прохода зависит от того, какие сегменты он связывает. Если нижний проход — туннель (либо снизу ад, а сверху туннель), то проход прямой, иначе кривой. Кривой проход тоже генерируется тем же алгоритмом генерации кривой линии, только немного не так: сначала генерируется форма осевой линии, а форма левой и правой границы отсчитывается от осевой линии.

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

Ну и ещё надо в проходах нарисовать лестницы, тут не вижу сложностей.

4. Текстуры

В игре используется:
1. Шум Перлина.
2. Клеточная текстура, это когда заранее выбирается N случайных точек, а потом текстура заполняется так: для каждой точки (i,j) берётся разница расстояний до двух ближайших точек.
3. Волновая текстура — тоже берётся N случайных точек, а потом для каждой точки суммируются синусы расстояний до них.
4. Просто шум, рандом в каждой точке.

Все текстуры имеют размер 64х64.

Итак, вот так выглядит типичный Перлин:

Мы видим зацикленное нечто. Я применил несколько приёмов расцикливания.

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

Чтобы его «расциклить», надо сгенерировать два Перлина, потом один из них растянуть в 7/16 раз, другой в 17/16 раз (чтобы числа плохо делились друг на друга и в итоге период был побольше) и взять полусумму:

int k = int(level.bunker1[sy*17/16][sx*17/16]<<7)+int(level.bunker2[sy*7/16][sx*7/16]<<7);
pixel = ColorToByte(tbal::Color(k,k,k));
//примечание - для текстур оператор [] сам берёт остаток по модулю

Получается совсем иная картинка, где цикл найти довольно трудно:

Вот такой вот фокус-покус! Основное условия, чтобы это сработало — это возможность заранее нарисовать огромный битмап. Впрочем, для 3D игр тоже можно, особенно если движок поддерживает кеширование текстур.

Приём 2: сделать криво.

Вот так выглядит клеточная текстура без примесей:

Видно, где даже центры клеток находятся.

А теперь делаем так: заводим текстуру-невидимку, заполняем по Перлину. Или две текстуры-невидимки. Растягиваем в кривое число раз. Делаем выборки. Но выбираем из них не цвет… а смещение! Из первой невидимки выбираем dx, из второй dy, а потом на карту уже выводим из клеточной текстуры пиксель с координатами не (x,y), а (x+dx, y+dy). Тем самым прямые линии становятся кривыми. А за счёт растяжения невидимок в кривое число раз кривизна становятся не повторяющейся:

        int dx = int(level.caves2[sy*17/16][sx*17/16]<<5);
        int dy = int(level.caves2[sy*5/4][sx*5/4]<<5);
        int r = std::min(255, int (level.caves1[sy+dy][sx+dx]<<8));
        int g = 0;

        pixel = ColorToByte(tbal::Color(r,g, std::min(r,g)));

Ой, ну у меня тут вообще одна и та же невидимка, только растяжение разное. Ну и ладно. Результат такой:

Зацикленность всё равно видна, но она теперь стала немного неявной.

Кривая кирпичная кладка сделана аналогично, ну и ещё пару Перлинов намешано сверху.

Для комнат-в-клеточку использовался просто шум. Только он растягивался в 16 раз и между текселей рисовались клеточки. Никаких смешиваний и прочих хитростей — растяжения в 16 раз достаточно.

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

5. Предметы и освещение

Освещение сделано просто, для каждого пикселя перебираются ближайшие источники света (не совсем все благодаря хешу), потом цвет умножается. Вернее, не для каждого, а только для пикселей, у которых обе координаты делятся на 8, для остальных интерполируется, но это не сильно ускоряет. В аду равномерное освещение максимальным значение, в лесу тоже равномерное освещение на 1/4 уровня, в остальных местах света изначально нет. Ещё к освещению прибавляется рандом, чтобы резкие переходы между уровнями заменялись на дизеринг.

Тут, в общем, не о чем разговаривать, кроме одного нюанса. В пещерах встречаются и синие, и жёлтые источники света. Цветное освещение в 8 битах — это уже необычно и проблемно. Смотрите, какая эта текстура на самом деле мерзко-белёсая:

Но кто про это узнает, если рядом с жёлтым источником света оно и незаметно ни разу? Зато без этой белёсости не будут работать синие источники света. Поэтому пришлось вот так вот текстуру испоганить.

Предметы — деревья и кустики — это фракталы. Провода тоже фракталы. Фонарики — дуга с кружочком. Лампочки — линия с кружочками на концах, или кружочек на палочке. Ящики — квадратики в полосочку. Для расстановки ящиков берётся хитрый рандом, который избегает мест под лестницей или над проёмами. Короче, про предметы нечего говорить тоже.

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

Из-за того, что отсчёт цветов делается от коричневого, а не от чёрного, картинка сильно «зажелтена». Кстати, небо тут не синее, а красное, проверьте пипеткой, будет (40,34,34).

В аду сверху две случайные линии, снизу — сжатый по вертикали Перлин, между ними случайные отрезочки:

Вот и всё.

Про двери и монстров говорить не буду, нарисовано всё в Painte. Количество контента достигнуто за счёт MadSkills, в ассетах картинки все есть, можете оценить, называется «программисты рисуют, пытаясь сделать поскорее».