Overview

Our project aims to simulate the patterns of a school of fish, following their movements based on several stimuli such as social interaction, interactions with inanimate objects, and predatory threats. This is part of a larger area of research of subjects called boids, which represents any emergent behavior of swarms, typically occurring in a biological setting, with examples being of birds, bees, fish, and even humans. This project is built off the cloth simulator from assignment 4, using its codebase and libraries with no additional libraries used. In essence, the relationships that these fish share with each other, with inanimate objects, its own curiosity (see wandering), and predatorial threats each produce an acceleration to the fish's kinematics, which mimic the behavior of fish in the wild. The base simulation involves a school of fish swimming around in a small area with no additional objects or predators; in this environment, the social interactions between fish dominates, and the emergent behavior of 'schooling' occurs. When predators are present, they will attempt to kill the fish and likewise, the fish themselves will try to avoid the predators as much as they can. When objects are introduced, the fish will attempt to maintain their schools, but can be broken up in an attempt to weave around these objects and not collide with them. In terms of visual representations, we altered the cloth simulator background to create a sea-like environment and implemented a custom texture shader for applying a sandfloor to the bottom of the simulation environment. The mesh models for the fish, predators, and objects such as pillars were created from scratch using OpenGL to create a visually stunning environment to display the fishes' behavior. Our approaches to simulating the behavior of a school of fish borrows from multiple sources including Craig Reynold's seminal work in "Flocks, herds and schools: A distributed behavioral model" (1987), a recent Bachelor's thesis by Erik Martin Vetemaa, "Simulating the Collective Movement of Fish Schools", and "Obstacle and Collision Avoidance Control Laws of a Swarm of Boids" by Bibhya Sharma, Jito Vanualailai, and Jai Ra for inspiration for collision avoidance.

Part 0: Kinematics and Parameters

Each of the following sections will dive into some fish behavior that is described by a resulting acceleration. This acceleration is used to motivate movement via the explicit Euler method. $$ x_{t+1} = x_t + \delta(t) \cdot x'_t $$ $$ x'_{t+1} = x'_t + \delta(t) \cdot x''_t $$ Although this method is usually frowned upon due to inaccuracies exploding over time, errors are mitigated by restricting the range of velocities of the fish and predators, which is physically and biologically reasonable assumption we are allowed to make. For each of the acceleration, only the direction of the acceleration is truly calculated, it producing a unit vector as it is normalized at the end of the process. What gives a certain acceleration scale is a parameter fixed manually by us. A large part of the Final product was tuning these parameters to best match the real-life description of schools of fish.

Part 1: Social Behavior

Implementing the social behavior of a school of fish follows three ideas: alignment, cohesion, and separation. Each of these three sources of acceleration for the fish are calculated based on the neighboring fish, those being within a certain radius of the fish.

Alignment is used to match the velocity of a fish to its neighbors. Cohesion is used to keep a fish close to its neighbors as well. This is done by calculating the weighted average of the neighboring fish's positions with the weight listed above and calculating the resulting acceleration as the fish's displacement to the weighted average position. Separation is used to prevent collisions between fish.

Part 1.1: Alignment

A fish in a school usually moves at a similar velocity as its neighbors. We implement this by altering the velocity vector of a fish based on its neighbors. This is done by taking the weighted average of the neighboring fish by first multiplying the neighboring fish's velocity vector by a weight that drops off with distance, that being $$ w = 1 - \frac{r}{R} $$ Where r is the distance between a fish and its neighbor, and R is the radius of detection for neighbors for Alignment. This weight has the effectiveness of an individual neighboring fish's contribution drop off by distance linearly. We had experimented with different drop off rates including quadratic, logarithmic, and exponential, but found the linear approach to be the most effective (and simplest). This weight being applied for alignment of the neighboring fish is used for cohesion and separation as well. Our implementation uses a 2D vector called alignment to control how this behavior is implemented. The first component is the detection radius, which is used to limit the neighboring fish to be within alignment.x of a fish for alignment calculation. The second component is used to scale the alignment itself, that is to say how strong the alignment should be.

