Representing and Solving a Maze Given an Image

Representing and solving a maze given an image

Here is a solution.

1. Convert image to grayscale (not yet binary), adjusting weights for the colors so that final grayscale image is approximately uniform. You can do it simply by controlling sliders in Photoshop in Image -> Adjustments -> Black & White.
2. Convert image to binary by setting appropriate threshold in Photoshop in Image -> Adjustments -> Threshold.
3. Make sure threshold is selected right. Use the Magic Wand Tool with 0 tolerance, point sample, contiguous, no anti-aliasing. Check that edges at which selection breaks are not false edges introduced by wrong threshold. In fact, all interior points of this maze are accessible from the start.
4. Add artificial borders on the maze to make sure virtual traveler will not walk around it :)
5. Implement breadth-first search (BFS) in your favorite language and run it from the start. I prefer MATLAB for this task. As @Thomas already mentioned, there is no need to mess with regular representation of graphs. You can work with binarized image directly.

Here is the MATLAB code for BFS:

function path = solve_maze(img_file)
  %% Init data
  img = imread(img_file);
  img = rgb2gray(img);
  maze = img > 0;
  start = [985 398];
  finish = [26 399];

  %% Init BFS
  n = numel(maze);
  Q = zeros(n, 2);
  M = zeros([size(maze) 2]);
  front = 0;
  back = 1;

  function push(p, d)
    q = p + d;
    if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0
      front = front + 1;
      Q(front, :) = q;
      M(q(1), q(2), :) = reshape(p, [1 1 2]);
    end
  end

  push(start, [0 0]);

  d = [0 1; 0 -1; 1 0; -1 0];

  %% Run BFS
  while back <= front
    p = Q(back, :);
    back = back + 1;
    for i = 1:4
      push(p, d(i, :));
    end
  end

  %% Extracting path
  path = finish;
  while true
    q = path(end, :);
    p = reshape(M(q(1), q(2), :), 1, 2);
    path(end + 1, :) = p;
    if isequal(p, start) 
      break;
    end
  end
end

It is really very simple and standard, there should not be difficulties on implementing this in Python or whatever.

And here is the answer:

Maze solving by image recognition

For simplicity, consider a colorspace which gives a channel where this kind of noise is rendered useless. For instance, if we take the S channel from HSB we get the image at left, which is easily binarized by Otsu -- image at right.

Note that at a higher manual threshold, we would obtain only the end points as well the starting point. By doing that, we can dilate these points (image at left) and add the result image to the top right image. Now if a geodesic dilation is performed in this resulting image using the image at left as a marker, we obtain the paths that connect at least two points -- image at right.

The starting point can be found by a simple template matching, thus you can eliminate the paths that do not contain the starting point. This gives the next image. Now all that you have to do is perform a flood fill in a breadth-first manner to obtain the minimal path from the starting point to some exit point.

How to read a maze from an image and convert it to binary values in Python

You can load a PNG, GIF, TIF or JPEG file like this, then ensure it only has 0 and 1 values and process the pixels with PIL/Pillow and Numpy.

I used this edited version of your mini-maze:

#!/usr/bin/env python3

from PIL import Image
import numpy as np

# Open the maze image and make greyscale, and get its dimensions
im = Image.open('maze.png').convert('L')
w, h = im.size

# Ensure all black pixels are 0 and all white pixels are 1
binary = im.point(lambda p: p > 128 and 1)

