Sharks and Fish

This problem basically involves a simulation of "particles" moving around and interacting subject to certain rules, which are not entirely physical but instructive and amusing. Also, this problem can be stated in different forms (see below), some are discrete (the sharks and fish can only occupy a discrete set of positions), and some are continuous (the sharks and fish can be anywhere).

There is a set of rules to follow in all forms of the problem:

Sharks and fish live in a 2D ocean, moving, breeding, eating and dying.
The ocean is square and periodic, so fish swimming out to the left reenter at the right, and so on.
The ocean may either be discrete, where sharks and fish are constrained to move from one grid point to a neighboring grid point, or the ocean may be continuous.

In all cases, the sharks and fish move according to a "force law" which may be written as:

 force on a shark (or fish) = force_External (a current, felt
                                 independently by each shark or fish,
                                 including a random component)
                                  +
                              force_Nearest_Neighbors 
                                 (sharks are strongly attracted by
                                  nearby fish)
                                  +
                              force_"Gravity"
                                 (sharks are attracted to fish, and
                                  fish repelled by sharks)

These three kind of forces can be parallelized in different ways: The external force can be computed independently for each fish, and will be the easiest force to parallelize. Forces which only depend on the nearest neighbors, or very close neighbors, require relatively little cooperation between processors and are next easiest to parallelize. Forces which depend on all other fish, like gravity, would require smart algorithms to compute efficiently (in parallel or serial).
Fish and Sharks breed if old enough.
A shark eats any fish it "collides" with, and dies if it does not eat for too long.

Here are few forms or different instances of the Sharks and Fish problem.

Form 1

The fish are points with masses fishm_i, moving according to Newton's laws (F = m a) subject to an external force (water current). The current depends on position.
Use Euler's method to integrate.

Accumulate the mean-square-velocity of all the fish:

          Square-root (Sum{i=1,...,number_of_fish}
                        (velocity_i² /
                          number_of_fish)
                      )

and plot it as a function of time.

Choose the time step dt in the integrator small enough to keep the simulation accurate:

         dt = 0.1 * (Max{i=1,...,number_of_fish}
                     |velocity_i|)  /
                    (Max{i=1,...,number_of_fish}
                     |acceleration_i|)

Form 2 (aka The Game of Life)

Fish occupy a d-by-d periodic grid, with at most one fish per grid cell.
The rules for deciding whether a fish occupies a cell during the next time step are:
1. A new fish is born at a grid cell if it is currently empty and exactly three of its eight neighboring cells are nonempty.
2. A fish dies of loneliness if it has 0 or 1 neighbors.
3. A fish dies of overcrowding if it has 4 or more neighbors.
4. Other cell configurations are stable.
Parallel execution of these rules are relatively simple because the next state is purely a function of 9 cells at the previous state and does not depend on other state changes at the same step.

Form 3

Sharks and Fish occupy a d-by-d grid of 2-D ocean, moving, breeding, eating and dying according to rules.
The square region is "periodic", meaning the right and left edges are connected, and the top and bottom regions are connected.
Fish and Sharks are perfect disks of radius 1, and must be disjoint.
Each fish has mass fishm and each shark mass sharkm.
Fish move according to Newton's law (F = m a ), under a force F which is the sum of
- an external force (current) which is a function of position, and
- a "gravitational repulsion" from all sharks, i.e. a 1/distance law with gravitational constant FISHREPEL (fish do not attract or repel fish).
Fish colliding with fish bounce perfectly elastically, conserving kinetic energy and momentum.
Fish "bread" at random, with the probability of a fish splitting into two new identical fish during [t,t+ tau] = Prob_breed_fish * tau for small tau. The new fish move with equal and opposite (relative) random velocities from the place of birth. Mass, momentum and energy are conserved.
Sharks also move according to Newton's law (F = m a), under a force which is the sum of
- an external force (current) which is a function of position, and
- a "gravitational attraction" to all fish, i.e. a 1/distance law with gravitational constant SHARKATTRACT (sharks do not attract or repel sharks), and
- a strong, local attraction to nearby fish, proportional to 1/(distance¹²).
Sharks colliding with Sharks bounce perfectly elastically, conserving kinetic energy and momentum.
Sharks "breed" at random, the same way fish do, with probability-of-breeding constant Prob_breed_shark.
Sharks colliding with fish eat the fish. Mass, momentum and energy are not conserved.
Sharks which have not eaten for a time STARVE die.