Problems withRecursive Maze Solver

This is a discussion on Problems withRecursive Maze Solver within the C Programming forums, part of the General Programming Boards category; My first post so will try my best to follow protocol. If it doesn't look like I know what I ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    3

    Problems withRecursive Maze Solver

    My first post so will try my best to follow protocol. If it doesn't look like I know what I doing you're right. I'm in second semester of CS program and have assignment to write recursive maze solving program. I've got one maze in which I've loaded cell values that determine the walls for that cell. I've got a second maze that I'm using to go through the maze leaving an 'O' visited cell.

    I'm about in panic mode over a couple things and would greatly appreciate any help: 1) Can't figure out why my takeStep function doesn't work. 2) How do I merge and print the maze with the wall info with the maze that has my path info? 3) How do I backtrack from a deadend?

    Just saw indents in my code aren't showing in post preview. Not sure why. Thanks for any help.

    Code:
    int main(int argc, char** argv)
    26 { 
    27 FILE* dataptr;
    28 
    29 msT* ms = (msT*)malloc (sizeof(msT));
    30 
    31 char** mspth = (char**)malloc (sizeof (char**));
    32 
    33 dataptr = fopen (argv [1], "r");
    34 if (!dataptr)
    35 {
    36 printf("Could not open file.\n\n");
    37 return EXIT_FAILURE;
    38 }
    39 
    40 ms = getMazedata (dataptr, ms);
    41 
    42 solveMaze (ms, mspth);
    43 
    44 return 0;
    45 }
    46 
    47 
    
    
    
    100 
    101 
    102 void solveMaze (msT* ms, char** mspth)
    103 {
    104 int i;
    105 int pp_row = ms->xs;
    106 int pp_col = ms->ys; 
    107 
    108 mspth = malloc(sizeof(char*) * ms->N);
    109 for (i=0; i < ms->N; i++)
    110 {
    111 mspth[i] = malloc(sizeof(char) * ms->M); 
    112 }
    113 
    114 mspth[ms->xs][ms->ys] = 'S'; //Loads start point.
    115 
    116 mspth[ms->xe][ms->ye] = 'F'; //Loads end point.
    117 
    118 
    119 takeStep(ms, mspth, pp_row, pp_col);
    120 
    121 return;
    122 
    123 }
    124 
    125 
    126 void takeStep(msT* ms, char** mspth, int pp_row, int pp_col)
    127 {
    128 int get;
    129 
    130 if((pp_row != 0) && (ms->maze[pp_row][pp_col] & north != 0) && (mspth [pp_row - 1][pp_col]!= 'X'))
    131 {
    132 pp_row --;
    133 }
    134 
    135 else
    136 {
    137 if((pp_col != ms->M) && (ms->maze[pp_row][pp_col] & east != 0) && (mspth [pp_row][pp_col + 1]!= 'X'))
    138 {
    139 pp_col ++;
    140 }
    141 else
    142 {
    143 if((pp_row != ms->N) && (ms->maze[pp_row][pp_col] & south != 0) && (mspth [pp_row + 1][pp_col]!= 'X'))
    144 {
    145 pp_row ++;
    146 }
    147 else
    148 {
    149 if((pp_col != 0) && (ms->maze[pp_row][pp_col] & west != 0) && (mspth [pp_row][pp_col - 1]!= 'X'))
    150 {
    151 pp_col --;
    152 }
    153 } 
    154 } 
    155 } 
    156 
    157 
    158 printf("print maze here\n\n"); // planed location for print maze function
    159 
    160 if (mspth[pp_row][pp_col] == "F") printf("Maze Solved\n\n");
    161 else
    162 {
    163 mspth[pp_row][pp_col] = 'O'; 
    164 }
    165 
    166 get = getc(stdin);
    167 
    168 takeStep(ms, mspth, pp_row, pp_col);
    169 
    170 }
    171 
    

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    You should indent your code like all the examples of C code everywhere.

    In order to modify pp_col, and pp_row, you need to pass them by reference; pass a pointer to them.

    You need to work out an algorithm for solving mazes on paper before you program it. Alternatively, search Google or Wikipedia.

    As for merging and printing, you need to decide what your desired output is, then work from there.
    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 2011
    Posts
    3
    As I said in my post, code was indented when I pasted it in but lost indents when I saw post preview. Is there a trick to keeping them or do I just reindent after pasting in the post box? ms output has just wall info i.e.
    +---+---+---+
    | |
    + +---+---+
    | | | |
    + + + +
    | |
    +---+---+---+

    mspth info i.e.
    O O O O O F
    O
    O X
    O O O O O S
    Pretty much exhausted Google will try Wikipedia next Thx. Have tried editing maze outputs twice but keep losing spaces for some reasong.
    Last edited by FloridaJoe; 10-23-2011 at 01:59 PM.

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    There are several ways to try to solve a maze.

    A common algorithm is depth first search, which treats a maze like a graph, will try going as far as it can, marking with some kind of breadcrumbs the path that it tries, and backtracks at every dead end to the previous intersection, never retrying the same path, because of the breadcrumbs.

    Another way, without breadcrumbs, is to follow a wall. This requires keeping track of not only location, but also facing direction. However it doesn't require breadcrumbs. Also, this won't work on mazes where there are multiple paths to the end and the end it not on the perimeter of the maze.
    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.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    void solveMaze (msT* ms, char** mspth)
    {
        int i;
        int pp_row = ms->xs;
        int pp_col = ms->ys; 
    
        mspth = malloc(sizeof(char*) * ms->N);
        for (i=0; i < ms->N; i++)
        {
            mspth[i] = malloc(sizeof(char) * ms->M); 
        }
        mspth[ms->xs][ms->ys] = 'S'; //Loads start point.
        mspth[ms->xe][ms->ye] = 'F'; //Loads end point.
        takeStep(ms, mspth, pp_row, pp_col);
        return;
    }
    You have a memory leak when this function returns, because you never free anything. You don't actually even need to be passing mspth because you can't assign it anything more than a char* and have it keep outside of the function.
    Code:
    void takeStep(msT* ms, char** mspth, int pp_row, int pp_col)
    {
        int get;
        if((pp_row != 0) && (ms->maze[pp_row][pp_col] & north != 0) && (mspth [pp_row - 1][pp_col]!= 'X'))
    You also haven't actually initialized mspth to have any useful values in it before you start passing it over to your take a step function.


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Oct 2011
    Posts
    3
    Ref memory leak: my idea was I'd be printing (as tasked) the maze with each step taken at each hit of the enter key and I'd be in takeStep till solution. Then the pgm would return to solveMaze and to main and end at which time allocated memory automatically goes back to OS. Are you saying proper thing to do is free mspth when exiting takeStep?

    Good point on initalizing mspth otherwise it'll just print garbage in all unvisited cells, but what did you mean by "useful info"? Each unvisited cell besides start ('S') and finish ('F') were going to be empty anyway.

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by FloridaJoe View Post
    Ref memory leak: my idea was I'd be printing (as tasked) the maze with each step taken at each hit of the enter key and I'd be in takeStep till solution. Then the pgm would return to solveMaze and to main and end at which time allocated memory automatically goes back to OS. Are you saying proper thing to do is free mspth when exiting takeStep?
    Of course. If you don't need something any more, get rid of it. If you allocate, you should free. C doesn't have a garbage collector. You shouldn't just allocate stuff and never free it.
    Quote Originally Posted by FloridaJoe View Post
    Good point on initalizing mspth otherwise it'll just print garbage in all unvisited cells, but what did you mean by "useful info"? Each unvisited cell besides start ('S') and finish ('F') were going to be empty anyway.
    Useful info as in whatever it is you expect to be stored there. You immediately check some spot for & north without ever having set what is supposed to be there to check against.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. maze solver
    By iamnew in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2010, 02:46 AM
  2. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 07:41 PM
  3. Recursive Stack Algorithm Maze Solver
    By unrestricted in forum C Programming
    Replies: 0
    Last Post: 09-04-2007, 03:11 AM
  4. CHeck my Maze Solver
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 07-31-2003, 10:37 PM
  5. Maze game, complete with maze editor and an example maze!
    By Brian in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 01-20-2002, 02:27 AM

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