Что такое хороший алгоритм для процедурного городского планирования на основе фракталов?

19

Фон

Я управляю сервером майнкрафт, где собираюсь спроектировать довольно крупный стартовый город. У меня есть ряд вещей, таких как знаки правил и клетки для мобов, которые я бы хотел разместить в зданиях. Сам город будет очень большим и разросшимся, предпочтительно размером до 1000 на 1000 блоков.

Сами здания будут иметь куб или прямоугольные следы, основанные на определенном базовом кубе, как все кратные 3 блокам. Улицы и расстояние между зданиями будут предпочтительно 5-11 блоков шириной, в зависимости от важности улицы.

Когда я начну планировать город, я точно буду знать, насколько большими будут здания и сколько их будет.

Проблема

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

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

Вопрос

Какие алгоритмы я мог бы использовать, чтобы помочь мне разработать его с использованием кода? Я думал, что это было бы наиболее естественно, если бы я использовал фракталы каким-то образом, поскольку майнкрафт использует фракталы уже в своем рельефе местности, и город, кажется, растет по фрактальной схеме естественным образом.

Я думаю, что он в некотором роде похож на алгоритм игры в тетрис, поэтому, если у кого-то есть решения, которые существуют в этом направлении, то это также поможет. Я представляю что-то, где я смогу определить формы, которые я хочу использовать, и затем программное обеспечение выполняет итерации, пока не найдет наиболее «оптимальное» решение для равномерного распределения зданий. Есть ли что-то, что поможет мне решить эту проблему с помощью Python, предпочтительно визуально с помощью Pygame?

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

редактировать Чтобы быть ясно, я просто смотрю на макет в этой точке , как здания будут спроектированы и построены в игре.

кругозор
источник
3
Minecraft использует фракталы? У меня сложилось впечатление, что он просто использует функции непрерывного шума (Perlin или Simplex, я считаю).
Мартин Сойка
@ Мартин Сойка Перлин шум на самом деле фрактал, так что есть.
Nevermind
1
@Nevermind: Определяющей характеристикой фрактала является самоподобие : если вы выберете его часть и масштабируете его до размера оригинала, он будет «похожим» (будет иметь такую ​​же структуру). В частности, частотный спектр фрактального сигнала инвариантен к масштабу. Если вы сделаете это с шумом Перлина, все, что вы получите, это увеличенная область шума Перлина; частотный спектр также сместится.
Мартин Сойка
@Nevermind Шум Perlin на самом деле не является фракталом, однако броуновское движение (это метод, который может использовать шум Perlin) является фракталом и обычно называется шумом Perlin.
Эльва
Да, извините, я всегда поправляю людей, когда они путают перлинский шум и розовый шум, но здесь я сам совершаю ту же ошибку. Моя единственная защита в том, что Minecraft на самом деле тоже использует розовый (броуновский) шум, IIRC.
Nevermind

Ответы:

20

Недавно я реализовал алгоритм для процедурного расположения города. Эта работа все еще находится в стадии разработки, но мне кажется многообещающей. Взглянем:

пример процессуального города

Алгоритм, использованный для создания этого макета, в основном основан на L-системах . У меня есть базовый Elementкласс, у которого есть прямоугольник, отмечающий его место на карте, и метод Grow, который создает другие Elementsвнутри прямоугольника и / или порождает некоторые объекты на карте. Тогда есть фактические элементы, унаследованные от этого базового класса: City, Street, и Buildingт.д.

Генерация начинается с ряда «начальных» объектов (в моем случае это просто один Cityэлемент, случайно размещенный на карте). Затем система выполняет итерацию по всем элементам, вызывая Grow, пока все элементы не станут неактивными ( Growвозврат false) или не произойдет какое-то большое количество проходов итерации.

Город на картинке построен по нескольким простым правилам:

  • Cityстановится Streetэлементом, разделяющим область где-то.
  • Все Streets растут 0-3 переулков, далее разделяя область.
  • Кроме того, мы Streetпостоянно пытаемся соответствовать случайному размеру Buildingсбоку.

Результат не очень интересный, но и неплохой. Система может быть легко расширена и достаточно проста, чтобы понять, что происходит (-8

Ничего
источник
Люблю простоту. Я полагаю, что города на самом деле являются органическими, потому что ими управляет органическая сущность - которая стремится создать совершенство в том виде, в каком ее видит разум - что делает L-системы, вероятно, наилучшим приближением этого процесса.
Джонатан Дикинсон
Мне это нравится. =) Теперь для реализации в Pygame ...
Кен
8

Есть этот GDC разговор о генерации процедурного строительства пару лет назад. Он предназначен для создания отдельных зданий на основе набора шаблонов, но не для создания целых городов (разметка улиц и т. Д.). К сожалению, нет никакого свободного кода, чтобы пойти с ним. Система, описанная в докладе , реализована в Unreal, хотя мне не ясно, в свободной ли она версии UDK или нет. В любом случае, вы можете использовать одни и те же идеи для создания своей собственной системы.

Погуглив «процедурные здания» или «процедурный город», вы также найдете множество других статей и статей на эту тему.

Натан Рид
источник
1

Я наткнулся на очень хороший / подробный учебник для создания процедурных городов некоторое время назад. Есть видео @ http://www.youtube.com/watch?v=-d2-PtK4F6Y Учебное пособие находится в блоге автора: http://www.shamusyoung.com/twentysidedtale/?p=2940 Надеюсь, это поможет AMB

AMB
источник
Выглядит как отличный урок из того, что я просмотрел, и он будет иметь несколько отличных указателей, если я решу создать города позже. =)
Кен