AP Computer Science Marine Biology Case Study

Executive Summary of Part II

---

The Big Picture

The "story" of Part II is that biologists want to simulate fish movement in San Francisco Bay, or any other bounded environment that can be modeled as a rectangular grid (perhaps a lake near you).

What kinds of objects (in other words, what classes) do we have in this program? Well, we are modeling fish swimming in a bay, so we have a Fish class and an Environment class to represent those. The Environment is represented as a rectangular grid (an apmatrix) of locations. We also want to be able to display the fish and the environment, so we'll use a Display object that knows how to do this. Finally, what do we want to do with these objects? We want to simulate fish movement, so we have a Simulation object that controls the simulation. Since this is a C++ program, we also have a main function, found in fishsim.cpp.

Class Summary:

We have many Fish objects, an Environment object, a Display object, and a Simulation object. We also have a main function.

There are a couple of other classes in the case study, but they play relatively minor roles. We'll come to them as we need them. [See below for more discussion of why there are separate Simulation and Display classes.]

What Do these Objects Do?

[Note: There are object diagrams on the College Board web site that illustrate these points.]

• The main function creates the Environment object, the Display object, and the Simulation object. It does NOT create the Fish objects -- the environment reads initial fish positions from a file and constructs the fish when it (the environment) is created. [Illustration of Environment construction]

  After constructing the basic objects, the main function repeatedly asks the Simulation object to execute one timestep of the simulation and then asks the Display object to display the resulting environment. [Illustration]

• When executing a timestep, the Simulation object asks the environment for a list of all the fish. The simulation then steps through the list and asks each fish to move. [Illustration]

• To move, a fish finds the adjoining positions that are empty and randomly chooses one of them to move to. [High-level illustration of Fish movement] There is a Position class that merely encapsulates the row and column of a position in the environment. The fish has a position, myPos, and asks it to calculate the positions to the north, south, east, and west of the fish. The fish then asks the environment whether each of those positions is empty. It puts each empty position in a Neighborhood object. (A neighborhood is merely an apvector of positions.) [Illustration of how a Fish creates a Neighborhood of empty neighbors] [See below for more discussion of the Neighborhood class.]

  Once the fish has put its empty neighbors in the neighborhood, it asks a RandGen (random number generator) object for a random number and uses that to choose which position in the neighborhood to move to. In other words, it replaces its position with the randomly chosen position. [High-level illustration of Fish movement]

  Class Summary:

  The three new classes are Position, Neighborhood, and RandGen (introduced in Part I of the Case Study).

The Three "Gotchas"

It seems like this should be the whole story, but it's not. There are three important "gotchas" that make it a bit more complex.

• The first is that the Environment object is represented as an apmatrix of Fish objects. An apmatrix is a homogenous aggregate data structure, meaning that every object in it has to be of the same type. If some of the objects are of type Fish, then they all have to be Fish. But what about the empty positions? They also have to be objects of type Fish. So we have a special kind of fish, an "undefined fish," that represents a fish that is not really a fish. (There is a Fish member function that lets you ask a fish whether or not it is an undefined fish.)

• The second "gotcha" is that the position of a fish is represented in two ways. The fish has a Position object, myPos, representing its current location. The fish's position is also represented indirectly by its location in the apmatrix. In other words, a fish whose myPos data member is (2, 2) should be at location (2, 2) in the matrix. What if the fish changes its myPos data member to (2, 3)? The fish now thinks it is at position (2, 3), but it is still at location (2, 2) in the matrix! We have a problem. For this reason, after the fish replaces its position with the position it is moving to, it has to ask the environment to update itself, in other words, to move the fish from its old location in the matrix to where it now thinks it is. [High-level illustration of Fish movement]

• There's another reason the fish has to ask the environment to update itself, and that's the third "gotcha." It turns out that when the Simulation object asked the Environment object for a list of all the fish, the environment copied the fish from an apmatrix (its own internal representation) into an apvector (the data structure to be returned to the Simulation object). Thus, the Fish objects in the apvector are clones of the objects in the apmatrix, not the actual Fish objects themselves. The Simulation object then asked each of the clones in the vector to move, and each clone changed its own position. Assume that a fish just moved from (2, 2) to (2, 3) by changing its myPos data member, but did not ask the environment to do an update. If we were to ask the environment for the fish at (2, 2) and display that fish's location, we would not get (2, 3), as one would think. The fish at location (2, 2) would still think it's at (2, 2). Only the clone that was asked to move thinks it's at (2, 3). So, what do we do? We could move the original fish in the matrix and then tell it to change its position to match the clone's, but the actual solution in the case study is to just put the clone, which already thinks it's at location (2, 3), into location (2, 3) and to "remove" the original fish at (2, 2) by replacing it with an "undefined fish."

  Summary:

  There are two reasons why a fish has to ask the environment to update itself. One is to keep the fish's sense of its own position synchronized with its location in the matrix. The other is that the fish that thinks it has moved is just a clone of the original fish; without the call to Update the fish hasn't moved at all.

Side Note: Why Have Separate Simulation and Display Classes? Why do we need a separate Display class? Why don't fish and environments just know how to display themselves? This is, in fact, how we used to design objects in the early days of object-oriented programming, but over time people realized that putting the display behavior in the object can create problems. If you decide to change how you want to display things (for example, go from a text-based display to a graphical one), you have to change code all over the place. Now people recognize that it is a good idea to separate the way you model something from the way you display (or view) it. If we change to a graphical view, we just plug in a different Display class; we don't have to change the way we model the fish or the environment at all. Similarly, it is a good idea to separate the program control from the basic objects we are modeling. For example, I might have classes that model a deck of cards. I could use them in a BlackJack game, a Gin Rummy game, or any of a number of other games that use decks of cards. This separation of model, view, and control is sometimes known as the MVC design pattern. Summary: Model: Environment and Fish classes View: Display class Control: Simulation class [Note to teachers: The control could also have been done fairly easily in main. The relative merits of these two design decisions could be the subject of an interesting class discussion.]

Side Note: Why Have A Separate Neighborhood Class? The neighborhood of empty positions could have been implemented as an apvector, especially since the Neighborhood class does not provide any additional functionality. (This is unlike Environment, which is much more than just another name for an apmatrix.) On the other hand, a neighborhood could be implemented using a different data structure. A set, for example, would allow neighbors of neighbors to be added to the neighborhood without creating duplicates. [Note to teachers: The relative merits of these design decisions could be the subject of an interesting class discussion, especially in a Data Structures course.]