3 replies to this topic

[posto2012]

Problem with recursive function
Hello,

I am writing a program that navigates a maze. I am trying to use a recursive function to do so. My problem is the function stops working partway through. This is the maze I am using:

ooooooooooo
o ```````` o
o`ooooooo `o
o+o```````o
ooo`ooooooo
o$o``````$o
o`o`ooooooo
o````````-o
ooooooooooo

The function gets as far as this and quits

ooooooooooo
o ########o
o #ooooooo `o
o+o```````o
ooo`ooooooo
o$o``````$o
o`o`ooooooo
o````````-o
ooooooooooo

void findDollar ( maz_t  *t){ // function to find checkpoint


	int i, j;


	 for (i=0;i<row;i++){  // loop to find a checkpoint

		for(j=0;j<column;j++){

			if (t->map[i][j] == '$'){

				t->dollarX = i;

				t->dollarY = j;

			}

		}

	 }

	


	if(t->map[t->startx-1][t->starty] != 'o' && t->map[t->startx-1][t->starty] != '#'){ // moves up

		  t->map[t->startx-1][t->starty] = '#';

		  t->startx = t->startx-1;

		

	}

	    else if(t->map[t->startx+1][t->starty] != 'o' && t->map[t->startx+1][t->starty] != '#'){ // moves down

		  t->map[t->startx+1][t->starty] = '#';

		  t->startx = t->startx+1;

		}

	      else if(t->map[t->startx][t->starty-1] != 'o' && t->map[t->startx][t->starty-1] != '#'){ // moves to the left

		  t->map[t->startx][t->starty-1] = '#';

		  t->starty = t->starty-1;

		  }

		  

	        else if(t->map[t->startx][t->starty+1] != 'o' && t->map[t->startx][t->starty+1] != '#'){ // moves to the right

		    t->map[t->startx][t->starty+1] = '#';

		    t->starty = t->starty+1;

			}

		

			if (t->startx != t->dollarX && t->starty != t->dollarY){  // If the checkpoint has not been reached, call function again.

			findDollar(t);

			}



  }// end function

I'm assuming that it's something with the way I am directing it to move down, but I can't see the problem. Any help would be greatly appreciated.

[TkTech]

Mind posting the entire thing, I don't feel like rebuilding your map by hand to test it.

[posto2012]

 #include <stdio.h>

#include <string.h>

#include <stdlib.h>


 


typedef struct maz {  // define structure for maze

 char map[40][40];

 int startx , starty;

 int dollarX, dollarY;

 int endX, endY;


} maz_t;


 


typedef struct node {  // define structure for nodes

 struct node *up, *down, *left, *right;

 int x, y;

 

} node_t;


 void findDollar( maz_t  *t);


 int row, column;


int main(){

int  i, j, x, y;// intitialize variables

FILE *myfile;

   

char maze[40][40];

node_t graph[40][40];

	maz_t mymaze;

 myfile = fopen("maze3.txt", "r"); // open text file for reading


 if(!myfile){  // if file does not exist

    printf("File not found.");

 }


 else {

  fscanf(myfile, "%d %d", &row, &column); // read in row and column values

  printf ("%d %d\n", row, column);

 

  

  for (i=0;i<row;i++){  // read in maze

	  fscanf(myfile, " %[^\n]", maze[i]);

  }

 

	for (i=0;i<row;i++){

		strcpy(mymaze.map[i], maze[i]);

	}


  

	for (i=0;i<row;i++){  //print original maze

		printf ("%s\n", mymaze.map[i]);

	}

	

  

 

  for (i=0;i<row;i++){  // loop to find start point

   for(j=0;j<column;j++){

	   if (mymaze.map[i][j] == '+'){

     mymaze.startx = i;

     mymaze.starty = j;

    }

   }

  }


  for (i=0;i<row;i++){  // loop to find end point

   for(j=0;j<column;j++){

	   if (mymaze.map[i][j] == '-'){

		mymaze.endX = i;

     mymaze.endY = j;

    }

   }

  }

  


	findDollar (&mymaze); // function for finding checkpoint

	

	for (i=0;i<row;i++){ // print maze

       printf("%s\n", mymaze.map[i]);

	}	


 }

 // end else 

 return 0;

 

}

  

	void findDollar ( maz_t  *t){ // function to find checkpoint


	int i, j;


	 for (i=0;i<row;i++){  // loop to find a checkpoint

		for(j=0;j<column;j++){

			if (t->map[i][j] == '$'){

				t->dollarX = i;

				t->dollarY = j;

			}

		}

	 }

	


	if(t->map[t->startx-1][t->starty] != 'o' && t->map[t->startx-1][t->starty] != '#'){ // moves up

		  t->map[t->startx-1][t->starty] = '#';

		  t->startx = t->startx-1;

		

	}

	    else if(t->map[t->startx+1][t->starty] != 'o' && t->map[t->startx+1][t->starty] != '#'){ // moves down

		  t->map[t->startx+1][t->starty] = '#';

		  t->startx = t->startx+1;

		}

	      else if(t->map[t->startx][t->starty-1] != 'o' && t->map[t->startx][t->starty-1] != '#'){ // moves to the left

		  t->map[t->startx][t->starty-1] = '#';

		  t->starty = t->starty-1;

		  }

		  

	        else if(t->map[t->startx][t->starty+1] != 'o' && t->map[t->startx][t->starty+1] != '#'){ // moves to the right

		    t->map[t->startx][t->starty+1] = '#';

		    t->starty = t->starty+1;

			}

		

			while (t->startx != t->dollarX && t->starty != t->dollarY){  // If the checkpoint has not been reached, call function again.

			findDollar(t);

			}



  }// end function

[speculatius]

Hello,

I think this could be the problem... Before you enter new level of recursion, you set char '#' on some position. For step left it is:

t->map[t->startx-1][t->starty] = '#';

t->startx = t->startx-1;

So when you get back from this recursion, you should do reverse operation. When you arrive from step left:

t->map[t->startx][t->starty] = '`';

t->startx = t->startx+1;