0

How would you go about simplifying a maze that is represented in terms of pixels into nodes based on the same color? I'm wring a program that solves a maze (represented as an image) using A* Algorithm. The walls are represented as black pixels and the rest as white pixels. However, I'm worried that the space complexity will be very high for large mazes. Therefore I'm trying to come up with a way to maybe group pixels of the same color together in order to create a graph of nodes which represents the entire matrix. That way when I run A* I can go node by node instead of pixel by pixel which is much more simple.

Jason
  • 27
  • 1
  • 4
  • `group pixels of the same color` - won't that be the entire half of the maze(solid or hollow part)? – 500 - Internal Server Error Nov 11 '14 at 18:36
  • Well, the short answer is that you represent each intersection as a node. If you're asking how to detect the intersections automatically, we're going to need some sort of sample image and any restrictions on your mazes/paths. – beaker Nov 11 '14 at 18:59
  • The only restrictions are there the walls are black and the paths through the maze are white. There is one entrance and exit to the maze. It is possible for there to be multiple paths to get to the exit. – Jason Nov 11 '14 at 19:35
  • @Jason what is large maze? check this http://stackoverflow.com/a/23779490/2521214 before you go from functional code to nodes. In most cases is pixel map + A* sufficient. also the other answers and comments there are worthy of looking at – Spektre Nov 12 '14 at 08:34
  • Thanks @Spektre. That post was definitely helpful. Maybe I will try it out first and test it. – Jason Nov 12 '14 at 19:31

0 Answers0