Rat in a maze complete source code using stacks
Arrays.h :
/*=================================================================================================* ==========================
2D multifunctional arrays:
==========================
Properties:
1. Arrays are 2D on frontend but 1D linear at backend.
2. Arrays can have different column widths for different rows.
3. Arrays can be shirnked but auto feature in question requirement.
4. Class requires following preoverloaded functions for non-primitive datatypes.
4.1 Assignment operator.
4.2 OStream operator overloaded.
4.3 Comparison operator overloaded.
5. Program initial feed data size is auto taken as per user created Array CAPACITY.
5.1 User must enter N*M size input.
5.2 Rows and Cols are user responsibility while feeding daata.
5.3 Same rows and cols must be used when feeding data as per as while declaring capacity.
Arslaan Muhammad Ali
Data structures
arslaan4113@gmail.com
=================================================================================================*/
#ifndef ARRAYS_HEADER_H
#define ARRAYS_HEADER_H
#include <cstdlib>
template <class Type>
class Arrays
{
Type *arr;
int rows, *rowSize,
size, cap;
int findRowNO(int);
int findColNO(int);
int convertToLinearIndex(const int, const int);
void copy(const Arrays<Type>&);
public:
//constructors.
Arrays(int, int);
Arrays(const Arrays<Type>&);
~Arrays();
//methods to perform required tasks...
//input function to feed initial data.
void feedInitData(int, int, Type**);
//the function will insert a new element at given index also
//updates the specific column size of that particular row.
void insertAtIndex(const Type&, int, int);
//the function will replaces a new element at given index also
//does not update the specific column size of that particular row.
void replaceAtIndex(const Type&, int, int);
//the function will delete element at given index
//array size will be decreased so it capacity.
void deleteAtIndex(int, int);
//the function will delete element at given index
//capacity will remain same.
void removeAtIndex(int, int);
//the function will double the capacity of Arrays.
void extendCapacity();
//the function will half the capacity irrespective of data loss.
void shrinkCapacity();
//the function will search for given data and return (X,Y) if found else (-1,-1)
void searchAndRetrieve(int&, int&, const Type&);
//the function will retrieve any value from the given index.
Type& retrieveAtIndex(int, int);
//YET TO BE IMPLEMENTED CORRECTLY
//the function will print Arrays
//requires overloaded << for all non-primitive data types.
//std :: ostream& operator<<(std :: ostream&);
//the function will assign one object to other.
const Arrays<Type>& operator=(const Arrays<Type>&);
};
template <class Type>
int Arrays<Type> :: findRowNO(int index)
{
int rowNum = 0, currRow = 0;
while(currRow <= index)
currRow += rowSize[rowNum++];
return rowNum - 1;
}
template <class Type>
int Arrays<Type> :: findColNO(int index)
{
int trows = findRowNO(index), tcols = 0;
for(int i = 0; i <= trows; ++i)
tcols += rowSize[i];
tcols -= index;
return tcols;
}
template <class Type>
int Arrays<Type> :: convertToLinearIndex(int xco, int yco)
{
int index = 0;
for(int i = 0; i < xco; ++i)
index += rowSize[i];
index += yco;
return index;
}
template <class Type>
void Arrays<Type> :: copy(const Arrays<Type>& next)
{
delete [] arr;
rows = next.rows;
for(int i = 0; i < rows; ++i)
rowSize[i] = next.rowSize[i];
cap = next.cap;
size = next.size;
arr = new Type [cap];
for(int i = 0; i < size; ++i)
arr[i] = next.arr[i];
return ;
}
template <class Type>
Arrays<Type> :: Arrays(int rows2, int cols2)
{
if(rows2 > 0 && cols2 > 0)
rows = rows2;
else rows = cols2 = 10;
rowSize = new int [rows];
for(int i = 0; i < rows; ++i)
rowSize[i] = cols2;
cap = rows2 * cols2;
size = 0;
arr = new Type [cap];
}
template <class Type>
Arrays<Type> :: Arrays(const Arrays<Type>& next)
{
delete [] arr;
rows = next.rows;
for(int i = 0; i < rows; ++i)
rowSize[i] = next.rowSize[i];
cap = next.cap;
size = next.size;
arr = new Type [cap];
for(int i = 0; i < size; ++i)
arr[i] = next.arr[i];
}
template <class Type>
Arrays<Type> :: ~Arrays()
{
delete [] arr;
delete [] rowSize;
}
//input function to feed initial data.
template <class Type>
void Arrays<Type> :: feedInitData(int rows2, int cols2, Type** data)
{
for(int i = 0; i < rows2; ++i)
for(int j = 0; j < cols2; ++j)
arr[i * rows2 + j] = data[i][j];
size = (rows2 * cols2) - 1;
return ;
}
template <class Type>
void Arrays<Type> :: insertAtIndex(const Type &next, int xpos, int ypos)
{
//invalid index case
int pos = convertToLinearIndex(xpos, ypos);
if(pos > cap) return ;
//valid index case.
//taking care of row<=>rowSize.
int index = findRowNO(pos);
rowSize[index]++;
Type *temp = new Type[cap + 1];
for(int i = 0; i < pos; ++i)
temp[i] = arr[i];
temp[pos] = next;
for(int i = pos; i < size; ++i)
temp[i + 1] = arr[i];
delete [] arr;
arr = temp;
cap++; size++;
}
template <class Type>
void Arrays<Type> :: replaceAtIndex(const Type &next, int xpos, int ypos)
{
//invalid index case.
int pos = convertToLinearIndex(xpos, ypos);
if(pos > cap) return ;
//replaces value at position pos or (xco, yco).
arr[pos] = next;
return ;
}
//removes an element from index.
template <class Type>
void Arrays<Type> :: deleteAtIndex(int xpos, int ypos)
{
//invalid index case.
int pos = convertToLinearIndex(xpos, ypos);
if(pos > cap) return ;
//valid index case.
//taking care of row<=>rowSize.
int index = findRowNO(pos);
rowSize[index]--;
Type *temp = new Type[cap - 1];
for(int i = 0; i < pos; ++i)
temp[i] = arr[i];
for(int i = pos; i < size; ++i)
temp[i] = arr[i + 1];
delete [] arr;
arr = temp;
cap--; size--;
}
//removes an element from index but does not remove space.
template <class Type>
void Arrays<Type> :: removeAtIndex(int xpos, int ypos)
{
//invalid index case.
int pos = convertToLinearIndex(xpos, ypos);
if(pos > cap) return ;
for(int i = pos + 1; i < size; ++i)
arr[i - 1] = arr[i];
size--;
}
//double capacity.
template <class Type>
void Arrays<Type> :: extendCapacity()
{
cap += rows * rows;
int prevRows = rows; rows *= 2;
Type *temp1 = new Type[cap];
int *temp2 = new Type[rows];
for(int i = 0; i < size; ++i)
temp1[i] = arr[i];
for(int i = 0; i < prevRows; ++i)
temp2[i] = rowSize[i];
for(int i = prevRows; i < rows; ++i)
temp2[i] = prevRows;
delete [] arr; delete [] rowSize;
arr = temp1; rowSize = temp2;
}
//half capacity.
template <class Type>
void Arrays<Type> :: shrinkCapacity()
{
if(size >= cap / 2)
size = cap / 2 - 1;
rows /= 2; cap = 0;
for(int i = 0; i < rows; ++i)
cap += rowSize[i];
Type *temp1 = new Type [cap];
int *temp2 = new int [rows];
for(int i = 0; i < cap; ++i)
temp1[i] = arr[i];
for(int i = 0; i < rows; ++i)
temp2[i] = rowSize[i];
delete [] arr; delete [] rowSize;
arr = temp1; rowSize = temp2;
}
//returns (-1,-1) if not found else (X,Y) values.
template <class Type>
void Arrays<Type> :: searchAndRetrieve(int &row, int &col, const Type& find)
{
int index = -1;
for(int i = 0; i < size; ++i)
if(find == arr[i]) {
index = i;
break;
}
if(index == -1)
row = col = -1;
else {
row = findRowNO(index);
col = findColNO(index);
}
}
//the function will retrieve any value from the given index.
template <class Type>
Type& Arrays<Type> :: retrieveAtIndex(int xco, int yco)
{ return arr[convertToLinearIndex(xco, yco)]; }
//YET TO BE IMPLEMENTED CORRECTLY.
/*template <class Type>
std :: ostream& Arrays<Type> :: operator<<(std :: ostream& out)
{
for(int i = 0; i < rows; ++i)
for(int j = 0; j < rowSize[i]; ++j)
out << arr[i] << ' ';
out << '\n';
return out;
}*/
template <class Type>
const Arrays<Type>& Arrays<Type> :: operator =(const Arrays<Type>& right)
{
//avoiding self-copying.
if(this != &right)
copy(right);
return *this;
}
#endif
maze.cpp:
#include "Maze.h"
#include <ctime>
#include <iostream>
namespace CONSTANTS
{
const char MOUSE = '@';
const char BLOCKAGE_BLUE = '#';
const char BLOCKAGE_RED = '&';
const char PROCESSING = '$';
const char TILES = ' ';
const char CHEESE = '*';
}
//constructors and deconstructors.
Maze :: Maze(int rows2, int cols2):
rows(rows2 >= 3 ? rows2 : 3),
cols(cols2 >= 3 ? cols2 : 3)
{
board = new Arrays<char>(rows, cols);
totalBlocks = (rows * cols) / 4;
blocks = new Point[totalBlocks];
mouse.xco = mouse.yco = 0;
next.xco = next.yco = 0;
path = new Stack<Point>(rows * cols);
}
Maze :: ~Maze()
{
delete board;
delete [] blocks;
delete path;
}
//private functions.
void Maze :: createBlueWalls()
{
//creating and initialising blocks.
srand(unsigned(time(NULL)));
for(int i = 0; i < totalBlocks; ++i)
{
blocks[i].xco = rand() % rows;
blocks[i].yco = rand() % cols;
}
//introduce blocks onto maze.
for(int i = 0; i < totalBlocks; ++i)
board -> replaceAtIndex
(CONSTANTS :: BLOCKAGE_BLUE, blocks[i].xco, blocks[i].yco);
return ;
}
void Maze :: createMouseAndCheese()
{
//instantiating mouse and cheese on maze.
board -> replaceAtIndex
(CONSTANTS :: MOUSE, mouse.xco, mouse.yco); //first block.
board -> replaceAtIndex
(CONSTANTS :: CHEESE, rows - 1, cols - 1); //last block.
return ;
}
void Maze :: startScreen()
{
std :: system("CLS");
std :: cout << "===>\tWELCOME TO MAZE GAME\t<===\n"
<< "\t====================\n\n"
<< "GUIDE:\n"
<< "======\n\n"
<< "->\tUP:\tW OR w\n"
<< "->\tDOWN:\tS OR s\n"
<< "->\tLEFT:\tA OR a\n"
<< "->\tRIGHT:\tD OR d\n\n"
<< "Press any key to continue...";
std :: cin.get();
std :: cin.ignore();
std :: system("CLS");
return ;
}
char Maze :: takeValidInputs()
{
char input = 0;
do
{
std :: cout << "Enter valid direction to move:\t";
std :: cin >> input;
}
while((input != 'W' && input != 'w') &&
(input != 'D' && input != 'd') &&
(input != 'A' && input != 'a') &&
(input != 'S' && input != 's'));
return input;
}
char Maze :: validTile(Point tile)
{
//out of bound check.
if((tile.xco >= 0 && tile.xco < cols)
&& (tile.yco >= 0 && tile.yco < rows))
return board -> retrieveAtIndex(tile.xco, tile.yco);
return 'I'; //invalid.
}
void Maze :: initializeMaze()
{
//setting board.
for(int i = 0; i < rows; ++i)
for(int j = 0; j < cols; ++j)
board -> replaceAtIndex(CONSTANTS :: TILES, i, j);
//initial mouse place, add it to stack on bootup.
path -> push(mouse);
//set walls.
createBlueWalls();
//set Mouse and Cheese.
createMouseAndCheese();
return ;
}
void Maze :: printMaze()
{
std :: system("CLS");
for(int i = 0; i < rows; ++i)
{
//decorating. thats all.
for(int j = 0; j <= 4 * cols; ++j)
std :: cout << '-';
std :: cout << ' ' << std :: endl;
for(int j = 0; j < cols; ++j)
std :: cout << "| " << board -> retrieveAtIndex(i, j) << ' ';
std :: cout << '|' << std :: endl;
}
//decoration.
for(int j = 0; j <= 4 * cols; ++j)
std :: cout << '-';
std :: cout << std :: endl;
return ;
}
void Maze :: setRedBlockingTiles(Point red)
{
board -> replaceAtIndex(CONSTANTS :: BLOCKAGE_RED, red.xco, red.yco);
return ;
}
void Maze :: setYellowProcessingTiles(Point yellow)
{
board -> replaceAtIndex(CONSTANTS :: PROCESSING, yellow.xco, yellow.yco);
return ;
}
void Maze :: moveMiceOneTile(Point next)
{
//add this tile to stack.
path -> push(next);
setYellowProcessingTiles(mouse);//set previous tile YELLOW.
mouse = next; //set current to next.
board -> replaceAtIndex(CONSTANTS :: MOUSE, mouse.xco, mouse.yco);
return ;
}
//this function'll only call when stack is poping up.
bool Maze :: checkAllSurroundingTiles(Point current)
{
//can be maximum 4 VALID neighbours.
const int FOUR = 4;
bool flag[FOUR]; char ch = 0;
Point neighbours[FOUR], temp;
for(int i = 0; i < FOUR; ++i)//simply initialisations.
{
flag[i] = false;
neighbours[i].xco = neighbours[i].yco = -1;
}
//up.
temp.xco = current.xco - 1;
temp.yco = current.yco;
ch = validTile(temp);
if(ch == CONSTANTS :: TILES
|| ch == CONSTANTS :: PROCESSING
|| ch == CONSTANTS :: CHEESE)
{
neighbours[0] = temp;
if(ch != CONSTANTS :: PROCESSING) flag[0] = true;
}
//left.
temp.xco = current.xco;
temp.yco = current.yco - 1;
ch = validTile(temp);
if(ch == CONSTANTS :: TILES
|| ch == CONSTANTS :: PROCESSING
|| ch == CONSTANTS :: CHEESE)
{
neighbours[1] = temp;
if(ch != CONSTANTS :: PROCESSING) flag[1] = true;
}
//right.
temp.xco = current.xco;
temp.yco = current.yco + 1;
ch = validTile(temp);
if(ch == CONSTANTS :: TILES
|| ch == CONSTANTS :: PROCESSING
|| ch == CONSTANTS :: CHEESE)
{
neighbours[2] = temp;
if(ch != CONSTANTS :: PROCESSING) flag[2] = true;
}
//down.
temp.xco = current.xco + 1;
temp.yco = current.yco;
ch = validTile(temp);
if(ch == CONSTANTS :: TILES
|| ch == CONSTANTS :: PROCESSING
|| ch == CONSTANTS :: CHEESE)
{
neighbours[3] = temp;
if(ch != CONSTANTS :: PROCESSING) flag[3] = true;
}
//returning flag result.
return (!flag[0] && !flag[1] && !flag[2] && !flag[3]);
}
void Maze :: MakeAllPossibleTilesIntoReds(Point current)
{
//if all flags are false make the given tile to red.
board -> replaceAtIndex
(CONSTANTS :: BLOCKAGE_RED, current.xco, current.yco);
return ;
}
//this function expects "A,W,S,D" only values(upper OR lower).
//returns true if cheese is found.
bool Maze :: operateGame(char input)
{
Point temp = next;
if(input == 'w' || input == 'W')//up
temp.xco--;
else if(input == 's' || input == 'S')//down
temp.xco++;
else if(input == 'a' || input == 'A')//left
temp.yco--;
else if(input == 'd' || input == 'D')//right
temp.yco++;
/*if valid work with stacks and update the maze.
set current tile to YELLOW
move Mice to next tile and make it YELLOW.
valid move check.*/
char ch = validTile(temp);
if(ch == CONSTANTS ::TILES
|| ch == CONSTANTS :: CHEESE)
{
next = temp;//make next to valid tile
moveMiceOneTile(next);//move the mice.
printMaze();//updated maze to console.
if(ch == CONSTANTS :: CHEESE) return true;
}
/*else check all surrouding boxes if all are blockages, end the game
if atleast one is yellow then check if any yellow box has white attached.
all those tiles who have no white attached change them into red.
jump the mouse to that tile which has white attached to it
and search that particular yellow tile into stack and popup all extra tiles from it.*/
else if(ch != 'I')//avoid out of bounds and blockags tiles.
{
//loop in poping up stack till a tile reached who has atleast one WHITE neighbour.
Point tpop = path -> retrieve();
while(checkAllSurroundingTiles(tpop))
{
//if true, turn the tile into blockage.
MakeAllPossibleTilesIntoReds(tpop);
//popup the Point from our stack.
path -> pop(tpop);
//update mouse location.
tpop = path -> retrieve();
}
//if mouse position has changed update it's new coordinates.
if(mouse.xco != path -> retrieve().xco
|| mouse.yco != path -> retrieve().yco)
{
mouse = path -> retrieve();
board -> replaceAtIndex(CONSTANTS :: MOUSE, mouse.xco, mouse.yco);
}
//priting updated maze.
printMaze();
}
return false;
}
maze.h:
//Arslaan Muhammad Ali
// Data structures
// arslaan4113@gmail.com
#ifndef MAZE
#define MAZE
#include "Stack.h"
#include "Arrays.h"
struct Point
{
int xco, yco;
};
class Maze
{
int rows, cols, totalBlocks;
Arrays<char> *board;
Point *blocks, mouse, next;
Stack<Point> *path;
//private functions of maze.
void createBlueWalls();
void createMouseAndCheese();
char validTile(Point);
void setRedBlockingTiles(Point);
void setYellowProcessingTiles(Point);
bool checkAllSurroundingTiles(Point);
void MakeAllPossibleTilesIntoReds(Point);
void moveMiceOneTile(Point);
public:
Maze(int = 3, int = 3);
~Maze();
void startScreen();
void initializeMaze();
void printMaze();
char takeValidInputs();
bool operateGame(char);
};
#endif // MAZE
stack.h
#ifndef STACK_H
#define STACK_H
template <typename T>
class Stack
{
int size, top;
T *stackPtr;
public:
explicit Stack(int = 10);
~Stack();
bool push(const T&);
T& retrieve();
bool pop(T&);
bool isEmpty() const;
bool isFull() const;
};
template <typename T>
Stack<T> :: Stack(int s) :
size(s > 0 ? s : 10), top(-1),
stackPtr(new T[size]) { }
template <typename T>
Stack<T> :: ~Stack(){ delete [] stackPtr; }
template <typename T>
bool Stack<T> :: push(const T& next)
{
if(isFull()) return false;
stackPtr[++top] = next;
return true;
}
template <typename T>
T& Stack<T> :: retrieve()
{ return stackPtr[top]; }
template <typename T>
bool Stack<T> :: pop(T& next)
{
if(isEmpty()) return false;
next = stackPtr[top--];
return true;
}
template <typename T>
bool Stack<T> :: isFull() const
{ return (top == size - 1); }
template <typename T>
bool Stack<T> :: isEmpty() const
{ return top == -1; }
#endif // STACK_H
main.cpp:
//Arslaan Muhammad Ali
// Data structures
// arslaan4113@gmail.com
#include "Maze.h"
#include <iostream>
int main()
{
bool countsLoop = true;
while(countsLoop)
{
int rows = 10, cols = 10;
std :: cout << "PRE-GAME MENU:\n"
<< "==============\n\n"
<< "===>\tPlease enter game board size >= [3x3]: ";
//std :: cin >> rows >> cols;
//creating maze game board.
bool gameLoop = true;
Maze *game = new Maze(rows, cols);
//game initial screen.
game -> startScreen();
//instantiating the maze.
game -> initializeMaze();
while(gameLoop)
{
//printing maze.
game -> printMaze();
//user inputs panel.
char direction = game -> takeValidInputs();
//game core starts here.
gameLoop = !(game -> operateGame(direction));
}
char rerun = 0;
std :: cout << "Game has been terminated successfully.\n"
<< "Would you like to play it once more?\n"
<< "[Y]es or [N]o:\t";
std :: cin >> rerun;
if(rerun == 'Y' || rerun == 'y')
std :: system("CLS");
else countsLoop = false;
}
//ending the game and clearing all screen.
std :: system("CLS");
return 0;
}
forliMgranta Alexis Thomas https://wakelet.com/wake/2us_iiiyUwP1h_lJarl3K
ReplyDeletexinpytingscob
conssegstingiPhoenix Maria Robinson download
ReplyDeletelink
link
click here
disrirosig
scanexVgliczu Melissa Trujillo program
ReplyDeleteclick here
toustanali