Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /******************************************************************************
- * 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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement