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
Fishclass and an
Environmentclass to represent those. The
Environmentis 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
Displayobject 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
Simulationobject that controls the simulation. Since this is a C++ program, we also have a
mainfunction, found in
Class Summary: We have many
Displayobject, and a
Simulationobject. We also have a
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.]
mainfunction creates the
Displayobject, and the
Simulationobject. It does NOT create the
Fishobjects -- the environment reads initial fish positions from a file and constructs the fish when it (the environment) is created. [Illustration of
After constructing the basic objects, the
mainfunction repeatedly asks the
Simulationobject to execute one timestep of the simulation and then asks the
Displayobject to display the resulting environment. [Illustration]
- When executing a timestep, the
Simulationobject 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
Fishmovement] There is a
Positionclass 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
Neighborhoodobject. (A neighborhood is merely an
apvectorof positions.) [Illustration of how a
Neighborhoodof 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
Class Summary: The three new classes are
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
Environmentobject is represented as an
apmatrixis 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
Fishmember 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
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
myPosdata member is (2, 2) should be at location (2, 2) in the matrix. What if the fish changes its
myPosdata 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
- 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
Simulationobject asked the
Environmentobject 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
Simulationobject). Thus, the
Fishobjects in the
apvectorare clones of the objects in the
apmatrix, not the actual
Fishobjects themselves. The
Simulationobject 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
myPosdata 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
Updatethe fish hasn't moved at all.
Side Note: Why Have Separate Simulation and Display Classes?
Why do we need a separate
Displayclass? 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
Displayclass; 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
Neighborhoodclass 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.]