EE 355 PA2

EE 355 PA2 ¨C A-maze-ing

1 Introduction

In this programming assignment you will write a program to read a given maze

configuration (provided as an ASCII text file) and then find the shortest path (in

terms of number of steps) from the source location to the finish.

This programming assignment should be performed INDIVIDUALLY. You may reuse portions of code from previous examples and labs provided in this class, but

any other copying of code is prohibited. We will use software tools that check all

students¡¯ code and known Internet sources to find hidden similarities.

2 What you will learn

After completing this programming assignment you will:

1. Use file streams to perform text file I/O

2. Perform dynamic memory allocation of arrays.

3. Understand 2D array index computation

4. Apply a Breadth-First-Search algorithm to find a shortest path through the maze

3 Background Information and Notes

Our goal is to find a shortest path through a given maze specified in a text file. The

first step is to read in a maze from a text file. We have defined the following format

of these files. The first line of the file contains two integer numbers indicating the

row and column size of the maze. The number of rows indicated will determine

how many lines of text follow (1 row per line). On each line will be one character

for each of the indicated number of columns followed by a newline character. The

characters can be a period (.) indicating a space in the maze, a ¡®#¡¯ sign indicating a

wall in the maze, an ¡®S¡¯ indicating the start location for your search, or an ¡®F¡¯ for the

desired finish location. We assume that WALLS are implicitly surrounding the

perimeter of the maze.

Sample Input File

4 4

..#.

..#S

F.#.

....

Character

. (period)

#

S

F

Last Revised: 2/11/2015

General File Format

rows cols

\n

...

\n

Meaning

Free space in the maze

Wall in the maze

Start location in the maze

Finish location in the maze

1

EE 355 PA2 - A-maze-ing

After reading in the maze, your search algorithm will attempt to find a shortest

path from the start cell to the finish. If successful, you will need to indicate this

path by filling in the character locations along the path with an asterisk, ¡®*¡¯ and

then write the resulting character (maze) array to an output text file. The output

text file for the maze given above should look as follows.

Output File

4 4

..#.

..#S

F*#*

.***

Breadth-First Search (BFS): A common computer search algorithm is known as

Breadth First Search. In any search algorithm we select a starting source location

and continue exploring successive, non-wall locations until we find our intended

destination/finish location or no more legal locations exist to be searched (i.e. no

path exists to the finish location). As we search we mark cells that we've explored

so that we don't explore them again. A BFS algorithm has the property that we

always explore ALL locations at a shorter distance from the start/source before

exploring any location at a longer distance from the start/source (i.e. all locations at

a distance of i are explored before any location at a distance of i+1 from the

source). This ensures a shortest path will be found.

File I/O: You will use an ifstream object discussed in class to read the maze data in

from the given file and an ofstream object to write your results to an output file.

Remember you can use the ifstream object like you do cin to read data into

variables (int or chars for this assignment). Also like cin, the ifstream object will

skip whitespace (newline characters in particular) so you can treat the input file

data as one contiguous set. Also by reading the number of rows and columns into

two integers initially, you can determine exactly how many subsequent characters

to read in and then just loop through reading one character at a time.

2-D Array Indexing: You will not know the size of the maze until run-time when the

maze file is specified. Thus we will need to dynamically allocate an array to hold

the maze data. In C/C++ it ends up being relatively difficult to use dynamic memory

allocation for a 2D array. Thus, we will allocate a 1-D array of NROWS*NCOLS

items. Though we cannot access the 1-D array with two indices directly (i.e.

maze[row][col] won¡¯t work if we only have a 1D array), we can ¡°artificially¡± use two

index values by computing the 1D index from the two index values. Since each row

has NCOLS items, we need to skip over NCOLS items for each row we want to move

down.

Thus, to access the item at row r, column c, we should access: maze[r*NCOLS + c].

If we are given a 1D index, idx, we can convert it to row/column indices by:

performing: r = idx / ____________; c= idx %______________;

2

Last Revised: 2/11/2015

EE 355 PA2 - A-maze-ing

4 Requirements

Your program shall meet the following requirements for features and approach:

1. Break your program into three files with the given structure:

File

Description / Function Definitions

main(int argc, char *argv[])

maze.cpp

? Accepts the input filename and output filename as

command line arguments

? Calls other functions

int maze_search(char *maze, int rows, int cols)

?

?

maze_io.h

maze_io.cpp

Performs the BFS search for a valid path, filling in the

path with ¡®*¡¯ characters if found

Returns 1/true if a valid path was found, 0/false if no

path was found and -1 if an error occurred during the

search. Possible errors include inability to find the start

(¡®S¡¯) cell or finish (¡®F¡¯) cell.

Prototypes for functions in maze_io.cpp

Functions:

char * read_maze(char *filename, int *rows, int *cols );

?

Reads the maze from the given filename, allocates an

array for the maze and returns it. The rows and cols

arguments should point to variables that can be filled in

with the dimensions of the maze read in from the file.

void print_maze(char *maze, int rows, int cols);

?

Prints the maze to the screen in a two dimensional

format

void write_maze(char *filename, char *maze, int rows, int cols);

?

Write the contents of the maze array to the given

filename in the correct text file format.

2. A valid path consists of steps north, west, south, and east but no diagonals.

3. Dynamically allocate a 1D array to hold the maze data. Use the ¡°artificial¡± 2D

indexing (r*NCOLS + c) discussed in the Background section to access this

array and any other array that mimics a 2D array (i.e. the predecessor array

discussed below).

4. Your BFS search will need to dynamically allocate an array for your BFS

array/queue of locations to be explored.

A list/queue is a data structure known as a FIFO (First-In, First-Out) and has

the property that items go in the back (or tail) but are removed from the

front (head). It acts like a list where we right items at the bottom and cross

Last Revised: 2/11/2015

3

EE 355 PA2 - A-maze-ing

them off as we do them from the top. It serves to help us remember what

we have to do (until it is time to actually process it) and in what order the

work arrived.

Array representing BFS lists/queue/FIFO:

Head

Tail

0

1

2

3

item

item

-

4

-

5

-

6

-

To implement this behavior let us allocate a large array (NROWS * NCOLS

which is large enough to hold all items if we needed). We will also maintain

two integer indices: head (the index of the front item) and tail (the index of

the back item). Both should start at 0. When an item is added, it should be

placed at the index specified by tail (i.e. 0 for the first item added) and then

the tail index should be incremented (i.e. to 1). Another addition to the

queue would cause the same behavior (placed at location specified by the

tail index and then the tail index incremented). When an item is to be

removed and processed, we should always take it from the front (head)

index and then increment the head. Now, we must be careful not to try to

remove an item if the list is ¡°empty¡±. We would know this if the head and

tail index are ever equal. Thus, by checking that tail > head, we can safely

know that items exists in the queue.

As you start your BFS, place valid cells not previously found (already in the

queue or already taken out of the queue) into the queue. The general steps

a BFS are shown below. Take note of how the BFSQ (BFS array) are used as

well as the predecessor array which is explained below:

add start location to BFSQ

while BFSQ is not empty do

front ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download