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

Question

我正在制作一个小行星生成器，它创建一个 bool 的二维数组。生成器采用一个 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

该函数通常打印不同剩余质量数量的整个范围，例如，-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 瓦片实体形状，例如从左上角开始，从左到右和自上而下添加瓷砖，直到您有 N 个瓷砖，但最终的形状可能不是非常逼真或“漂亮”的小行星。

因此，我不会详细描述单个算法，而只是建议一些应该有效的方法，让您选择最适合您的方法:

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

• 同上，但将连接检查延迟到结束。如果您发现任何孔洞，请将小行星边缘的瓷砖移动到内部以填充它们。

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

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