The objective of this lab is to gain experience using 2-dimensional arrays, and
ID: 3856991 • Letter: T
Question
The objective of this lab is to gain experience using 2-dimensional arrays, and algorithm development. Also, it will reinforce the concepts of loop structures, random number generation, functions, and text formatting. This goal of this assignment is to simulate a robot negotiating a room. The first version will use a "random walk" algorithm which the "robot" in maze will just randomly wander until an exit is found. The second version will modified the original solution to block off any dead ends that the "robot" may find. The later version should result in shorter path (both time and distance wise) being found through the maze. Review Random Number Generation Review Two Dimensional C++ arrays Read Problem Specification Create and Test a class called mazeSolver. You may find the functions names listed in the specification useful. Use the filenames of amazing_random_walk.cpp and amazing_intelligent.cpp for GITHUB submission. Submit Assignment to GIT under maze solver with containing amazing_random_walk.cpp, amazing_intelligent.cpp, and least three test maze files (all text files). You will be working extensively with a two dimensional character array in this assignment to simulate a robot navigating a series of rooms to an exit point. The robot at first will just be taught how to randomly walk around the room. The robot then will be given a more intelligent algorithm that allows the robot to avoid travelling in certain areas that the robot has travelled before (dead ends). You may want to review the Wikipedia article on maze solving. First make sure you seed the random number generator in main (). You only need to call srand () once. Use the following 2d character array to test your simulator: | | | | | | | | | | | | | | | |nnnnnn| nnnnnn| |nnnnnn| nnnnnn| |nnnnnnnnnnnnn| |nnnnnnnnnnnnn| |nnnnnnnnnnnnn| |nnn| nnnnn| nnn| |nnn| nnnnn| nnn| | | | | | | | | | | | ddd| where: | -barrier n-not a barrier d-doorway You should be able to randomly place the robot in any point of the room as long as it is not a barrier or door way and the robot should be able to find its way out of the room. Once the robot is placed in the room it will randomly choose a direction (north, south, west, east, northeast, northwest, southeast, and southwest) to go. Your robot should give preference to spaces it has not visited before. Once the direction is decided the robot will attempt to move in that direction. If the path is blocked by a barrier (wall) it will need to find another path. Once it founds a doorway the simulation ends. You program should display the current maze and position of the robot as it progresses through the maze. Random Walk with Dead End Pruning Once part 1 is complete you will need to add "dead end pruning" to your random walk. The basic premise is that if the robot finds its way into a dead end it will remember the dead end in some manner so it does not take that path again. The easiest way is to modify the array to change the 'n' to some other character that represents that the robot has already visited that space. Test your functions by running the simulator. When you are satisfied that the program is operating properly, generate three other rooms and verify that the program works properly. You may find the following topic useful when solving this problem. You may want to use a structure and a vector to store this table. These are the numbers you need to add to the current row and col to move in that particular direction. Using the sample code for reference and given the maze below: If the robot is positioned at location 1, 1 indicated by R in the following: You can not move in the north, west, or north-west directions. However, all other directions are possible. We decide move in the cast direction. Using the move table above to you need a column offset of 1 and the row offset of zero to move east. The new position of the robot is 1, 2. For part one of this assignment you will need to randomly generate these directions. Using the move table or something similar randomly walk around the maze until you find an exit. For part two you can still randomly generate directions as well. You will need to at the very least eliminate dead ends from the maze. However, it may be better to move in a more ordering fashion. Maybe go clockwise around the move table above. It is up to you. Review material used in assignment Review functions, arrays, random number generation, and read the problem specification before continuing. Function Development part 1 The student is required to create the class in source file called amazing_random_walk.cpp. Implement the solution as specified in part 1. Function Development part 2 The student is required to copy and modify the class from Task 2 into source file calledExplanation / Answer
Here is a maze program
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
// Used for proper response structuring.
// reduces code on check_for_dots and check_for_xs.
struct Response
{
bool tf;
char maze[][12];
int col;
int row;
};
typedef Response res;
// Shows maze
void show(char [][12]);
// Check for some character.
bool check_for(char, char [][12], int, int);
// Traverse through the maze.
void traverse(char [][12], int, int, int, int);
// Checks for dots
res check_for_dots(char [][12], int, int);
// Checks for x's
res check_for_xs(char [][12], int, int);
int main()
{
// start
int start_row = 4;
int start_col = 11;
// end
int end_row = 2;
int end_col = 0;
char maze[12][12] = {
{ '#', '#', '#', '#', '#', '#', '#', '#', '#' ,'#', '#', '#' },
{ '#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#' },
{ '.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#' },
{ '#', '#', '#', '.', '.', '.', '.', '.', '.', '#', '.', '#' },
{ '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '.' },
{ '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
{ '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
{ '#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#' },
{ '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#' },
{ '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#' },
{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }
};
traverse(maze, 4, 11, 2, 0);
show(maze);
cout << " Game comes to an end! " << endl;
return 0;
}
/**
* Traverse through given maze, one step at a time.
* @param {char[][12]} maze
* @param {int} row maze row.
* @param {int} col maze column.
* @param {int} end_row Row to end game.
* @param {int} end_col Column to end game.
*/
void traverse(char maze[][12], int row, int col, int end_row, int end_col)
{
show(maze);
// EOG
if (row == end_row, col == end_col)
{
maze[end_row][end_col] = 'X';
return;
}
res r1 = check_for_dots(maze, row, col);
if (r1.tf == true)
return traverse(maze, r1.row, r1.col, end_row, end_col);
// Couldn't find a dot at all.
else {
res r2 = check_for_xs(maze, row, col);
if (r2.tf == true)
return traverse(maze, r2.row, r2.col, end_row, end_col);
// logic error, this will never be hit.
else
{
cerr << "Logic error in the maze!" << endl;
exit(1);
}
}
}
/**
* Checks for given identifier in a given row and column of maze.
* @param {char} identifier Symbol to find.
* @param {char[][12]} maze
* @param {int} row maze row.
* @param {int} col maze column.
*/
bool check_for(char identifier, char maze[][12], int row, int col)
{
if (maze[row][col] == identifier)
return true;
// Not found.
else
return false;
}
/**
* Prints maze.
* @param {char[][12]} maze
*/
void show(char maze[][12])
{
cout << " Maze" << endl;
cout << "==== " << endl;
for (int i = 0; i < 11; ++i) {
for (int j = 0; j < 11; ++j)
cout << " " << maze[i][j];
cout << endl;
}
cout << " ==== " << endl;
}
/**
* Checks for dots.
* @param {char[][12]} maze
* @param {int} row maze row.
* @param {int} col maze column.
*/
res check_for_dots(char maze[][12], int row, int col)
{
res r1;
r1.tf = true;
r1.row = row;
r1.col = col;
char default_cell_character = maze[row][col];
// Set to a value first, change back to default if does not satisfy some
// conditions. (saves 4 lines of code).
maze[row][col] = 'X';
// Check right
if (col != 11 && check_for('.', maze, row, col+1))
r1.col = col+1;
// Check left
else if (col != 0 && check_for('.', maze, row, col-1))
r1.col = col-1;
// Check top
else if (row != 0 && check_for('.', maze, row-1, col))
r1.row = row-1;
// Check bottom
else if (row != 11 && check_for('.', maze, row+1, col))
r1.row = row+1;
// catch for all outcasts
else if (row == 0 || row == 11 || col == 0 || col == 11) {
maze[row][col] = default_cell_character;
}
// Dot not found.
else {
maze[row][col] = default_cell_character;
r1.tf = false;
}
return r1;
}
/**
* Checks for xs.
* @param {char[][12]} maze
* @param {int} row maze row.
* @param {int} col maze column.
*/
res check_for_xs(char maze[][12], int row, int col)
{
res r1;
r1.tf = true;
r1.row = row;
r1.col = col;
char default_cell_character = maze[row][col];
// Set to '@' at first and change back to 'X' if necessary(saves 4 lines.)
maze[row][col] = '@';
// Check right
if (col != 11 && check_for('X', maze, row, col+1))
r1.col = col+1;
// Check left
else if (col != 0 && check_for('X', maze, row, col-1))
r1.col = col-1;
// Check top
else if (row != 0 && check_for('X', maze, row-1, col))
r1.row = row-1;
// Check bottom
else if (row != 11 && check_for('X', maze, row+1, col))
r1.row = row+1;
// catch for all outcasts
else if (row == 0 || row == 11 || col == 0 || col == 11)
maze[row][col] = default_cell_character;
// Couldn't find an 'X' either! Hence blocked!
else {
cerr << "There's something wrong with the maze!!" << endl;
exit(1);
}
return r1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.