CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Jun 2018
    Posts
    1

    Question 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;
    	}
    
    }

  2. #2
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,150

    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.
    Marc Gregoire - NuonSoft (http://www.nuonsoft.com)
    My Blog
    Wallpaper Cycler 3.5.0.97

    Author of Professional C++, 4th Edition by Wiley/Wrox (includes C++17 features)
    ISBN: 978-1-119-42130-6
    [ http://www.facebook.com/professionalcpp ]

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
  •  





Click Here to Expand Forum to Full Width

Featured