Вороной, Манхэттен, рандом

Уровень сложности Простой Время на прочтение 34 мин Количество просмотров 2.8K C++ *Разработка игр *Алгоритмы *Математика *Godot * Ретроспектива

Это история про то, как не довести дело до конца, но получить уйму опыта, и вообще ни разу не обломаться.

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

Осторожно, очень много картинок!

С чего все началось

Я C++ разработчик в небольшой геймдев студии. У меня есть друг Илья. Он художник, артовик, дизайнер, у него есть своя ламповая студия графического дизайна.

В какой-то момент Илья постучался ко мне и сказал, что у него есть пулл работ, зарисовок, концептов, которые вполне можно было бы использовать для 2D инди-игры, и если у меня есть желание, то мы могли бы на пару замутить что-нибудь интересное в свое свободное время.

Я подумал, почему бы и нет, и согласился.

Стилистика

Мы рассудили, что суть игры и лор мы постараемся черпать из контента, на базе которого решим делать игру. Мы порылись в концептах Ильи и выбрали вот такую стилистику и игровой мир:

Подробнее про концепт в этой стилистике можно почитать в этой ретроспективной статье от Ильи.

Было решено в качестве пробы пера сделать небольшой прототипный уровень, чтобы просто посмотреть, как у нас будет выходить. Требования к уровню были минималистичными:

• Плоский уровень, вид сбоку, главный герой идет слева направо

• Несколько уровней заднего фона, которые должны создавать эффект параллакса

• Базовое передвижение главного героя: ходьба, бег, прыжок, анимация покоя

• Несколько платформ, куда можно запрыгнуть

Задачи обозначены, цель ясна, но у нас все еще не был выбран игровой движок.

В поисках игрового движка

Для проекта я хотел выбрать какой-то простой игровой 2D движок, на котором вместе с тем при необходимости можно было бы решать сложные задачи. Мне хотелось, чтобы я мог сесть и без долгих разбирательств добиться желаемого результата. Это в свою очередь требовало, чтобы у движка был какой-то простой скриптовый язык, на котором за пару минут можно что-то наваять без особых трудностей. Наличие редактора — строго обязательно.

С другой стороны я хотел, чтобы движок, при условии, что он мне понравится, мог бы использоваться мною в дальнейшем и для других проектов. Какой у тебя будет проект следующим, и что ты захочешь на нем делать — неизвестно; насколько проект будет требовать каких-то серьезных вычислений — тоже. Поэтому требуется, чтобы движок при необходимости давал возможность написать часть функционала на взрослом компилируемом языке вроде C++ или Rust.

Какие движки рассматривались и были отвергнуты:

• Unreal Engine. Этот движок мне знаком. Но это как стрелять из пушки по воробьям применимо к нашим задачам, да и весит он десятки гигабайт, а UE5 переваливает за сотню. Совсем не хотелось прибегать к нему, хотя это был мой запасной вариант;

• Unity. Ничего не могу сказать. Это самый популярный выбор тех, кто делает 2D-игры. Но уж как-то не лежало у меня сердце писать на C#. Плюс по какой-то абсолютно субъективной причине у меня сложилось к движку какое-то скептическое отношение еще с давних времен;

• Bevy. Очень молодой движок, игру нужно писать на Rust — это меня максимально подкупало. Но фатальные минусы затмили все: нет редактора, в движке жестко навязывается ecs-подход, и архитектуру игры заставляют буквально прогнуть под эту парадигму. После этого никакую миграцию на другой движок вы не сделаете от слова совсем — просто выкидываете весь код и пишете все с нуля.

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

Скажу сразу, я не разочаровался в выборе, и движок меня за все время ни разу не подвел. Что я могу сказать о Godot по прошествии времени:

• У него есть свой скриптовый язык GDScript схожий с Python. Он простой и удобный;

• В качестве альтернативы можно писать на C++ или на C#. Забегая вперед — C++ мне в итоге очень как пригодился. При желании на Godot существуют и биндинги для других языков, например для Rust;

• Godot — апогей простоты. Ты буквально берешь и делаешь. Ни долгих вчитываний в документацию, ни раскачки. Уже после перового базового туториала ты реально берешь — и делаешь.

Могу ли я сказать что-то плохое про Godot? Его логотип просто ужасен.

Godot Logo

Прототипный уровень

Т.к. уже было сказано, что разработка на Godot не представляет из себя никаких трудностей, не удивительно, что в короткий срок прототипный уровень был реализован. Выглядело это так:

Размер всего уровня вытянутый, показать его одной картинкой трудно, но вот вам скрин из движка, чтобы оценить:

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

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

В конце концов на одной из встреч прозвучали поворотные для проекта слова Ильи: «Слушай, я тут подумал, side scrolling платформер — это как-то скучно, особо не развернешься. Давай замутим какой-нибудь рандомно-генерируемый мир с биомами, как в моей любимой Don’t Starve».

Вот тут-то я и напрягся, потому что понимал, насколько это может быть нелегко. Я выказал все опасения насчет непредсказуемости рандома, трудностью совладания с ним, что проект станет ощутимо сложнее. Но Илья ответил: «А давай попробуем». Я подумал, почему бы и нет, и согласился. И мы стали пробовать.

Как генерируют биомы в этих ваших интернетах

