Problems withRecursive Maze Solver

[FloridaJoe]

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.

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 

[King Mir]

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.

[FloridaJoe]

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.

[King Mir]

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.

[quzah]

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.

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.

[FloridaJoe]

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.

[quzah]

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.

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.