0

I have a physical maze grid image that I have converted into a normalized binary matrix, as shown in the image below. I have color data trained for the red, blue, and green blocks.

Given a starting and ending block (i.e., start at red and go to blue), I want to calculate the shortest path between the two. As you can see, the maze is not "perfect", and contains random obstacles and open paths. This has made it difficult to adapt standard algorithms.

I have looked into the following algorithms:

  • A*: I was unable to adapt the given example program to my scenario, as it allows for diagonal movement
  • Recursively: A recursive algorithm in Java seemed to be a reasonable fit to the problem, but I was unable to get it working properly in Matlab due to functions needing their own file
  • Right-hand solving: I want to avoid this option, as the maze is more difficult to traverse than a "perfect" maze. This method also isn't efficient

Any general advice or direction would be much appreciated. The code to get the normalized binary matrix is across multiple files, so I am hesitant to post it all here until necessary.

enter image description here

Maytham Fahmi
  • 31,138
  • 14
  • 118
  • 137
Alan
  • 506
  • 7
  • 24
  • try bfs, dfs or dijkstra – Maytham Fahmi Apr 25 '17 at 20:36
  • My recursive attempt was bfs. – Alan Apr 25 '17 at 20:38
  • what is the problem than – Maytham Fahmi Apr 25 '17 at 20:38
  • MATLAB functions made it difficult to execute it recursively, especially pertaining to returning binary values when certain conditions were met – Alan Apr 25 '17 at 20:39
  • What was the difficulty? Recursion is used in Matlab all the time, and it does not seem to be any more difficult than in e.g. Java. – flawr Apr 25 '17 at 20:40
  • I do not know if this would help found it by google search https://se.mathworks.com/matlabcentral/fileexchange/14661-dijkstra-very-simple – Maytham Fahmi Apr 25 '17 at 20:43
  • Consult the duplicate. You already have a binary image as the maze so that cuts some of the work. The post implements a basic BFS in MATLAB to find the path out of a maze. – rayryeng Apr 25 '17 at 20:47
  • This is not a duplicate. I consulted that post and tested those algorithms, and they depend on the start and end points being holes on the outside of the maze. I need to calculate the path between points within the maze. Please consider reopening. – Alan Apr 25 '17 at 20:48
  • The implementation in the marked duplicate has variables for the start and end locations. – beaker Apr 25 '17 at 21:00
  • @AlanGeorge That's not true at all and that's not how BFS works. As long as you clearly define a start and end node, it should be able to find a path between both nodes provided there is one. It does not have to be at the extremes. As what beaker said, you can define where the start and ends are in the code. I'm rather skeptical of your assertion that it doesn't work. If you say it doesn't work, I'm open to being proven wrong. Please edit your post to actually show your maze failing when you use the implementation found in the duplicate and I'll certainly elect to reopen it. – rayryeng Apr 25 '17 at 21:07

0 Answers0