Part 1.2: Cohesion

Naturally, schools of fish usually travel in large groups. As such, we have implemented behavior such that a fish will always swim towards its neighbors by using a cohesion vector, which is the centroid of the fish minus the average centroid of its neighbors. This is a weighted centroid scaled by the weights mentioned earlier. This is added to the fish's acceleration, which gradaually steers it towards its peers. And similar to how we implemented alignment, we also used a vector called cohesion to control the area of neighboring fish considered as well as the magnitude of the cohesion.

Part 1.3: Separation

In order to keep fish from colliding with each other, a separation vector is used to keep a fish from making contact with other fish. The separation vector is computed by subtracting the average centroid of all the neighboring fish from the centroid of the fish itself. This vector is added to the fish's acceleration, which will gradually steer it away from its companions and prevent any collisions. This happens to be the opposite of how cohesion is implemented, where the direction of the adjustment vector is reversed. And just like the previous two parts, a vector called separation is used to control the separation mechanism. Intuitively, the radius of separation is much smaller than the radius of cohesion. If they were to be comparable, they would cancel each other out.

Part 2: Wandering Behavior

While a school of fish generally have similar movements, in reality they are not always moving the same direction at the same speed. This is why we have the wandering behavior, where a fish will sometimes deviate from its path behavior defined by alignment, cohesion, and separation, and in the case that it's isolated, it's straight forward trajectory. In order to achieve a random and smooth function of Wander Acceleration, we refer to Cubic Hermite Interpolation as suggested in Vetemaa in their thesis. For our implementation, each fish keeps track of 4 random points, which are generated when the fish are initialized. These points are interpolated to produce a random and smooth acceleration vector that deviates the fish's path for 3000 time steps; when 3000 time steps have passed, new points are needed to keep the random acceleration function going. All but the last interpolation point are refreshed every 3000 time steps (to ensure continuity from the previous set of points) using the instance variable personalTime to keep track of it. Unlike the social accelerations, this acceleration is not normalized, as that would break the continuous nature of the acceleration.

Part 3: Boundary Behavior

The fish in our simulation are technically allowed free domain over the entirety of the computed space; however, this is inconvenient for show business. Therefore, we introduced an artificial acceleration that will restrict the fish to an observable and controllable area. This is implemented by creating a bounding box over the desired area and having the acceleration being linearly proportional to the distance it travels beyond the bounded volume. The direction of this acceleration is towards the closest point of the bounded volume, and given it is a box, this is calculated easily as the difference of the components.

Part 4: Obstacle Avoidance

Fish are able to perceive the path in front of them and avoid incoming objects, rather than bump into them. There are many methods of having simulated fish avoid these objects whether it come in the form of vector fields and scalar fields of distance produced by these obstacles or sampling random points until a direction directed towards empty space with least acceleration is found. For our implementation, we take a relatively novel (it may exist in literature elsewhere) where we drew inspiration from ray-tracing where we view the fish's future path and trace a ray from its current position ahead until it hits an object within a set 'eye-sight' radius, let's call this vector the incident vector. Then, to calculate the actual acceleration produced to avoid colliding with an object, we take the incident vector and bounce it off the surface, having an angle relative to the normal of the surface being equal to the incident angle. The acceleration is then taken from the component of this reflected vector that is perpendicular to the incident vector. What this allows is an acceleration that is perpendicular to the velocity, meaning the actual speed won't increase but the direction as well. This also resolves a shortcoming of the aforementioned methods, where the resultant acceleration is naively equal to the normal of the surface, which is not the path a boid would take to avoid an object as it would require more effort. Below is a diagram of the incident and resultant vectors as well as the acceleration. This was implemented for simpler shapes such as a plane, sphere, and cylinder (pillar).

The following are videos of the obstacle avoidance acceleration in action with simpler shapes, which were implemented using algorithms from the ray-tracing assignment for intersections and finding the reflected vectors.

