9
\$\begingroup\$

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).

Enter image description here

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.

Enter image description here

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.

Enter image description here

\$\endgroup\$
1
  • 2
    \$\begingroup\$ If you have new/updated code, please wait 24h till after the first one and post a new question instead. \$\endgroup\$
    – Mast
    Dec 28, 2022 at 10:50

1 Answer 1

8
\$\begingroup\$

Code Style:

There are a few minor issues:

  • indentation should be 4 spaces, not 2, to be PEP-8 compliant
  • the code can only run once; write a function to find the path from any arbitrary starting point to any arbitrary goal

Algorithmic improvements

This is where the biggest improvement could be found.

You start by declaring a corner as a goal. Then you go over every single pixel in the entire image (so looping over 10,000 times) to determine that 2 spots are adjacent to that corner. Then you loop over every single pixel once more to find what is adjacent to those 2 spots. Then you loop again...

The shortest possible path to the centre, which would assume zero obstacles, would require 100 steps. Each step requires 10,000 loops. Your best case solution is 1,000,000 loops. This is \$O(n^3)\$ for the best case scenario.

\$O(n^3)\$ means a 200x200 image would take 8 times longer.

What you want is to start by creating a list. The original list will just have the goal in it. Find every valid unexplored pixel adjacent to each element in the list: add those to a new list, and mark what step (k) you found it on. You now no longer need the original list, and can repeat on the new list.

When repeating on the new list, you don't add previously added pixels, only new ones.

What this would look like for the first few steps would be: just the corner [(0, 0)], then the 2 pixels adjacent [(1, 0), (0, 1)], then the 3 adjacent to that [(2, 0), (1, 1), (0, 2)] (the middle one only gets added once - when it gets looked at again it is already marked, just like the origin), then so on.

When this method finds the goal, it can stop the loop. Your code already knows how to follow the marked path.

This would at least mean the possibility space wouldn't creep up on you as quickly as it is currently. Thus, it would run faster not just here, but as you get larger and larger images the difference would be quite noticeable.

Advanced

Expand around both the goal & the origin simultaneously. The search area increases the further you get away from your starting position, so by searching in both directions at once, they are likely to overlap (and thus find you the solution) before the search gets as big as it would otherwise.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you, that's an excellent suggestion. I added the updated code as an edit. The speed improved by a factor of 45. While this is already sufficient for my application, I'll see if I can optimize it even further \$\endgroup\$
    – Nik
    Dec 28, 2022 at 9:39
  • 2
    \$\begingroup\$ There is also inconsistent formatting, e.g. "k -= 1" vs. "k-=1" (also covered by PEP 8?). \$\endgroup\$ Dec 28, 2022 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.