Генерация города (процедурная)?

Question

[xmoonlight]

Карта
Режим 2D.
Есть уровень квадратной сетки (зелёное поле) размерности X*Y.

Объекты
Есть набор объектов для замощения разных типов:
1. Постройки - 3 вида фигур, состоящие из квадратов (аналог: из "тетриса").
2. Деревья - 3 вида, размер: 1x1, 2x2, 3x3
3. Автомобильная дорога - размер: 3x3 (для одной полосы).
4. Пешеходная дорога - размер: 2x2.

Условия:
1. На любую поверхность могут вставать любые постройки и деревья.
2. Нельзя проходить только через постройки и деревья 1x1.
3. Любые непроходимые объекты не примыкают к друг другу.

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

Comments

[kunjut19]

по итогу на чем остановились?

[xmoonlight]

kunjut19, коллапс волн в плоской упаковке.

Answer 1

[GavriKos]

Классная задача.
Я бы нагенерил (скорее всего руками - чтобы красиво было) много шаблонов - а ля "кварталы" ток поменьше, а потом из них уже клеил город.

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

Ну и пара статей:
https://habr.com/ru/company/piter/blog/455004/
https://habr.com/ru/post/320140/ (да, это лабиринт а не город - но общие черты есть)

Comments

[xmoonlight]

Спасибо, гляну!

[yavaskript]

для генерации кварталов можно использовать что-то типа такого

[xmoonlight]

yavaskript, да, согласен!

[xmoonlight]

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

[xmoonlight]

PS: GavriKos на чём моделлить по-проще чтобы было алгоритм отладить? Ты как делаешь?

[GavriKos]

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

[xmoonlight]

GavriKos, возьму JS, сразу и нафонгаплю заодно моделлер карманный)

Answer 2

[Almost]

Думаю, коллапс волновой функции вам может помочь.

Comments

[xmoonlight]

Кратко, но точно!

Answer 3

[yavaskript]

нууууу, это вам нужно отдельные статьи по теме, а не здесь спрашивать. Потому что тема очень объемная (если вы хотите что-то действительно похожее на город, а не просто рандомно разбросанные объекты).
Если вам все равно, как это будет выглядеть по итогу, то могу сходу, не думая, предложить 2 варианта:
1) плясать от домов - расставить случайным образом дома, а потом прокладывать рандомно дороги между ними, параллельно раскидывая деревья вокруг
2) понастроить дорог, а вдоль дорог понаставить дома, дома между собой связать пешеходными дорожками, а деревья понакидать случайно на пустые участки

Comments

[xmoonlight]

Почти то, что нужно!

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

[yavaskript]

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

[xmoonlight]

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

[GavriKos]

Плясать ИМХО лучше от дорог ) Все таки они по идее должны быть все соединены. А то будет потом столб посреди дороги...

[xmoonlight]

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

[GavriKos]

xmoonlight, не получишь потом "бублик" ни с чем не связанный? ))
Ну т.е. если цель - добраться из любой точки в любую точку используя только дороги и тротуары - то лучше ИМХО от дорог плясать. Или усложнять генераци не дорог.

[xmoonlight]

GavriKos, Ну вот нужно продумать, как собрать суперпозиции и критерии.
Веса и критерии дорог и других объектов - это разные вещи.
Т.е., что-то вроде волнового каскада надо..

[kunjut19]

xmoonlight, так называемый "упрощенный вариант Poisson Disk Sampling" хорошо подойдет для случайной расстановки деревьев или домов в квартале. Вы задаете только плотность"застройки", и деревья (или дома) сами раскидываются случайным образом, согласно заданному параметру плотности. Я писал что-то подобное недавно

[xmoonlight]

kunjut19, тут немного не то: хаотично - мне не нужно.
Нужно, чтобы было красиво: чтобы город - был городом (как бы я руками бы его билдил).

Answer 4

[mayton2019]

Город похож на город когда дома и кварталы в нем имеют углы - близкие к 90 градусов. Такой вот нечеткий криетрий.

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

Comments

[xmoonlight]

На квадратной сетке и так все углы 90 градусов.
И как именно на этой сетке создать город - в этом вопрос.
С чего начать и т.д.

[mayton2019]

Я-бы начал с исторических предпосылок. Город строится как 1 большая главная улица. На ней есть Вокзал. Ратуша. Аптека. Банк. Далее от центральной улицы - переулки. Всё рандомное. Рандомной длины. Далее строятся дома. Деревья вдоль дорог.

[xmoonlight]

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

На ней есть Вокзал. Ратуша. Аптека. Банк. Далее от центральной улицы - переулки. Всё рандомное. Рандомной длины. Далее строятся дома. Деревья вдоль дорог.

Это я понимаю. Вопрос был: как автоматизировать застройку случайным образом?

[mayton2019]

Отлично. На первом шаге мы случайным образом выбираем форму главной улицы. Г образная. П-образная. Прямая. И далее снова по моему алгоритму.

[xmoonlight]

mayton2019, Алгоритм не будет работать: после дорог - дома не расставить так, чтобы было нормально.

[mayton2019]

А как в реальной жизни происходит?