As part of a game, I am building a 2d grid where I need to find out if two items on the grid are connected. There are e.g. traps and walls that are blocking the way so basically I end up with separate parts of the grid divided by the walls and traps, so I'm flood filling the grid starting from a point P on the grid to find out which points belong to the same part with P.
Here's what the code basically does:
1) build the grid based on an input file (works)
2) find the starting point P (works)
3) flood fill from P (DOES NOT WORK)
4) print the grid to check if it's right (works)
The grid is built just fine, and the starting point is found as well, but the flood fill function does not work. Any ideas?
Example input file:
7 9
#######
#..#G.#
#...TG#
#.....#
#...G.#
#...#.#
###.P.#
#G#.TG#
#######
(UPDATED, works ok now) Running the code with that prints the following:
Start point at: [4, 6] (i.e. in grid[6][4])
[0, '#'][2, '#'][2, '#'][0, '#'][2, '#'][2, '#'][0, '#']
[2, '#'][1, '.'][1, '.'][2, '#'][1, 'G'][1, '.'][2, '#']
[2, '#'][1, '.'][1, '.'][1, '.'][2, 'T'][1, 'G'][2, '#']
[2, '#'][1, '.'][1, '.'][1, '.'][1, '.'][1, '.'][2, '#']
[2, '#'][1, '.'][1, '.'][1, '.'][1, 'G'][1, '.'][2, '#']
[2, '#'][1, '.'][1, '.'][1, '.'][2, '#'][1, '.'][2, '#']
[0, '#'][2, '#'][2, '#'][1, '.'][1, 'P'][1, '.'][2, '#']
[0, '#'][0, 'G'][2, '#'][1, '.'][2, 'T'][1, 'G'][2, '#']
[0, '#'][0, '#'][0, '#'][2, '#'][0, '#'][2, '#'][0, '#']
(UPDATED, works fine) And here's the code itself:
if __name__ == "__main__":
class Node:
UNEXPLORED = 0
CONNECTED = 1
VISITED = 2
def __init__(self, x, y, value):
self.x = x
self.y = y
self.state = Node.UNEXPLORED
self.value = value
def neighbor_with(self, node):
x_dist = abs(self.x - node.x)
y_dist = abs(self.y - node.y)
if x_dist == 1 and y_dist == 0:
return True
elif x_dist == 0 and y_dist == 1:
return True
else:
return False
def trap_or_wall(self):
if self.value == "T" or self.value == "#":
return True
else:
return False
def __str__(self):
return str([self.state,self.value])
with open('in1.txt', 'r') as f:
row = f.readline()
dimensions = row.split(" ")
w = int(dimensions[0])
h = int(dimensions[1])
grid = [[Node(j,i, None) for i in range(w)] for j in range(h)]
#set grid
for i in range(h):
row = f.readline()
for j in range(w):
grid[i][j].value = row[j]
#find P
p = []
for i in range(h):
for j in range(w):
if grid[i][j].value == "P":
p = [grid[i][j].y, grid[i][j].x]
print("Start point at: {:} (i.e. in grid[{:}][{:}])".format(p,p[1],p[0]))
#define function to flood fill the connected part
def fill_connected(matrix, node):
if node.state == Node.UNEXPLORED:
node.state = Node.VISITED
if not node.trap_or_wall():
node.state = Node.CONNECTED
#recursively for neighbors
for i in range(h):
for j in range(w):
if matrix[i][j].neighbor_with(node):
fill_connected(matrix, grid[i][j])
#flood fill from P
fill_connected(grid, grid[p[1]][p[0]])
#check grid, i.e. print it
for i in range(h):
for j in range(w):
print(grid[i][j], end="")
print("\n", end="")
print()
EDIT:
I updated the code to account for the mistakes in the order of coordinates, x=4 and y=6 should now be grid[6][4]. I fixed the other errors after that then, but I still do not understand one thing: in the last line of the flood fill function definition, why does it have to be grid[i][j] instead of grid[j][i]? The latter one produces an out of range error.
