Как сформировать городскую уличную сеть?

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

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

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

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

Хорошее место, чтобы начать с процедурного поколения городов - это Процедурное моделирование городов Приэша и Мюллера . В их документе представлена L-система, в которой правила, касающиеся плотности населения и структуры дорог (прямоугольная сетка, радиальные и минимальные изменения высоты), объединяются, а затем фиксируются для учета местных ограничений, таких как водные фасады и эстетика дороги. Хотя результаты этой системы впечатляют, ее критикуют за излишнюю сложность . Альтернативное решение Барретта изложено в блоге разработчика Spare Parts Rudzicz следующим образом:

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

Этот подход удаляет большую часть наследования служебного переписывания символов в L-системе Приходов и Мюллера. Вы можете увидеть демо этого подхода здесь .

Преимущество этого подхода заключается в том, что он не зависит от формы города - вы можете добавлять ограничения контура по мере необходимости, чтобы форма вашего города могла определяться вашими игровыми потребностями, а не алгоритмом. В зависимости от размера вашего города, это может быть достаточно хорошо, как есть. Вот результат вышеприведенной демонстрации с пределом сегмента 100: Но если вам нужно что-то большое, у вас могут возникнуть проблемы; вот результат с пределом сегмента 500:

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

Преобразуйте сетку своего города в график, где каждая улица - это край, а каждое пересечение - это узел. Затем используйте любой алгоритм, который вы предпочитаете, чтобы преобразовать график в лабиринт . Вот последний пример, превращенный в лабиринт:

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

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

Если вы ищете в средневековом / старом городе планы в Google, вы найдете много разных вариантов, в основном в зависимости от происхождения города (например, случайное поселение против организованной военной позиции).

Я предполагаю, что вы ищете более естественно выращенный / хаотичный поселок.

Для них я бы попробовал такой подход:

• Начните с главной дороги, идущей от одного конца к другому (и в идеале соединяющей некоторые другие населенные пункты. Если вы хотите, создайте третью дорогу, чтобы получить перекресток, на котором можно начать поселение.
• Разместите несколько домов вдоль дороги (только на одной стороне).
• Теперь расширите эту дорогу вдоль домов и добавьте главную достопримечательность на другой стороне (обычно церковь, но это также может быть какая-то мельница или подобное). Это будет ваш центр / рынок.
• Теперь выберите две позиции за пределами области с домами и создайте новую дорогу, охватывающую дома.
• При желании можно создать несколько небольших союзников между домами, соединяющими старую и новую дороги.
• Теперь повторяйте, пока вы не будете довольны своим «ядром»:
  • Добавьте еще несколько домов.
  • Добавьте другую дорогу, окружающую их.
  • Добавьте обратно переулки, соединяющие дороги.
• Как только вы довольны этим, все готово. Если это должен быть город, окружите его стенами и повторите последние шаги еще несколько раз, добавив дополнительные дома за стенами.

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

Будет псевдокод в JS, так как это легче понять.

1º Определите точку входа, так как вы хотите построить средневековый город, мы начнем с квадрата, поэтому предположим, что в вашем городе будет 300 квадратных квадратов, а квадрат будет посередине (обозначен знаком X).

       300
________________
|               |
|               |
|               | 300
|       X       |
|               |
|               |
|_______________|

const square = [ 150, 150 ];

2º теперь у нас будут проспекты, их будет случайное количество, они будут прямыми и начнутся со средней площади или с других проспектов.

let avenues = [] // will contain start and end [[sx,sy],[ex,ey]]
const n_avenues = RANDOM(4, 8); // number of avenues
const n_av_from_square = RANDOM(0, avenues); // starting in the square

for av in av_from_square
  avenues.push(square, [RANDOM(0, 200) + 100, RANDOM(0, 200) + 100])
  // we want avenues to have, at least 100 units length, thats why we randomize just te last 200 units of the whole town size

Это должно дать вам площадь и пару главных улиц

       300
________________
|   \\          |
|    \\         |
|     \\        | 300
|       X=====  |
|               |
|               |
|_______________|

Теперь мы должны установить проспекты, которые не начинаются на главной площади, они будут пересекать другие проспекты

for av in (n_avenues - av_from_square){
  const av_to_intersect = avenues[RANDOM(0,avenues.length)];

  //check av_to... and get a perpendicular vector (explained bellow)
  av[0] = [ av_to_intersect[0][1], - av_to_intersect[0][0] ];
  av[1] = [ av_to_intersect[1][1], - av_to_intersect[1][0] ];

}

Чтобы получить перпендикулярные векторы, вы должны поменять местами шнуры x, y и отменить новый y:

swiped == x: noswiped.y, y: -1 * (noswiped.x)

Прямо сейчас у вас должно быть что-то похожее на это, разве это не похоже на город? :П

       300
________________
|   \\  //      |
|    \\//  ||   |
|     \\   ||   | 300
|    //\X=====  |
|   //     ||   |
|          ||   |
|_______________|

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

Помните, чем короче ваши улицы, тем хаотичным выглядит город.