Генератор случайных зданий и улиц для процедурного города в 2D

Курсовая работа решает классическую задачу процедурной генерации контента (PCG) в геймдеве и геоинформационных системах. Основная цель заключается в создании генератора, который по числовому зерну (seed), заданной площади карты и коэффициенту плотности выдаёт корректную карту города без пересечений геометрии и изолированных районов.

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

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

• Опиши выбор координатной системы и структур для хранения геометрии вроде списков смежности графа дорог и списков полигонов кварталов
• Рассмотри применение пространственных индексов вроде Quadtree, R-tree или регулярной пространственной решётки для быстрого поиска коллизий между объектами при генерации
• Сравни регулярную прямоугольную сетку (grid-based) и полигональное разбиение на базе диаграммы Вороного с точки зрения естественности получаемой городской среды

Алгоритмический пайплайн генерации дорожной сети

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

• Разбери метод генерации на основе L-систем (систем Линденмайера) с набором контекстно-зависимых грамматик для ветвления проспектов и переулков
• Рассмотри альтернативный метод на основе триангуляции Делоне с последующим поиском минимального остовного дерева (MST) алгоритмом Крускала или Прима и добавлением запасных рёбер для образования циклов
• Опиши иерархию дорог по ширине, допустимым радиусам кривизны и правилам слияния пересечений в единые перекрёстки
• Приведи алгоритм проверки связности графа дорог через поиск в ширину (BFS) или алгоритм Тарьяна для исключения отрезанных сегментов

Разбиение кварталов, размещение зданий и зелёных зон

Замкнутые циклы рёбер в планарном графе дорог образуют городские кварталы (blocks). Эту геометрию необходимо нарезать на участки (lots) и заполнить объектами с учётом санитарных отступов от дорожного полотна.

• Алгоритм нахождения минимальных циклов в планарном графе для извлечения границ каждого квартала
• Применение метода прямого скелета (straight skeleton) или бинарного разбиения пространства (BSP) для нарезки кварталов на участки трапециевидной и прямоугольной формы
• Упаковка прямоугольных полигонов зданий с контролем расстояний до границ участка и соседних строений
• Размещение рекреационных зон и парков через сэмплирование методом диска Пуассона (Poisson Disk Sampling) для естественного распределения зелёных насаждений
• Формулы расчёта плотности застройки как отношения суммарной площади фундаментов к общей площади квартала

Критерии преподавательской оценки

Преподаватель на защите курсовой по информатике оценивает работу как инженерно-математическое решение. Основное внимание уделяется программной реализации и строгости алгоритмов.

• Оценка асимптотической сложности ключевых шагов алгоритма в нотации Big O, например сравнение наивного поиска коллизий O(N²) с квадродеревом O(N log N)
• Точность работы с планарными графами и отсутствие топологических дефектов вроде самопересечений полигонов или изолированных дорожных петель
• Детерминированность генератора, когда фиксированное целочисленное значение seed воспроизводит абсолютно идентичный город на любом запуске
• Наличие тестов производительности при увеличении параметров площади и количества объектов от сотен до десятков тысяч элементов

Где искать материалы и литературу

Для теоретической части потребуются фундаментальные издания по вычислительной геометрии и статьи конференций по компьютерной графике. Используй книги Марка де Берга «Вычислительная геометрия: алгоритмы и приложения» для разделов по триангуляции и разбиениям. Ищи классическую статью Йохена Париса (Yoann Parish) и Паскаля Мюллера (Pascal Müller) «Procedural Modeling of Cities» (SIGGRAPH 2001), которая заложила основы применения расширенных L-систем для улиц. Практические разборы реализации алгоритмов генерации городских графов детально описаны на ресурсе Red Blob Games у Амита Пателя.