Свое исследование на предмет, как можно генерировать рандомные карты и биомы, я начал с шикарной статьи Polygonal Map Generation for Games за авторством Amit Patel, которая, будучи написанной аж в 2010 году, наверное, стала живой классикой. Я видел, как на нее не раз и не два ссылались разные люди, соприкасавшиеся со схожей задачей. А на хабре есть перевод этой статьи. На самом деле это не просто статья — это целый конгломерат статей от одного автора, где он планомерно раскрывает все аспекты его наработок по данной теме. Статья в общем целом про то, как генерировать острова с биомами, реками, дорогами; как сделать так, чтобы это выглядело убедительно и реалистично. Например, вот такой полностью рандомно сгенерированный и процедурно отрисованный остров:

Это было шикарное чтиво, я до сих пор помню эту статью от корки до корки, я даже делал на нее конспект с пометками у себя в Obsidian, настолько мне этот труд запал в душу:

Статья настолько всеобъемлюща, что для нашего проекта было достаточно только самых базовых идей, заложенных в нее; буквально первых шагов алгоритма:

• Генерация рандомных точек на 2D-плоскости;

• Построение карты Вороного по этим точкам;

• Назначение каждой ячейке карты Вороного типа биома.

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

Не преминул я и почитать, как генерировали свой мир в Don’t Starve — на статью об этом я наткнулся на fandom-wiki по игре. В ней так же говорилось, что отправная точка их генерации — карта Вороного.

Карта Вороного

Я слышал про существование такого понятия, как диаграмма Вороного, и знал, что она разбивает 2D пространство на регионы. На этом мои познания заканчивались, и я пошел в Википедию. Суть вкратце — диаграмма имеет вот такой вид:

Это 2D-пространство, разбитое на участки; внутри каждого участка есть точка. При этом карта построена не абы как — она обладает следующим свойством: если указать на произвольное место на такой карте, то участок, в который вы при этом попадете — это участок с самой близкой для вас точкой из всех точек на карте. Другими словами, если представить, что карта Вороного — это гигантский парк, а точки — это общественные туалеты, то, если вы сейчас находитесь в красном полигоне, то бегите к туалету, который принадлежит этому полигону — остальные туалеты будут гарантированно дальше, это основополагающее свойство диаграммы Вороного. Если вы на границе полигонов, то подбрасывайте монетку и бегите к любому из двух туалетов соседствующих участков — по всей границе расстояние до обоих туалетов одинаково. Если вы на углу участка, вам сложнее всего — вы на одинаковом расстоянии до трех а то и до четырех туалетов сразу.

В общем, суть вы поняли. Карта Вороного часто используется в картографии и в других прикладных алгоритмах, где требуется найти ближайший объект на плоскости. А в играх так и вовсе диаграмма Вороного может использоваться просто как универсальный алгоритм построения случайных полигонов на игровой карте. Вам достаточно нагенерировать на плоскости случайные точки и построить по ним карту. Именно это и было в моих планах, но оставалось понять, как реализовать алгоритм построения диаграммы.

Русскоязычная статья на Википедии оказалась не то чтобы детальной по алгоритмической части, поэтому я заглянул в англоязычную версию статьи — англоязычные, как правило, длиннее и богаче на подробности. Статья действительно оказалась посерьезнее. А еще я увидел там это:

И это меня уже серьезно заинтересовало — посмотрите на картинку справа за подписью «Manhattan distance» — я буквально в момент понял, что это ровно то, что нужно для нашей игры. Взгляните на эти концепты, и вы тоже это увидите:

Четкие, прямо-диагональные линии границ биомов — прямое попадание в нашу рубленую стилистику. Это как если бы обычную карту Вороного взяли и стилизовали четко под арт Ильи. В общем, я понял, что хочу разбиение игровой карты на биомы такой формы. Такой и больше никакой.

Расстояния

Но как такая разновидность диаграммы строится, и что такое этот ваш Manhattan distance? Ответы снова пошел искать в Википедии. Вкратце: Манхэттенское расстояние — это альтернативный способ считать расстояние между двумя точками.

Как мы обычно считаем расстояние от пункта A до пункта B? Мы прокладываем между точками прямую и измеряем ее длину. Эта длина и будет расстоянием между A и B. Это Евклидово расстояние, его формула общеизвестна:

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

Посмотрите на эти три пути из одной точки в другую:

Все три пути — это три варианта наикратчайшего пути из точки в точку. И этих вариантов на самом деле еще больше. И все эти наикратчайшие пути имеют одно и то же расстояние. В случае с точками на изображении — это 12 клеток. Это и есть Манхэттенское расстояние. Оно достигается большим количеством вариантов, но имеет вполне себе конкретную величину, которую можно посчитать по формуле:

Манхэттенское расстояние так же называют расстоянием городских кварталов или taxicab space. А Манхэттенское оно потому что уличная планировка Манхэттена имеет выраженную блочную структуру. А еще Манхэттенскими расстояниями ходит ладья по шахматной доске.

Так вот, применительно к карте Вороного: от того, какой метрикой мы будем измерять расстояние, будет зависеть, как будет выглядеть карта Вороного. И метрик, оказывается, есть бесконечное множество. Т.е. существует бесконечное множество способов посчитать расстояние? В общем-то да, есть даже обобщающая формула, называемая расстоянием Минковского:

где

— это так называемый порядок.

А теперь следите за руками: если в формулу подставить

, то мы получим формулу Манхэттенского расстояния; а если подставить

, то получим

что в общем-то эквивалентно

т.е. Евклидовому расстоянию.

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

. При

формула выродится до так называемого расстояния Чебышёва:

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

превращает эту формулу в

. Если кто-то в комментариях сможет доступно на пальцах это объяснить мне, буду очень благодарен.

В общем, я смекнул: велика вероятность, что мне захочется использовать разные метрики, поэтому теперь у меня в загашнике есть универсальная функция для этого:

