Swimming Fish Laboratory

February 1996

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
In addition, the folder contains the files:
SwimFishSolution // sample solution
SwimmingFish Lab // this document
The file SwimFish.cp is the main program and the file SwimFish.rsrc is a small resource file which contains bit map images for the large fish and the school of small fish. Once the file SwimFish.rsrc is included in the project file SwimFish. , its images can be read into the executable program as data. This step has already been done for you.

Educational Goals

The essence of abstraction is to make manifest the crucial concepts at the highest level and to hide the technical details at lower levels. In this laboratory, you will learn to think with abstractions. You will design the search algorithm of the large fish for the school of small using only three abstract routines together with simple loops and branch statements:
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?
In the process, you will learn the intellectual advantages of working with a few simple abstractions rather than with lots of messy details.

Once you have completed the laboratory, we hope you become interested in how the technical details were in fact organized. You will see that the substructure is built using the object-oriented concepts of class and object. A maze class is used to create the cave and a fish class is used to create the large fish and the school of small fish. To handle the geometric issues, a spot class supports both the maze class and the fish class. The three functional abstractions which you use to create the search algorithm are fashioned in a straightforward way from the tools provided by these classes.

After you have examined the design of SwimFish.cp , you will have at least an idea of how to create classes and objects. Of course, you will need to do much more work before this idea becomes completely solid. In any case, we hope that this laboratory gives you a good introduction to the power of abstraction and of object-oriented design.

Laboratory Activities

To get an idea of how the search for food proceeds, run the SwimFishSolution . You will see that this solution provides two methods:

FastSearch: Move as quickly as possible to the right in search of the school of small fish

CompleteSearch: Check out every cell in the current column before moving right to check the next column.

When running SwimFishSolution , say No to the Pause question (otherwise you will need to click the mouse once for each move of the fish). You can set the Delay value to a number smaller than 10 but then the fish motion may be too fast to follow. If you want to speed up the motion to maximum speed, press Caps Lock down. This signals the delay code to ignore delays.

In SwimFish.cp , both of the routines FastSearch() and CompleteSearch() have been left empty. In this laboratory, you should design and program the FastSearch() algorithm and, if time permits, the CompleteSearch() algorithm.

Let us focus on FastSearch() for the moment. The heart of the body of this routine must be a loop that continues until the food is found. How can we tell when this happens? With the routine FoundFood() of course. Since FoundFood() is true when the food is found, that is, when the loop should stop , we must negate this condition if we want to say when the loop should continue to run . Thus the main loop should have the form:
while (!FoundFood()) {   // ! means not
 main        // loop while: food is not found
 loop        // exit when:  food is found
 body
}

In the body of the loop, you need to move the fish or change your direction of motion as you search for the food. Before you move the fish in any direction, you must test using FreeToMove(direction) whether the fish can move in that direction. If you fail to test, the fish may bore through solid rock (which is considered an error).

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
}

The problem with this solution is that if the fish cannot move right, it will move up until the top of the column is reached. Then it will move down once. At this point it will move up again! An infinite oscillation will begin (the famous "infinite loop").

Note: If you happen to fall into an infinite loop, press down the following three keys together:

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.


Last Updated: October 11, 1997 11:08 am by
Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN,
Boston, MA 02115
Internet: fell@ccs.neu.edu
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: http://www.ccs.neu.edu/home/fell/COM1100/PROG/SwimmingFish.html