Автор проекта — о том, как одним движением руки (буквально) создать уникальные здания.
Экспериментальный градостроительный симулятор Townscaper вышел летом 2020 года и за полгода собрал в Steam более 7000 положительных отзывов. Это песочница, в которой игрок строит город на тайловой сетке с уникальным узором, не имея под рукой конструктора. Нужно просто указать место для блока, а алгоритм автоматически превратит его в дом, арку, лестницу, мост или двор, бесшовно встраивая в окружение.
Проект создал разработчик Оскар Стальберг (Oskar Stalberg), который до этого занимался процедурной генерацией голографической карты в Tom Clancy’s The Division и выпустил инди-игру Bad North. На конференции IndieCade Europe и на своей странице в Imgur Стальберг рассказал, какие алгоритмы и способы оптимизации он использовал для Townscaper.
Обычно при генерации окружения из готовых фрагментов используется равномерная прямая тайловая сетка, на которой удобно собирать здания, улицы, или целые уровни. Но Стальберг решил отказаться от строгости и симметрии в пользу более интересных форм, вдохновившись извивающимися улочками старых европейских городов.
Он даже примерно представлял, как это можно реализовать, но в Твиттере его запрос не восприняли всерьёз.
Посоветуйте мне кто-нибудь алгоритм для генерации бесконечной неповторяющейся детерминированной сетки с уникальным узором из четырёхугольников.
Инди-разработчик
Источник цитаты: Twitter
Тогда Стальберг решил придумать алгоритм сам, и со временем он пришёл к такой последовательности:
сгенерировать шестигранник, состоящий из треугольников;
превратить треугольники в четырёхугольники, удалив случайно выбранные грани (несколько треугольников всё же останется, но это будет исправлено на следующем шаге);
разбить все получившиеся фигуры на более мелкие четырёхугольники, тем самым избавившись от оставшихся треугольников (аналог операции Smooth, используемой в 3D);
несколько раз прогнать шестигранник через алгоритм ослабления вершин (аналог операции Relax, используемой в 3D).
В результате у Стальберга получилась сетка из четырёхугольных полигонов, которую можно наращивать в любую сторону, присоединяя к ней новые кластеры.
У такого способа генерации сетки нашёлся ещё один плюс — Стальберг смог хранить координаты тайлов в целочисленном формате. После прочтения этой статьи, он описал в коде шестигранники как кубы, стоящие друг на друге, на которые зритель смотрит под углом.
Стальберг отметил, что если бы он использовал формат float, это бы неизбежно привело к потере точности позиционирования, что очень критично при работе с такой большой геометрией.
Когда сетка была готова, Стальберг начал моделировать в Maya тайлы (к концу проекта в библиотеке скопилось около 400 фрагментов зданий).
Стальберг рассказал, что в основу сборки города из тайлов лёг алгоритм Marching Cubes (с английского — «Шагающие кубики»), который часто используется в 3D сканировании и моделировании. Алгоритм определяет, где находятся углы существующего тайла, и присоединяет к нему новый.
Но у такого способа был существенный минус — при работе с большим количеством тайлов, алгоритм не мог соединить их бесшовно.
Тогда разработчик обратился к программированию ограничениями и начал использовать алгоритм Wave Function Collapse (с английского — «Коллапс волновой функции»). Если коротко, то выбирая в библиотеке тайл, алгоритм анализирует его окружение и получает список ограничений. Чем больше «соседей» у будущего тайла, тем меньше выбора у алгоритма.
Так, если пользователь захочет удалить этаж из середины готовой башни, алгоритм поймёт, что это место нельзя оставить пустым — иначе третий этаж останется левитировать в воздухе. Нельзя поставить здесь крышу, мостовую или перекинуть лестницу к другой башне (у них нет общих тайлов). Единственный тайл из библиотеки, который в данном случае подходит под все ограничения — вертикальные колонны. При этом, встав на место, тайл сам становится источником ограничений для ближайших соседей — поэтому (на скриншоте выше) алгоритм заменил тайл первого этажа на более подходящий, с площадкой на крыше.
Подробнее о работе алгоритма Wave Function Collapse можно почитать в этой статье на Habr и на github автора.
Стальберг рассудил, что без теней здания будут смотреться скучно, и потому решил добавить в сцену мягкий естественный свет. При этом он не мог запечь освещение заранее или пересчитывать на ходу, так как хотел, чтобы проект был максимально нетребователен к железу.
Поэтому тени в проекте реализованы просто: при создании тайла на текстуре появляется его размытый силуэт. Разработчик отметил, что такой способ подходит только для объектов кубической формы, стоящих очень близко друг к другу — но для его задумки это было именно то, что нужно.
На следующем этапе разработки Стальберг добавил возможность выбирать для тайлов цвет, что ещё больше увеличило визуальное разнообразие города.
Стальберг отметил, что сперва моделировал двери, окна и прочие детали прямо на тайлах, но от такого подхода пришлось отказаться — из-за особенностей сетки было трудно найти для них подходящее место. Поэтому, когда заканчивается генерация стен, запускается специальный алгоритм, который занимается расстановкой мелких объектов.
На видео ниже разработчик показывает, как при расстановке дверей и окон на стенах появляются углубления — это сделано с помощью технологии Stencil Buffer.
Отражения в воде сделаны при помощи простого старого трюка: сгенерированная геометрия отражается без деталей по вертикали с наложенной на неё анимацией волны.
Как отметил сам Стальберг, похожие технологии он использовал для генерации уровней в своей предыдущей игре Bad North, где игрок защищает от викингов небольшое островное королевство. А Townscaper это пока игра-песочница, но разработчик не исключает, что со временем в ней появятся геймплей и соперники.