Hi I have a 16x16 maze where 1's represent walls and 0's represents paths.
I used a breadth first search algorithm and my program successfully finds a path from a user specified start to a user specified exit.
However I am stuck on how to output the shortest path using a coordinate system.
Checking the paths that the computer took, I could see that it tried many dead ends before it could find the exit. How would I skip those dead ends and make it output a path leading from the start to end?
For every graph node, you need to keep track of the node that reached it. That way, when you find the exit node, you can traverse back to the beginning, marking the path.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
But how would I do that? Say a starting point I picked has four open spaces next to it(up, down, left, and right) and the exit point I want is two spaces right of the starting point. Using the breadth search, it will add all four spaces next to the starting point. From there it branches out and checks the open spaces of each individual nodes. I'm not very sure how to implement the traversing part.
Recursion( or alternatively a stack ) can be used for implementation.Originally Posted by chickenlittle
Devoted my life to programming...
There are two ways. One way is when you queue a space, you can add to the node in the queue data pointing to the node that that square is entered from. The other way is to mark the maze itself to have a direction from where it was entered, so that you can backtrack from the end, "recoloring" the path, as you follow it to start.
Incorrect. A stack would yield depth first search, not breadth first search. That said, I'd expect a depth first search to be more appropriate for maze solving.
Last edited by King Mir; 10-23-2011 at 05:02 PM.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
You can avoid looking at most dead ends by using the algorithm that is ideal for maze solving...
That's the A* algorithm
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
But isn't the breadth first search best for finding the shortest path? That is what my main objective is.
I have tried to store the nodes that the program visits but would it outputs it back to me I could still see it includes the coordinates of tat are redundant to getting to the exit.
iMalc is right, A* is a better algorithm for navigating obstacles then breadth first search. Both will get you the shortest path. Breadth first short is simpler, but slower. For a maze, like you find in a restaurant place-mat, I recommend depth first, but not for when you want to find the shortest path around an obstacle.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
A* will complement your search algorithm. What it does is significantly reduce the time needed to find the shortest path, but does not always work.
Take a look and see.
"does not always work"?!
Of course it does! As long as an admissable heuristic is used then it is guaranteed to always work, and guaranteed to find the shortest path.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
My point was that you cannot always find such a function. Sorry if that caused any confusion.
