algorithm - 在网格上生成城市/城镇(只是我的方法)

Question

问题

我正在尝试为游戏创建一个城市生成器，该游戏创建具有类型(住宅、工业、商业)的 block 。我所有的街道都是 90 度，因为我希望它是 block 状的(而不是之字形)。

方法

我的第一个方法是选择一个起点，然后在 map 上随机移动 X 次。如果我遇到了死胡同，我会回溯一些随机数，有点像迷宫生成器，但这给我留下了很多区域，这些区域的道路相邻，而道路不是直线行驶。我也研究过使用 perlin 噪音，但我相信这两个会给我经常曲折的道路。

当前解决方案

我想出了一种方法，几乎​​可以满足我的需求，但我认为它比它需要的更复杂，或者至少比它可能的效率低。目前，如果我尝试将其放大到更大的 map ，可能需要几秒钟的时间来处理。

JS fiddle

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

算法

1. 制作一个二维网格并填充空单元格
2. 获取所有可能单元格的列表并将其打乱
3. 遍历洗牌列表中的每个单元格
   • 根据单元格生成一个大小随机的矩形并为其指定唯一 ID
   • 为矩形中的每个单元格指定唯一 ID
   • 随机选择其类型(住宅、商业、工业)
4. 将整个阵列扩大 2
5. 遍历按比例放大的数组，并将具有不同唯一 ID 的相邻图 block 替换为 ROAD 图 block 的所有图 block 。

缩放数组示例(有点像缩放图像):

[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] 

我放大网格的原因是，如果我不这样做，任何以前面积为 1x1 的图 block 都会生成一个 map ，其中两个或多个道路图 block 将成为邻居。

可视化

最终输出

注意:这与可视化中的输出不同

总结

总结一下我的问题，有没有人对如何提高效率或清洁度有任何建议。我认为很难为我当前的流程编写伪代码，所以我认为还有改进的余地。我还必须让它变得更加复杂，比如删除 1x1 的单元格，因为没有房子会四面八方被街道包围。我也不希望城市成为一个完美的正方形(所以我不得不删除边界上的随机区域并关闭它们的街道)。

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

新网格 → 网格

迭代

要获得相同的 block 顺序，我们必须将正方形大小加倍(引用 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/