Tuesday, December 8, 2009

Finding a Path Algorithm - Driver Program

The following (and the 3-4 posts before) is an incomplete, not-working-quite-right program I wrote in the equivalent of a CMPT 306 class while at Snow; just tossing it up here to get some feedback on it. Take a gander if ya like, though it's not my best work...

/*
Title: Programming Project 5 - Maze and Creature
Author: Daniel J. Tanner
Class: CS 2420 - Data Abstraction & Problem Solving w/ C++
Date: October 17th, 2005 (latest update)
*/

#include
#include
#include
#include "TannMaze.h"
#include "TannCreature.h"
#include
using namespace std;

//function declarations
void displayGreeting();

int main()
{
displayGreeting();

//set variables
Coord start, end;
int width, height;
char choice;
string filename;
TannMaze basicMaze;
TannCreature bob;
bool success;

//Find out if user has a file he'd like to use or if he'd like to
//manually input the data
cout << "Would you like to get the data from a file?:(y/n) "; cin >> choice;
if(toupper(choice) != 'Y')
{
//get width and height
cout << "input the width: "; cin >> width;
cout << "input the height: "; cin >> height;

//get start and exit
cout << "Please enter the coordinates for the entrance of your\n" << "maze in the form (x y): "; cin >> start.x >> start.y;
cout << "Do the same for the exit: "; cin >> end.x >> end.y;

//adjust for proper array usage
start.x--; start.y--;
end.x--; end.y--;

//generate maze
basicMaze.generateMaze(width, height, start, end);
}
else
{
//get filename
cout << "Please input the name of your file, including the extension: "; cin >> filename;

//generate maze based on file
basicMaze.generateMaze(filename);
}

//create a creature and have it go through the maze after displaying it
cout << "Your maze appears as follows: \n\n";
basicMaze.displayMaze();
cout << endl;
bob.setMaze(basicMaze);

//show the solution to the maze:
cout << "The solution to your maze is as follows: \n\n";
success = bob.findExit();
if(!success)
cout << "Unfortunately your maze is unsolveable.\n\n";
else
{
basicMaze.displayMaze();
cout << endl << endl;
}


return 0;
}

void displayGreeting()
{
cout << "Greetings! This program will generate a maze and provide a solution\n"
<< "should there be one. You can tell the program the width and height\n"
<< "yourself or you can open a file that you've already input the data\n"
<< "into.\n\n";
}

Finding a Path - Creature Class Definition

/*
Title: Creature Class Function Definitions
Author: Daniel J. Tanner
Class: CS 2420 - Data Abstraction & Problem Solving w/ C++
Date: October 17th, 2005 (latest update)
*/

#include
#include
#include
#include "TannCreature.h"
using namespace std;

//Function definitions

/* Default Constructor
Sets the creature to (0,0) and makes the maze pointer point to NULL
*/
TannCreature::TannCreature()
{
position_.y = 0; position_.x = 0;
maze_ = NULL;
}

/* Explicit value constructor
Purpose: This functions will take a maze as a parameter and set the position
of the creature to the start of the maze
Rec./Ref: an instance of the maze class
*/
TannCreature::TannCreature(TannMaze &maze)
{
maze_ = &maze;
position_ = maze.getStart();
}

/* set function
Purpose: this function will do the same as the explicit value constructor, but
will allow it to be done after initialization
*/
void TannCreature::setMaze(TannMaze &maze)
{
maze_ = &maze;
position_ = maze.getStart();
}

/* findExit function
Purpose: This function will begin a set of recursive calls that will take the
creature from the start to the end if possible. It will return a bool
representing success or failure.
Return: bool representing success or failure
*/
bool TannCreature::findExit()
{
//Book problem had a way to have start and end at same point but this program
//doesn't, so it does not make a check to see if the start is the end
if(goNorth())
return true;
else if(goWest())
return true;
else if(goEast())
return true;
else
return false;
}

/* movement functions
Purpose: These functions will move the creature north, west, south, or east,
and return a bool representing success or failure. failure is when
the move north is blocked by a wall or is not inside the maze
If the creature can move in a specified direction, it marks the new
space as path...if it has to backtrack, it marks the space as 'visited'
Return: A bool representing success or failure
*/
//move North function
bool TannCreature::goNorth()
{
if(position_.y - 1 > 0
&& maze_->checkCoord(position_.x, position_.y - 1) != WALL
&& maze_->checkCoord(position_.x, position_.y - 1) != VISITED)
{
position_.y--;
if(maze_->checkCoord(position_.x, position_.y) == EXIT)
return true;
else
{
maze_->mark(position_, PATH);
if(goNorth())
return true;
else if(goWest())
return true;
else if(goEast())
return true;
else
{
maze_->mark(position_, VISITED);
position_.y++;
return false;
}
}
}
else
return false;
}

