# Navigating a maze recursively

• 06-04-2003
JOsephPataki
Navigating a maze recursively
Hi I'm trying to teach myself cprogramming. I'm a couple of chapters past recursive and decided to go back and see if I can do this problem from the end of that chapter. This is what I have so far.

Right now I'm stuck at a logic error where I am trying to use function move to get from 0,0 to 7,7. I didn't add in any obstacles so I can finish move function first. I'm really bad at making recursive functions so I get stopped very easily.
Anyways what I have so far is, I'm just moving along the horizontal.
It gets to 6,0 from 0,0 and stops. When I should get to 7,0.

Thanks for any help

Code:

```// Navigate a maze using recursive #include <stdio.h> #include <string.h> #define ARSIZ 8 void initialize_array(int maze[ARSIZ][ARSIZ], int x, int y, int tf); void move(int maze[ARSIZ][ARSIZ], int x, int y, int tf); void neighbors(int maze[ARSIZ][ARSIZ],char check[4], int x, int y); int main(){         int maze[ARSIZ][ARSIZ];         int n = ARSIZ - 1;         initialize_array(maze, n, n, 0);         move(maze,0,0,0);         return 0; } //set the maze so there are no obstacles until I finish navigation part. void initialize_array(int maze[8][8], int x, int y, int tf){         if(tf == 1){                 if(x > 0){                         //change first array element position                         initialize_array(maze,x-1,ARSIZ-1,0);                 }         }else{                 if(y >= 0){                         //change second array element position                         initialize_array(maze,x,y-1,0);                         maze[x][y] = 0;                 }else{                         //go back to first array element position manipulation                         initialize_array(maze,x,y,1);                 }         } } //Ahhhhhhh HELP void move(int maze[ARSIZ][ARSIZ], int x, int y, int tf){         char check[5];         if(tf == 1){         }         else{                 neighbors(maze,check,x,y);                 if(check[0] == '1'){                         printf("%d,%d\t%s\n",x,y,check);                         move(maze,x+1,y,0);                 }         }         } void neighbors(int maze[ARSIZ][ARSIZ],char check[5], int x, int y){         //check[0] = right         //check[1] = left         //check[2] = up         //check[3] = down         strcpy(check,"0000");         //         if(x < ARSIZ - 1){                 if(maze[x+1][y] == 0){                         check[0] = '1';                 }         }         if(x != 0){                 if(maze[x-1][y] == 0){                         check[1] = '1';                 }         }         if(y != 0){                 if(maze[x][y-1] == 0){                         check[2] = '1';                 }         }         if(y != 7){                 if(maze[x][y+1] == 0){                         check[3] = '1';                 }         } }```
• 06-05-2003
DavT
Quote:

Anyways what I have so far is, I'm just moving along the horizontal.
It gets to 6,0 from 0,0 and stops. When I should get to 7,0.
if you change your move function very slightly:
Code:

```void move(int maze[ARSIZ][ARSIZ], int x, int y, int tf){   char check[5];   if(tf == 1){   }   else{     neighbors(maze,check,x,y);     printf("%d,%d\t%s\n",x,y,check);     if(check[0] == '1'){       move(maze,x+1,y,0);     }   }        }```
by printing the state outside of the if statement that checks if the next move is valid, you can see that you have indeed made it to position {7,0} with sensible 'check' values.
• 06-05-2003
JOsephPataki
hmmmm..
Thanks for that, but now I am stuck again.

I've created a little pocket of obstacles at 6,1 6,2 and 7,2

0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0

Right now I'm just using a lot of if's and how I thought it would work is go all the way right. Hit the wall go down, hit the obstacle look for another way to go, go up, go left and try to go down, it can't so move left one more and try to go down.

I charted its path, and as it is going left and trying to move down, it goes left one more time than is necessary.

Code:

```void initialize_array(int maze[8][8], int x, int y, int tf){         if(tf == 1){                 if(x > 0){                         initialize_array(maze,x-1,ARSIZ-1,0);                 }         }else{                 if(y >= 0){                         initialize_array(maze,x,y-1,0);                         maze[x][y] = 0;                         if(x == 6 && y == 1){                                 maze[x][y] = 1;                         }                         if(x == 6 && y == 2){                                 maze[x][y] = 1;                         }                         if(x == 7 && y == 2){                                 maze[x][y] = 1;                         }                 }else{                         initialize_array(maze,x,y,1);                 }         } } void move(int maze[ARSIZ][ARSIZ], int x, int y, int tf){         char check[5];         printf("%d,%d\t\n",x,y);         if(x != (ARSIZ-1) || y != (ARSIZ-1)){                 //up2 & left1                 if(tf == 1){                         neighbors(maze,check,x,y);                         if(check[2] == '1'){                                 move(maze,x,y-1,1);                         }else if(check[1] == '1'){                                 move(maze,x-1,y,2);                         }else if(check[0] == '1'){                                 move(maze,x+1,y,0);                         }else if(check[3] == '1'){                                 move(maze,x,y+1,0);                         }                 }                 //down3 & right0                 else if(tf == 0){                         neighbors(maze,check,x,y);                         if(check[0] == '1'){                                 move(maze,x+1,y,0);                         }else if(check[3] == '1'){                                 move(maze,x,y+1,0);                         }else if(check[1] == '1'){                                 move(maze,x-1,y,2);                         }else if(check[2] == '1'){                                 move(maze,x,y-1,1);                         }                 }                 else if(tf == 2){                         neighbors(maze,check,x,y);                         if(check[3] == '1'){                                 move(maze,x,y+1,0);                         }else if(check[1] == '1'){                                 move(maze,x-1,y,1);                         }                 }                                }         }```
• 06-05-2003
JOsephPataki
Can someone help me with this function. I had it semi-working earlier. It could navigate certain obstacles. But the way I had it going was it would go right,down,left, then up is last resort. If I blocked it off so it had to go straight down on first try and made it have to turn right somewhere in the middle of the wall it would keep going up and down and up and down without being able to turn. I fixed that, but that messed up something else. Now I've just been changing everything in a random order hoping it would work, but making it worse.

Code:

```//Ahhhhhhh HELP void move(int maze[ARSIZ][ARSIZ], int x, int y, int tf){         char check[5];         printf("%d,%d\t\n",x,y);         if(x != (ARSIZ-1) || y != (ARSIZ-1)){                 //right0                 if(tf == 0){                         //printf("I'm in 1\n");                         //move(maze,x+1,y,0);                         //move(maze,x-1,y,1);                         //move(maze,x,y-1,2);                         //move(maze,x,y+1,3);                         neighbors(maze,check,x,y);                         if(check[3] == '1'){                                 move(maze,x,y+1,3);                         }else if(check[0] == '1'){                                 move(maze,x+1,y,0);                         }else if(check[2] == '1'){                                 move(maze,x,y-1,2);                         }else if(check[1] == '1'){                                 move(maze,x-1,y,1);                         }                 }                 //left1                 else if(tf == 1){                         //printf("I'm in 0\n");                         neighbors(maze,check,x,y);                         if(check[2] == '1'){                                 move(maze,x,y-1,2);                         }else if(check[1] == '1'){                                 move(maze,x-1,y,1);                         }else if(check[3] == '1'){                                 move(maze,x,y+1,3);                         }else if(check[0] == '1'){                                 move(maze,x+1,y,0);                         }                 }                 //up2                 else if(tf == 2){                         //printf("I'm in 2\n");                         neighbors(maze,check,x,y);                         if(check[1] == '1'){                                 move(maze,x-1,y,1);                         }else if(check[2] == '1'){                                 move(maze,x,y-1,2);                         }else if(check[0] == '1'){                                 move(maze,x+1,y,0);                         }else if(check[3] == '1'){                                 move(maze,x,y+1,3);                         }                 }                 //down 3                 else if(tf == 3){                                 neighbors(maze,check,x,y);                         if(check[0] == '1'){                                 move(maze,x+1,y,0);                         }else if(check[3] == '1'){                                 move(maze,x,y+1,3);                         }else if(check[1] == '1'){                                 move(maze,x-1,y,0);                         }else if(check[2] == '1'){                                 move(maze,x,y-1,2);                         }                 }         }         }```
• 06-06-2003
JOsephPataki
Ok I just had an idea on how I would defeat this problem. I would start at 0,0. Then I will check which direction(s) I can move to and move to all possibilities. From each of these new spaces I would move to every possibility again. The only problem is I don't know how to display the quickest path. I'm also suppose to design this with the possibility that no path exists and in this case I would not display any path coordinates and just display no path exists.

here is complete update..

Code:

```// Navigate a maze using recursive #include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> #define ARSIZ 8 void initialize_array(int maze[ARSIZ][ARSIZ], int x, int y, int tf); void print_array(int maze[ARSIZ][ARSIZ]); void move(int maze[ARSIZ][ARSIZ], int x, int y, int prevdirect); void neighbors(int maze[ARSIZ][ARSIZ],char check[4], int x, int y); int main(){         int maze[ARSIZ][ARSIZ];         int n = ARSIZ - 1;         int arbitarray[3];         int a;         for(a = 0; a<=2; a++){                 arbitarray[a] = 0;         }         srand((unsigned)time( NULL ));         initialize_array(maze, n, n, 0);         print_array(maze);         move(maze,0,0,1);         return 0; } //set the maze so there are no obstacles until I finish navigation part. void initialize_array(int maze[8][8], int x, int y, int tf){         int myRand;         if(tf == 1){                 if(x > 0){                         initialize_array(maze,x-1,ARSIZ-1,0);                 }         }else{                 if(y >= 0){                         initialize_array(maze,x,y-1,0);                         /*myRand = rand() % 100 + 1;                         if(myRand >= 75){                                 maze[x][y] = 1;                         }else{                                 maze[x][y] = 0;                         }                         if(((x == 0) && (y == 0)) || ((x == 7) && (y == 7))){                                 maze[x][y] = 0;                         }*/                         maze[x][y] = 0;                                                 if(x == 1 && y == 0){                                 maze[x][y] = 1;                         }                         if(x == 1 && y == 1){                                 maze[x][y] = 1;                         }                         if(x == 1 && y == 2){                                 maze[x][y] = 1;                         }                         if(x == 1 && y == 3){                                 maze[x][y] = 1;                         }                         if(x == 1 && y == 4){                                 maze[x][y] = 1;                         }                         if(x == 1 && y == 5){                                 maze[x][y] = 1;                         }                         if(x == 1 && y == 7){                                 maze[x][y] = 1;                         }                         if(x == 3 && y == 7){                                 maze[x][y] = 1;                         }                         if(x == 4 && y == 7){                                 maze[x][y] = 1;                         }                         if(x == 4 && y == 6){                                 maze[x][y] = 1;                         }                         if(x == 4 && y == 5){                                 maze[x][y] = 1;                         }                         if(x == 3 && y == 5){                                 maze[x][y] = 1;                         }                 }else{                         initialize_array(maze,x,y,1);                 }         } } void print_array(int maze[ARSIZ][ARSIZ]){         int a,b;         for(a = 0; a <= ARSIZ-1;a++){                 for(b = 0; b <= ARSIZ-1; b++){                         printf("%d ",maze[b][a]);                 }                 printf("\n");         } } //Ahhhhhhh HELP void move(int maze[ARSIZ][ARSIZ], int x, int y, int prevdirect){         char check[5];         printf("%d,%d\n",x,y);         neighbors(maze,check,x,y);         if(x != (ARSIZ-1) || y != (ARSIZ-1)){                 if(prevdirect == 0){                         if(check[2] == '1'){                                 move(maze,x,y-1,2);                         }                         if(check[0] == '1'){                                 move(maze,x+1,y,0);                         }                         if(check[3] == '1'){                                 move(maze,x,y+1,3);                         }                 }                 if(prevdirect == 1){                         if(check[3] == '1'){                                 move(maze,x,y+1,3);                         }                         if(check[1] == '1'){                                 move(maze,x-1,y,1);                         }                         if(check[2] == '1'){                                 move(maze,x,y-1,2);                         }                 }                 if(prevdirect == 2){                         if(check[1] == '1'){                                 move(maze,x-1,y,1);                         }                         if(check[2] == '1'){                                 move(maze,x,y-1,2);                         }                         if(check[0] == '1'){                                 move(maze,x+1,y,0);                         }                 }                 if(prevdirect == 3){                         if(check[0] == '1'){                                 move(maze,x+1,y,0);                         }                         if(check[3] == '1'){                                 move(maze,x,y+1,3);                         }                         if(check[1] == '1'){                                 move(maze,x-1,y,1);                         }                 }         }         else{                 printf("You won");                 exit(1);         }         } void neighbors(int maze[ARSIZ][ARSIZ],char check[5], int x, int y){         //check[0] = right         //check[1] = left         //check[2] = up         //check[3] = down         strcpy(check,"0000");         //         if(x < ARSIZ - 1){                 if(maze[x+1][y] == 0){                         check[0] = '1';                 }         }         if(x != 0){                 if(maze[x-1][y] == 0){                         check[1] = '1';                 }         }         if(y != 0){                 if(maze[x][y-1] == 0){                         check[2] = '1';                 }         }         if(y != 7){                 if(maze[x][y+1] == 0){                         check[3] = '1';                 }         } }```