-
June 19th, 2018, 12:00 PM
#1
Creating a "mouse" for a 2D array based maze generator.
So I am new to C++ and just finished building a 3x3 maze generator. It's in the code below. When it runs it generates the maze like it should. But now I have to add a "mouse" to the maze. Its supposed to find it's way through the maze. As long as it gets from the start cell to the end cell, it counts. So it doesn't need to worry about efficiency or anything like that. It also needs to be represented by an asterisk. The code for the maze generator is below, how would I code this solver/mouse?
Code:
/******************************************************************************
* File: maze.cpp
* Author: Damian Morgan
* Class: COP2001; 201805; 50135
* Purpose: Random maze generator using multi dimensional arrays
*******************************************************************************/
#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>
using namespace std;
#define BYTE unsigned char
// wall & visited flag vales
const BYTE CELL_TOP = 1;
const BYTE CELL_BOTTOM = 2;
const BYTE CELL_LEFT = 4;
const BYTE CELL_RIGHT = 8;
const BYTE CELL_VISITED = 16;
// maze dimensions
const int MAZE_ROWS = 3;
const int MAZE_COLS = 3;
// starting cell
const int START_CELL_ROW = 0;
const int START_CELL_COL = 0;
const int START_WALL = CELL_LEFT;
// ending cell
const int END_CELL_ROW = 2;
const int END_CELL_COL = 2;
const int END_WALL = CELL_RIGHT;
// location indexes
const int CELL_ROW_INDEX = 0;
const int CELL_COL_INDEX = 1;
// maze print characters
const char OUT_TOP_LEFT = '-';
const char OUT_TOP_MID = '-';
const char OUT_TOP_RIGHT = '-';
const char OUT_SIDE_LEFT = '|';
const char OUT_SIDE_RIGHT = '|';
const char OUT_BOT_LEFT = '-';
const char OUT_BOT_MID = '-';
const char OUT_BOT_RIGHT = '-';
const char INSIDE_MIDDLE = '+';
const char CELL_TOP_BOT = '-';
const char CELL_LEFT_RIGHT = '|';
const char CELL_OPEN_HORZ = ' ';
const char CELL_OPEN_VERT = ' ';
const char CELL_VISITIED_ON = '.';
const char CELL_VISITIED_OFF = ' ';
// function declarations
bool hasUnvisitedCells(BYTE cells[][MAZE_COLS]);
bool hasAvailableNeighbors(BYTE cells[][MAZE_COLS], int location[]);
void chooseRandomNeighbor(BYTE cells[][MAZE_COLS], int current[], int neighbor[]);
void removeWalls(BYTE cells[][MAZE_COLS], int current[], int neighbor[]);
void initMaze(BYTE cells[][MAZE_COLS]);
int pushStack(int stack[][2], int location[], int stackPoint);
void popStack(int stack[][2], int location[], int& stackPoint);
void copyOneLocTwo(int locOne[], int locTwo[]);
void printMaze(BYTE cells[][MAZE_COLS]);
void printMazeDebug(BYTE cells[][MAZE_COLS]);
int main() {
char tmp; // pause program
// init random generator
srand(time(NULL)); // stdlib; time.h
// sotrage for the maze cells
BYTE maze[MAZE_ROWS][MAZE_COLS] = { 0 };
// storage for our stack of visited cells
int stack[MAZE_ROWS * MAZE_COLS][2] = { 0 };
int stackPointer = -1; // empty stack value
initMaze(maze);
// set starting cell
int startCell[2];
startCell[CELL_ROW_INDEX] = START_CELL_ROW;
startCell[CELL_COL_INDEX] = START_CELL_COL;
// turn off starting wall
maze[startCell[CELL_ROW_INDEX]][startCell[CELL_COL_INDEX]] ^= START_WALL;
// turn off ending wall
maze[END_CELL_ROW][END_CELL_COL] ^= END_WALL;
printMaze(maze);
cout << endl;
printMazeDebug(maze);
cout << endl;
cin >> tmp;
// 1. Make the inital cell the current cell and mark it as visited
int currentCell[2];
copyOneLocTwo(startCell, currentCell);
// mark visited flag
maze[currentCell[CELL_ROW_INDEX]][currentCell[CELL_COL_INDEX]] ^= CELL_VISITED;
// 2. While there are unvisited cells
while (hasUnvisitedCells(maze)) {
// i. if the current cell has any neighbors which have not been visited
if (hasAvailableNeighbors(maze, currentCell)) {
// 1. Chose randomly one of the unvisited neighbors
int neighborCell[2] = { 0 };
chooseRandomNeighbor(maze, currentCell, neighborCell);
// 2. Push the current cell to the stack
stackPointer = pushStack(stack, currentCell, stackPointer);
// 3. Remove the wall between the current cell and the chosen cell
removeWalls(maze, currentCell, neighborCell);
// 4. Make the chosen cell the current cell and mark it as visited
copyOneLocTwo(neighborCell, currentCell);
// mark visited flag
maze[currentCell[CELL_ROW_INDEX]][currentCell[CELL_COL_INDEX]] ^= CELL_VISITED;
// 5. Print the Maze
printMaze(maze);
cout << endl;
printMazeDebug(maze);
cout << endl;
cin >> tmp;
} // end has any neighbors
// ii. Else if the stack is not empty
else if (stackPointer > -1) {
// Pop the last cell from the stack and make it the current cell
popStack(stack, currentCell, stackPointer);
}
} // end while there are unvisitied cells
// 3. Print the Maze
printMaze(maze);
cout << endl;
printMazeDebug(maze);
cout << endl;
// pause program
cin >> tmp;
return 0;
} // end main
/***/
bool hasUnvisitedCells(BYTE cells[][MAZE_COLS]) {
bool isVisited = true;
int row = 0;
while (isVisited && row < MAZE_ROWS) {
int col = 0;
while (isVisited && col < MAZE_COLS) {
isVisited = cells[row][col] & CELL_VISITED;
col++;
}
row++;
}
return !isVisited;
}
/**
* Checks to see if there are any available neigbors
* @param cells - the maze
* @param location - the position of the cells
*/
bool hasAvailableNeighbors(BYTE cells[][MAZE_COLS], int location[]) {
// check if has neighbor above
if (location[CELL_ROW_INDEX] > 0) {
// check if not visited
if (!(cells[location[CELL_ROW_INDEX] - 1][location[CELL_COL_INDEX]] & CELL_VISITED)) {
return true;
}
}
// check if has neighbor below
if (location[CELL_ROW_INDEX] < MAZE_ROWS - 1) {
// check if not visited
if (!(cells[location[CELL_ROW_INDEX] + 1][location[CELL_COL_INDEX]] & CELL_VISITED)) {
return true;
}
}
// check if has left neighbor
if (location[CELL_COL_INDEX] > 0) {
// check if not visited
if (!(cells[location[CELL_ROW_INDEX]][location[CELL_COL_INDEX] - 1] & CELL_VISITED)) {
return true;
}
}
// check if has right neighbor
if (location[CELL_COL_INDEX] < MAZE_COLS - 1) {
// check if not visited
if (!(cells[location[CELL_ROW_INDEX]][location[CELL_COL_INDEX] + 1] & CELL_VISITED)) {
return true;
}
}
return false;
} // end hasAvailableNeighbors
/**
* Chooses a random neighbor in the maze
* @param cells - the maze
* @param current - the current position of the maze
* @param neighbor - the position of the neighbor
*/
void chooseRandomNeighbor(BYTE cells[][MAZE_COLS], int current[], int neighbor[]) {
bool done = false;
while (!done) {
int randNeighbor = rand() % 4; // random 0 through 3
switch (randNeighbor) {
case 0: // TOP
if (current[CELL_ROW_INDEX] > 0) {
if (!(cells[current[CELL_ROW_INDEX] - 1][current[CELL_COL_INDEX]] & CELL_VISITED)) {
neighbor[CELL_ROW_INDEX] = current[CELL_ROW_INDEX] - 1;
neighbor[CELL_COL_INDEX] = current[CELL_COL_INDEX];
done = true;
}
}
break;
case 1: // BOTTOM
if (current[CELL_ROW_INDEX] < MAZE_ROWS - 1) {
if (!(cells[current[CELL_ROW_INDEX] + 1][current[CELL_COL_INDEX]] & CELL_VISITED)) {
neighbor[CELL_ROW_INDEX] = current[CELL_ROW_INDEX] + 1;
neighbor[CELL_COL_INDEX] = current[CELL_COL_INDEX];
done = true;
}
}
break;
case 2: // LEFT
if (current[CELL_COL_INDEX] > 0) {
if (!(cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX] - 1] & CELL_VISITED)) {
neighbor[CELL_ROW_INDEX] = current[CELL_ROW_INDEX];
neighbor[CELL_COL_INDEX] = current[CELL_COL_INDEX] - 1;
done = true;
}
}
break;
case 3: // RIGHT
if (current[CELL_COL_INDEX] < MAZE_COLS - 1) {
if (!(cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX] + 1] & CELL_VISITED)) {
neighbor[CELL_ROW_INDEX] = current[CELL_ROW_INDEX];
neighbor[CELL_COL_INDEX] = current[CELL_COL_INDEX] + 1;
done = true;
}
}
break;
} // end switch
}
} //end chooseRandomNeighbor
/**
* Remove the wall between the current cell and the chosen cell
* @param cells - the maze
* @param current - the current position of the maze
* @param neighbor - the position of the neighbor
*/
void removeWalls(BYTE cells[][MAZE_COLS], int current[], int neighbor[]) {
// test for the location of current and neighbor
// test for neighbor above
if (neighbor[CELL_ROW_INDEX] < current[CELL_ROW_INDEX]) {
cells[neighbor[CELL_ROW_INDEX]][neighbor[CELL_COL_INDEX]] ^= CELL_BOTTOM; // toggle wall off
cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX]] ^= CELL_TOP;
}
// test for neighbor below
else if (neighbor[CELL_ROW_INDEX] > current[CELL_ROW_INDEX]) {
cells[neighbor[CELL_ROW_INDEX]][neighbor[CELL_COL_INDEX]] ^= CELL_TOP; // toggle wall off
cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX]] ^= CELL_BOTTOM;
}
// test for neighbor left
else if (neighbor[CELL_COL_INDEX] < current[CELL_COL_INDEX]) {
cells[neighbor[CELL_ROW_INDEX]][neighbor[CELL_COL_INDEX]] ^= CELL_RIGHT; // toggle wall off
cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX]] ^= CELL_LEFT;
}
// neighbor must be right
else {
cells[neighbor[CELL_ROW_INDEX]][neighbor[CELL_COL_INDEX]] ^= CELL_LEFT; // toggle wall off
cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX]] ^= CELL_RIGHT;
}
} // end removeWalls
/**
* Initialize maze array elements to turn all
* walls on and visited off
* @param cells - the grid of cells in the maze
*/
void initMaze(BYTE cells[][MAZE_COLS]) {
for (int row = 0; row < MAZE_ROWS; row++) {
for (int col = 0; col < MAZE_COLS; col++) {
cells[row][col] = CELL_TOP | CELL_BOTTOM | CELL_LEFT | CELL_RIGHT;
}
}
}
/*
* Adds a cell location onto the stack
* @param stack - the location stack
* @param location - row and col of a maze cell
* @param stackPoint - last location added to the stack
* @return int - new stack pointer
*/
int pushStack(int stack[][2], int location[], int stackPoint) {
int spNew = stackPoint;
spNew++; // move sp up the stack
copyOneLocTwo(location, stack[spNew]);
return spNew;
}
/*
* Pull a cell location off the stack
* @param stack - the location stack
* @param location - row and col of a maze cell
* @param stackPoint - last location added to the stack and return new
*/
void popStack(int stack[][2], int location[], int& stackPoint) {
copyOneLocTwo(stack[stackPoint], location);
stackPoint--;
}
/*
* Copies the contents of one location to another
* @param locOne - one location
* @param locTwo - another location
*/
void copyOneLocTwo(int locOne[], int locTwo[]) {
locTwo[CELL_ROW_INDEX] = locOne[CELL_ROW_INDEX];
locTwo[CELL_COL_INDEX] = locOne[CELL_COL_INDEX];
}
/**
* Printing the maze to the console
* @param cells - the grid of cells in the maze
*/
void printMaze(BYTE cells[][MAZE_COLS]) {
for (int row = 0; row < MAZE_ROWS; row++) {
// print the top row of the cells
for (int col = 0; col < MAZE_COLS; col++) {
/*** print left spacer ***/
// are we on the top row
if (row == 0) {
// are we on the left wall
if (col == 0) {
cout << OUT_TOP_LEFT;
}
else {
cout << OUT_TOP_MID;
}
}
else { // not on top row
// are we on the left wall
if (col == 0) {
cout << OUT_SIDE_LEFT;
}
else {
cout << INSIDE_MIDDLE;
}
}
// print top left spacer
/*** print cell top ***/
if (cells[row][col] & CELL_TOP) {
cout << CELL_TOP_BOT;
}
else {
cout << CELL_OPEN_HORZ;
}
// print last right spacer
if (col == MAZE_COLS - 1) {
//top row
if (row == 0) {
cout << OUT_TOP_RIGHT;
}
else { // not top row
cout << OUT_SIDE_RIGHT;
}
}
} //print top row
// move down to start printing side walls
cout << endl;
// print side walls of the cells
for (int col = 0; col < MAZE_COLS; col++) {
// prints cell left side wall
if (cells[row][col] & CELL_LEFT) {
cout << CELL_LEFT_RIGHT;
}
else {
cout << CELL_OPEN_VERT;
}
// print cell visited
if (cells[row][col] & CELL_VISITED) {
cout << CELL_VISITIED_ON;
}
else {
cout << CELL_VISITIED_OFF;
}
// print right wall
if (col == MAZE_COLS - 1) {
// prints cell right side wall
if (cells[row][col] & CELL_RIGHT) {
cout << CELL_LEFT_RIGHT;
}
else {
cout << CELL_OPEN_VERT;
}
}
} // print side walls
// move down to start printing next top walls
cout << endl;
// print bottom row
if (row == MAZE_ROWS - 1) {
// print the bottom row of the cell walls
for (int col = 0; col < MAZE_COLS; col++) {
// print spacer
if (col == 0) {
cout << OUT_BOT_LEFT;
}
else {
cout << OUT_BOT_MID;
}
// print cell bottom wall
if (cells[row][col] & CELL_BOTTOM) {
cout << CELL_TOP_BOT;
}
else {
cout << CELL_OPEN_HORZ;
}
// print right corner
if (col == MAZE_COLS - 1) {
cout << OUT_BOT_RIGHT;
}
} // bottom walls
// end the cells
cout << endl;
} // bottom row
} // end row loop
} // end printMaze
/**
* Printing the maze call values to the console
* @param cells - the grid of cells in the maze
*/
void printMazeDebug(BYTE cells[][MAZE_COLS]) {
for (int row = 0; row < MAZE_ROWS; row++) {
for (int col = 0; col < MAZE_COLS; col++) {
cout << to_string(int(cells[row][col])) << " ";
}
cout << endl;
}
}
-
June 19th, 2018, 02:15 PM
#2
Re: Creating a "mouse" for a 2D array based maze generator.
There are several algorithms possible.
https://en.wikipedia.org/wiki/Maze_solving_algorithm would be a good start to get some ideas.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|