I am trying to solve a maze in Python where parts of the maze are not explored, meaning in each step the player has to move toward an unexplored area and explore it until they discover the exit.
I have a working solution, but it is quite inefficient. It takes approximately 2 seconds for a 100x100 pixel map. I'm looking for a more efficient solution.
The maze itself is relatively simple. In the following image, I show the walls (white), the starting position (red) which is always in the center of the maze, and the unexplored area (blue).
I'm looking for the purple line, i.e., the path that connects the starting point with the next unexplored area. Because the white walls are always closed, we can tell that the unexplored area starts where the white walls end (the walls don't end there, they are just not discovered yet).
To solve this, I am choosing a random corner (here marked in green) and doing a breadth-first search. The resulting path is shown in the following image.
Here is my code:
import cv2
import numpy as np
maze_image = cv2.imread("mypath/maze.png")
maze = np.asarray(maze_image) # maze_image is the 100x100 black and white image of the maze
start = (0, 0) # we start the search at the goal
end = (int(maze.shape[1]/2), int(maze.shape[0]/2)) # this is the position of the player
maze[start[0]][start[1]] = 1
maze[end[0]][end[1]] = 0
# breadth-first connecting start and goal
def make_step(k):
for i in range(len(maze)):
for j in range(len(maze[i])):
if maze[i][j] == k:
if i>0 and maze[i-1][j] == 0:
maze[i-1][j] = k + 1
if j>0 and maze[i][j-1] == 0:
maze[i][j-1] = k + 1
if i<len(maze)-1 and maze[i+1][j] == 0:
maze[i+1][j] = k + 1
if j<len(maze[i])-1 and maze[i][j+1] == 0:
maze[i][j+1] = k + 1
k = 0
while maze[end[0]][end[1]] == 0:
k += 1
make_step(k)
# finding the shortest path
i, j = end
k = maze[i][j]
path = [(i,j)]
while k > 1:
if i > 0 and maze[i - 1][j] == k-1:
i, j = i-1, j
path.append((i, j))
k-=1
elif j > 0 and maze[i][j - 1] == k-1:
i, j = i, j-1
path.append((i, j))
k-=1
elif i < len(maze) - 1 and maze[i + 1][j] == k-1:
i, j = i+1, j
path.append((i, j))
k-=1
elif j < len(maze[i]) - 1 and maze[i][j + 1] == k-1:
i, j = i, j+1
path.append((i, j))
k -= 1
print(path)
The code explained: We start at the goal and give its pixel the value 1. Then we check for any neighbor pixels that have the value 0 (0 = not a wall). These get the value 2. Any neighbors of them that are not walls get value 3, and so on until we reach the center of the maze. Once we have reached the center, we just connect pixels in reverse value until we reached the goal, which gives us the shortest path between the start and the goal.
The algorithm works fine, but it takes around 2 seconds for the 100x100 pixel maze. To make it practical, I would need to go 10x faster. Any suggestions for improvement are very welcome. I have attached the original 100x100 maze below. The start position is the center of the maze.
