具有特定规则的细分矩形

Question

所有人。首先，我是一个业余程序员。为了学习，我尝试用C++和SFML制作一个简单的城市建设应用程序。这并不是一个真正的游戏，因为它只会建造城市街区和建筑物，并向用户展示。现在，我可以创建城市街区。我的问题是如何将这些建筑物细分为建筑物。我真的不知道该怎么做。可能的解决方案是(我没有足够的声誉发布图片，但有链接)：https://i.postimg.cc/630GKGW7/bitmap.png

唯一的规则是：(1)每座建筑物必须符合已知的最小和最大尺寸；(2)每座建筑物必须至少有一张脸接触任何块边缘；(3)不应留下任何空位。

我已经胡思乱想好几天了。有人能告诉我怎么做吗？伪码也很好。

提前谢谢！

Answer 1

请注意，我将使用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，即使一个有效的细分是可能的。考虑到您的用例，我认为size约束不会带来任何问题，更“随机”的解决方案更好，而不是更确定的解决方案。

我们开始吧！我们将创建一个名为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) }，我们已经细分了我们的城市街区。

P.S.，这段代码不是有效的，这也是一篇很长的文章。如果这里有什么东西不能正常工作，请编辑/评论这个答案。我希望这能给你一些关于你可以采取的方法的一些见解。

编辑:为了澄清，您应该在每个递归级别上的水平和垂直细分之间切换。