maze is made with the help of pillow(python library)
def draw_matrix(a,m, the_path = []): im = Image.new('RGB', (zoom * len(a[0]), zoom * len(a)), (255, 255, 255)) draw = ImageDraw.Draw(im) for i in range(len(a)): for j in range(len(a[i])): color = (255, 255, 255) r = 0 if a[i][j] == 1: color = (0, 0, 0) if i == start[0] and j == start[1]: color = (0, 255, 0) r = borders if i == end[0] and j == end[1]: color = (0, 255, 0) r = borders draw.rectangle((jzoom+r, izoom+r, jzoom+zoom-r-1, izoom+zoom-r-1), fill=color) if m[i][j] > 0: r = borders draw.ellipse((j * zoom + r, i * zoom + r, j * zoom + zoom - r - 1, i * zoom + zoom - r - 1),fill=(255,255,0)) for u in range(len(the_path)-1): y = the_path[u][0]*zoom + int(zoom/2) x = the_path[u][1]*zoom + int(zoom/2) y1 = the_path[u+1][0]*zoom + int(zoom/2) x1 = the_path[u+1][1]*zoom + int(zoom/2) draw.line((x,y,x1,y1), fill=(255, 0,0), width=5) draw.rectangle((0, 0, zoom * len(a[0]), zoom * len(a)), outline=(0,255,0), width=2) images.append(im)
BFS is done through travering the pacman through the maze to each leaf node to get the destination node
def make_step(k): for i in range(len(m)): for j in range(len(m[i])): if m[i][j] == k: if i>0 and m[i-1][j] == 0 and a[i-1][j] == 0: m[i-1][j] = k + 1 if j>0 and m[i][j-1] == 0 and a[i][j-1] == 0: m[i][j-1] = k + 1 if i<len(m)-1 and m[i+1][j] == 0 and a[i+1][j] == 0: m[i+1][j] = k + 1 if j<len(m[i])-1 and m[i][j+1] == 0 and a[i][j+1] == 0: m[i][j+1] = k + 1
while k > 1: if i > 0 and m[i - 1][j] == k-1: i, j = i-1, j the_path.append((i, j)) k-=1 elif j > 0 and m[i][j - 1] == k-1: i, j = i, j-1 the_path.append((i, j)) k-=1 elif i < len(m) - 1 and m[i + 1][j] == k-1: i, j = i+1, j the_path.append((i, j)) k-=1 elif j < len(m[i]) - 1 and m[i][j + 1] == k-1: i, j = i, j+1 the_path.append((i, j)) k -= 1 draw_matrix(a, m, the_path) for i in range(10): if i % 2 == 0: draw_matrix(a, m, the_path) else: draw_matrix(a, m)
DFS is done by directly searching one single node and going deep node by node to get the destination node.
def dfs(i,j): global path, i_end,j_end, a, k if i<0 or j<0 or i>len(a)-1 or j>len(a[0])-1: return if (i,j) in path or a[i][j]>0: return k += 1 path.append((i,j)) a[i][j] = 2 draw_matrix(a,path) if(i,j) == (i_end,j_end): for animate in range(10): if animate % 2 == 0: draw_matrix(a, path) else: draw_matrix(a) m = path print(m) path.pop() return else: dfs(i-1,j) dfs(i+1,j) dfs(i,j-1) dfs(i,j+1) path.pop() draw_matrix(a,path) return
@sanskarzanwarmaheshwari007