I have an assingment in which i have to right an algorithim to get through a maze. I dont know where to really start with it. I know in the instructions it said to write it as though we used our right hand as a guide. in other words we walk through the maze with our right hand on the wall. if there is no wall we turn where the wall turns.in the end we will have traveled the whole maze but eventually get out. any help would be greatly appreciated.
thanks!!:)
hurbano 0 Junior Poster in Training
hurbano 0 Junior Poster in Training
i need help writing an algorithim to get through a maze. i have a rough idea on where to start but am not
entirely sure on the concept. i do know we have to write it as though we are using our right hand as a guide
hand. in other words we put our right hand on the wall. as we walk we use our right hand as a guide hand. if
we feel no wall we turn folling our right hand along the wall. we eventuall will get out of the maze. it is a slow
process but that is the way the assingment is. any help would be greatly appreciated. thanks!! =)
Coder++ 0 Newbie Poster
just do what your teacher said then man ;). Assuming your maze is an integer array of zeros and ones then just have your program keep moving "forward" in a sense that forward is constantly changing, and assuming zero is walkable and one is a wall, check whether or not the block to the right of you is a one. If the block isn't a one, change forward to that direction and your app will move in that direction now, because it is forward ;).
ie: (very tiny map for example hehe)
int map[5] = {
{1,1,1,1,1},
{1,0,0,0,2},
{1,0,1,1,1},
{1,0,0,0,1},
{1,1,1,1,1},
};
//...
std::string direction;
int x = 3; //x is 'y' because the array coordinates are backwards ;)
int y = 3 //as y is 'x'
//...
if (direction == "left")
{
if (map[y - 1][x] == 0)
direction = "up";
}
//...
return 0;
}
that only provides for left but i think you can figure the rest out right? pm me if you still don't get it. And are you sure your teacher doesn't want you to use the pathfinding algorithm?
lllllIllIlllI 178 Veteran Poster
Here is an A* Path finding tutorial, it will be able to help, because path finding is probably the easiest way to get through this problem.
http://www.policyalmanac.org/games/aStarTutorial.htm
hurbano 0 Junior Poster in Training
i have something like this so far. our group came up with this but im not sure if its whats supposed to be. thanks
void mazeWalk(char** &maze, int xCoord, int yCoord, int direction)
{
printMaze(maze);
maze[xCoord][yCoord]='x';
if(yCoord==11)
{
cout<<"Maze has been successfully solved! :)";
return;
}
if(yCoord==0)
{
maze[xCoord][yCoord]='x';
cout<<"Begin MAZE!!!";
//return;
}
int count=0;
for(int move=direction; count <4;(move++)%4, count ++)
{
if( direction==RIGHT)
{
if(move==RIGHT)
{
if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
mazeWalk(maze,xCoord, yCoord+1,RIGHT);
}
else if (move==DOWN)
{
if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
mazeWalk(maze, xCoord-1,yCoord, RIGHT);
}
else if (move==LEFT)
{
if (yCoord!=1)
if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
mazeWalk(maze, xCoord,yCoord-1, RIGHT);
}
else if (move==UP)
{
if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
mazeWalk(maze, xCoord+1,yCoord, RIGHT);
}
}
else if( direction==DOWN)
{
if(move==RIGHT)
{
if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
mazeWalk(maze,xCoord, yCoord+1,RIGHT);
}
else if (move==DOWN)
{
if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
mazeWalk(maze, xCoord-1,yCoord, RIGHT);
}
else if (move==LEFT)
{
if (yCoord!=1)
if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
mazeWalk(maze, xCoord,yCoord-1, RIGHT);
}
else if (move==UP)
{
if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
mazeWalk(maze, xCoord+1,yCoord, RIGHT);
}
}
else if( direction==LEFT)
{
if(move==RIGHT)
{
if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
mazeWalk(maze,xCoord, yCoord+1,RIGHT);
}
else if (move==DOWN)
{
if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
mazeWalk(maze, xCoord-1,yCoord, RIGHT);
}
else if (move==LEFT)
{
if (yCoord!=1)
if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
mazeWalk(maze, xCoord,yCoord-1, RIGHT);
}
else if (move==UP)
{
if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
mazeWalk(maze, xCoord+1,yCoord, RIGHT);
}
}
else if( direction==UP)
{
if(move==RIGHT)
{
if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
mazeWalk(maze,xCoord, yCoord+1,RIGHT);
}
else if (move==DOWN)
{
if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
mazeWalk(maze, xCoord-1,yCoord, RIGHT);
}
else if (move==LEFT)
{
if (yCoord!=1)
if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
mazeWalk(maze, xCoord,yCoord-1, RIGHT);
}
else if (move==UP)
{
if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
mazeWalk(maze, xCoord+1,yCoord, RIGHT);
}
}
}
} hurbano 0 Junior Poster in Training
Correction!
This is the code we got. Were confident it works but can anyone help us as to why it does not begin. we were just supposed to write the algorithim to get through the maze but the rest was given to us by the teacer. why does it not work? we do not understand what it means by "the solution will be printed in the output file" how do we set that up? sorry if the answer is simple. were just stressed and cant seem to get it at the moment. any help would begreatly appreciatied. thanks
#include <iostream>
#include <string>
#include <fstream>
#define DOWN 0
#define RIGHT 1
#define UP 2
#define LEFT 3
using namespace std;
void initMaze(char** &);
void mazeWalk(char** &, int, int, int);
void printMaze (char** &);
int Rows, Columns;
int XSTART, YSTART;
ifstream indata;
ofstream outdata;
int main (int argc, char* argv[])
{
if ( argc != 3 )
{
cerr << "The program should take two arguments, \nthe names of the input and output files!" <<endl;
cerr << "The input file is a plain text file with a maze; the solution will be printed in the output file" <<endl;
return 0;
}
indata.open(argv[1]);
outdata.open(argv[2]);
char **maze;
initMaze(maze);
mazeWalk(maze, XSTART, YSTART, RIGHT);
printMaze(maze);
for (int i=0; i<Rows; i++)
delete maze[i];
delete maze;
indata.close();
outdata.close();
return 0;
}
void initMaze(char** &maze)
{
Rows = 12;
Columns = 12;
maze = new char*[Rows];
for (int i=0; i<Rows; i++)
maze[i] = new char[Columns];
for (int i=0; i<Rows; i++)
for (int j=0; j<Columns; j++)
indata >> maze[i][j];
indata >> XSTART >> YSTART;
return;
}
void mazeWalk(char** &maze, int xCoord, int yCoord, int direction)
{
printMaze(maze);
maze[xCoord][yCoord]='x';
if(yCoord==11)
{
cout<<"Maze has been successfully solved!!";
return;
}
if(yCoord==0)
{
maze[xCoord][yCoord]='x';
cout<<"Begin MAZE!!!";
//return;
}
int count=0;
for(int move=direction; count <4;(move++)%4, count ++)
{
if( direction==RIGHT)
{
if(move==RIGHT)
{
if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
mazeWalk(maze,xCoord, yCoord+1,RIGHT);
}
else if (move==DOWN)
{
if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
mazeWalk(maze, xCoord-1,yCoord, RIGHT);
}
else if (move==LEFT)
{
if (yCoord!=1)
if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
mazeWalk(maze, xCoord,yCoord-1, RIGHT);
}
else if (move==UP)
{
if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
mazeWalk(maze, xCoord+1,yCoord, RIGHT);
}
}
else if( direction==DOWN)
{
if(move==RIGHT)
{
if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
mazeWalk(maze,xCoord, yCoord+1,RIGHT);
}
else if (move==DOWN)
{
if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
mazeWalk(maze, xCoord-1,yCoord, RIGHT);
}
else if (move==LEFT)
{
if (yCoord!=1)
if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
mazeWalk(maze, xCoord,yCoord-1, RIGHT);
}
else if (move==UP)
{
if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
mazeWalk(maze, xCoord+1,yCoord, RIGHT);
}
}
else if( direction==LEFT)
{
if(move==RIGHT)
{
if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
mazeWalk(maze,xCoord, yCoord+1,RIGHT);
}
else if (move==DOWN)
{
if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
mazeWalk(maze, xCoord-1,yCoord, RIGHT);
}
else if (move==LEFT)
{
if (yCoord!=1)
if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
mazeWalk(maze, xCoord,yCoord-1, RIGHT);
}
else if (move==UP)
{
if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
mazeWalk(maze, xCoord+1,yCoord, RIGHT);
}
}
else if( direction==UP)
{
if(move==RIGHT)
{
if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
mazeWalk(maze,xCoord, yCoord+1,RIGHT);
}
else if (move==DOWN)
{
if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
mazeWalk(maze, xCoord-1,yCoord, RIGHT);
}
else if (move==LEFT)
{
if (yCoord!=1)
if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
mazeWalk(maze, xCoord,yCoord-1, RIGHT);
}
else if (move==UP)
{
if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
mazeWalk(maze, xCoord+1,yCoord, RIGHT);
}
}
}
}
//WRITE THE DEFINITION OF YOUR FUNCTION HERE
void printMaze (char** &maze)
{
outdata << "---" <<endl;
for (int i=0; i<Rows; i++)
{
for ( int j=0; j<Columns; j++)
outdata << maze[i][j];
outdata << endl;
}
outdata << "---" <<endl;
return;
} Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.