Printable View
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.
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.Quote:
Originally Posted by chickenlittle
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.Quote:
Originally Posted by chickenlittle
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.Quote:
Originally Posted by GReaper
You can avoid looking at most dead ends by using the algorithm that is ideal for maze solving...Quote:
Originally Posted by chickenlittle
That's the A* algorithm
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.
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"?!Quote:
Originally Posted by Elysia
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 point was that you cannot always find such a function. Sorry if that caused any confusion.