Need help with finding the shortest coordinate of a maze

This is a discussion on Need help with finding the shortest coordinate of a maze within the C++ Programming forums, part of the General Programming Boards category; Hi I have a 16x16 maze where 1's represent walls and 0's represents paths. I used a breadth first search ...

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    45

    Need help with finding the shortest coordinate of a maze

    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?

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    2,028
    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.

  3. #3
    Registered User
    Join Date
    Oct 2010
    Posts
    45
    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.

  4. #4
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,624
    Quote Originally Posted by chickenlittle View Post
    I'm not very sure how to implement the traversing part.
    Recursion( or alternatively a stack ) can be used for implementation.
    Devoted my life to programming...

  5. #5
    Registered User
    Join Date
    Apr 2006
    Posts
    2,028
    Quote Originally Posted by chickenlittle View Post
    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.
    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 GReaper View Post
    Recursion( or alternatively a stack ) can be used for implementation.
    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.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by chickenlittle View Post
    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?
    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"

  7. #7
    Registered User
    Join Date
    Oct 2010
    Posts
    45
    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.

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,028
    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.

  9. #9
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,556
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by Elysia View Post
    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"

  11. #11
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,556
    My point was that you cannot always find such a function. Sorry if that caused any confusion.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 07:41 PM
  2. need some help in finding the shortest distance
    By jackhasf in forum C Programming
    Replies: 8
    Last Post: 02-15-2009, 10:58 AM
  3. Need help finding a simple 'shortest path' algorithm
    By ashley in forum C Programming
    Replies: 2
    Last Post: 04-19-2007, 12:38 PM
  4. some help plz with finding long/shortest words
    By bethan in forum C Programming
    Replies: 4
    Last Post: 02-20-2005, 09:14 PM
  5. Finding Y coordinate
    By Extol in forum Windows Programming
    Replies: 3
    Last Post: 04-16-2003, 07:50 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21