I'm generating caves for a game. The caves are 50x50 matrix builded by cellular automata, where 0(purple) is wall and 1(yellow) is empty space (where the player can move).Here is an example of my output
I pointed out my problem with the red circles. There are "holes" in the walls which are unreachable by the player. I'm trying to fill this holes but I cannot. Basically I want to turn 1 surrounded by 0 into 0.
I have tried to use floodfill with this approach to do this:
First I count how many cells I paint with floodfill from a starting point x,y. If this count is less than 16 and greater than 1 then I actually paint the cells.
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 is an array where I append every cell I visit in floodfill_count. This is how I think to count inside recursive algorithm and probably where my mistake is.
This is 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
and floodfill:
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
This implementation of floodfill works, I have tried before so my problem is on floodfill_count.
With this code I have this final output
The problem is in cellmap_aux = cellmap this line of code. Python assigned lists as a reference, so any changes to cellmap_aux would be the changes in cellmap (therefore floodfill_count paints all the field). cellmap_aux = cellmap.copy() should be used instead.
