M. Clancy and E. Lagache, U.C. Berkeley
The scene is an urban park; a cat watches a mouse run around the base of a statue of the first computer. Over the course of a minute, the somewhat witless mouse moves one meter counterclockwise around the statues base, which is circular and two meters in diameter. Every sixty seconds, the cat pursues the mouse as follows: If the cat can see the mouse, the cat moves one meter toward the statue. If the cat can't see the mouse, the cat circles 1.25 meters counterclockwise around the statue. The cat plans eventually to get close enough to the mouse to make a juicy lunch of it.
Write Fortran and Matlab programs to simulate this situation and determine if the cat catches the mouse. The Fortran program should ask the user for the initial positions of the mouse (angle) and the cat (both radius and angle). It should then simulate the chase using the rules listed above to determine how the cat and mouse move, with the cat moving first. The program should print the position of the cat and mouse after each move, followed by the results of the chase (either the mouse becomes lunch, or the cat gives up after 30 minutes). The Matlab program should be a collection of functions, one of which is called cateatsmouse ; this function should take legal cat and mouse positions as arguments and run the simulation as just described, returning a true value if the cat catches the mouse and returning false if the cat gives up.
Because both the cat and mouse are running in circles around the statue, the best way to represent the positions of both animals is with polar coordinates. Since the radius of the mouse is always 1, you only need to keep track of the angle of the mouse. While you need to keep track of both the angle and the radius of the cat, it is still easier to work with polar coordinates because the cat only moves in only one direction (either angle or radius) per minute.
This problem is easier to think about (and work on) from the bottom up. The last thing you need to do (in at least some cases) is check if the cat has caught the mouse. In this simulation, the mouse will be considered caught if: 1) the cat is at the same radius as the mouse, and 2) the cat passes the mouse while running along the base of the status. Condition 1 is easy; the radius of the cat has to be 1. It turns out that condition 2 is true exactly when the following conditions hold:
Your program should include a logical function SEES that returns true if the cat sees the mouse (again, see the appendix for a derivation of this result). In terms of actually developing this program, you should probably stop and test these functions before going on to write any more parts of this assignment.
From here, you might want to write the functions (or subroutines) that return the movements of the cat and mouse. Three are required: one for the mouse, one for when the cat moves toward the statue, and one for when the cat moves around the statue. The first two are very simple mathematical expressions. However, your subprogram to move the cat toward the statue should not allow the cat to move in closer than 1 meter (the base of the statue). The last subprogram is relatively easy to implement if you remember the relationship for arc length:
The need to deal with radians in fact occurs everywhere in the program because the trigonometric functions built into Fortran expect angles in radians, not degrees. Most students write functions to convert from degrees to radians and back again so that they can enter values in a more familiar notation. Should you choose to do that, we recommend that you keep all your variables in radians and change values only when doing input/output. That greatly decreases the risk of bugs resulting from angles in the wrong format. In any case you should write a function that reduces angles when they become greater than 2p (the AMOD function can be very useful for this). This function is needed because the Fortran trig functions become less accurate for angles that are out of the range 0 to 2p.
Finally one can sketch out the structure of the main program. It will need to read in the positions of the cat and mouse (this should be done by still another subprogram). There is one bit of error checking that must be done. You should check to make sure that the entered radius of the cat is greater than 1, otherwise you could place the cat inside the statue! After reading in the positions, checking them, and converting the angles to radians (if necessary), your program should enter the simulation loop. Each minute, you should do the following things: check if the cat has caught the mouse; if not, move both animals based on the rules given above (and encoded in your movement subprograms); finally, print out the status of the simulation. The information printed should include the current time, the current angle of the mouse, the current angle of the cat, and the current radius of the cat. This output should be in a columnar table format. You may wish to use FORMAT statements to achieve this.
You should use only structured loops in your program (i.e. simulated WHILE or REPEAT-UNTIL loops). In order to make this assignment fit those type of loops, you will need to embed an IF statement within the loop to deal with the two distinct possibilities (either the cat catches the mouse at this minute, or it doesnt). When your program finally exits from the loop you should print out a summary of the events (did the mouse get caught or not) and how much time had elapsed.
The cateatsmouse function of the Matlab version should perform somewhat differently. It need not do any error checking on the cat and mouse positions supplied as arguments. Instead of printing the successive cat and mouse positions inside the simulation loop, it should save them in vectors and plot those vectors in each loop iteration, producing something like the plot below in which the cat circles six times and moves toward the mouse twice.
One can quickly summarize the subprograms needed for this assignment by a decomposition tree. One is presented below. Boxes indicate program components; arrows show which components call or include others. It is certainly not the only way this problem could be solved, but is a useful way to think about the problem.
These functions should be tested separately using techniques described earlier. Print out copies of your test programs and sample output to show to the tutor when you have your program graded. Finally, your Matlab program should produce plots of the cat and mouse positions as described previously.
plus whatever other values are necessary to ensure that all statements in your program have been executed at least once. Be sure to check that the output makes sense for these tests, since the output is what most tutors will check first. Students are sometimes embarrassed to have a tutor point out that their programs have the cat moving deeper and deeper inside the statue, or moving away from the mouse instead of approaching it. (Your Matlab plots should make such mistakes much more obvious.)
Type the command echo $DISPLAY to the UNIX command prompt to find out if the variable is set. If you're not using a computer with graphics capabilities, you wont be able to display anything anyway. If you plan to log in on a workstation remotely, ask a tutor how to set things up to enable Matlab to run easier.
Most of the mathematical expressions used in the program in fact capture very clear visual situations. Let's start with the SEES relation. Our model of the cat assumes that it is looking straight at the statue, so the limit of the cat's vision is given by the two rays that are tangent to the statue's base. Let's look at one; the other will be symmetric about the line between the cat and the statue. The diagram below has all the essential facts:
Finding the expression for BTWEEN is a bit more difficult because there are three angles: the previous cat angle, the current mouse angle, and the current cat angle. To solve this problem we will subtract away one angle to change to a more convenient frame of reference (as if the old cat angle was the zero position). The intuition behind the BTWEEN relation is to project the distance traveled by both the cat and mouse onto the line between the old cat position and the center of the statue. Those distances will be cosines of some angles shown on the following diagram:
From the diagram it is clear that if the mouse position is between the cat's old position and the cat's new position, the line traveled by the mouse must be longer than the line traveled by the cat (the cat has to get closer to the origin). So we get the first part of the BTWEEN relation:
will be true is if F is a positive angle (cosine of a smaller angle is larger), but will not be true if F is negative. Requiring both conditions makes sure that the above diagram is correct, and that the mouse has been indeed passed by the cat.
The scene is an urban park, where a cat watches a mouse run around the base of a statue of Klaus Wirth. Over the course of a minute, the somewhat witless mouse moves one meter counterclockwise around the statues base, which is circular and two meters in diameter. Every sixty seconds, the cat pursues the mouse as follows. If the cat can see the mouse, the cat moves one meter in toward the statue. If the cat can't see the mouse, the cat circles 1.25 meters counterclockwise around the statue. The cat plans eventually to get close enough to the mouse to make it a juicy lunch.
Write a program to keep track of the cat's pursuit of the mouse. Your main program should contain statements to input and check the initial positions of the cat and mouse; within the program, all positions should be represented in polar coordinates, and the mouses radius should be assumed to be one meter. It should also contain a loop, each repetition of which represents the passage of one minute, and which contains calls to procedures to move the mouse and the cat.
Your program should contain, within its loop, statements to print the new positions of the cat and mouse after each minute, and to keep track of how much time the cat is taking to catch the mouse. The output should be in the form of a table for maximum readability. (Informative output at other places in the program may also prove useful.)
Your program is to include procedures to move the cat if it sees the mouse, to move the cat if it doesn't see the mouse, and to move the mouse; a real function to reduce an angle to the equivalent angle less than 2p; and boolean functions to determine if the cat sees the mouse and if an angle is between two others (see 3 above). Pass the information these subprograms need through parameters. You should then test these subprograms singly, using appropriate test data, to see if they work independently before putting them all together. Tutors may ask to see the results of these tests. In no case should any of your routines contain more than twenty-four lines of Pascal.
The scene is an urban park; a cat watches a mouse run around the base of a statue of Bjarne Stroustrup. Over the course of a minute, the somewhat witless mouse moves one meter counterclockwise around the statues base, which is circular and two meters in diameter. Every sixty seconds, the cat pursues the mouse as follows: If the cat can see the mouse, the cat moves one meter toward the statue. If the cat can't see the mouse, the cat circles 1.25 meters counterclockwise around the statue.
The cat plans eventually to get close enough to the mouse to make it a juicy lunch. The mouse by accident, however, may manage to keep completely out of sight of the cat, since both the cat and the mouse are moving counterclockwise. The cat will eventually tire of the chase if this happens.
Complete the program found in ~cs9f/lib/cat+mouse.cc to produce a simulation of this situation and determine if the cat catches the mouse. Don't change any of the code already provided in that file. The program uses a Position class declared in ~cs9f/lib/positions.h ; you are also to provide a file positions.cc that correctly implements the operations of this class.
The program first calls the GetPositions function to ask the user for the initial positions of the mouse (angle in degrees) and the cat (both radius and angle in degrees). You may assume that the user provides legal position values.
The program then calls the RunChase function to simulate the chase using the rules listed above. (The cat moves first.) Your code should use member functions of the Position class where appropriate. It should print the position of the cat and mouse after each move, followed by the results of the chase (either the mouse becomes lunch, or the cat gives up after 30 minutes).
The cos function appears in the C++ math function library. Note that the argument to this function must be specified in radians, not degrees. A source file that uses any of the math functions must include the line
(You can abbreviate this command using the make program described later in this document; a make file for this assignment is available in ~cs9f/lib/p2a.makefile .) Computing Concepts second edition says you can use
You should test the member functions of the Position class in isolation, using appropriate test data, to see if they work independently before calling them from the RunChase function. Tutors may ask to see the results of these tests. Your test data should include the following values:
plus whatever other values are necessary to ensure that all statements in your program have been executed at least once. Be sure to check that the output makes sense for these tests, since the output is what most tutors will check first. Students are sometimes embarrassed to have a tutor point out that their programs have the cat moving deeper and deeper inside the statue, or moving away from the mouse instead of approaching it.
Your code should call Position member functions where appropriate; code in cat+mouse.cc should not duplicate their functionality. You should not change the public interface of the Position class; you may, however, provide additional private member functions. (Don't forget to provide the function prototypes for any functions you provide.) Your program should also adhere to standards described in the section Style guidelines of this document.
The directory ~cs9f/lib/inherit/cat+mouse contains a version of the cat-and-mouse programs. You are to complete it by adding a module that uses inheritance. The following files are provided in ~cs9f/lib/inherit/cat+mouse .
This contains the main program, which constructs a scene of animals running around the statue and runs the simulation. The simulation stops when one of the animals in the scene captures its target. The code doesn't do much error checking. Dont worry about that; just use it unmodified.
These comprise the module for the scene and the basic animal object. The Scene constructor prompts the user for the name, animal type, starting position, and target object for each animal in the simulation. The Animal class is the base class for simulation animals. It defines a virtual Chase method that Animal objects use to move.
These comprise a module for positions similar to what you wrote for the flow of control project. Use the appropriate .o file depending on whether you work on a Hewlett-Packard workstation (in Soda or Cory), a DEC workstation (in Cory), or a workstation running Solaris (in Soda). If youre working on another platform, you will have to implement the changes yourself to the positions module from the flow-of-control project, but they wont be difficult.
You are to provide files animals.h and animals.cc that define classes Mouse , Cat , and Person . A Mouse object doesnt chase anything; it merely moves counterclockwise around the statue, one meter per call to Chase . A Cat object has a Mouse object as its target. If the cat sees its target, it moves one meter toward the statue; otherwise it circles 1.25 meters counterclockwise around the statue. A Person object is trying to photograph the situation. It doesn't try to capture anything. If it sees its target, it doesn't move; otherwise it circles 2 meters clockwise around the statue.
Mouse , Cat , and Person are to be derived from class Animal . Provide enough diagnostic output in each member function so that a tutor can see whether its performing as specified. Test your program in the same way you did for the flow-of-control project. Your program should also adhere to standards described in the section "Style guidelines" in this study guide.
The scene is an urban park; a cat watches a mouse run around the base of a statue of the first computer. Over the course of a minute, the somewhat witless mouse moves one meter counterclockwise around the statue's base, which is circular and two meters in diameter. Every sixty seconds, the cat pursues the mouse as follows:
Complete an applet to simulate this situation and determine if the cat catches the mouse. The applet instantiates a Cat object and a Mouse object, each having a move method, and sets up a button that when clicked executes the next step of the simulation (either a mouse move or a cat move). Clicking the button once the cat has caught the mouse or abandoned the chase (after 30 simulated minutes) merely causes an error message to be displayed.
Applet framework files are in the directory ~cs9g/cat+mouse . They include the files CatMouseChase.fw.java , Position.fw.java , Cat.fw.java , and Mouse.java described below. ("fw" stands for "framework".)
To supply cat and mouse positions, use parameter names "mouseangle", "catradius", and "catangle" whose values are expressed in radians. For example, an html file that starts the cat on the x axis 3 meters from the statue and the mouse on approximately the opposite side of the statue contains the specification
Supply sufficient html files to test your applet thoroughly, making sure that every statement in your code has been exercised at least once. Bring listings of these files to the Self-Paced Center when you have your applet graded.
Be sure to check that the output makes sense for all your tests; a student is sometimes embarrassed to have someone point out that his or her program has the cat moving into and through the statue, or moving away from the mouse instead of approaching it.
applet to test the Position methods;
an init method in that applet that supplies sufficiently comprehensive tests;
html files that exercise all statements in the remainder of the applet.