double distance(Point a, Point b, SpaceMetric metric = SpaceMetric::Euqlid) { switch (metric) { default: case SpaceMetric::Euqlid: return sqrt(pow(b.x — a.x, 2) + pow(b.y — a.y, 2)); case SpaceMetric::Manhattan: return abs(b.x — a.x) + abs(b.y — a.y); case SpaceMetric::Chebyshev: return std::max(abs(b.x — a.x), abs(b.y — a.y)); } }

Ну или если вам известна метрика на этапе компиляции, и она не будет меняться в рантайме, то лучше даже так:

template<SpaceMetric METRIC = SpaceMetric::Euqlid> double distance_t(Point a, Point b) { if constexpr (METRIC == SpaceMetric::Manhattan) { return abs(b.x — a.x) + abs(b.y — a.y); } else if constexpr (METRIC == SpaceMetric::Chebyshev) { return std::max(abs(b.x — a.x), abs(b.y — a.y)); } else // SpaceMetric::Euqlid { return sqrt(pow(b.x — a.x, 2) + pow(b.y — a.y, 2)); } }

Бонус

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

Он показывает, как разнится расстояние между двумя точками у муравья, короля и ладьи на шахматной доске. Муравей ходит Евклидовыми расстояниями, и его расстояние будет равно классической формуле гипотенузы для катетов длиной 4 и 3; т.е. муравей пройдет от точки до точки за 5 единиц. Король ходит по метрике Чебышева, поэтому он может считерить — его диагональные ходы равны горизонтальным и вертикальным, поэтому он дойдет до цели за 4 шага. Ладья ходит нашим любимым Манхэттеном и замыкает тройку лидеров, придя к финишу аж за 7 шагов.

Наивная реализация

Во-первых, сразу стоит оговориться, что существует самый простой и примитивный алгоритм построения диаграммы Вороного с любой метрикой. Он заключается в том, что мы перебираем каждый пиксель 2D-пространства и сравниваем расстояние этого пикселя до каждой из точек (если угодно — туалетов) на этом пространстве. Когда мы находим самую близкую к пикселю точку, мы понимаем, что пиксель относится к полигону с этой точкой и закрашиваем этот пиксель в соответствующий цвет.

Так можно запросто построить и диаграмму Вороного и в taxicab space (т.е. с Манхэттенскими расстояниями). Поэтому я, чтобы оперативно оценить карту Вороного в действии, реализовал этот алгоритм прямо на GDScript в Godot, чтобы пощупать руками карты с разными метриками. Если отбросить всю мишуру и нюансы, то код алгоритма в вакууме будет выглядеть так:

for y in range(SIZE): for x in range(SIZE): var p := Vector2(x, y) var min_dist := 9999999.0 var belonged_site := -1 for site_idx in sites.size(): var site := sites[site_idx] var dist := distance(site, p) if dist < min_dist: min_dist = dist belonged_site = site_idx var c := sites_colors[belonged_site] draw_point(p, c)

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

Евклид. Классическая карта Вороного

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

Чебышев

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

Карта с порядком Минковского p=1.5

Фактически это усреднение карт Евклида и Манхэттена. При этом границы перестают состоять из прямых линий и превращаются в кривые. Такая карта Вороного вполне могла бы кому-то пригодиться, особенно если вам нужна стилизация с мягкими округлыми очертаниями. Тем более, что с

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

Но осторожно! С вами может случиться вот это:

p=0.5

Да, если мы уходим в слишком мелкий порядок

, пространство начинает нехило искажаться, и карта начинает принимать сюрреалистический вид.

В общем, с таким примитивным алгоритмом я смог наиграться с разными видами карты Вороного вдоволь. И укрепиться в своем желании использовать версию с taxicab-расстояниями. Но почему тогда бы на этом алгоритме не остановиться? А потому что он нежизнеспособен и обладает рядом фатальных недостатков и выбывает из нашего рассмотрения по куче причин:

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

• Умеет только заливать сплошным цветом. Алгоритм не рисует границы участков карты, он рисует именно сами участки, цветом. В итоге вы не сможете на свои участки ни натянуть текстуру, ни как-то процедурно красиво их обыграть — только сплошная заливка цветом, без границ;

• Скорость. У алгоритма ужасная производительность: его сложность —

  . И приходится перебирать все существующие координаты пространства, что сильно усугубляет картину. Так, построение карты размером 640×640 в среднем занимает 3.3 секунды, 1024×1024 — 7-8 секунд на ПК, рассчитанном на профессиональную разработку игр. Это ужасно долго для такой примитивной цветастой разукрашенной картинки;

Еще есть похожий, но более производительный алгоритм под названием jump flooding algorithm, но его мы тоже не будем рассматривать, поскольку он так же раскрашивает карту на части, а не строит полигоны.

В поисках нужного алгоритма

Хорошо, подумал я, значит мы поступим так: нужно просто взять и реализовать один из эффективных алгоритмов построения диаграммы Вороного — как правило со сложностью

и построением полигонов в качестве результата — но каждый раз когда мы будем вычислять расстояние, мы будем применять taxicab-версию функции расстояния!

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

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

Алгоритм Форчуна вообще строит границы полигонов карты Вороного параболами. Параболами, Карл! Где там применяется функция расстояния? Она там применяется, но для косвенных вещей. Мой план снова не будет здесь работать.

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

Поэтому я решил посмотреть на готовые библиотеки и пошел шерстить GitHub. Большинство решений ожидаемо были заточены под обычные Евклидовы карты Вороного без возможности использовать альтернативные метрики и построить нестандартную карту Вороного. Это было обидно, поскольку в том числе попадались хорошие высокопроизводительные библиотеки. Возможно, я плохо искал или искал не там, где надо — не знаю. По итогу мне попался лишь один проект, реализующий карту Вороного Манхэттенской метрикой, но с диковинным алгоритмом и на JavaScript. А с JavaScript мне не было особо что делать в парадигме проекта на Godot. Вот такая вот грусть.

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

А потом совершенно внезапно среди всего многообразия сомнительного ютубного контента я наткнулся на бриллиант: видео, в котором подробно и дотошно описывается математика, стоящая за картой Вороного и алгоритмом Форчуна в частности. Это настолько потрясающее видео, что всем интересующимся данной темой я рекомендую его посмотреть от начала и до конца — оно доступно объясняет природу алгоритма, причем с неожиданным выходом в 3D-пространство для того, чтобы потом вернуться в 2D-пространство и применить то, что было освоено в 3D. Звучит как крутой сюжетный твист. Уже теперь, в процессе написания статьи, я понял, почему наткнулся на это видео далеко не сразу: когда я стал искать его снова для этой статьи, я потратил, наверное, полдня, чтобы снова его отыскать. Проблема видео в его названии «How Parabolas Can Help Describe Nature and Business | Fortune’s Algorithm #some2». Ни слова о карте Вороного, только упоминание алгоритма Форчуна в самом конце. Любопытен и сам автор ролика, Alexa Joy — у него всего 3 видео и 170 подписчиков, и остальные два видео совершенно не такого масштаба, и от этого еще удивительнее, что он выдал такой хороший материал.

Так вот, помимо того, что видео само по себе оказалось очень увлекательным, в его третьей, последней части рассказывается про расстояние Манхэттена и его применение к алгоритму Форчуна. Но давайте сначала посмотрим визуализацию того, как этот алгоритм работает с Евклидовой метрикой:

Алгоритм Форчуна в действии

За идущей вниз горизонтальной линией, хитрым образом следуют параболы, пересечения которых рисуют границы регионов карты Вороного. Не буду вдаваться в хитрости самого алгоритма — как по мне, он достаточно головоломный. Что нас интересует, это как автор ролика смог мне доступно объяснить, что все теми же параболами можно нарисовать и карту Вороного в Манхэттенской метрике. Только парабола будет не Евклидовой, а представленной в Манхэттенском пространстве.

Как это? Давайте зайдем издалека. Как можно описать, что такое окружность? Это кривая, все точки которой имеют одинаковое расстояние до специальной точки — центра. Я конечно же намекаю на термин «расстояние» в этом определении. А что если попытаться построить фигуру, обладающую такими же свойствами, но чтобы расстояния мерялись в Манхэттенском пространстве? В Википедии есть показательное изображение такой фигуры:

Окружность в taxicab space

Как видите, все зависит от размера сетки, или «кварталов». Но если представить, что сетка бесконечно мелкая, то такая «окружность» приобретает очертания ромба! Да-да, это и есть окружность в taxicab space. Сообразно, в taxicab геометрии можно получить и другие фигуры. Например, парабола станет вот такой причудливой вещью:

Парабола в taxicab space

Если что,

не является частью параболы — это ее директриса. Напомню, что основное свойство параболы — это одинаковость расстояния до фокуса

и расстояния до директрисы

каждой точки на всей кривой параболы. Попробуйте взять любую точку на параболе и померять ее Манхэттенское расстояние (помним — это как ходит шахматная ладья) сначала до фокуса, затем до горизонтальной прямой. Оно всегда будет одинаковым, поэтому эта фигура и является taxicab space параболой.

Ну и наглядная анимация из ролика про работу алгоритма Форчуна, который строит диаграмму Вороного taxicab-параболами:

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

Я пробовал скачивать разные библиотеки, реализующие классический алгоритм Форчуна, и модифицировать их сообразно моему новому видению. Но делал я это достаточно неумело, можно сказать, вслепую, поскольку постоянно разбивался о зубодробильную математику и невозможность понять, как переориентировать ее на taxicab рельсы. Чтобы вы понимали, плывущие параболы в алгоритме — это лишь идея, концепция. Сам итоговый алгоритм настолько переработал и видоизменил эту концепцию, что от нее остались лишь какие-то абстрактные шаги, которые эффективным образом приводят к тому же результату, какой вы видите на гифках, что я показал выше.

Мои мытарства можно лицезреть в одном из черновиков, где я пытался укротить неевклидовы параболы:

Тяжело

В общем, да, я потратил на это очень много времени.

Найденное решение

Как вы понимаете, по итогу, я каким-то образом смог построить нужную мне карту Вороного. Но то, как я это сделал, вас сильно разочарует.

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

Так что да — всю предыдущую главу можно просто выкинуть. Зачем я заставил вас ее читать, чтобы обломать в самом конце? Ну, в этом есть свой смысл:

• Вы прочувствовали мой путь и мою боль;

• Вы, возможно, узнали столько же интересного, сколько узнал я в процессе этого увлекательного нырка в тупик.

А что я сделал в итоге. Я уже писал, что натыкался на реализацию диаграммы Вороного в taxicab пространстве, написанную на JavaScript. Я долго на нее смотрел, облизывался, запускал проект, видел, что этот код работает. У автора даже есть демо-страница, где показан результат работы его библиотеки.

А еще код алгоритма располагался в одном файле и занимался всего 800 строк. И я решился просто переписать этот код на C++. У меня проскакивала такая мысль еще тогда, когда я впервые наткнулся на проект, но тогда мне это казалось чем-то недостойным. Теперь же мне уже было все равно 🙂 Большая благодарность Joe Dragovich за его проект.

Для интересующихся — алгоритм, реализованный автором проекта — это хитрый алгоритм за авторством D. T. Lee и Chak-Kuen Wong, который дает возможность построить карту Вороного для любой метрики, включая метрику Чебышева

. Автор репозитория реализовал частный случай для taxicab space (

), просто потому что по его словам «This creates cells that have kinked edges and strange protrusions. In short, they just look cool!». Мои мысли один в один.

К слову, я попробовал почитать pdf с оригинальным текстом научной статьи про этот алгоритм 1980 года и умудрился понять практически все, включая все определения, леммы и теоремы вплоть до того момента, пока в конце не началось описание непосредственно самого алгоритма. Там пошла какая-то жесть, которую я не был способен воспринять. Обидно, но не сильно — ведь у меня на руках была готовая реализация алгоритма, который я принялся переписывать на C++.

А еще процесс адаптации кода на C++ был любопытным с точки зрения разности двух языков. Дело в том, что автор проекта написал код в функциональном стиле с использованием map, reduce, filter, forEach и подобного. Было интересно, как на современном C++ такие конструкции выглядят в сравнении с тем же JavaScript. Плюс у меня были развязаны руки (а не как обычно у плюсовиков), и я смог насладиться прелестями C++20 и его библиотеки std::ranges. Ну, как насладиться — вскоре стало ясно, что плюсовые рейнджи все еще сырые и будут таковыми продолжительное время. Так, вы не можете заменить вот такой JS-код:

data .map(…) .filter(…) .sort(…) .filter(…)

на C++ аналог вида:

data | std::views::transform(…) | std::views::filter(…) | std::views::sort(…) | std::views::filter(…)

поскольку адаптера std::views::sort не существует, есть только std::ranges::sort, который не поддерживает пайпинг |. А еще ranges не поддерживает accumulate и reduce, а превращение view обратно в контейнер через | доступен только в C++23.

А вот еще один курьез — сравните:

JS-код

// combine all the merge arrays let mergeArray = [initialBisector, …upStrokeArray, …downStrokeArray];

C++-код

// combine all the merge arrays std::vector<BisectorRef> mergeArray; mergeArray.reserve(1 + upStrokeArray.size() + downStrokeArray.size()); mergeArray.emplace_back(std::move(initialBisector)); mergeArray.insert( mergeArray.end(), std::make_move_iterator(upStrokeArray.begin()), std::make_move_iterator(upStrokeArray.end()) ); mergeArray.insert( mergeArray.end(), std::make_move_iterator(downStrokeArray.begin()), std::make_move_iterator(downStrokeArray.end()) );

Да, в C++23 подъехал std::vector::append_range, с которым код мог бы выглядеть приятнее, но даже плюсовик с развязанными руками в 2022 году не мог себе этого позволить. В комментариях можете написать более читабельные и короткие варианты этого кода. Главное условие — чтобы не нигде происходило копирования и было минимум аллокаций памяти.

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

Внедрение кода в Godot

Итак, C++ код был написан и оттестирован, и работал так же, как JavaScript-оригинал. Как теперь внедрить это добро в игровой движок?

Я уже говорил, что Godot помимо GDScript дает возможность писать и на других языках, в том числе и на C++. Делается это в рамках специальной технологии, которая в Godot 3 называется GDNative, а в Godot 4 — GDExtension. Я успел поработать с обеими. Базовый принцип их работы в любом случае одинаков:

• Вы пишете C++ классы или функции, используя C++-биндинги для движка Godot;

• При компиляции получается dll-библиотека;

• При запуске игры или игрового редактора dll-библиотека подгружается движком;

• Классы и функции, которые написали на C++ становятся доступны для дерева сцены и для GDScript;

• Вы используете интерфейс этих классов и функций, а они под капотом выполняются как быстрый, производительный native-код.

Внедрение C++-кода не вызвало каких-то особенных проблем, документация Godot хорошо с примерами показывает весь процесс.

Генерация карты

Наступил один из ключевых моментов. Теперь у меня была возможность генерировать карту Вороного в taxicab пространстве. Работало это примерно так:

• В Godot я генерировал некоторое количество случайных точек;

• Точки и параметры 2D-холста скармливались в native-код;

• Native-код выдавал мне готовые полигоны для холста;

• Полигоны оставалось отрисовать на экране.

Вот что в итоге получалось:

Можно накидать больше точек и получить больше полигонов:

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

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

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

Что нас смущает в текущем варианте карты:

• Карта прямоугольная или квадратная. А хочется получить остров с неровными краями;

• Биомы хочется как-то дифференцировать. Хотя бы цветами. А еще лучше — текстурами.

Самый простой способ превратить квадратную карту в остров — удалить все крайние биомы, которые формировали периметр карты. Тогда оставшиеся биомы будут своими неровными краями формировать островной силуэт. На этом способе и остановимся. А каждый биом окрасим в случайный цвет и получим следующую картину:

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

Проблему с дорогами мы с Ильей решили на время отложить, пока убрать их с карты и заняться вплотную исключительно биомами и доводкой их до какого-то завершенного вида. А на будущее я заготовил совершенно другой алгоритм построения дорог, который в основе своей брал бы информацию о точках интереса/притяжения на карте и строил бы хитрый граф дорог таким образом, чтобы точки интереса или находились у дороги или дорога проходила прямо сквозь них. Но это в свою очередь требует генерацию точек интереса на карте, что уже совсем другая история… В общем, вы видите, как одно тянет за собой другое, и как это может превратиться в бесконечную историю. Именно поэтому мы сперва решили закончить с биомами.

Формируем игровые биомы

Наш план на игровой мир был внушительным:

• Нам нужно было сделать 4 карты разного вида: лес, подземелья, инфернальный разлом и гористая местность;

• Каждая карта будет разбита на биомы, по 3-4 разновидностей биомов на карту;

• У каждого биома будет свое наполнение предметами и пропсами. Например, на травяном биоме лесной карты должно быть много деревьев и грибов; а на каменистом биоме можно случайно встретить меч, воткнутый в землю.

Илья отрисовал концепты, показывающие, как в идеале должна выглядеть каждая карта:

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

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

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

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

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

Бездушные полигоны сразу стали ощущаться землей с травой и почвой — волшебное преображение.

Обратите внимание на неровные границы биомов. Это я написал шейдер, рисующий кляксу, и применил его на линии полигонов. В Godot к любому видимому объекту на сцене можно применить шейдер — очень удобно.

Помимо текстур у меня в распоряжении были предметы для разных карт, которые надо было рандомно раскидать по миру. Наставления от Ильи были в духе: «Ну, вот на травяном биоме надо, чтобы генерировались деревья и грибы, а на каменной — камни и еще меч». Оукей, раскидаем, ведь звучит просто и безобидно, не так ли? Я реализовал примитивнейший алгоритм, который в каждом полигоне генерировал какое-то количество чего-то в случайных местах в зависимости от типа биома. Так выглядел лесной биом:

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

Когда Илья увидел это, он прислал мне:

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

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

Оттачиваем визуал биомов

Илья дал мне промежуточную установку — добиться, чтобы карта выглядела вот так:

Список требований:

• Границы между биомами должны выглядеть так, будто они покрыты цветными травинками;

• Периметр острова должен иметь особую окантовку;

• Остров должен иметь «толщину» в виде стилизованного откоса вниз;

• Соседние биомы не должны быть одинаковыми — например, не может быть такого, чтобы два травяных биома соседствовали и были разделены странной границей. Можете снова посмотреть на ужасный скриншот карты подземелья, что я показал выше, и увидеть, как два кафельных биома соседствуют друг с другом — это выглядит неправильно и неестественно;

• Рандом расстановки объектов по карте должен быть «нормальным» и приятным глазу;

• Тут же забегу вперед и скажу, что в процессе работы всплыла еще одна проблема, которая потребовала решения: иногда карта Вороного генерировала полигоны с предельно короткими ребрами, то есть две соседние точки у полигона стояли настолько близко друг к другу, что расстояние между ними стремилось к считанным пикселям. Это давало нехорошие визуальные артефакты, которые я покажу позже. Сейчас лишь скажу, что такие точки нужно было каким-то образом починить: либо удалить одну из точек, либо как-то превратить две точки в одну.

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

Мы пробежимся по всем этим задачам.

Границы между биомами

Илья дал мне изображение травинки

и попросил сделать так, чтобы все стыки биомов были покрыты такими травинками. Каждая травинка должна иметь немного измененный цвет и должна иметь случайный поворот. Это было нетрудно — нужно было лишь написать новый шейдер и сделать в нем вышеозвученные манипуляции с травинкой. При применении шейдера на границу шейдер тайлит свое выполнение по длине всей линии и получается вот такая картина:

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

Периметр острова

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

Основной остров и островочек

Мы не определились, что делать с этими островами-отщепенцами в будущем, поэтому они так и остались в игре.

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

Толщинный срез

Тут все вышло несложно. В основном из-за моей лени. Смотрите, как это выглядит в теории:

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

• От двух соседних точек периметра карты строим вертикальные отрезки вниз константной высотой

  ;

• Соединяем эти вертикальные отрезки еще двумя отрезками, чтобы получился четырехугольник.

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

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

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

Карта мира стала походить на резную доску, что нам с Ильей весьма понравилось.

Манипуляции с точками

Я уже обмолвился о возникшей проблеме со слишком близко расположенными точками на карте. Они например делали вот такие неприятные вещи:

Как видим, если внутри карты эти точки не критичны, и мы можем их и не заметить вовсе, то на толщинном срезе это все же ощутимо сказывается.

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

Мысль выразить будет нелегко, поэтому будем периодически поглядывать на вот эти эзотерические схемы:

Итак, схема

показывает карту с пятью полигонами. Это не обязательно карта Вороного, точнее скорее всего это не карта Вороного, но это неважно — мы уже можем забыть про карту Вороного до конца статьи, теперь мы оперируем чисто полигонами, которые:

• Соседствуют вместе. Они «прилипают» друг к другу, образуя пространство с биомами;

• Между соседствующими полигонами не может существовать дыр, иначе это уже не карта, а бардак какой-то. Можете посмотреть на схему

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

Теперь представим, что мы хотим переместить на карте одну из точек, как показано на

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

мы немного разнесли все полигоны в пространстве, чтобы все их грани было хорошо видно.

Так же на схеме

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

, где карта сломана. Точка была подвинута у полигона 1, но такая же точка есть и у полигона 2, и ее тоже нужно было подвинуть. То есть, если мы будем внимательно следить за общими точками и будем двигать их все вместе, то задача будет решена? Нет. Это хорошо видно по полигону 5. Он хоть технически и не имеет такую же точку, но точка, которую мы хотим подвинуть лежит на одном из ребер полигона 5. Поэтому полигон 5 как бы мнимо содержит в себе эту точку.

И это уже проблема. Как двигать точку, которой на полигоне нет? Ее следует создать, потом двигать все это добро вместе. Только вот задача становится больно муторной. Более того — это ведь одна частная задача с точками на карте. А что если нам понадобится удалять точки или удалять ребра полигонов на карте или хитро подвинуть границы одного биома? Все эти задачи будут проходить через одни и те же боль и страдания — соседние полигоны всегда придется учитывать и танцевать вокруг всего этого великолепия с бубном.

После долгих прикидок и размышлений я подумал: а что если отойти от концепции набора полигонов и превратить всю карту в граф? Чтобы было единое пространство с точками и ребрами, как на схеме

, и никаких полигонов-соседей. Идея звучала хорошо для задачи с точками, но плохо для всего остального: для отрисовки карты полигоны подходили куда больше. Да и карта в Godot была отрисована как набор полигонов, на которые натягивалась текстура.

Стало ясно, что должна быть возможность иметь оба представления карты одновременно: и как набор полигонов, и как граф. На C++ я сделал класс, который представляет скормленную ему карту как граф и позволяет выполнять над ним манипуляции. А когда все желаемые манипуляции произведены, он дает возможность создать новое полигональное представление карты.

Таким образом я смог получить схему

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

схему

. На

мы остановимся поподробнее: на схеме есть цветные точки. Красные точки — избыточные. Если их удалить из графа, ничего не изменится. Значит будем удалять — избыточная информация не нужна. Зеленые точки, с другой стороны, спорные — они нужны полигонам 1, 2, 3 и 4, но избыточны для полигона 5. Поэтому, когда мы будем конвертировать граф обратно в полигоны, из желательно убрать, но только с полигона 5. В графовом же представлении они нужны, поэтому они остаются. А красные точки уходят, и мы получаем схему

. Ну а при конвертации графа в полигоны мы приходим к финальному результату

.

Точка подвинута, дыр нет, все на месте. К тому же мы всегда можем снова превратить карту в граф, как-то ее переработать и снова пересобрать карту в новые видоизмененные полигоны. Так что подход получился гибким, хорошим, а наша проблема — близкие точки — пропали как явление после того, как я легко смог их устранить на графовом представлении карты:

Раскраска биомами

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

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

Это убивало фан, рушило экосистему карты и портило ее эстетику и внешний вид. Нужно было раздавать биомность полигонам каким-то более хитрым способом.

Фактически все сводилось к задаче о раскраске карты. Только вот теорема о четырех красках ясно нам дает понять, что в общем случае тремя красками ты уже карту не замостишь так, чтобы соседи были уникальными. Только четыре краски и более. Вот и выходило, что наши карты с 3-5 типами биомов не имели возможности железобетонной грамотной раскраски. Все, что оставалось — попытаться покрасить карту с максимально разношерстными соседями, но только лишь попытаться.

За алгоритмом я пошел за помощью к ChatGPT, который подсказал мне простое не замороченное решение, базирующееся на какой-то несложной эвристике в духе:

• Красим себя;

• Красим некрашеных соседей, стараясь не повторять биомы;

• Если в какой-то момент мы зашли в тупик, и соседи дублируются, можно попытаться откатиться на шаг назад и присвоить предыдущему полигону другой цвет и заново попробовать покрасить всех его соседей;

• При желании количество откатов назад можно увеличить, если вам не лень хранить больше временной информации;

• Повторять до конца.

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

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

Нормальный рандом

Вот тут пошло веселье, поскольку, что такое «нормальный рандом» — тема расплывчатая, дискуссионная. Я хотел добиться от Ильи менее туманных формулировок и пощупать нормальность в цифрах. Однако, это было не так просто, поскольку если умом мы примерно представляем, как должна выглядеть расстановка деревьев на опушке, то вот облачить это в численные показатели — вряд ли кто-то из нас сходу сумеет.

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

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

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

• Единичные предметы. Их на весь биом (иногда даже на всю карту) должно быть сгенерировано определенное количество, иногда в каком-то допустимом диапазоне, иногда с какими-то индивидуальными оговорками. Например, сгенерировать один на всю карту меч, воткнутый в землю. С 50% вероятностью он может быть сгенерирован в одном из биомов: каменном или земляном;

• Кластеры предметов. Тут уже речь идет скорее не о количестве, а о плотности их распределения на биоме и о самом характере этого распределения.

Если с первым типом генерации все достаточно очевидно — бери и генерируй сообразно продиктованным для предмета правилам — то как генерировать вторые предметы, я не знал. Пришлось снова поломать голову.

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

Первое же, что приходит на ум тому, кто хоть сколько-то разрабатывал игры — это шум Перлина. С его помощью генерируют любые рандомные 2D вещи на свете, которые выглядят природно естественно, плавно: облака, спец-эффекты, разводы и даже целые карты и острова можно генерировать шумами Перлина. Для основной генерации карты, как мы видим, шум Перлина нам не пригодился — у нас принципиально иной подход с Вороным, Манхэттеном и вот этим вот всем — зато пригодится сейчас для генерации леса.

Шум Перлина выглядит, как вот такая размытая клякса в градациях серого:

Шум Перлина — бесконечное полотно на 2D-пространстве, на изображении выше показан лишь маленький его кусочек. То есть этого бесконечного изображения хватит и на всю нашу карту целиком, если возникнет такая необходимость. Характер шума может выглядеть совершенно иначе, если сгенерировать его с другими параметрами.

Представим, что абсолютно черный цвет на этой кляксе — это 0.0, а абсолютно белый — 1.0. Остальные пиксели на шуме Перлина соответственно лежат в диапазоне (0.0; 1.0). Типовой способ работать с этими цифрами — превратить этот шум в бинарный, взяв некоторый порог и превратив каждый пиксель шума Перлина в 0.0 там, где значение шума было ниже порога, в 1.0 — там где значение было выше порога или равно ему. На изображении ниже показаны бинарные версии показанного ранее шума Перлина:

Применение разных значений порога на шум Перлина

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

Звучит хорошо, но есть проблема. Вот там, где белое, где должен быть лес — с какой частотой там должны быть рассажены деревья? Не с плотностью в один пиксель же? — это был бы абсурд. Это я вам заявляю, как человек, решивший провести быстрый эксперимент и рассадить деревья по шуму с частотой в 10 пикселей (даже не 1!) ради веселья. Всего лишь десять вдумчивых минут от мощного ПК, 60 Гб оперативной памяти, занятой процессом игры — и один биом с гипер-плотной рассадкой готов:

OMG

Некрасиво, долго, дорого и бессмысленно. А тогда как? Есть ощущение, что шум нас немного подводит и не дает всей информации о том, как производить рассадку. И это действительно так, полномочия шума Перлина тут заканчиваются — плотность рассадки и ее равномерность придется как-то настраивать и считать самому.

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

Я снова пошел за советом к ChatGPT, который рассказал мне, что если мне нужно расставлять объекты на первый взгляд случайно, но с соблюдением равномерной плотности, чтобы они отстояли друг от друга на плюс-минус одинаковое расстояние, то мне подойдет алгоритм Бридсона, который является вариацией известного алгоритма poisson disk sampling. Про оба алгоритма можно почитать в отличной статье.

В итоге получился симбиоз использования шума Перлина, который отвечал за геометрию и паттерн рассадки; и алгоритма Бридсона, который регулировал плотность этой самой рассадки.

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

Cредней плотности лес, идущий замысловатой кривой

Мелкие густые кластеры

Гипер-густые кластеры

Равномерный редкий лесок

А вот как мы настроили рассадку деревьев и шипов на горной карте — редкие скопления деревьев кучками:

Рассадка на горной карте

Что было дальше

У нас было еще очень много планов: на карту, ее модификации. Но мы решили сделать паузу и отвлечься на другие механики: инвентарь, крафтовую систему и прочее.

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

Вот так статья неожиданно обрывается так же, как оборвалась разработка этой интересной задумки.

Резюме по алгоритмам

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

На стороне Godot:

• Устанавливаем глобальные параметры карты: ее желаемый размер, примерное количество биомов, типы биомов, которые должны присутствовать на карте;

• Генерируем случайные точки по всей площади предполагаемой карты;

Потом с точками на руках мы ныряем в C++-код, где будем делать трудозатратные вычисления для генерации полигонов карты.

C++:

• На основе точек формируем карту Вороного;

• Из карты Вороного получаем список полигонов;

• На основе полигонов формируем граф из точек для промежуточных оптимизаций;

• На графе удаляем слишком близкие точки;

• Превращаем граф обратно в полигоны;

• Вычисляем соседей для каждого полигона;

• Присваиваем каждому полигону свой тип биома, стараясь делать так, чтобы одинаковые биомы соседствовали по минимуму;

• Ищем соседей с одинаковыми биомами и сливаем эти полигоны вместе;

Полученный набор полигонов возвращается в GDScript, где мы будем заниматься их визуальным воплощением.

Снова Godot:

• Отрисовываем каждый полигон, текстурируем его сообразно его типу биома;

• Отрисовываем границы полигонов шейдером с травинками;

• Находим все острова на карте;

• У островов находим их периметр, обводим каждый периметр толстой линией;

• Отрисовываем толщинный срез у каждого острова;

• У каждого острова генерируем коллизию, чтобы персонаж не мог выйти за его пределы;

• Генерируем наполнение каждого биома сообразно частотным таблицам. Тут надо сказать, что за распределением точек по алгоритму Бридсона мы снова ныряем в C++ код, который нам посчитает это распределение.

Ну а в качестве бонуса и дани уважения моему труду снова обратимся к моим черновикам, как символу этого проекта по генерации карты:

Тяжело 2

Производительность

А что там с производительностью? — спросите вы. А на самом деле очень и очень хорошо. Вот вам видео ряд с оригинальной скоростью воспроизведения:

Чтобы вы понимали, генерируемый мир в среднем имеет размеры 20 000 на 20 000 пикселей, и нажатием одной кнопки он генерируется с нуля в мгновение ока. На гифке я просто раз за разом нажимаю пробел — все быстрее и быстрее. Если бы я писал весь код на GDScript, уверяю вас, результаты были бы много-много хуже.

Выводы

Для чего вообще написана эта статья?

Я думаю, что наш опыт мог бы пригодиться кому-то из вас — тем, кто только хочет начать делать игру; тем, кто уже начал и смотрит в сторону рандомной генерации карты или чего-то схожего. Тем, кто хочет знать, с какими задачами может столкнуться программист, какие трудности могут встать на его пути, и как их можно решить или обойти.

В какой-то степени статья нужна была и мне самому, чтобы освежить, структурировать и переосмыслить полученные в процессе разработки опыт, код, алгоритмы, которые несомненно пригодятся мне в будущем.

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

Теги:

• геймдев
• рандом
• генерация
• c++
• godot

Хабы:

• C++
• Разработка игр
• Алгоритмы
• Математика
• Godot

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку Задонатить
Источник