填充元胞自动机生成的洞穴上的洞

Question

我正在为游戏生成洞穴。洞穴是由元胞自动机构建的 50x50 矩阵，其中 0（紫色）是墙，1（黄色）是空的 space（玩家可以移动的地方）。Here is an example of my output

我用红圈指出了我的问题。玩家无法到达的墙壁中有 "holes"。我正试图填补这个漏洞，但我做不到。基本上我想把 0 包围的 1 变成 0.

我曾尝试通过这种方法使用 floodfill 来做到这一点：

首先，我计算从起点 x,y 开始用 floodfill 绘制了多少个单元格。如果此计数小于 16 且大于 1，那么我实际上会绘制单元格。

for x in range(0, WIDTH - 1):
    for y in range(0, HEIGHT - 1):
        number_cells_paint = floodfill_count(cellmap, x, y, number_cells_paint)
        if 16 > len(number_cells_paint) > 1:
            floodfill(cellmap, x, y)

        number_cells_paint = []

number_cells_paint 是一个数组，我将访问的每个单元格附加到 floodfill_count 中。这就是我认为在递归算法中计数的方式，可能是我的错误所在。

这是floodfill_count：

def floodfill_count(cellmap, x, y, number_cells_paint):
  cellmap_aux = cellmap
  if len(number_cells_paint) > 16:
      return number_cells_paint

  if cellmap_aux[x, y] == 1:
      cellmap_aux[x, y] = 0
      number_cells_paint.append(cellmap[x, y])

      if x > 0 and cellmap[x - 1, y] == 1:
          floodfill_count(cellmap_aux, x - 1, y, number_cells_paint)

      if x < WIDTH - 1 and cellmap[x + 1, y] == 1:
          floodfill_count(cellmap_aux, x + 1, y, number_cells_paint)

      if y > 0 and cellmap[x, y - 1] == 1:
          floodfill_count(cellmap_aux, x, y - 1, number_cells_paint)

      if y < HEIGHT - 1 and cellmap[x, y + 1] == 1:
          floodfill_count(cellmap_aux, x, y + 1, number_cells_paint)

      if x < WIDTH - 1 and y < HEIGHT - 1 and cellmap[x + 1, y + 1] == 1:
          floodfill_count(cellmap_aux, x + 1, y + 1, number_cells_paint)

      if x > 0 and y < HEIGHT - 1 and cellmap[x - 1, y + 1] == 1:
          floodfill_count(cellmap_aux, x - 1, y + 1, number_cells_paint)

      if x < WIDTH - 1 and y < HEIGHT - 1 and cellmap[x + 1, y - 1] == 1:
          floodfill_count(cellmap_aux, x + 1, y - 1, number_cells_paint)

      if x > 0 and y < HEIGHT - 1 and cellmap[x - 1, y - 1] == 1:
          floodfill_count(cellmap_aux, x - 1, y - 1, number_cells_paint)


  return number_cells_paint

和填充：

def floodfill(cellmap, x, y):

  if cellmap[x, y] == 1:
      cellmap[x, y] = 0

      if x > 0 and cellmap[x - 1, y] == 1:
          floodfill(cellmap, x - 1, y)

      if x < WIDTH - 1 and cellmap[x + 1, y] == 1:
          floodfill(cellmap, x + 1, y)

      if y > 0 and cellmap[x, y - 1] == 1:
          floodfill(cellmap, x, y - 1)

      if y < HEIGHT - 1 and cellmap[x, y + 1] == 1:
          floodfill(cellmap, x, y + 1)

      if x < WIDTH - 1 and y < HEIGHT - 1 and cellmap[x + 1, y + 1] == 1:
          floodfill(cellmap, x + 1, y + 1)

      if x > 0 and y < HEIGHT - 1 and cellmap[x - 1, y + 1] == 1:
          floodfill(cellmap, x - 1, y + 1)

      if x < WIDTH - 1 and y < HEIGHT - 1 and cellmap[x + 1, y - 1] == 1:
          floodfill(cellmap, x + 1, y - 1)

      if x > 0 and y < HEIGHT - 1 and cellmap[x - 1, y - 1] == 1:
          floodfill(cellmap, x - 1, y - 1)


  return cellmap

这个 floodfill 的实现有效，我以前试过所以我的问题是 floodfill_count。

使用此代码我有 this final output

Answer 1

问题出在cellmap_aux = cellmap这行代码。 Python 分配列表作为参考，因此对 cellmap_aux 的任何更改都将是 cellmap 中的更改（因此 floodfill_count 绘制所有字段）。 cellmap_aux = cellmap.copy() 应该改用。

填充元胞自动机生成的洞穴上的洞

Fill holes on cave generated by cellular automata

python

algorithm

flood-fill

cellular-automata