Процедурная генерация архитектурных структур для виртуальных миров на основе WFC-подобного алгоритма

Введение

С развитием технологий создания виртуальных миров всё более актуальным становится использование процедурного контент-генератора – программных систем, способных создавать уникальные и логически согласованные объекты без участия человека. Особенно это важно в случае масштабных проектов, таких как игровые вселенные, метавселенные или образовательные VR/AR-приложения [1, с. 75].

Однако, несмотря на широкое применение шума Перлина, L-систем, BSP-деревьев и других методов, остаются нерешёнными проблемы:

1. Обеспечения логической целостности,
2. Избежания пересечений между элементами,
3. Сохранения структурной согласованности при случайном расположении.

Для решения этих задач предложен алгоритм, сочетающий элементарные полигональные формы (куб, пирамида, призма) с WFC-подобным подходом выбора типа блока на основе окружения [2, с. 31]. Алгоритм реализован в игровом движке Unity, что позволило эффективно управлять 3D-сценой и тестировать параметры генерации в реальном времени.

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

Объекты и методы исследования

Объект исследования

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

Методы исследования

Разработка и реализация алгоритма проводилась следующими методами:

• Проектирование модульной архитектуры: система разделена на независимые компоненты, такие как GridManager, PrimitiveGenerator, CastleGenerator.
• Использование дискретной карты занятости (StructuresSpaceDictionary): хранение информации о состоянии ячейки пространства (свободна/занята/дорога/здание).
• Программное создание полигональных примитивов: базовые формы (куб, пирамида, призма) используются как строительные блоки.
• Алгоритм выбора типа примитива: основан на анализе соседних элементов, аналогично принципам Wave Function Collapse.
• Генерация дорожной сети: дороги строятся после размещения всех объектов, чтобы связать их между собой.
• Цветовые палитры: используются массивы цветов для имитации различных материалов (камень, дерево, черепица).

Результаты и их обсуждение

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

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

Рис. 1. Входные параметры генерации

Ниже на рисунке 2 отображается результат генерации с заданными параметрами.

Рис. 2. Пример генерации

Экспериментальная часть

Таблица

Результаты эксперимента производительности

Для наглядности построим график с соответствующими осями. Построенный график изображён на рисунке 3.

Рис. 3. График зависимости площади от времени генерации

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

Заключение

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

1. Структурную целостность,
2. Визуальную узнаваемость,
3. Отсутствие коллизий между элементами,
4. Связность проходимых зон.

Система может быть использована в игровой индустрии, VR/AR-приложениях, образовательных и исторических симуляциях. Также она допускает расширение за счёт добавления новых типов объектов и улучшения алгоритмов управления пространством.

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