Overview
In this laboratory, you will simulate the search of a large fish for food (a school of small fish) in an underwater cave.



To simplify the problem, the large fish will initially be at the left hand side of the cave and the food at the right. The cave is designed so that the large fish only needs to move up, down, or to the right. The large fish never needs to backtrack to the left due to a dead end. A typical randomly generated cave is shown below:



The next snap shot shows the path taken by the large fish until it has located and eaten the school of small fish:



Materials
To begin this laboratory, copy the folder Fish to your hard drive or floppy disk. This folder contains all of the source files needed for the project:

SwimFish.cp	// main program
SwimFish.rsrc	// resource file
SwimFish.	// project file

SwimFishSolution // sample solution
SwimmingFish Lab // this document

void MoveFish(short direction);		// move large fish in this direction
bool FreeToMove(short direction);	// is large fish free to move in this direction?
bool FoundFood();			// has large fish found small fish?

while (!FoundFood()) {   // ! means not
 main        // loop while: food is not found
 loop        // exit when:  food is found
 body
}

If a fish is free to move in a certain direction, then you may move the fish with MoveFish(direction) . The fundamental design question is: How should you decide in what direction to move?

The available directions are Up, Down, Left, Right . To make this assignment simpler, we guarantee that the school of small fish is in the rightmost part of the cave and that it will never be necessary for the large fish to "back up" and go to the left. Beyond this simplification, you need to figure out what to do.

Because we guarantee that the school of small fish is in the rightmost part of the cave, you can always go right if that is possible. If that is not possible, then you must decide whether to go up or down. To illustrate that this may be tricky, let us present a solution with a bug:

// buggy solution to FastSearch()
while (!FoundFood()) {
	if (FreeToMove(Right))			// move Right if you can
		MoveFish(Right);
	else
		if (FreeToMove(Up))		// or move Up if you can
			MoveFish(Up);
		else
			MoveFish(Down);		// or move Down if you must
}

Command-Key and Option-Key and Control-Key

This key combination signals the delay tools package to leave your code and return to the main Search routine. For convenience, these keys are next to one another on the lower left of the keyboard.

Note: If this fails, you may need to reboot your system. Sorry!

To resolve the dilemma of the infinite loop, you will need one or more auxiliary variables to help remember where the large fish has been or has already searched. You need to control the actions in the loop body based both on FreeToMove and on the contents of your variables.

Designing the auxiliary variables and the branch structures ( if or switch ) within the main loop is the heart of what you must do in this lab. The actual code is not long. Getting it right is the issue.

One more hint: It is possible and recommended that you do not use sub-loops within the main loop. The reason is that testing (!FoundFood()) will not occur as frequently as is desirable. You can actually generate a better solution if your loop body does at most one fish move per cycle together with some changes of your variables as needed.

In designing your code, do not use information from the lower level classes and objects that form the foundation of the code. This will not help and will prevent you from learning to work fluently with abstractions.

CompleteSearch

As we mentioned, if time permits, program the CompleteSearch() algorithm also. In this case, you must visit every cell in a column before moving to the right . This turns the strategy of moving right whenever possible completely around. You will have to be more careful to make sure that you visit all cells in a column and that you do not get stuck in an infinite up-and-down loop. Here is an illustration of what the situation and the solution will look like in this case:

Original situation:



Complete solution:



Additional Comments

Many simple algorithms use straightforward loops and easy decisions. This exercise is an interesting example of a problem where you cannot predict when a change in direction may be necessary. If you are too simpleminded, you may change too often and simply oscillate or may fail to change when needed and crash through walls.

An interesting aspect of this exercise is that you obtain a global solution - food is found - simply using local information - what directions are open to the fish at the current position. In computing, it is pleasing when you can find an efficient global solution using only local information.

The fact that local information is sufficient for the solution makes it easy to set up the abstractions FreeToMove, FoodFound, and MoveFish which help to hide the internal data structures and thereby permit a clean program design. When efficiency requires examination of global data structures, then more effort is required to write a quality program.

Technical Note

You may be curious about how the pictures of the fish and the food were created and later attached to the project. Here is a brief synopsis.

The pictures were created using fats bits mode in a paint program . Since the cells in the SwimmingFish program are 23x23, a square border enclosing the same size area was created in the paint program for each picture. Then by trial and error, each of the pictures was drawn bit by bit. Later, when this lab description was being written, the pictures were imported by cut and paste into our word processor.

To get the pictures into a form usable by a C++ program, a brand new resource file was created using the program ResEdit. This file is the resource file SwimFish.rsrc. We used ResEdit to create a new resource of type PICT which was initially empty. Switching to the paint program, we selected the 23 x 23 cell with the fish in fats bits mode. Choosing copy ( -C), we now had the fish image on the clipboard. Switching back to ResEdit, we selected paste ( -V) and voilà we had the fish as a PICT resource. The same steps were repeated for the food image.

When ResEdit creates a new PICT resource, it begins the resource ID numbering with 128. Since we had no other pictures from other files with the same numbers, the default IDs of 128 and 129 were fine for the fish and the food pictures. Therefore, we had no further work to do in ResEdit, so we Quit the program and answered Yes in the final dialog box to save the changes to SwimFish.rsrc. This file was then loaded into the project SwimFish. just like any other source file.

Note that the fish and food resource ID numbers must be known in the C++ program so that the call to GetResource can load the proper pictures into the program during initialization. The ID numbers form the bridge between the resource file and the C++ code.