# Resize to half its height and width so we can fit on Stack Overflow, get new dimensions
binary = binary.resize((w//2,h//2),Image.NEAREST)
w, h = binary.size

# Convert to Numpy array - because that's how images are best stored and processed in Python
nim = np.array(binary)

# Print that puppy out 
for r in range(h):
    for c in range(w):
        print(nim[r,c],end='')
    print()

Here's the result:

000000000000000000001111111111111111111000000000000000000000000000000000000000000000000000000000000
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
001111111111111111110000000000000000000000000000000000000000000000000000000000111111111111111111100
001111111111111111110000000000000000000000000000000000000000000000000000000000111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111100
000000000000000000001111111111111111110011111111111111111110000000000000000000111111111111111111100
000000000000000000001111111111111111110011111111111111111100000000000000000000011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111100111111111111111110011111111111111111100
001111111111111111110111111111000000000001000000000000001100111111111111111110011111111111111111100
001111111111111111110000000000000000000000000000000000000000111111111111111110011111111111111111100
001111111111111111100000000000000000000000000000000000000000111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111100111111111111111111111111111111111111100111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
001111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111100
000000000000000000000000000000000000000011111111111111111110000000000000000000000000000000000000000
000000000000000000000000000000000000000011111111111111111110000000000000000000000000000000000000000

Best algorithm for maze solving?

This is an interesting question. Let's explore it to see why you might be seeing what you're seeing.

Of the four algorithms you've mentioned - BFS, DFS, Dijkstra's and A* - three of them (BFS, Dijkstra's, and A*) are designed to find shortest paths in structures where there are multiple different paths available and you're interested in finding the shortest. In that sense, running BFS, Dijkstra's, and A* will all, in some sense, incur a cost overhead because you're paying for something you aren't using. Dijkstra's algorithm, in particular, should perform no better than BFS in this case. Taking any step will cost you the same amount, and the cost of maintaining a priority queue or some other structure to find the lowest-cost node in the frontier will likely cost more than a standard queue. In that sense, we can probably rule out Dijkstra's as a candidate for the fastest algorithm here.

That leaves us BFS, A*, and DFS. Let's first compare BFS and DFS. The advantage of DFS is that it's theoretically fast (linear time) and the memory access patterns involved in running DFS (maintaining the top of a stack and probing places near the most-recently-visited spot) plays well with caches. The advantage of BFS is that it will stop searching as soon as it finds the shortest path, with the drawback being that memory accesses are more scattered and play less well with caches.

Let's make a quick geometric argument here. BFS expands outward from the starting location by exploring paths of progressively longer and longer lengths. In that sense, you can imagine that the regions searched by BFS will form something that vaguely approximates a circle centered on the start location. The radius of this circle will be equal to the length of the shortest path found. In that sense, if there were no obstacles, you'd expect BFS to visit some constant fraction of the total spaces in the maze before finding the exit, and with obstacles present it's likely to explore most, if not all, of the spaces. DFS stops as soon as it finds the exit, and it's likely to explore lots of dead ends along the way, so there's similarly a good chance that it'll explore a large fraction of the maze cells. Given the choice between the two, my bet is that DFS would be slightly faster, since generally speaking the constant factor for DFS is lower than BFS.

Then there's DFS versus A*. That's a harder one to analyze a priori. DFS is generally speaking a much faster algorithm than A* because of the associated overhead of maintaining distances in A*, but A* tends to search in directions that are much more likely to get you to the destination. It would probably depend on the shape of the maze. If the maze was constructed in a way that has a lot of long, twisty passageways, then A* would probably do better because it would avoid going the wrong direction until it absolutely had to, where DFS might spend lots of effort descending the wrong way. But you'd have to look at the balance between those factors to be sure.

There's one other issue and that's how the maze itself was generated. There are many different maze generation algorithms - you can use Kruskal's algorithm, DFS, Prim's algorithm, or Wilson's algorithm, for example, to generate mazes. Mazes made with DFS tend to have fewer, longer corridors, while Kruskal's algorithm and Prim's algorithm tend to make many shorter corridors. It may be the case that DFS tends to do better in some of those cases than others, while A* may do better or worse as well. So perhaps the difference between A* and DFS has to do with the maze shape in addition to their own implementation details.

So overall, I'm not surprised to hear that your DFS was the fastest maze-solving algorithm mostly due to DFS's simplicity and good cache locality compared with the other algorithms. The fact that it's beating A* is likely due to the overhead associated with A* not being worth the savings in spaces explored. But to get more data, perhaps you should look at the following:

• What fraction of the maze, on average, does each algorithm explore before finding the shortest path?

• How long are the shortest paths in the mazes?

• How were the mazes generated, and do the answers to the above questions depend on the algorithm used?

How to find shortest path in skeletonized maze image?

It's because you are reassigning you reference to the skeletonized graph here

G = nx.path_graph(len(ps))
G = nx.karate_club_graph()

---

Related Topics