Description

Maze Generator

using a Stack

You will do this project without using the java.util library, which means, you'll have

to do ALL the implementation work yourself except for Scanner and Random.

A maze is a 2D array of char (char [][] maze;)

Walls are marked with '#' and open paths are marked with space ' '.

This maze represents 11 rows and 11 columns.

###########

#s # #

### # #####

# # # #

# ### # # #

# # # #

# ####### #

# # # #

### # # # #

# # f#

###########

Create a Maze with a Stack

The process of drawing a maze is very similar to solving a maze, but instead the goal is

to explore all spaces, removing walls along the way, such that there exist a path

between any two spaces through a series of reachable spaces. That also means that

there will exist a path from the start to the end.

The algorithm to ensure all reachability will work as follows:

 Initialize a stack with the start index (1,1)

 Loop Until: stack is empty

o pop current index off the stack and mark it as visited

o If current index has any unvisited neighbors

 Choose a random unvisited neighbor index

 Remove the wall between the chosen neighbor index and the

current index

 push the current index on the stack

 push the randomly choose neighbor index on the stack

o Continue the loop.

Looking over this routine, you should be able to envision how this procedure will dive

through the maze randomly, like a snake, until the snake reaches a dead end (a space

without any unvisited neighbors). The exploration of the snake would then have to

backtrack until there is a space with unvisited neighbors and explore from there.

CSCI 260 Prof. Kadri

Page 2 of 3

Eventually, the snake will have explored the entire maze, at which point, you're done.

This search pattern is also referred to as Depth First Search (or DFS)

Because we need to have walls not just paths, we will need to look 2 cells away for an

unvisited neighbor, otherwise it would not be possible to have walls. The outside

perimeter should be a wall.

(15 points)

You will need to create the following classes:

1. Location class that represents a location on the maze to have a row number and

a column number. You will use it to create a location object when you need to

push a location onto the stack. You might also need getter and setter methods.

2. LocationStack class implemented by a Linked List, that would hold Location

objects. You can modify a copy of our stack example that holds numbers. So

instead of int values, it should hold Location objects.

3. CreateMaze class where you write your main() method.

Your main method should do the following:

(5 points)

a. Ask the user for the number of rows and columns of the maze to create.

b. Create a 2D char [][] array with number of rows and columns as specified by the user.

c. Fill the maze with '#' characters. So the entire array is made of solid walls.

d. Write a method to print the maze to make sure your code creates the maze correctly.

###########

###########

###########

###########

###########

###########

###########

###########

###########

###########

###########

(10 points)

d. Write code to find paths and mark the path cells with ' ' as described in the

algorithm on the previous page.

e. Print the resulting maze.

CSCI 260 Prof. Kadri

Page 3 of 3

(5 points)

f. Ask the user for a file to save the maze. The format is the same as the one we used to

solve a maze.

11 11 1 1 10 11

###########

#s # #

### # #####

# # # #

# ### # # #

# # # #

# ####### #

# # # #

### # # # #

# # f#

###########

The numbers that appear in the first row represent the number of rows, columns, the

entry point and the exit point.

The rest of the file would contain the maze you generated using the characters '#'

and ' '.

(5 points)

Design, use of meaningful variables, correct alignment and documentation for each

method.

(10 points)

Each team member is required to complete (typed):

1. Write a short, individual paper summarizing what you learned from the assignment

and what you contributed to the team.

2. Fill out the Peer Work Group Evaluation Form

3. Fill out the Numerical Peer Evaluation (Self Included)