Hello!

I am trying to write a program using recursive functions to identify the path to a given maze. The thing that I am confused about is how to move to the next direction in order to check which way the path goes. For example:

000000
011100
010100
010110
0S00F0
000000

With this maze if I start at S, then I would have to check each side (left, right, up, and down) in order to see where the path continues. S-start F-finish 1-path 0-blocked.

Here is the code I have so far:

#include <iostream>
#include <fstream>
using namespace std;

enum Direction{N, S, E, W, failed};
Direction directionCheck;

bool findPath(char array[15][15],int x,int y);

int main(){
   char mazeArray[15][15];
   ifstream infile;
   infile.open("Home\\COSC220\\Project1\\mazereadin");
   for(int i=0;i<15;i++){
     for(int j=0;j<15;j++){
       infile>>mazeArray[i][j];
     }
   }
   bool path;
   path=findPath(mazeArray,13,1);
   if(path==true){
     for(int k=0;k<15;k++){
       for(int a=0;a<15;a++){
	 cout<<mazeArray[k][a]<<" ";
       }
       cout<<endl;
     }
   }
   infile.close();
   return 0;
}

bool findPath(char array[15][15],int x,int y){
  bool found;
  if(array[x][y]=='F')
    return true;
  else if(array[x][y]=='C' || array[x][y]=='X')
    return false;
  array[x][y]='X';
  if(array[x][y]=='O' || array[x][y]=='S'){
    if(array[x][y]!='C'){
      directionCheck=N;
      found=false;
    }
    while(found==false && directionCheck!=failed){
      if(directionCheck==N)
	found=findPath(array,x,y-1);
      else if(directionCheck==E)
	found=findPath(array,x+1,y);
      else if(directionCheck==S)
	found=findPath(array,x,y+1);
      else if(directionCheck==W)
	found=findPath(array,x-1,y);
      directionCheck++;
    }
    if(found==false){
      array[x][y]='O';
      return false;
    }
  }
}

Thanks for all your help!

If I was attacking this problem I would create two functions. The first one would find the starting position and the second one would be my recursive function.

Also, will the path through the array have loops in it?

Edited 5 Years Ago by gerard4143: n/a

I've already figured out how to find the starting point and I have the recursive function. I'm not sure what you mean will the path through the array have loops in it. I'm just not sure how to go about changing to the next direction.

Your original posting had a loop in the path which made solving it difficult. Try tracing
through this array and you'll find you have a loop where I indicated.

000000000000000
011111111011110
010000001000010
011111001111110//loop ends here
010001001000000//loop
011111001000000//loop starts here
000100001111110
000100000001010
000111111101010
010000001001010
010000001001000
011100001011110
000100001010000
0S11111110111F0
000000000000000

Are you talking about a circle in the maze or in the program?

Are you talking about a circle in the maze or in the program?

Yes, that circle makes solving your problem a very difficult task.

Wouldn't it not matter if you are only checking the next square from the one that it is at?

Wouldn't it not matter if you are only checking the next square from the one that it is at?

Because your only checking the next character for possible path directions you'll end up in an infinite loop when you encounter a path that loops back onto its self. If you think about it makes sense, you found this path once and nothing has changed so when you loop back you'll travel around again and again.

Edited 5 Years Ago by gerard4143: n/a

Well I have the program set so that once it goes through a box it places a X in the square so that if it runs into another X it says that it is blocked. But do you understand how to change directions that the program looks. Like it checks the up direction first but then I am not sure about how to make the program check the next direction.

Well I have the program set so that once it goes through a box it places a X in the square so that if it runs into another X it says that it is blocked. But do you understand how to change directions that the program looks. Like it checks the up direction first but then I am not sure about how to make the program check the next direction.

I still see a problem with your approach. Consider a path that has a loop in it, as your program walks through, one element a time X'ing out elements, it may inadvertently close the path prematurely, especially if you have to navigate through that loop to get to F. I would get this problem working for the simpler 'non-loop' path first and then look at a looped path.

Edited 5 Years Ago by gerard4143: n/a

Could you possibly explain the idea of how to navigate through with a non-loop path then please?

Hey! So I couldn't figure out how to reply to the message you sent but thank you so much! I figured out how to change the direction now and the program compiles, you were a lot of help!!! The only problem that I am having now is that instead of printing Xs where the program found the path to be its printing out random characters in the space of the maze. You wouldn't happen to know what's wrong would you? Again thanks so much!

Well I have the program set so that once it goes through a box it places a X in the square so that if it runs into another X it says that it is blocked. But do you understand how to change directions that the program looks. Like it checks the up direction first but then I am not sure about how to make the program check the next direction.

After a full night's sleep I realized your right. If you handle the logic correctly you can navigate a path with loops using the X out method.

This article has been dead for over six months. Start a new discussion instead.