Part 1: Recursion and text file input [60 Marks]

You are in a dark, twisty passage.

This assignment will ask you to find a path through a maze whose form is given to you via an input file. The input file will indicate the broad outline of a square Maze that you will find your way out of.

Such a maze in the file might look like the following (all characters are separate by a single space).

S	.	.	#	#	#	#	#
#	.	#	#	.	.	D	.
#	.	.	R	.	#	#	.
#	.	#	#	.	#	#	.
.	.	#	#	#	#	#	.
#	.	.	R	#	#	#	.
#	#	#	.	.	.	#	.
#	#	#	.	#	E	.	.

The Legend for this maze is the follows:

S => Start Point

E => End Point (Our Goal)

. => Open Path (Cost is 1)

# => Stone Impassable

R =>Rabbit (Cost is 10)

D => Dragon (Cost is 75)

The idea is that you are an adventurer trying to find your way through this maze using the least expensive path. If your path takes you on a . square then the cost of this path is 1. However, if you encounter a Rabbit then you have to fight the rabbit for the square at a cost of 10. Finally if you encounter a Dragon then a major fight will ensue at a cost of 75. Lets take a look at couple of examples for different paths through the maze

Solution Design

Your program is to implement a Recursive solution to the problem of finding a path through the maze. In order to do this we are going to ask you to implement a GameCell Class and a GameBoard Class. A GameBoard is to be composed of a 2D square array of GameCell Entries. Each of these GameCell entries will correspond to one square in the maze. The GameBoard will then represent the entirety of the maze. UML diagrams for these classes can be found on the next pages.

GameCell

-cVal:char

-nRow:int

-nCol:int

-bVisited:boolean

+Rabbit_Cost:int

+Dragon_Cost:int

+Blocked_Cost:int

+Open_Cost:int

+GameCell(cVal:char,nRow:int,nCol:int)

+isVisited():boolean

+setVisited(bVal:boolean)

+getCurrentCost():int

+isBlocked():boolean

+isStart():boolean

+isEnd():Boolean

+toString():String

+getRow():int

+getCol():int

+getVal():char

The Methods are described as following:

GameCell - This method takes the current value that the square is to be associated with in the maze (i.e. R is rabbit, . Is open) and the row and the column position of the cell in the maze.

isVisited,setVisited These are used for determination of whether a square has been visited.

getCurrentCost This returns the current cost for a square (i.e. 1 open, 75 for dragon).

isStart,isEnd These indicate whether or not the current square is a start or end square (no cost).

getRow,getCol - Return the corresponding row and column values in the maze.

getVal Returns the corresponding character in that cell.

toString This will just return a string consisting of the current character value and a space character.

The following page will list the GameBoard UML Diagram

GameBoard

-aBoard:GameCell[][]

-nSquareSize:int

-nStartRow:int

-nStartCol:int

+GameBoard(String:sFileName)

#loadBoard(String:sFileName)

#getSize(String:sFileName):int

+playGame():void

-findStart():void

#findPath(nRow:int,nCol:int):Vector

#canGoUp(nRow:int, nCol:int):boolean

#canGoLeft(nRow:int, nCol:int):boolean

#canGoRight(nRow:int,nCol:int):boolean

#canGoDown(nRow:int,nCol:int):boolean

+pathCost(obPath:Vector):int

+printBoard():void

The Methods are described as follows:

GameBoard This is the constructor that takes the name of the file that is supposed to hold a representation of the maze (see Notes on input later).

loadBoard Helper routine which will handle the actual details of reading the file and instantiating the corresponding GameCells.

getSize This routine will return the number of lines in the associated file. Note that we will only be working with square matrices and the number of lines in the file is the same as the number of rows and columns in the max.

findStart This is a helper routine which sets the nStartRow and nStartCol values. Note that these values do not have to be on border square.

playGame This routine will print out

• If there is a path from the start point to the end
• The cost of path that was found
• The Cell positions (row,column) on the path path.

It works by determining the starting position and then calling the recursive findPath routine.

findPath - This is the recursive routine that will walk the maze. In a nutshell this routine will determine if we can go left, right, up, or down and then call itself again in any valid directions. It will return the path from its current position to the end or null if no path from the current point to the end position exists.

canGoLeft, canGoRight, canGoUp, canGoDown - These routines will, when given the current cell position as an argument, indicate if it is ok to go in one of the indicated directions. A cell is valid to visit if

• It is in the game boundary (i.e. you cant go left if you are in column 0).
• It is not blocked (i.e. associated value is #)
• You have not visited the cell before.

pathCost This routine given a path (as stored in a Vector) will return the cost of all squares on that path.

printBoard() This function will print out the contents of the current game board to the screen. The output should look like the following:

Game Board

# . . # # # # #

# . # # . . D .

# . . R . # # .

# # # # . # # S

. . # # # # # .

# . . R # # # .

# # # . . . # .

# # # . # E . .

// in java language