Нужны алгоритмы генерации города. - Программирование - Общие обсуждения программистов

Нужны алгоритмы генерации города.

Дата: Среда, 11 Марта 2015, 04:42 | Сообщение # 1

JavaSE Game Developer

Сейчас нет на сайте

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

Суть заключается вот в чем. Имеется прямоугольник с заданными размерами. Запускается процедура его деления на четыре прямоугольника. Места разреза выбираются рандомно, но с учетом переменной, отвечающей за разницу размеров новых прямоугольников — чем она больше, тем больше вероятность, что две дороги будут граничить друг с другом, тем самым образовывая больше пустого пространства. Каждый образованный прямоугольник так же делится на четыре части, и продолжается деление до тех пор, пока каждый из прямоугольников не достигнет определенного размера (чем он меньше, тем плотнее будут дороги). Затем этот прямоугольник, достигший своего размера, добавляется в список. Далее создается изображение, в которое отрисовываются все прямоугольники из списка, формируя карту. Генерация домов банальна — рандомное их размещение в пустых областях карты с проверкой, не допускающей создание дома поверх другого.

Уроки по GM
Minecraft 2D на GM
— Мои проекты —
Blood Harvest [2D] — Original
Blood Harvest [2D]: Remastered Edition
Adventure Craft [2D] — Sandbox
Space Shock [2D] — Scroll Shooter
Intel® Core™ i5-3570K 3.40 GHz, 8 GB RAM, GeForce GTX 750 Ti, Monitor: LG 23EA63V-P.

Сообщение отредактировал FadeBaker - Среда, 11 Марта 2015, 04:52

Ordan

Дата: Среда, 11 Марта 2015, 04:57 | Сообщение # 2

Главный зомби

Сообщений: 3276

Сейчас нет на сайте

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

Цитата недели: Из-за леса, из-за гор, кишки, месиво, хардкор. (Берсерк ТВ-2)

Мои проекты ТЫК
Мои видяхи на ютубэ ТЫК

Если ты споришь с идиотом, вероятно тоже самое делает и он.

FadeBaker

Дата: Среда, 11 Марта 2015, 05:04 | Сообщение # 3

JavaSE Game Developer

Сообщений: 1532

Сейчас нет на сайте

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

Ordan

Дата: Среда, 11 Марта 2015, 05:08 | Сообщение # 4

Главный зомби

Сообщений: 3276

Сейчас нет на сайте

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

FadeBaker

Дата: Среда, 11 Марта 2015, 06:05 | Сообщение # 5

JavaSE Game Developer

Сообщений: 1532

Сейчас нет на сайте

Ordan, мне конкретный алгоритм нужен, а не просто последовательность действий для достижения нужного результата. Не имея алгоритма, слова "нарисовать дороги" не воплотятся в код. Мне и так известно, что нужно сделать, вопрос заключается в том — как.

KamiRonin

Дата: Среда, 11 Марта 2015, 08:23 | Сообщение # 6

почти ветеран

Сообщений: 1034

Сейчас нет на сайте

Алгоритм подразумевает как раз последовательность действий, а не код.
Я предлагаю такой, например:
0. Город = двумерный массив точек хранящий ИД объекта города. Плюс отдельно список объектов (дома, парки, улицы), в которых хранятся занимаемые точки.

1. Устанавливаем точку начала построений (пока 0, 0), ставим там стартовую точку дороги. Принимаем тип дорог в городе - одна дорога не поворачивает под прямым углом (углы образуются только в пересечениях), нет колец. Это значит что отклонение дороги идет только по принципу I или Y из каждой следующей точки сегмента.

2. вычисление рандом участка дороги (квартала) = направление, длительность. Построив сегмент дороги (например, направление 8 (север), длительность 2 ед.) рандомим дома только вдоль дороги - длина и ширина занимаемого прямоугольника + рандомный флуктуатор формы дома (внутри занимаемоего прямоугольника накидать прямоугольников двух типов - тело, пустота) , ориентация вдоль дороги. Можно сразу закладывать типы объектов - рандом по типу (дом, газон, водоем, площадка) и если тип не дом - то сглаживать прямоугольность.

3. вычисляем следующий участок дороги - алгоритм = рандом типа сегмента (тупик, дорога, въезд-коннектор), рандом направления из доступных трех (вперед, 45" влево или 45" вправо).

3.1. проверка на пересечение существующих областей новым сегментом - если пересекает дорогу, то перекресток, если наткнулся на объект, то сегмент устраняется, делается тупик.

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

3.3. если достиг края города - то либо вернуться в начало текущей дороги (в этом примере - в центр (0, 0)) - и начать дорогу в другую сторону, либо установить точку отсчета в свободной зоне и начать алгоритм от этой точки, и тп. вариантов много.

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

перевести такую модель в код будет вполне реально за пару дней имхо.
там пять служебных функций:
ComputeLineSegment(start : Vector2) - берет поле города, строит следующий сегмент дороги от точки start по алгоритму из пункта 2., проверяет на пересечения и тп.
ComputeFromLine(start : Vector2, end : Vector2) - вычисляет прямоугольные зоны вдоль сегмента дороги, задает их рандомно и передает флуктуатору
ComputeNofillZone(point : Vector2) - возвращает незаполненную зону начиная проверку с заданной точки.
SetObjectsInZone(zone : Vector2[,]) - рандомит прямоугольные заполнения в заданной зоне по принципу упаковки рюкзака.
FluctuateZone(pointInZone : Vector2) - рандомит заполнение прямоугольной (ну в идеале любой формы) зоны прямоугольниками пустот и тел - для одного объекта.

И Main функция, в которой описан базовый алгоритм с определением зоны города, отслеживающий завершение циклов и тп и тд.
Пул объектов - улица, строение (парк, площадка, водоем, здание). Улица содержит точки полилинии и ширину, отображается в массив карты города маркируя там каждую точку своим идом. Здание - содержит в себе высоту, цвет, особенности внешнего вида, занимаемую зону города, маркирует массив карты своим идом. И тп.

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

Сообщение отредактировал KamiRonin - Среда, 11 Марта 2015, 09:14

OpenGOO

Дата: Среда, 11 Марта 2015, 13:31 | Сообщение # 7

почти ветеран

Сообщений: 881

Сейчас нет на сайте

Знать бы какой город ты строишь, было бы проще.

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

Мои проекты:
- Свободный и открытый клон World Of Goo
- TrueEngine2D (2D игровой фреймворк основанный на FreeBASIC)

[GameMaker: Studio v1.4.9999]