COSC 2010 / 2100 Data Structures

Fall 2014

Homework Assignment #4 : Psychic Gecko!

Due: Wednesday, September 24th, Noon CDT

Submit: Turn in your and source files using the turnin command on

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.


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.

Starting position
Initial board
Starting position
After first step -- path of flowers
Starting position
Final resting position,
after flowers eaten

The PsychicGecko's navigation algorithm is as follows:

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:

My implementation uses two helper functions to streamline the code, in addition to the recursive search method:

The PsychicBean class is merely a placeholder, like Rock. My implementation overrides the act method to remove itself from the grid after each step.


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 source file.

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:

[Revised 2014 Aug 28 23:00 DWB]