//move West function
bool TannCreature::goWest()
{
if(position_.x - 1 > 0
&& maze_->checkCoord(position_.x - 1, position_.y) != WALL
&& maze_->checkCoord(position_.x - 1, position_.y) != VISITED)
{
position_.x--;
if(maze_->checkCoord(position_.x, position_.y) == EXIT)
return true;
else
{
maze_->mark(position_, PATH);
if(goNorth())
return true;
else if(goWest())
return true;
else if(goSouth())
return true;
else
{
maze_->mark(position_, VISITED);
position_.x++;
return false;
}
}
}
else
return false;
}

//move East Function
bool TannCreature::goEast()
{
if(position_.x + 1 <>getWidth()
&& maze_->checkCoord(position_.x + 1, position_.y) != WALL
&& maze_->checkCoord(position_.x + 1, position_.y) != VISITED)
{
position_.x++;
if(maze_->checkCoord(position_.x, position_.y) == EXIT)
return true;
else
{
maze_->mark(position_, PATH);
if(goNorth())
return true;
else if(goEast())
return true;
else if(goSouth())
return true;
else
{
maze_->mark(position_, VISITED);
position_.x--;
return false;
}
}
}
else
return false;
}

//move South Function
bool TannCreature::goSouth()
{
if(position_.y + 1 <>getHeight()
&& maze_->checkCoord(position_.x, position_.y + 1) != WALL
&& maze_->checkCoord(position_.x, position_.y + 1) != VISITED)
{
position_.y++;
if(maze_->checkCoord(position_.x, position_.y) == EXIT)
return true;
else
{
maze_->mark(position_, PATH);
if(goWest())
return true;
else if(goEast())
return true;
else if(goSouth())
return true;
else
{
maze_->mark(position_, VISITED);
position_.y--;
return false;
}
}
}
else
return false;
}

Finding a Path Algorithm - Maze Class Definition

/*
Title: Maze Class Function Definitions
Author: Daniel J. Tanner
Class: CS 2420 - Data Abstraction & Problem Solving w/ C++
Date: October 17th, 2005 (latest update)
*/

#include
#include
#include
#include
#include
#include
#include "TannMaze.h"
using namespace std;

//Maze Class Definitions
//Destructor
TannMaze::~TannMaze()
{
delete [] maze;
}

//Constructors
/* Default
Purpose : This constructor will simply create an instance of the Maze
class
and have the 2-d array pointer point to null
Rec./Ref.: N/A
*/
TannMaze::TannMaze()
{
try
{
mazeHeight_ = 5; mazeWidth_ = 5;
start_.x = 2; start_.y = 4;
end_.x = 2; end_.y = 0;
generateMaze();
}
catch(MazeError error)
{throw(error);}
}

/* Explicit Value Constructor
Purpose: To accept from the user a height, a width, and a start and an end
and then to redirect this information to the generateMaze function
Rec.: height, width, start coord and end coord
Call: function generateMaze(height, width, start, end)
*/
TannMaze::TannMaze(int width, int height, Coord &start, Coord &end)
{
cout << "using explicit input constructor to generate maze..." << endl;
try
{
generateMaze(width, height, start, end);
}
catch(MazeError error){throw error;}
}

/* Filename Constructor
Purpose: This constructor will redirect the program to the generateMaze
function that deals with files directly
Rec/Ref: the filename of the file that will be opened and read from
Send: that same filename to the appropriate maze generator function
*/
TannMaze::TannMaze(string filename)
{
try{
generateMaze(filename);
}
catch(MazeError error)
{
throw(error);
}
}

//Maze generation functions
/* Explicit Value Maze Generator
This function will set all the different variables at once and then redirect
the program to the default generateMaze function
*/
void TannMaze::generateMaze(int width, int height, Coord &start, Coord &end)
{
mazeHeight_ = height; mazeWidth_ = width; start_ = start; end_ = end;
try{generateMaze();}
catch(MazeError error)
{ throw(error);}
}

/* Explicit Value (from file) Maze Generator
This function will set all the variables based on a file as described by the
problem definition in the book
*/
void TannMaze::generateMaze(string filename)
{
fstream fileIn(filename.c_str());
if(!fileIn)
throw MazeError("Error opening file " + filename);
int height, width;
Coord start, end;
fileIn >> width >> height >> end.x >> end.y >> start.x >> start.y;
mazeHeight_ = height; mazeWidth_ = width; start_ = start; end_ = end;
try{generateMaze();}
catch(MazeError error)
{ throw(error);}
}