An interesting thing to note, is that the presence of obstacles has the potential to divide up schools of fish if the velocity of the school of fish is heading directly for one of these obstacles.

Part 5: Predators

Every school of fish has one thing to fear, and its predators. A predator's behavior is similar to a regular fish with some differences.

Part 5.1: Fleeing

The fleeing behavior is very similar to the separation behavior described previously. However, the main difference here is that the positions of the predators are used instead of the neighboring fish. We also used a scalar value flee to control the magnitude of the avoidance vector. In other words, flee controls how scared a fish should be of nearby predators. Likewise, with parameter tuning, the radius of the predator detection is much greater than that of friendly neighbors.

Part 5.2: Hunting

A predator's hunting behavior also follows a similar pattern to fish alignment and cohesion. However, the difference here is that a predator will lock onto the nearest fish and accelerate towards it for a certain period of time that either terminates with the predator's success or fatigue. This lock-in mechanism is implemented by having an instance variable of a predator be that of a fish, which is held only for a set period of time. Its acceleration is controlled by the hunt value. Just like the flee value, hunt controls how fast a predator accelerates towards its prey. When a predator makes contact with a fish, the fish becomes dead and will sink to the bottom of the sea floor. Don't worry! This is just a temporary state for the fish as it will recover (unrealistic, but artistic freedom). After that, the predator enter's a "rest period", being satisfied with its meal, where it will temporarily not attack any fish.

An interesting pattern that evolves from this, is that eventually, the targeted fish breaks off from the school to avoid the predator. Furthermore, schools of fish are likely to be broken up with a predator in close proximity.

Part 6: Fish + Predator Meshes and Textures

Both fish and predators are composed of triangle meshes. This was difficult as we were unfamiliar with OpenGL, but the actual meshes consist of two base-to-base 16 sided pyramids (representing the head and body), and the tip of one of the 16-sided pyramids connected with a 4-sided pyramid (representing the tail). This was created in a local coordinate system and required a scaling and rotation matrix to transform it into the space of the fish simulator to give the fish it's thin look along the x-axis and to orient the fish to face forward in accordance with its velocity; this also included a translation as well to the position of the fish. Each triangle vertex in the mesh is also assigned a uv coordinate of (0, 0), (1, 0), (0, 1), or (1, 1) to fit desired scale pattern for the fish or stone pattern for the pillars (custom obstacle built). For this project, we have decided to use the shaders that were implemented for the clothsim to apply textures to both the fish and predators. The shaders are also used to create a sand floor in the simulated aquarium and object textures.

Part 7: Results

Overall, we are satisfied with the similarities our simulated school of fish share with real-life schools of fish. It was a great deep dive into the tools we've used over the past semester such as OpenGL, and a multi-faceted review that borrowed elements from all of the assignments we've done this past semester. Please see link at the top for full simulation (file is too large for GitHub to host).

While we are proud of what we have accomplished, there are many improvements that could be made in the future. This includes adding more features for the fish to interact with such as rewards like food. Another important detail is considering fluid dynamics, as movement in the water is bound to create changes in the water such as pressure and velocity of the water (leading to drag and other physical consequences). Due to the lack of experience with OpenGL, a more complex environment with different obstacles is desirable as well as the actual design of the fish.

Part 8: References

1) Simulating the Collective Movement of Fish Schools by Eric Vetemaa

2) Adobe Stock Photos

3) Flocks, herds and schools: A distributed behavioral model by Craig Reynolds

4) Obstacle and Collision Avoidance Control Laws of a Swarm of Boids by Bibhya Sharma, Jito Vanualailai, and Jai Ra

Part 9: Contributions

William implemented the social behaviors, which include Alignment, Cohesion, and Separation acclerations. Stefan helped with the social behaviors. He implemented the boundary, wandering, and collision avoiding accelerations. Stefan also constructed the new classes and meshes for them including the fish, predator, and pillar as well as the scenes used. An implemented the predator behvior, which includes the flee and hunt accelerations. An also worked on the shaders used for the ground and fish.