Использование L-Systems для процедурной генерации городов

В настоящее время я делаю приложение, которое фокусируется на процедурно сгенерированном контенте. До сих пор я успешно реализовал процедурную генерацию рельефа и формы карты с использованием симплексного шума. Я действительно доволен тем, как это выглядит. Сейчас я пытаюсь сделать то же самое для городов. Мне просто нужно создать 2D макет улиц и зданий. Я посмотрел на это, и, похоже, большинство людей предлагают использовать L-Systems. Однако я не могу обернуться вокруг них. Я понимаю концепцию, но не реализацию в коде. У кого-нибудь есть примеры кода L-Systems для процедурно сгенерированных городов или предложения о других способах обработки городов?

L-системы , из того, что я могу сказать *, представляют собой набор правил подстановки, подобных грамматике, которые вы можете применять рекурсивно, чтобы получить интересные, «органические» результаты.

На заводах часто используются L-системы, так как они демонстрируют большой рекурсивный рост (то есть ветвь распадается на большее количество ветвей). Для простого примера я покажу дерево «леденцов», созданное с использованием L-системы:

variables : | o              (these are the things that will grow)
start  : o
         |                   (this is what we start with)
rules  : (o → o   o)         (these are the substitution rules that we apply
               \ /            one step at a time)

Итак, в первом поколении у нас только есть начало:

o
|

Во втором поколении мы следуем каждому из правил и заменяем существующие части согласно правилам. Заменим «шары» на «две палочки и шары»:

o   o
 \ /
  |

Поколение 3:

o o   o o
 \|   |/
   \ /
    |

Скоро у нас будет довольно (дрянное) большое дерево!

Чтобы сделать это в коде, вы можете сделать это рекурсивно (например, DFS), непрерывно применяя правила к одним и тем же частям, пока не достигнете некоторого произвольного конца, или вы можете сделать это итеративно (например, BFS), как мы делали в этом примере выполняя одно правило «пройти» на всех элементах и ​​повторяя несколько шагов. Это:

Рекурсивный:

tree = start
grow(tree, start)

func grow(tree, part)
    if this part of the tree is big enough
        stop
    if part is 'o'
        replace part with 'o\/o'
        grow(tree, the left 'o')
        grow(tree, the right 'o')

Итеративно:

tree = start
for a number of iterations
    for each part in tree
        if part is 'o':
            replace with 'o\/o'

Многие применения L-Systems выполняют этап «роста» с использованием подразделения - то есть, части становятся меньше по мере того, как они «растут», большие части просто делятся. В противном случае ваша растущая система может начать перекрывать себя. В моем примере с леденцом на палочке, я волшебным образом гарантировал, что две ветви не пересекаются в середине, изменяя форму новых ветвей. Давайте сделаем пример города, используя подразделение:

variables: block_vertical block_horizontal road_vertical road_horizontal
start: block_vertical
rules: (block_vertical → block_horizontal road_vertical block_horizontal)
       (block_horizontal → block_vertical road_horizontal block_vertical)

Это будет иметь смысл через минуту.

Поколение 1:

+--------------------+
|                    |
|                    |
|                    |
|        V           |
|                    |
|                    |
|                    |
+--------------------+

Единственный, скучный вертикальный блок. (V обозначает вертикальный.)

Поколение 2: мы заменяем вертикальный блок горизонтальными блоками на вертикальную дорогу посередине

+--------------------+
|       r            |
|       r            |
|       r            |
|   H   r      H     |
|       r            |
|       r            |
|       r            |
+--------------------+

R обозначает дорогу! Я случайно разбил разделение, мы не хотим скучных регулярных частей в PCG.

Поколение 3: мы заменяем горизонтальные блоки вертикальными блоками, разделенными горизонтальными дорогами. Существующие дороги остаются; для них нет правил.

+--------------------+
|   V   r            |
|       r            |
|rrrrrrrr            |
|       r      V     |
|   V   r            |
|       rrrrrrrrrrrrr|
|       r      V     |
+--------------------+

Обратите внимание, как дороги соединяются друг с другом, что приятно. Повторите это достаточно много раз, и в итоге вы получите что-то вроде этого (откровенно сорвало связанный ответ ):

Обратите внимание, что есть много деталей, которые я не раскрыл, и что этот результат выглядит «явно» сгенерированным - реальные города выглядят несколько иначе. Вот что делает PCG веселым / сложным. Есть бесконечные вещи, которые вы можете сделать, чтобы настроить и улучшить свои результаты, но будучи не связанным с L-Systems, я оставлю этот ответ здесь; надеюсь, это поможет вам начать.

_{* - Я не изучал L-системы формально, хотя я встречал определенные типы, такие как грамматика и растительность PCG; поправьте меня, если я ошибаюсь в определениях или понятиях}

Ответ @congusbongus отличный, позвольте мне добавить несколько вещей.

Блоки должны быть разбиты на строительные участки в соответствии со всеми дорогами, которые их граничат. Когда у вас есть дорога вокруг, общая картина - кольцо. Смотрите эту ссылку, например: http://oldurbanist.blogspot.fr/2012/01/city-blocks-spaces-in-between.html

(В зависимости от плотности, в центре кольца может не быть места, см. Коулун).

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

И чтобы добавить к этому жизнь, вы можете захотеть повлиять на поколение с помощью таких сред, как ландшафт или экономическая карта: дороги (за исключением Сан-Франциско) имеют тенденцию обходить большие холмы, а не идти прямо, и типы домов сильно под влиянием части города, в котором они находятся.

радоваться, веселиться.