MAZE SOLVING C++: 1. Change the dimensions of the maze to 20x20 with walls aroun
ID: 3725136 • Letter: M
Question
MAZE SOLVING C++:
1. Change the dimensions of the maze to 20x20 with walls around the borders. Out of the empty space in the middle, randomly fill 25% of them with walls. Then pick a random start location (that is empty) and a random Exit location (that is empty). Since you are using random numbers, you should get a different maze with a different start and end. There is a small chance that it is impossible to get from the start to the exit, but don't worry about that possibility (when the program runs it should just not print any solution).
2. The algorithm we covered in class prints out the path from the start to the exit in reverse order. Modify the program so the path is output in forward order. One way to do this is to make an array (or arrays) that store the (x,y) coordinates of the current position as the recursive function exits. With all of the coordinates in an array, inside the main function you can now loop through the array in the proper order to output the moves from start to exit.
3. Your program should output a solution to the randomly generated maze, if one exists.
Start with the computer maze-solving program covered in class. Here is the code that needs to be modified:
#include
#include
#include
using namespace std;
const int WIDTH = 10;
const int HEIGHT = 10;
// Function prototypes
void printMaze(char maze[][WIDTH], int curx, int cury);
bool validMove(char maze[][WIDTH], bool visited[][WIDTH], int newX, int newY);
bool move(char maze[][WIDTH], bool visited[][WIDTH], int &curX, int &curY, int newX, int newY);
// Return true or false if moving to the specified coordinate is valid
// Return false if we have been to this cell already
bool validMove(char maze[][WIDTH], bool visited[][WIDTH], int newX, int newY)
{
// Check for going off the maze edges
if (newX < 0 || newX >= WIDTH)
return false;
if (newY < 0 || newY >= HEIGHT)
return false;
// Check if target is a wall
if (maze[newY][newX]=='X')
return false;
// Check if visited
if (visited[newY][newX])
return false;
return true;
}
// Make the move on the maze to move to a new coordinate
// I passed curX and curY by reference so they are changed to
// the new coordinates. Here we assume the move coordinates are valid.
// This returns true if we move onto the exit, false otherwise.
// Also update the visited array.
bool move(char maze[][WIDTH], bool visited[][WIDTH],int &curX, int &curY, int newX, int newY)
{
bool foundExit = false;
if (maze[newY][newX]=='E') // Check for exit
foundExit = true;
curX = newX; // Update location
curY = newY;
visited[curY][curX] = true;
return foundExit;
}
// Display the maze in ASCII
void printMaze(char maze[][WIDTH], int curx, int cury)
{
for (int y=0; y < HEIGHT;y++) {
for (int x=0; x < WIDTH; x++) {
if ((x==curx) && (y==cury))
cout << "@";
else
cout << maze[y][x];
}
cout << endl}
}
// Recursively search from x,y until we find the exit
bool search(char maze[][WIDTH], bool visited[][WIDTH], int x, int y)
{
bool foundExit;
if (maze[y][x]=='E')
return true;
visited[y][x]=true;
if (validMove(maze,visited,x,y-1))
foundExit = search(maze,visited,x,y-1);
if (!foundExit && (validMove(maze,visited,x,y+1)))
foundExit = search(maze,visited,x,y+1);
if (!foundExit && (validMove(maze,visited,x-1,y)))
foundExit = search(maze,visited,x-1,y);
if (!foundExit && (validMove(maze,visited,x+1,y)))
foundExit = search(maze,visited,x+1,y);
if (foundExit)
{
printMaze(maze,x,y);
cout << endl;
return true;
}
return false;
}
int main()
{
char maze[HEIGHT][WIDTH] = {
{'X','X','X','X','X','X','X','X','X','X'},
{'X',' ',' ',' ',' ',' ','X',' ',' ','X'},
{'X',' ','X',' ',' ',' ','X',' ',' ','X'},
{'X',' ','X','X','X',' ','X',' ',' ','X'},
{'X',' ',' ',' ','X',' ','X',' ',' ','X'},
{'X',' ',' ',' ','X',' ',' ',' ','X','X'},
{'X',' ','X','X','X',' ',' ',' ',' ','X'},
{'X',' ','X',' ',' ',' ','X',' ',' ','X'},
{'X',' ',' ',' ',' ',' ','X',' ','E','X'},
{'X','X','X','X','X','X','X','X','X','X'}
};
bool visited[HEIGHT][WIDTH];
int x = 1, y = 1;
bool foundExit = false;
srand(time(NULL));
// Initialize visited locations to false
for (int x = 0; x < WIDTH; x++)
for (int y = 0; y < HEIGHT; y++)
visited[y][x] = false;
visited[y][x] = true;
cout << search(maze,visited,x,y) << endl;
}
Explanation / Answer
#include <iostream>
#include <windows.h>
const int MazeWidth = 30;
const int MazeHeight = 20;
const char MazeExit = '$';
const char Wall = '#';
const char Free = ' ';
const unsigned char SomeDude = 254;
COORD MazeExitCoords;
COORD StartingPoint;
using namespace std;
char Maze [MazeHeight][MazeWidth];
void FillDaMaze(){
MazeExitCoords.X = MazeWidth - 20;
MazeExitCoords.Y = 2;
StartingPoint.X = 3;
StartingPoint.Y = MazeHeight - 3;
for(int i = 0; i < MazeHeight; i++){
for(int ii = 0; ii < MazeWidth; ii++){
if(i == 0 || i == MazeHeight - 1 || ii == 0 || ii == MazeWidth - 1){
Maze[i][ii] = Wall;
}
else{
Maze[i][ii] = Free;
}
if(i == MazeExitCoords.Y && ii == MazeExitCoords.X){
Maze[i][ii] = MazeExit;
}
else if(i == StartingPoint.Y && ii == StartingPoint.X){
Maze[i][ii] = SomeDude;
}
}
}
}
void PrintDaMaze(int color){
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),color);
for(int i = 0; i < MazeHeight; i++){
for(int ii = 0; ii < MazeWidth;ii++){
cout << Maze[i][ii];
}
cout << endl;
}
}
void FindYourWayThroughTheMaze(){
if(Maze[StartingPoint.Y + 1][StartingPoint.X] != Wall && Maze[StartingPoint.Y + 1][StartingPoint.X ] != SomeDude){
StartingPoint.Y++;
}
else if(Maze[StartingPoint.Y][StartingPoint.X + 1] != Wall && Maze[StartingPoint.Y][StartingPoint.X + 1] != SomeDude){
StartingPoint.X++;
}
else if(Maze[StartingPoint.Y - 1][StartingPoint.X] != Wall && Maze[StartingPoint.Y - 1][StartingPoint.X ] != SomeDude){
StartingPoint.Y--;
}
else if(Maze[StartingPoint.Y][StartingPoint.X - 1] != Wall && Maze[StartingPoint.Y][StartingPoint.X - 1] != SomeDude){
StartingPoint.X--;
}
Maze[StartingPoint.Y][StartingPoint.X] = SomeDude;
}
int main(){
FillDaMaze();
PrintDaMaze(10);
while(StartingPoint.X != MazeExitCoords.X || StartingPoint.Y != MazeExitCoords.Y){
FindYourWayThroughTheMaze();
system("CLS");
PrintDaMaze(10);
Sleep(50);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.