随意且有效地用形状填充空间

Question

使用尽可能多的非重叠形状随机填充空间的最有效方法是什么？在我的具体情况下,我用圆圈填充一个圆圈.我随机放置圆圈,直到外圆的某个百分比被填充或者一定数量的放置失败(即被放置在与现有圆重叠的位置).这很慢,除非我允许大量的失败,否则通常会留下空白空间.

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

Answer 1

你遇到的问题

您正在使用优惠券收集器的问题,因为您正在使用拒绝采样技术.

您也在对"随机填充"的内容做出强有力的假设.你的算法会在圆之间留下很大的空隙; 这就是"随机"的意思吗？然而,这是一个完全有效的定义,我赞成它.

解

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

可能的危险

但是你必须小心你的编码方式!可能的危险:

• 如果你做了类似的事情,if (random point in invalid grid){ generateAnotherPoint() }你就会忽略这种优化的好处/核心理念.
• 如果你做了类似的事情,pickARandomValidGridbox()你会略微降低在较大圆圈边缘附近制作圆圈的可能性(尽管如果你是为图形艺术项目做这个而不是科学或数学项目,这可能会很好); 但是如果你将网格大小设置为圆的半径的1/sqrt(2)倍,则不会遇到这个问题,因为无法在大圆的边缘绘制块,因此可以忽略所有网格框在边缘.

履行

因此,避免优惠券收集器问题的方法的推广如下:

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等连续块.请注意,许多具有跨越远距离(山脉)和小距离(火炬)的特征的游戏通常需要递归分割的网格(即,一些块被分成另外的2x2或2x2x2子块),从而生成树结构.这种具有大量簿记功能的结构允许您随机放置连续的块,但需要大量编码.然而,您可以使用圆网格算法首先放置较大的特征(当地图上有大量空间可以使用时,您可以检查相邻的网格框以获取集合而不会遇到优惠券收集器的问题),然后放置较小的功能.如果您可以按此顺序放置您的功能,除了在放置1x2/3x3 /等时检查相邻的网格箱是否存在冲突,这几乎不需要额外的编码.组.

Answer 2

一种方法可以产生有趣的效果

create an empty NxM grid
create an empty has-open-neighbors set
for i = 1 to NumberOfRegions
   pick a random point in the grid
   assign that grid point a (terrain) type
   add the point to the has-open-neighbors set
while has-open-neighbors is not empty
   foreach point in has-open-neighbors
      get neighbor-points as the immediate neighbors of point 
          that don't have an assigned terrain type in the grid
      if none
         remove point from has-open-neighbors
      else
         pick a random neighbor-point from neighbor-points
         assign its grid location the same (terrain) type as point
         add neighbor-point to the has-open-neighbors set

完成后,has-open-neighbors将为空,并且网格将填充最多NumberOfRegions区域(具有相同地形类型的某些区域可能相邻,因此将组合形成单个区域).

使用此算法的样本输出具有30个点,14个地形类型和200x200像素世界:

编辑:试图澄清算法.