Thread: Shortest Path Maze Solver (Breadth Search Help)

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    16

    Shortest Path Maze Solver (Breadth Search Help)

    Hullo. My latest assignment in computar class has me trying to create a maze solver. Now it is not necessary for the computer to solve for the shortest path, however there are delicious extra marks if it does. I've already figured out how to solve the maze - using the recursive backtracking technique. I know a breadth search is used to find the shortest path in a maze solving problem. However I am having great trouble in trying to implement this algorithm (recursively).

    Now, this isn't done in the C programming language, its suppose to be done in Java. But the syntax is so similar you can post C code and I'll be able to tell what it is.

    Here's what I have so far (this is the recursive method).

    The maze is broken up into 'nodes'

    Maze: (S is start X is exit * is path and B is border)
    BBBBBBB
    B****BB
    X***SBB
    BBBBBBB

    Nodes:
    '0' '1' '2' '3' '4' '5' '6'
    '7' '8' '9' '10' '11' '12' '13'
    '14' '15' '16' '17' '18' '19' '20'
    '21' '22' '23' '24' '25' '26' '27'

    Now you start at S and place that node into an array specifically meant to hold nodes. Then you look up, down, left, and right for any 'path' symbols. If there is path symbol, place it in a que array. Then recursively call the method turning the recently discovered que into the new node. Continue until exit is found. I've tried doing this but it doesn't work. It will find the exit, but it is not the shortest path. Is there something I'm missing from the algorithm? I'm having some trouble understanding the algorithm, this is what I've got out of it so far.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Do you have to use breadth first search?

    In my (limited) experience, it's a pita, and noticeably slower than using depth first search, despite what you read in theory books.

    I'm confident we can find the shortest path with it.

    I'll post up a little example of it, in an edit to this, and see if you're not *really* tempted by it.

    This is a DFS on a "simple" 8 digit slide puzzle.

    Code:
    /* Will solve via brute force, the 8 tile 2D "rubik's cube" puzzle, when finished
    Adak, Nov. 2008 
    
    Status: just started 7/11/08
    */
    
    #include <stdio.h>
    
    void copyB(int);
    int move1(int);
    int move2(int);
    int move3(int);
    
    void showB(int);
    int isSolved(int);
    
    int b[2][4][20];    //b is shorthand for the board
    int t[1][4];        //t is a temporary holding row
    int line[20];       //the line of moves that are played
    
    int main(void)  {
       int i, r, row, c, col, move, deep, depth, solved, reset, gar;
    // test right shift    
    /*   b[0][0][0] = 2; b[0][1][0] = 3; b[0][2][0] = 4; b[0][3][0] = 1;
       b[1][0][0] = 7; b[1][1][0] = 6; b[1][2][0] = 5; b[1][3][0] = 8;
    */
    // test row swap
    /*   b[0][0][0] = 8; b[0][1][0] = 7; b[0][2][0] = 6; b[0][3][0] = 5;
       b[1][0][0] = 1; b[1][1][0] = 2; b[1][2][0] = 3; b[1][3][0] = 4;
    */
    // test Rotate 4 inner tiles
    /*   b[0][0][0] = 1; b[0][1][0] = 3; b[0][2][0] = 6; b[0][3][0] = 4;
       b[1][0][0] = 8; b[1][1][0] = 2; b[1][2][0] = 7; b[1][3][0] = 5;
    */
    // test depth of 2, solution 1 + 2
    /*   b[0][0][0] = 7; b[0][1][0] = 6; b[0][2][0] = 5; b[0][3][0] = 8;
       b[1][0][0] = 2; b[1][1][0] = 3; b[1][2][0] = 4; b[1][3][0] = 1;
    */
    //test depth of 2, solution 2 + 3  no depth=2 solution found for 1+3
       b[0][0][0] = 8; b[0][1][0] = 2; b[0][2][0] = 7; b[0][3][0] = 5;
       b[1][0][0] = 1; b[1][1][0] = 3; b[1][2][0] = 6; b[1][3][0] = 4;
    
    //test depth of , solution 
    /*   b[0][0][0] = ; b[0][1][0] = 2; b[0][2][0] = 1; b[0][3][0] = 4;
       b[1][0][0] = 8; b[1][1][0] = 7; b[1][2][0] = 6; b[1][3][0] = 5;
    */
       printf("\n Starting position:\n");
       showB(0);
       //getch();
       depth = deep = solved = reset = 0;
    
       do  {
          move = 1; depth = 2;
    
            
          while(1)  {   // this is the main loop, for now
             ++deep;
             if(move == 1)
                solved = move1(deep);
             else if(move == 2)
                solved = move2(deep);
             else
                solved = move3(deep);
    
             if(solved) 
                break;
    
             if(reset)  {    //depth was reset, move needs to reset to 1 again
                move = 1;
                reset = 0;
                continue;
             }
    
    
             if(deep >= depth)  {
                line[deep-1] = 0;
                deep = depth - 1;
                if(++move > 3) { 
                   deep -= 1;
                   move = line[deep] + 1;
                   if(move > 1)
                      reset = 1;
                }
             }
          }
    
       }while(!solved);
    
       printf("\n\n\t Press Enter to Quit\n ");
       gar = getchar(); gar++;
       return 0;
    }
    void copyB(int d)  {  //copy the old board position, into the new depth
       int r, c, temp;    
       
       for(r = 0; r < 2; r++) 
          for(c = 0; c < 4; c++)
             b[r][c][d] = b[r][c][d-1];
    }
    int move1(int d)  {  //shifts all numbers one column to the right &  wraps
       int r, c, solved, temp;
       solved = 0;
       printf("\n Right shift:");
       copyB(d);
       //showB(d);
       //++d;
    
       for(r = 0; r < 2; r++)  {
          temp = b[r][3][d];
          for(c = 2; c >-1 ; c--)  
             b[r][c+1][d] = b[r][c][d];
          b[r][0][d] = temp;
       }
       
       showB(d);
       line[d-1] = 1;
       solved = isSolved(d);
       
       return solved;
    }
    int move2(int d)  { //swaps rows
       int r, c, solved;
       solved = 0;
       printf("\n Swap rows:");
       copyB(d);
       //showB(d);
       
       for(c = 0; c < 4; c++)  {
          t[0][c] = b[0][c][d];
          b[0][c][d] = b[1][c][d];
          b[1][c][d] = t[0][c];
       }
    
       showB(d);
       line[d-1] = 2;
       solved = isSolved(d);
       
       return solved;
    }
    int move3(int d) { //turns the 4 inner tiles, clockwise
       int r, c, solved, temp;
       solved = 0;
       printf("\n Rotate 4 inner tiles:");
       copyB(d);
       //showB(d);  
    
       temp = b[0][1][d];
       b[0][1][d] = b[1][1][d];
       b[1][1][d] = b[1][2][d];
       b[1][2][d] = b[0][2][d];
       b[0][2][d] = temp;
    
       showB(d);
       line[d-1] = 3;
       solved = isSolved(d);
       
       return solved;
    }         
    void showB(int d)   {
       int r, c, tab;
       printf("\n");
       for(tab = 0; tab < d; tab++)
          putchar('\t');
       for(r = 0; r < 2; r++) {
          for(c = 0; c < 4; c++)  
             printf(" %d", b[r][c][d]);
          putchar('\n');
          for(tab = 0; tab < d; tab++)
             putchar('\t');
       }
    }
    int isSolved(int d)  {
       int i, gar;
       int done = 0;
       if(b[0][0][d]==1 && b[0][1][d]==2 && b[0][2][d]==3 && b[0][3][d]==4)
          if(b[1][0][d]==8 && b[1][1][d]==7 && b[1][2][d]==6 && b[1][3][d]==5)  {
             done = 1;
             printf("\n\n\t\t It's solved!");
             showB(d);
             printf("\t Line: ");
             for(i = 0; i < d; i++)
               printf(" %d", line[i]);
    
             //printf("\n\t Press Enter to Continue");
             //gar = getchar(); ++gar;
          }
          
       return done;
    }
    Last edited by Adak; 04-05-2009 at 10:59 PM.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Yes a breadth-first search is essentially going to find the shortest path, but it will be very slow!
    To speed it up, rather than examining all paths of length n before those of length n+1, you have a heuristic that biases it towards following those paths that are getting you measurably closer to the goal. This is the basic idea behind the algorithm called A*. That algorithm is what you need to read up on.
    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"

  4. #4
    Registered User
    Join Date
    Feb 2009
    Posts
    16
    I got it to work

    Turns out there was a lot more involved then I thought there was. We didn't have to use breadth first search I just decided on that one because it seemed to be the easiest out of the 'find the quickest route' bunch. Thanks for the suggestions and thanks Adak for the code on depth, I'll sure use it for reference.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Well done, R Man!

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    BFS is a really fun exercise. You could have really wowed your professor if you had let them pick which method they wanted to use from a menu.

    Anyway, back to BFS:
    Code:
    add the starting point to the first list
    while not at the exit 
        for each room in one list
            if not exit
                add its neighbors to the other list
            else
                return the shortest path
        swap lists
    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. shortest path problems
    By talz13 in forum C++ Programming
    Replies: 7
    Last Post: 05-08-2004, 06:13 AM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  3. linked list recursive function spaghetti
    By ... in forum C++ Programming
    Replies: 4
    Last Post: 09-02-2003, 02:53 PM
  4. Pathfinding AI? (Not the A* Algorithim)
    By harryP in forum C++ Programming
    Replies: 22
    Last Post: 08-01-2003, 02:32 PM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM