python - 在 2D 数组中生成具有 N 个图 block 的实体形状

Question

我正在制作一个小行星生成器，它创建 bool 的二维数组s。 生成器采用 int参数，size ，这应该确定有多少 True单元格将位于二维数组中。

如何保证输出数组中没有漏洞，并且单元格的数量是 True ？

我看到了问题Randomly Generating Clusters in a 2d Array ，但我想不出一种方法将其应用到我的用例中，因为我需要知道必须生成的图 block 数量。

在下面的代码中，我随机放置图 block ，然后使用元胞自动机进行平滑并确保没有孔，但保持正确的 True 数量细胞是问题所在，特别是因为随机取出 True满足正确尺寸的细胞可能会产生孔。

def create_shape(size, seed):
    # init rng with seed
    rng = random.Random(seed)
    # initial grid values empty and full mass left
    # make the grid size by size so any shape could fit
    grid = [[False for x in range(size)] for y in range(size)]
    mass_remaining = size
    # guarantee the center is something
    center = size // 2
    grid[center][center] = True
    mass_remaining -= 1 # remember to reduce available mass
    # generate random values
    for x in range(size):
        for y in range(size):
            # skip the already filled in center
            if x == y == center:
                continue
            # assign random value
            value = bool(rng.randint(0, 1))
            grid[y][x] = value
            # remember to reduce mass
            if value: 
                mass_remaining -= 1
    # smoothen things out with cellular automata neighbor checking
    for x in range(size):
        for y in range(size):
            # skip the center
            if x == y == center:
                continue
            # get neighbors
            # set neighbors is the count of neighbors set to True
            set_neighbors = 0
            for i in range(-1, 2):
                for j in range(-1, 2):
                    # skip counting self
                    if i == j == 0:
                        continue
                    nx, ny = x + i, y + j
                    if 0 <= nx < size and 0 <= ny < size:
                        # only get in-range cells
                        if grid[ny][nx]:
                            set_neighbors += 1
            # more than 3 -> become True, less than 3 -> become False
            if set_neighbors > 3:
                grid[y][x] = True
                mass_remaining -= 1
            elif set_neighbors < 3:
                grid[y][x] = False
                mass_remaining += 1
            else:
                # otherwise leave it the same
                pass
    # find out how well the mass is staying "in-budget"
    print(mass_remaining)
    return grid

函数常print找出一系列不同的剩余质量，例如 -14处于“债务”状态或拥有 42额外的。我期望输出为 0功能是否正常。

例如，像这样输出...

create_shape(8) ->

[ 0, 0, 0, 0, 0, 0,
  0, 1, 1, 0, 0, 0,
  0, 1, 1, 1, 0, 0,
  0, 1, 1, 1, 1, 0,
  0, 1, 1, 1, 1, 0 ]

...是实心的，但设置的图 block 太多。

Answer 1

您的问题没有单一明确的答案，特别是因为基本任务(“生成 2D 小行星形状”)未指定且基本上是主观的。当然，原则上你总是可以生成一个 N 个平铺实体形状，例如从左上角开始，从左到右、从上到下添加图 block ，直到有 N 个图 block ，但最终的形状可能不是非常现实或“好看”的小行星。

因此，我不会详细描述单个算法，而是仅建议一些可行的方法，并让您选择最适合您的方法:

• 从单个中心图 block 开始，随机添加与现有图 block 相邻的新图 block 。在添加每个图 block 之前，请检查添加它是否不会在小行星内部留下一个洞；如果可以，请选择另一 block 瓷砖。 (连接性检查可能是该算法中最昂贵的部分，尽管有多种方法可以优化它。特别是，您可以从仅检查新图 block 的现有直接邻居开始；如果它们都是连续的，则新瓷砖无法桥接边缘的两个独立部分。)

• 与上面相同，但将连接检查延迟到最后。如果发现任何洞，请将瓷砖从小行星边缘移动到内部以填充它们。

• 申请midpoint displacement算法到一个圆。也就是说，使用该算法生成半径的随机数组(两端具有相同的半径)，然后使用这些半径作为从任意选择的中心点到小行星表面的距离，就好像您正在绘制一个radar graph 。这不会为您提供 N 个图 block 的精确面积，但您始终可以放大或缩小半径，直到获得所需的大小。最终的形状将始终是 star-convex ，因此没有洞。 (这对于相当大的 N 来说可能效果最好。该方案的一个优点是，它也会以一种相当简单且有效的方式推广到 3D 形状:只需从随机多面体开始，然后应用到面的中点位移。)

• 使用任何通常能够生成无洞小行星的算法。然后检查是否有漏洞，如果有则重新启动。只要重启的概率足够低，这个rejection sampling方法将相当有效。