Build a hero to traverse a Binary Tree in search of the Golden Scales, while avoiding the dreaded Wumpus. The goal of this assignment is to output a path from the root of the tree to the golden scales, as demonstrated in the output below. A hero may walk to any room (a node) in our Mountain (a Binary Tree) and look for gold, as well as smell for a nearby Wumpus. Start by downloading all of the files for this assignment and reviewing the comments in the following files.
(1) WMDriver (the main)
(2) WumpusHero (the parent class you must subclass to make a Hunter)
a. Look at the startAt() method, which you must override in your subclass.
(3) MountainNode (a room in our simulation)
(4) MountainFactory (a superclass for building Mountains)
a. BinaryMountainFactory (Start here for Binary Mountains where k == 2)
b. TertiaryMountainFactory (Optional extra Mountains, k == 3)
The goal of Wumpus
Mountain is for your Wumpus Hunter (the hero) to
search the mountain pathways (a Binary Tree) for the golden scales left behind
by all baby Wumpus hatchlings. While there is currently
no risk of death, and no shooting arrows in this version of the Wumpus World, you WILL be exploring new territory in search
of gold.
The Wumpus Mountain project is similar to the goals
in the File Search assignment in that we will need to navigate a tree structure
in some logical order using a data structure (frequently a stack).
Note that both of these assignments could be done recursively, and Java's
runtime would then manage the stack for us, but I'd
like you to explicitly use the stack structure (an iterative approach) for this
assignment.
Read the code in the WumpusHunter superclass to gain an understanding of the functions you will need to implement in your WumpusHunter subclass. Traversing a tree can be accomplished via a number of algorithms including a DFS (Depth First Search), which uses a Stack to track mountain nodes, or a BFS (Breadth First Search) which uses a Queue to track mountain nodes, or even a random search which could use any number of structures to accomplish this.
(1) Make a subclass of the WumpusHunter
(2) In your subclass, override the startAt() method to accomplish the following:
a. Move your hunter around around the mountain.
b. Look for golden scales in each room you visit
c. Remember where your hunter has been in the event it finds the scales
i. Specifically, your hunter reports the path from the root to the current node
These classes generate static K-nary mountains for your hunter to experiment with. Once your hunter can solve the Binary Mountain case (where k==2), consider trying your algorithm on a different type of Tree (where k>2) such as the included TertiaryMountainFactory. Feel free to make your own MountainFactory subclass – look at the MountainFactory superclass to get started.
Hunter's name: StackBasedV1Hunter
Hunter's report:
Entering the Mountain Top
Entering the Crooked Way
Entering the Snake Room
Entering the Hidden Nook
We've neared the scales!
Entering the Treasure Room
We've found the scales!
...The path is...
Start at the Mountain Top
and then visit the Crooked Way
and then visit the Hidden Nook
and then visit the Treasure Room
Notice that above, the top part of the output is generated as my WumpusHunter travels around the Mountain, and the final (shortest path) list is generated/printed after we’ve found the gold.
· Your classes must inherit from the WumpusHunter class to compile and run.
· Turn in every class that you modify or change
o Alternatively, turn in all the java files in your project.
· You must override the startAt() method, and keep track of where you are in the mountain with some type of list structure
· Test your software as you build each function.
· Don’t wait till the last minute to get help from the Instructor.