algorithm - 用特定规则分割矩形

所有人。
首先，我是个业余程序员我正在尝试用C++和SFML来做一个简单的城市建筑应用，用于学习。这不是一个真正的游戏，因为它只会建立城市街区和建筑物，并显示给用户。
现在，我可以创建城市街区我的问题是如何把这些街区划分成建筑物我不知道怎么做。
可能的解决方案是（我没有足够的声誉发布图片，但有链接）：
https://i.postimg.cc/630GKGW7/bitmap.png
唯一的规则是：
（1）每个建筑物必须符合已知的最小和最大尺寸；
（2）每个建筑物必须至少有一个面接触任何砌块边缘；
（3）不得留有空位。
我已经为此纠结好几天了有人能告诉我怎么做吗伪代码也很好。
提前谢谢！

最佳答案

请注意，我将使用oop语法来简化此过程，但它不是有效的代码。我们首先创建一个接口来定义我们想要的行为：

class CityBlock {
  Building[] buildings // should initially contain one building taking up the whole CityBlock

  double width
  double height
  double maxBuildingSize
  double minBuildingSize

  splitBuilding(horizontal/vertical, coord) // This will split a building horizontally/vertically
  createRandomBuildings() // this is what we want to create!
}

class Building {
  Point position // position of top-left corner
  Building[] subBuildings // buildings created by subdivision

  double width
  double height

  double size() { return width * height }
}

有趣的是！让我们尝试使用createRandomBuildings()方法我将采取的方法是重复细分建筑，直到它们介于2 * minBuildingSize和maxBuildingSize之间（小于这意味着没有细分可以创建两个有效的建筑）。
重要提示：此方法仅在maxBuildingSize >= 2 * minBuildingSize的情况下保证有效建筑，即使可以进行有效的细分。考虑到您的用例，我认为大小约束不会带来任何问题，一个更“随机”的解决方案会比一个更确定的解决方案更好。
我们开始吧！我们将创建一个名为subdivide的递归函数来完成繁重的工作。

Building[] subdivide(Building b, horizontal/vertical) {} // Subdivides b into a random number of other buildings

我将对每个建筑进行细分的方法是将其拆分为随机数量的水平/垂直段前任。

从这个

为了这个
注意：为了简化问题，我将把细分处理为垂直的，如上图所示对于水平细分，只需交换宽度/高度。
当然，我们不能使用任何数量的细分太多了，所有的建筑物都会太小因此，我们应该首先定义的最大数量的细分，仍然可以让我们创造有效的建筑物。

minSubdivisionWidth = minSize / b.height // ensures that subdivisionWidth * b.height >= minSize
maxSubdivisions = floor(b.width / minSubdivisionWidth)

subdivisions = randomInt(2, maxSubdivisions)

现在我们已经有了一个有效的细分数字，我们需要在确保建筑不太小的同时随机对它们进行空间划分为此，我们将可用空间分成两部分：最小空间和可用空间。每个细分需要有最小的空间，但也有等于b.size() - minBuildingSize * subdivisions的空闲（或剩余）空间。这个自由空间是我们想要在细分的矩形中随机分布的。

蓝色是最小空间，粉色是自由空间
让我们分配这个空间：

widths[] // This will be the widths of our subdivided buildings
freeWidth = b.width - minSubdivisionWidth * subdivisions
weights[] // randomly assigned weight for free space
sumWeight

for i = 1 to subdivisions {
  randWeight = random()
  weights[i] = randWeight
  sumWeight += randWeight
}

for i = 1 to subdivisions {
  widths[i] = minSubdivisionWidth + (weights[i] / sumWeight) * freeWidth
}

现在我们可以做实际的细分：

// transform individual widths into coordinates for building split
cumulativeWidth = 0

for i = 1 to (subdivisions - 1) {
  cumulativeWidth += widths[i]
  splitBuilding(vertical, cumulativeWidth)
}

我们快到了现在，如果建筑低于最大值，我们只需要一个片段来随机不细分：

probToNotSubdivide = .3 // obviously change this to whatever
if b.size() < maxBuildingSize and randomDouble(0, 1) <= probToNotSubdivide { return }

如果建筑太小，一个不可细分：

if b.size() < minBuildingSize * 2 { return }

如果它会从街区边缘切断一栋建筑，则不进行细分：

/*
If the building is touching a horizontal edge, vertical subdivisions
will not cut anything off. If the building is touching both
vertical edges, one subdivision can be made.
*/
if not (b.position.y == 0 or (b.position.y + b.height) == cityBlock.height) {
  if b.width == cityBlock.width {
    // do one subdivision and recurse
    splitBuilding(vertical, randomDouble(minSubdivisionWidth, cityBlock.width - minSubdivisionWidth)
    for subBuilding in b.subBuildings {
      subdivide(horizontal, subBuilding)
    }
    return
  } else { return }
}

在结尾添加一点递归。。。

Building[] subdivide(Building b, horizontal/vertical) {
  // exit conditions
  if b.size() < maxBuildingSize and randomDouble(0, 1) <= probToNotSubdivide { return }
  if b.size() < minBuildingSize * 2 { return }

  /*
  If the building is touching a horizontal edge, vertical subdivisions
  will not cut anything off. If the building is touching both
  vertical edges, one subdivision can be made.
  */
  if not (b.position.y == 0 or (b.position.y + b.height) == cityBlock.height) {
    if b.width == cityBlock.width {
      // do one subdivision and recurse
      splitBuilding(vertical, randomDouble(minSubdivisionWidth, cityBlock.width - minSubdivisionWidth)
      for subBuilding in b.subBuildings {
        subdivide(horizontal, subBuilding)
      }
      return
    } else { return }
  }

  // get # subdivisions
  minSubdivisionWidth = minSize / b.height // ensures that subdivisionWidth * b.height <= minSize
  maxSubdivisions = floor(b.width / minSubdivisionWidth)
  subdivisions = randomInt(2, maxSubdivisions)

  // get subdivision widths
  widths[] // This will be the widths of our subdivided buildings
  freeWidth = b.width - minSubdivisionWidth * subdivisions
  weights[] // randomly assigned weight for free space
  sumWeight

  for i = 1 to subdivisions {
    randWeight = random()
    weights[i] = randWeight
    sumWeight += randWeight
  }

  for i = 1 to subdivisions {
    widths[i] = minSubdivisionWidth + (weights[i] / sumWeight) * freeWidth
  }

  // transform individual widths into coordinates for building split
  cumulativeWidth = 0

  for i = 1 to (subdivisions - 1) {
    cumulativeWidth += widths[i]
    splitBuilding(vertical, cumulativeWidth)
  }

  // recurse
  for subBuilding in b.subBuildings {
    subdivide(horizontal, subBuilding)
  }
}

就这样！现在我们有了createRandomBuildings() { subdivide(vertical, initialBuilding) }，我们又细分了我们的城市街区。
再说一遍，这个代码不是有效的，这也是一个很长的帖子。如果这里的某些内容不正确，请编辑/评论此答案我希望这能让你对你能采取的方法有所了解。
编辑：为了澄清这一点，您应该在每个递归级别上的水平和垂直细分之间切换。