Thread: Navigating a maze recursively

  1. #1
    Registered User
    Join Date
    May 2003
    Posts
    26

    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';
    		}
    	}
    
    }

  2. #2
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    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.
    DavT
    -----------------------------------------------

  3. #3
    Registered User
    Join Date
    May 2003
    Posts
    26

    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);
    			}
    		}			
    
    	}
    	
    }

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    26
    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);
    			}
    		}
    
    	}
    	
    }

  5. #5
    Registered User
    Join Date
    May 2003
    Posts
    26
    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';
    		}
    	}
    
    }

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. Having trouble solving maze.
    By eurus in forum C Programming
    Replies: 3
    Last Post: 02-17-2006, 01:52 AM
  3. Solving A Maze Using C Language!!!!
    By jonnybgood in forum C Programming
    Replies: 6
    Last Post: 11-08-2005, 12:15 PM
  4. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 09:28 AM
  5. My Maze Game --- A Few Questions
    By TechWins in forum Game Programming
    Replies: 18
    Last Post: 04-24-2002, 11:00 PM