Как я могу создать такую ​​карту?

Question

Я пытаюсь сделать базовые карты улиц для игры в C. Каждый блок представлен 1 или 0 в массиве. На изображении 1 является белым и представляет собой улицу. Черный равен нулю и представляет собой строительный блок. Улица должна быть на одном блоке повсюду, и вы можете добраться от любой части улицы до любой другой улицы.

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

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

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

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

Есть ли очевидное решение, о котором я не думаю? Решение должно иметь возможность генерировать заданное изображение, а также другие варианты.

Answer 1

• Начать с очереди с одним прямоугольником в ней, всей картой.

• Петля: Возьмите прямоугольник из очереди.

  • Если прямоугольник достаточно мал, то (с некоторой вероятностью) ничего не предпринимайте, и вы закончите с этим прямоугольником.
  • В противном случае выберите длинную сторону. Отрежьте эту сторону улицей (измените массив) и добавьте прямоугольники с каждой стороны в очередь.

Существует некоторая гибкость, когда вы решите, является ли прямоугольник достаточно мал, и как вы решите, где вырезать прямоугольник. Вы можете не оставлять квадраты 1x1, не разрезая 4x1 или меньшие прямоугольники. Вы можете позволить, чтобы у вас был прямоугольник размером 3x5, и шанс вы его разрезали.

Answer 2

Вы можете проверить изолированные уличные улицы, например, используя DFS (http://en.wikipedia.org/wiki/Depth-first_search). Затем вы можете соединить эти части, соединив две ближайшие (или любые другие) точки, сделав сегменты по каждой точке.

Answer 3

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

Как конкретный пример, давайте рассмотрим ваш пример, где у вас есть сетка 13x9.

Начиная с (1,1) случайным образом выбирают размер здания. Скажем так, как в вашем примере, я получаю здание 4x2. ОК. Так что теперь я добавляю улицы вокруг этого. Затем я возвращаю и создаю карты для области 4x6 справа от нее и области 8x9 ниже. Таким образом, на первый у меня есть:

xx 111111 
xx 111111 
xx 111111 
xx 111111 

222222222 
222222222 
222222222 
... 

Где «x» отмечает расположение здания, «» на улице. «1» - это одна область, для которой мне все еще нужна карта. «2» - это еще один регион, для которого мне нужна карта.

Теперь давайте работать в области 4x6, отмеченной 1 справа. В его (1,1) положении этой области или абсолютном положении (1,4). Я произвольно выбираю здание 1x2. Итак, теперь, после того, как вы разместите улицу вокруг нее, я бы:

xx xx 3333 
xx 3333 
xx 44 3333 
xx 44 3333 

2222222222 
2222222222 
2222222222 
.... 

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