Генерация города / города на сетке (просто мой подход)

Question

проблема

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

подходы

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

Текущее решение

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

JS Fiddle

https://jsfiddle.net/jrj2211/0exe9jne/

Алгоритм

1. Создайте 2D-сетку и заполните пустые ячейки
2. Получить список всех возможных ячеек и перемешать его
3. Перебрать каждую ячейку в перетасованном списке
   • Создайте прямоугольник случайного размера из ячейки и присвойте ему уникальный идентификатор
   • Дайте каждой ячейке в прямоугольнике уникальный идентификатор
   • Случайно выбрать его тип (жилой, коммерческий, промышленный)
4. Масштабировать весь массив на 2
5. Прокрутите масштабированный массив и замените любые плитки, которые имеют соседнюю плитку, с другим уникальным идентификатором в качестве плитки ROAD.

Пример масштабирования массива (вроде как масштабирование изображения):

[1, 2, 2]     [1, 1, 2, 2, 2, 2]
[1, 3, 3] =>  [1, 1, 3, 3, 3 ,3]
[4, 4, 4]     [4, 4, 4, 4, 4, 4] 

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

Визуализация

Окончательный вывод

Примечание. Это не тот же вывод, что и в визуализации.

Резюме

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

Answer 1

Одним из способов обойти создание большого массива является немедленная реализация нужного макета. Ключ к масштабированию curTile вместо grid, обратите внимание на изменение от ++ в +=2,

// Get all cells as a 1 dimensional array
function GetAllCells() {
  var cells = [];
  for (var i = 0; i < mapSize; i+=2) {
    for (var j = 0; j < mapSize; j+=2) {
      cells.push(grid[i][j]);
    }
  }
  return cells;
}

Спина к спине

IsInBoundsScaled → IsInBounds

newGrid → grid

повторять

Чтобы получить одинаковый порядок блоков, мы должны удвоить квадратные размеры (ссылка minSize, maxSize).

// Get a random order to loop through the cells
var checkOrder = shuffle(GetAllCells());
var minSize = 4;
var maxSize = 10;

for (var id = 1; id < checkOrder.length; id++) {
  var curTile = checkOrder[id];

  if (curTile.type == TYPES.NONE) {
    var direction = (Math.random() > .5 ? 1 : 0);
    var square_width = RandomRange(minSize, (direction ? maxSize : minSize));
    var square_height = RandomRange(minSize, (direction ? minSize : maxSize));

    var zones = [TYPES.RESIDENTIAL, TYPES.COMMERCIAL, TYPES.COMMERCIAL, TYPES.RESIDENTIAL, TYPES.INDUSTRIAL];
    var zone = zones[Math.floor(Math.random() * zones.length)];
    var color = getRandomColor();

    for (var i = 0; i < square_width; i+=2) {
      for (var j = 0; j < square_height; j+=2) {
        if (IsInBounds(curTile.i + i+1, curTile.j + j+1)) {
          grid[curTile.i + i][curTile.j + j].id = id;           // [x] O
          grid[curTile.i + i][curTile.j + j].type = zone;       //  O  O

          grid[curTile.i + i+1][curTile.j + j].id = id;         //  x [O]
          grid[curTile.i + i+1][curTile.j + j].type = zone;     //  O  O

          grid[curTile.i + i][curTile.j + j+1].id = id;         //  x  O
          grid[curTile.i + i][curTile.j + j+1].type = zone;     // [O] O

          grid[curTile.i + i+1][curTile.j + j+1].id = id;       //  x  O 
          grid[curTile.i + i+1][curTile.j + j+1].type = zone;   //  O [O]
        }
      }
    }
  }
}

JS Fiddle Fork

https://jsfiddle.net/7srfrx55/