/* Default Maze Generator
This is THE main maze generator function
Purpose: To generate a 2-dimensional array-based maze made up of ascii
characters, and then randomly fill it with walls and open spaces
along with a specific startpoint and a specific endpoint.
Precondition: The height, width, start, and end variables must have already
been assigned to the class' variables for this to work
correctly
it is therefore only able to be called by member functions which
already assign those properties.
*/
void TannMaze::generateMaze()
{
//create the 2d array, throwing an error if there's not enough memory
try
{
maze = new mazeSquare*[mazeWidth_];
for(int index = 0; index < mazeWidth_; index++)
maze[index] = new mazeSquare[mazeHeight_];
}
catch(bad_alloc error) {throw MazeError("Error allocating memory");}

//set up random number generator to be based off current time
srand(unsigned(time(NULL)));

//fill the maze with squares of either WALL or CLEAR
for(int heightCount = 0; heightCount < mazeHeight_; heightCount++)
{
for(int widthCount = 0; widthCount < mazeWidth_; widthCount++)
{
switch(rand() % 2)
{
case 0:
maze[widthCount][heightCount] = WALL;
break;
case 1:
maze[widthCount][heightCount] = CLEAR;
break;
}
}
}

//set the start and end
maze[start_.x][start_.y] = START;
maze[end_.x][end_.y] = EXIT;
}

void TannMaze::displayMaze()const
{
for(int hIndex = 0; hIndex < mazeHeight_; hIndex++)
{
for(int wIndex = 0; wIndex < mazeWidth_; wIndex++)
{
switch(maze[wIndex][hIndex])
{
case WALL:
cout << 'X';
break;
case CLEAR:
cout << ' ';
break;
case EXIT:
cout << 'E';
break;
case START:
cout << 'S';
break;
case PATH:
cout << '@';
break;
case VISITED:
cout << '*';
break;
default:
break;
}
}
cout << endl;
}
}

/* Mark Function
Purpose: This function will change the status of one maze square to visited or to path
Rec.: the location of the square as a coord, and the new status
*/
void TannMaze::mark(const Coord &sqLoc, enum mazeSquare demarcation)
{
maze[sqLoc.x][sqLoc.y] = demarcation;
}

Finding a Path algorithm - Maze Class Declaration

/*
Title: Maze Class Declaration
Author: Daniel J. Tanner
Class: CS 2420 - Data Abstraction & Problem Solving w/ C++
Date: October 17th, 2005 (latest update)
*/

#ifndef TANNMAZE_H
#define TANNMAZE_H

/*This maze will be made up of several individual squares (represented by
characters).
C = a clear space the creature can walk thru
P = the correct path as travelled by the creature from the entrance to the
exit
X = exit of maze
W = a wall that the creature cannot walk through.
S = start of maze
V = a clear space that the creature has visited, but lead to a dead end.
*/

#include
#include
#include
#include
#include
using namespace std;

//Define enumerated data type for squares
enum mazeSquare{CLEAR, WALL, EXIT, START, PATH, VISITED};

//Special structure for handling incoming and outgoing squares
struct Coord
{
int x, y;
};

//Class TannMaze Declaration
class TannMaze
{
private:
mazeSquare **maze;
int mazeHeight_;
int mazeWidth_;
Coord start_;
Coord end_;

public:
//Error class
class MazeError
{
private:
string problem_;
public:
MazeError(string problem) {problem_ = problem;}
string getProblem() {return problem_;}
};

void mark(const Coord &sqLoc, mazeSquare demarcation);
void displayMaze()const;

//inline get & set functions
int getHeight()const {return mazeHeight_;}
int getWidth()const {return mazeWidth_;}
Coord getStart()const {return start_;}
Coord getEnd()const {return end_;}
mazeSquare checkCoord(int y, int x) {return maze[y][x];}
void setStart(Coord &start) {start_ = start;}
void setEnd(Coord &end) {end_ = end;}
void setHeight(int height) {mazeHeight_ = height;}
void setWidth(int width) {mazeWidth_ = width;}

//Maze Generator functions
void generateMaze(int width, int height, Coord &start, Coord &end);
void generateMaze(string filename);
void generateMaze();

//Constructors
TannMaze();
TannMaze(int width, int height, Coord &start, Coord &end);
TannMaze(string filename);

//Destructor
~TannMaze();
};

#endif

Finding a path algorithm - Creature Class Declaration

/*
Title: Creature Class Declaration
Author: Daniel J. Tanner
Class: CS 2420 - Data Abstraction & Problem Solving w/ C++
Date: October 17th, 2005 (latest update)
*/

#include
#include
#include
#include "TannMaze.h"
using namespace std;

//Class declaration
class TannCreature
{
private:
Coord position_;
TannMaze *maze_;
bool goNorth();
bool goSouth();
bool goWest();
bool goEast();

public:
TannCreature();
TannCreature(TannMaze &maze);
void setMaze(TannMaze &maze);
bool findExit();
};