algorithm - 用形状随机有效地填充空间

Question

用尽可能多的非重叠形状随机填充空间的最有效方法是什么？在我的具体情况下，我正在用圆圈填充圆圈。我随机放置圆圈，直到一定比例的外圆被填满或一定数量的放置失败(即放置在与现有圆重叠的位置)。这非常慢，并且通常会留下空白空间，除非我允许大量失败。

那么，有没有其他类型的填充算法可以用来快速填充尽可能多的空间，但看起来仍然是随机的？

Answer 1

您遇到的问题

您正在遇到 Coupon collector's problem因为您使用的技术是 Rejection sampling .

您还对什么是“随机填充”做出了强有力的假设。你的算法会在圆圈之间留下很大的空隙；这就是你所说的“随机”吗？尽管如此，这是一个完全有效的定义，我赞同它。

---

解决方案

要调整您当前的“随机填充”以避免拒绝采样优惠券收集器的问题，只需将您正在填充的空间划分为一个网格。例如，如果您的圆的半径为 1，则将较大的圆划分为 1/sqrt(2) 宽度 block 的网格。当填充网格框变得“不可能”时，在选择新点时忽略该网格框。问题解决了!

---

可能的危险

然而，你必须小心你如何编码!可能的危险:

• 如果您执行类似 if (random point in invalid grid){ generateAnotherPoint() } 的操作，那么您将忽略此优化的好处/核心思想。
• 如果您执行类似pickARandomValidGridbox() 的操作，那么您将略微降低在较大圆圈边缘附近制作圆圈的可能性(尽管如果您为图形执行此操作可能会很好艺术项目而不是科学或数学项目)；但是，如果您将网格大小设置为圆半径的 1/sqrt(2) 倍，则不会遇到此问题，因为不可能在大圆的边缘绘制 block ，因此您可以忽略所有网格框在边缘。

---

实现

因此，您避免优惠券收集者问题的方法概括如下:

Inputs: large circle coordinates/radius(R), small circle radius(r)
Output: set of coordinates of all the small circles
Algorithm:
  divide your LargeCircle into a grid of r/sqrt(2)

  ValidBoxes = {set of all gridboxes that lie entirely within LargeCircle}

  SmallCircles = {empty set}

  until ValidBoxes is empty:
    pick a random gridbox Box from ValidBoxes
    pick a random point inside Box to be center of small circle C

    check neighboring gridboxes for other circles which may overlap*
    if there is no overlap:
      add C to SmallCircles
      remove the box from ValidBoxes  # possible because grid is small
    else if there is an overlap:
      increase the Box.failcount
      if Box.failcount > MAX_PERGRIDBOX_FAIL_COUNT:
        remove the box from ValidBoxes

  return SmallCircles

(*) 这一步也是一个重要的优化，我只能假设你还没有。没有它，您的 doesThisCircleOverlapAnother(...) 函数在每次查询 O(N) 时效率极低，这将使填充圆圈几乎不可能实现大比例 R>>r.

这是您的算法的精确概括，以避免缓慢，同时仍保留其优雅的随机性。

---

泛化到更大的不规则特征

编辑:由于您评论说这是针对游戏的，并且您对不规则形状感兴趣，因此您可以将其归纳如下。对于任何小的不规则形状，将其围成一个圆圈，表示您希望它与事物的距离。您的网格可以是最小地形特征的大小。较大的特征可以包含 1x2 或 2x2 或 3x2 或 3x3 等连续 block 。请注意，许多具有跨越大距离(山脉)和小距离( torch )的功能的游戏通常需要递归分割的网格(即，一些 block 被分割成更多的 2x2 或 2x2x2 子 block )，生成树结构。这种具有广泛簿记功能的结构将允许您随机放置连续的 block ，但是它需要大量的编码。然而，您可以做的是使用圆形网格算法首先放置较大的要素(本地图上有很多空间可供使用时，您可以只检查相邻的网格框以获取集合而不会遇到优惠券收集者的问题)，然后放置较小的特征。如果您可以按此顺序放置您的功能，除了在放置 1x2/3x3 等时检查相邻网格框是否发生碰撞外，这几乎不需要额外的编码。组。