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

Question

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

如何保证输出数组中没有空洞并且单元格数量正确True？

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

在下面的代码中，我随机放置了图块，然后使用元胞自动机进行平滑处理并确保没有孔洞，但保持正确数量的 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 列出不同剩余质量数量的整个范围，例如，"debt" 中有 -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 ]

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

Answer 1

您的问题没有唯一明确的答案，尤其是当基本任务 ("generate 2D asteroid shapes") 未明确说明且从根本上说是主观的时候。当然，原则上你总是可以生成一个 N 瓷砖实体形状，例如从左上角开始，从左到右和自上而下添加瓷砖，直到你有 N 个，但最终的形状可能不是很逼真或 "nice-looking" 小行星.

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

从单个中心图块开始，随机添加与现有图块相邻的新图块。在添加每一块瓷砖之前，检查添加它不会在小行星内部留下一个洞；如果可以，请选择另一块瓷砖。（尽管有多种方法可以优化它，但连通性检查可能是该算法中成本最高的部分。特别是，您可以从仅检查新图块的现有直接邻居开始；如果它们都是连续的，则新图块无法桥接边缘的两个独立部分。）
同上，但将连通性检查延迟到结束。如果发现任何洞，请将小行星边缘的瓷砖移到内部以填充它们。
应用一个midpoint displacement algorithm to a circle. That is to say, use the algorithm to generate a random array of radii (with the same radius at each end) and then use those radii as distances from an arbitrarily chosen center point to the surface of your asteroid, as if you were plotting a radar graph. This won't give you an exact area of N tiles, but you can always scale the radii up or down until you get the size you want. The resulting shape will always be star-convex，这样就没有漏洞了。（这可能最适用于相当大的 N。这种方案的一个优点是它也将以一种相当直接和有效的方式推广到 3D 形状：从随机化开始多面体并将中点位移应用于面。)
使用任何通常生成 hole-free 小行星的算法。然后检查是否有漏洞，如果有，则重新启动。只要重启的概率够低，这个rejection sampling的方法还是比较有效的。

Answer 2

top-down 技术将是：

从位图中随机绘制的填充椭圆开始，反复尝试直到获得理想的结果，单元格现在是像素，例如：http://www.star.bris.ac.uk/~mbt/topcat/figures/plot2-layer-xyellipse.png
将位图栅格化到您的单元格中，如果像素为空则转换为 0，如果像素已填充则转换为 1
使用邻居检测技术填充漏洞

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

Generating a solid shape with N tiles in a 2D array

python

multidimensional-array

procedural-generation

cellular-automata