Here is the program assignment:
Graph abstraction is important because it is used in many different areas of science, engineering, computer sciences and software engineering. For instance, the Internet makes use of graphs to represent the Internet router network configuration in order to determine the best route for forwarding packets from the source at one end of the Internet to the destination at the other end. Once a graph is constructed to represent the Internet configuration accurately, then the router executes an algorithm to determine the shortest path from each node to each destination and stores the information in its routing table.
In this programming assignment, you will have fun constructing a similar graph to represent a maze which can be used by the user to implement a simple maze game. You will analyze, design, implement and test the Tiger Maze App system. Once the graph is constructed by the game system, the user will try to traverse the maze from a starting point to a finish point, by selecting the direction to take at each node. Since the maze configuration is hidden from the user, he/she will first randomly select each direction and learn and remember past dead-end routes and try to find the correct route to the finish point. When the user reaches the finish point, the program will print out the number of steps taken by the user.
What is a graph?
A graph consists of multiple nodes and edges. For instance, a graph can be represented by the figure below, where the circles represent the nodes and the lines represent the edges. An edge connects two nodes. In this lab assignment, we will only consider special graphs, where each node can have at most four edges, in the four directions: North, East, South and West. An implementation detail to note here is that although the edge is represented by a single line, there are actually two links in both directions between the two nodes. For example, the line between A and B below is implemented by a link from A to B and another link from B to A.
What is the Tiger Maze game system?
In the Tiger Maze game, there is a maze of rooms and passages connecting the rooms. The maze of rooms and passages can be represented by a graph, such as the graph shown above. The nodes can be thought of as rooms and an edge represents a passage that connects one room to another. Each room can be connected to at most four rooms in the four directions: North, East, South and West, as represented by the graph above.
Design and Implementation Requirements
In this programming assignment, you will implement the maze above using references to instances of a Node class, which you will define. Each node in the graph will be implemented as an instance of Node. The edges correspond to the links that connect one node to another and can be represented in Node as instance variables that reference another Node class object. Since there are four possible links, Node must contain four links (pointers) ̶ north, south, east and west ̶ to other Node objects.
The Start variable references is a Node pointer type that points to the node where the user starts, which may represent the room A. The goal is to reach the finish point which is the node that is referenced by the Finish variable which may reference the node representing the room L.
Graph Configuration
The configuration of the graph that you will use in the program will be read in from a text file. Your program must first prompt the user for name of the Graph Configuration file, e.g. graphConfig1.txt, and then opens the file for reading. Each line in the file indicates information on each node, i.e. the name of the node, and the links that may exist from that node to another node in the North, East, South and West directions. If there is no link in a specific direction, then there is an ‘*’ in place of the node name. For example, the configuration file for the graph above is as follows:
A E B * *
B * * * A
C G * * *
D H * * *
E * F A *
F J G * E
G K H C F
H * * D G
I * J * *
J * * F I
K * L G *
L * * * K
In the first line of the configuration file above, the name of the node is A. It has a pointer to node E in the North direction and a pointer to node B in the East direction but no link in either the South or West direction. Thus the South and West pointers are set to NULL.
Your program will first read the graph configuration file and construct the graph data structures used for the Tiger Maze app. Your program must work with any graph configuration file. Several test configuration files will be released to you close to the deadline for you to test the correct execution of your program. All graph configuration files will have exactly twenty-four nodes, but their edges will be different.
To construct the graph based on the configuration file, you need to search for a certain node with a particular name, e.g. in the first line, Node A must be linked to Node E and you need to find E in order to set the north link of A to E. In order to search for E, the easiest way is to put every node in an array and then scan the array for a particular node name. Define a new class called NodeList that contains an array of Node pointers that points to all the nodes in the maze. The array may be initialized by creating the nodes in the array using new operator. Then each of the node is given the nae 'A', 'B', ... The NodeList contains a member function to search for a particular node with a particular name.
Traversing the Graph
The game will traverse the graph based on the inputs given by the user. When the user is at a current room, the program will output the possible moves in the North, East, South or West directions. The user will then enter the room in the desired direction. While the program traverses the graph, it also counts the number of steps. Upon reaching the finish point, it will print out the congratulation banner and the number of steps taken.
The user interface must check for correct input value from the users. If there is any error, e.g. selecting an invalid direction, then the program must display the appropriate error message and continue to prompt for the correct input. Your program must not exit or terminate when there is an incorrect input value.
Your program's output need not exactly match the style of the sample output (see the end of this file for one example of sample output).
Important Notes:
You must use an object-oriented programming strategy in order to design and implement this Tiger Maze app system (in other words, you will need write class definitions and use those classes, you can’t just throw everything in main() ). A well-done implementation will produce a number of robust classes, many of which may be useful for future programs in this course and beyond. Some of the classes in your previous lab project may also be re-used here, possibly with some modifications. Remember good design practices discussed in class:
a) A class should do one thing, and do it well
b) Classes should NOT be highly coupled
c) Classes should be highly cohesive
You should follow standard commenting guidelines.
You DO NOT need any graphical user interface for this simple, text-based application. If you want to implement a visualization of some sort, then that is extra credit.
Error-Checking:
You should provide enough error-checking that a moderately informed user will not crash your program. Your prompts should still inform the user of what is expected of them, even if you have error-checking in place.
Sample Usage
Execute your program in the jGrasp execution window. The results of the execution will appear in the execution window. If your program expects inputs, type in the input data at the execution window. To submit your execution trace, copy the execution trace from the execution window to a text file and submit the execution trace text file together with your source program.
The following is a sample usage, execution trace and user interface where user inputs are in bold.
A sample execution is shown below, where the bold fonts indicate input by the user.
===========================================================
| Welcome to Tiger Maze! |
===========================================================
Enter the graph configuration file name: graphConfig1.txt
Maze graph construction completed.
You are currently in Room A of the Amazing Maze, you can go North or East. What is your choice? N
You are currently in Room E of the Amazing Maze, you can go East or South. What is your choice? E
You are currently in Room F of the Amazing Maze, you can go North, East or West. What is your choice? E
You are currently in Room G of the Amazing Maze, you can go North, East, South or West. What is your choice? N
You are currently in Room K of the Amazing Maze, you can go East or South. What is your choice? E
Congratulations! You have reached the finish point.
You took 5 steps.Here is my code so far:
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
struct Node
{
Node();
char Name;
Node *North;
Node *South;
Node *East;
Node *West;
char get_Name();
void set_Name(char k);
string move_options();
char name;
Node get_North();
Node get_South();
Node get_East();
Node get_West();
void set_North(Node *n);
void set_South(Node *s);
void set_East(Node *e);
void set_West(Node *w);
void Read_Maze2(string file);
Node(char e)
{
Name = e;
North = NULL;
South = NULL;
East = NULL;
West = NULL;
}
};
Node Node:: get_North()
{
return *North;
}
Node Node:: get_South()
{
return *South;
}
Node Node:: get_East()
{
return *East;
}
Node Node:: get_West()
{
return *West;
}
void Node:: set_North(Node *n)
{
North = n;
}
void Node:: set_South(Node *s)
{
South = s;
}
void Node:: set_East(Node *e)
{
East = e;
}
void Node:: set_West(Node *w)
{
West = w;
}
char Node:: get_Name()
{
return name;
}
void Node:: set_Name(char k)
{
name = k;
}
Node:: Node()
{
}
struct MazeMovement
{
int StepsTaken;
Node CurrentRoom;
bool MazeDone;
MazeMovement() {StepsTaken = 0;}
bool is_MazeDone();
void Movement(char Direction);
Node get_CurrentRoom();
int get_StepsTaken();
void Read_Maze(string file);
char Name;
Node Rooms[30];
Node find_Node(char Name);
};
Node MazeMovement:: get_CurrentRoom()
{
return CurrentRoom;
}
int MazeMovement:: get_StepsTaken()
{
return StepsTaken;
}
bool MazeMovement:: is_MazeDone()
{
if(CurrentRoom.get_Name() == 'd')
{
MazeDone = true;
}
return MazeDone;
}
void MazeMovement:: Movement(char Direction)
{
string Moves = CurrentRoom.move_options();
switch(Direction)
{
case 'N':
case 'n':
size_t nfound;
nfound = Moves.find("North");
if(int(nfound) >= 0)
{
CurrentRoom = CurrentRoom.get_North();
StepsTaken++;
}
else
{
cout << "Invalid selection. Please try again. \n";
}
break;
case 'S':
case 's':
size_t sfound;
sfound = Moves.find("South");
if(int(sfound) >= 0)
{
CurrentRoom = CurrentRoom.get_South();
StepsTaken++;
}
else
{
cout << "Invalid selection. Please try again. \n";
}
break;
case 'E':
case 'e':
size_t efound;
efound = Moves.find("East");
if(int(efound) >= 0)
{
CurrentRoom = CurrentRoom.get_East();
StepsTaken++;
}
else
{
cout << "Invalid selection. Please try again. \n";
}
break;
case 'W':
case 'w':
size_t wfound;
wfound = Moves.find("West");
if(int(wfound) >= 0)
{
CurrentRoom = CurrentRoom.get_West();
StepsTaken++;
}
else
{
cout << "Invalid selection. Please try again. \n";
}
break;
default:
cout << "Invalid selection. Please try again. \n";
}
}
void MazeMovement::Read_Maze(string FileName)
{
string line;
ifstream inStream;
inStream.open(FileName.c_str(), ios::in);
int test = inStream.peek();
int i = 0;
if (!(inStream.fail()))
{
while(getline(inStream, line))
{
Node n(line[0]);
if(!(line[2] == '*'))
{
Node North = find_Node(line[2]);
(find_Node(line[0])).set_North(&North);
}
if(!(line[4] == '*'))
{
Node East = find_Node(line[4]);
(find_Node(line[0])).set_East(&East);
}
if(!(line[6] == '*'))
{
Node South = find_Node(line[6]);
(find_Node(line[0])).set_South(&South);
}
if(!(line[8] == '*'))
{
Node West = find_Node(line[8]);
(find_Node(line[0])).set_West(&West);
}
}
CurrentRoom = find_Node('A');
}
else
{
cout << "Could not open the file name entered!" << endl;
exit(1);
}
}
string Node::move_options()
{
string options;
if(!(North == NULL))
{
options += "North\n";
}
if(!(South == NULL))
{
options += "South\n";
}
if(!(East == NULL))
{
options += "East\n";
}
if(!(West == NULL))
{
options += "West\n";
}
if(options.empty())
{
options += "There is no where for you to move, sorry. Please choose another maze!";
}
return options;
}
Node MazeMovement::find_Node(char Name)
{
Node found('*');
for(int i=0; i <30; i++)
{
if(Rooms[i].get_Name() == Name)
{
found = Rooms[i];
}
}
return found;
}
int main()
{
string FileName;
MazeMovement myMaze;
Node myNode;
cout << "Please enter the name of the file: ";
getline(cin,FileName);
FileName += ".txt";
myMaze.Read_Maze(FileName);
cout << "========================================================================= " << endl;
cout << " Welcome to the Tiger Maze! " << endl;
cout << "========================================================================= " << endl;
do
{
string SelectedDirection;
char selection;
cout << "You are currently in Room ";
cout << myMaze.get_CurrentRoom().get_Name();
cout << " of the Amazing Maze, you can go " +
myMaze.get_CurrentRoom().move_options() +".\n What is your choice?";
getline(cin, SelectedDirection);
selection = SelectedDirection[0];
myMaze.Movement(selection);
}
while(!myMaze.is_MazeDone());
{
cout << "Congratulations! You have reached the finish point. \nYou took ";
cout << myMaze.get_StepsTaken();
cout << " steps." << endl;
exit(1);
}
char a;
bool found = false;
ifstream InFile;
Node *Root[20][20] = {NULL};
InFile.open("FileName");
for(int i = 0; i <=30; i++)
{
for(int j = 0; j <= 30; j++)
{
InFile >> a;
if(Root[i][j] == NULL)
Root[i][j] = new Node(a);
Root[i][j] -> North = Root[i-1][j];
Root[i][j] -> South = Root[i+1][j];
Root[i][j] -> West = Root[i][j-1];
Root[i][j] -> East = Root[i][j+1];
//cout << Root[i][j].Name;
}
cout << endl;
}
while(found == false)
{
found = true;
}
for(int i= 0; i <= 30; i++)
{
for(int j = 0; j <= 30; j++)
{
a = Root[i][j] -> Name;
cout << a;
}
}
return 0;
}Here is the output with maze entered as my file name:
Please enter the name of the file: maze
=========================================================================
Welcome to the Tiger Maze!
=========================================================================
You are currently in Room 10 of the Amazing Maze, you can go There is no where for you to move, sorry. Please choose another maze!.
What is your choice?Invalid selection. Please try again.
Congratulations! You have reached the finish point.
You took 0 steps.I've attached the text file used by the program. My program will shut down correctly if a wrong file name is entered. But as you can see, my program is not reading in the correct room or directions and I'm completely stumped right now and can't figure it out. Any suggestions or tips are appreciated. Thank you.
