Representing and solving a maze given an image

by

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:

Enter image description here

More Related Contents:

  1. Segmenting License Plate Characters
  2. How can I efficiently process a numpy array in blocks similar to Matlab’s blkproc (blockproc) function
  3. Check if all elements in a list are identical
  4. Efficiently Using Multiple Numpy Slices for Random Image Cropping
  5. Detecting consecutive integers in a list [duplicate]
  6. Evenly distributing n points on a sphere
  7. How to merge a transparent png image with another image using PIL
  8. Sorting text file by using Python
  9. find length of sequences of identical values in a numpy array (run length encoding)
  10. Maximum sum sublist?
  11. Image segmentation based on edge pixel map [closed]
  12. How to straighten a rotated rectangle area of an image using OpenCV in Python?
  13. Find elements of array one nearest to elements of array two
  14. How to template match a simple 2D shape in OpenCV?
  15. Complexity of list.index(x) in Python
  16. Why does Python’s itertools.permutations contain duplicates? (When the original list has duplicates)
  17. Detect text area in an image using python and opencv
  18. Get HOG image features from OpenCV + Python?
  19. How to properly use cv2.findContours() on opencv version 4.4.0.?
  20. Adding collision to maze walls
  21. Python: Remove Exif info from images
  22. Getting the bounding box of the recognized words using python-tesseract
  23. Is Laplacian of Gaussian for blob detection or for edge detection?
  24. What is the time complexity of heapq.nlargest?
  25. OpenCV – Saving images to a particular folder of choice
  26. creating a spiral array in python?
  27. Understanding change-making algorithm
  28. Automatic White Balancing with Grayworld assumption
  29. How to remove repititve pattern from an image using FFT
  30. How can I improve my paw detection?

Leave a Comment