COSC 2010 / 2100 Data Structures
Fall 2014
Homework Assignment #4 : Psychic Gecko!
Due: Wednesday, September 24th, Noon CDT
Submit: Turn in your PsychicGecko.java and PsychicBean.java source files
using the turnin command on morbius.mscs.mu.edu.
Work may be completed in teams of two.
Be certain to include both partner's names in your file. Try to avoid both partners submitting code -- we have to grade that twice, and only the lower grade will be kept.
You may submit multiple times, but only the last turnin will be kept. The automatic submission system will not accept work after the deadline.
GridWorld
Our MagneticChameleon from Project #1
followed a very simple navigational algorithm when trying to locate its
mate on the board. As a result, it was easy to construct a board in which
the MagneticChameleons never found each other, despite valid paths
existing on the board.
For this assignment, we return to the
Advanced Placement
GridWorld Case Study to improve upon our previous algorithm
with a recursive search.
Begin by
downloading GridWorld
code, as well as
the Student
Manual for your reference.
For this assignment, you will be implementing your own extension of an existing GridWorld classes to simulate the PsychicGecko.
Psychic Gecko
Unlike the MagneticChameleons, which are drawn inexorably towards
one another, the PsychicGecko does not move until it has already
foreseen the entire path that leads to its counterpart.
The bounded grid for this assignment will always begin with precisely two
PsychicGeckos on the board, an arbitrary number of Rocks,
and no other Actors.
The PsychicGecko will use a new Actor subclass, PsychicBean to leave a trail of breadcrumbs in grid locations it has
already explored telepathically.
When the trail of PsychicBeans finds the other PsychicGecko, the seeds turn into Flowers, leaving a path that the PsychicGeckos will eat on their way to meet each other.
Initial board
After first step -- path of flowers
Final resting position,
after flowers eaten
The PsychicGecko's navigation algorithm is as follows:
- If there is an adjacent PsychicGecko, move nowhere.
- If there is an adjacent Flower, move toward it and eat it.
- If there are neither of these, execute a recursive search of all
adjacent grid locations.
The PsychicGecko's telepathic search should use Recursive Backtracking and marking to prevent repeated searching of dead ends. It begins by examining each empty location
immediately adjacent to the PsychicGecko:
- If a PsychicGecko distinct from the original is found, the
search terminates, and each PsychicBean along the found path
should be replaced with a Flower.
- Otherwise, a new PsychicBean is placed at the location, marking
the space so that the search does not circle back around needlessly.
- Each empty location adjacent to this new PsychicBean is
then recursively searched in the same way. If there are several
such empty squares to consider, they are sorted in order according
to their difference from the direction of the
other PsychicGecko.
My implementation uses two helper functions to streamline the code, in
addition to the recursive search method:
- private int getDirectionToOther(Location loc)
Detects another PsychicGecko on the grid and returns its
direction from loc in terms of the static constants in
the Location class.
- private ArrayList<Location> sortByDirection(Location origin,
int direction,
ArrayList<Location> unsorted)
Returns a sorted version of the unsorted list, with the
locations in ascending order by difference in direction from the
given origin point.
The PsychicBean class is merely a placeholder, like Rock.
My implementation overrides the act method to remove itself from the
grid after each step.
Testing
Points for this assignment will be awarded based upon successful
completion of a battery of testcases. As you might guess, test
scenerios will consist of placing
two PsychicGeckos at various
locations on the board, with diverse patterns of Rocks between
them.
You should create many of your own testcases,
but we will only evaluate
your PsychicGecko.java source file.
- Name your class precisely -- spelling and capitalization must match
this assignment specification for you to pass any of our testcases.
- Do not modify any of the other GridWorld classes -- or, at least,
do not make your solution depend upon any modifications you make to
other GridWorld classes. Your PsychicGecko.java source file
will be graded in a fresh copy of GridWorld, with our own test framework,
by the TA-bot.
- Make certain that your code compiles correctly -- no points
can be awarded if your submission will not run to pass any of
the testcases.
- If you put any debugging System.out.println()
statements in your code during development, please comment these
out before submission. Stray output from your program will
confuse TA-bot.
Useful links:
Extra Challenges
If you complete this assignment quickly, you might like to think about
variations on the problem. Do not turn these in -- many will break
TA-bot's grading testcases -- but do give them some thought:
- The PsychicGecko is a significant improvement on the
MagneticChameleon, but it can still be tricked with
complex boards. While it will find a path if one exists, it's
"head toward the other Gecko" heuristic does not guarantee
that it finds the shortest, or even a very good path. Can you
devise a board in which the configuration of Rocks
prompts the PsychicGecko to take a lengthy detour on
its way to its counterpart?
- Under what circumstances will there still be Flowers
left on the grid after the Geckos have reached each other?
- PsychicBeans are replaced with Flowers when
a path is found, but you may still see some leftovers in the grid
after a path has been found. Under what circumstances will you
still see PsychicBeans in the grid after the step in
which the Gecko telepathically searches the board?
- Are there circumstances in which the Flower path connecting
the Geckos is ambiguous?
- Many of the quirks of this problem could be solved by finding the
shortest path between two PsychicGeckos. How would
you implement this?
[Revised 2014 Aug 28 23:00 DWB]
