# CS2D7 - Lab 8 - Particle and Particle Systems

In Lab 7, we discussed how we can visualise algorithms by displaying one step at a time, through the use of Python. By doing this, we can see each stage of the algorithm as a nice (though sometimes choppy) animation. In this lab, we are going to be extending this to visualising physics principles across a large amount of particles.

You may notice we are not in Visual Studio Code for this lab. Rather than Python, we are going to be using a specialised visualisation program called Processing. These are installed onto the DCS system, and can be installed on your personal machine here. The general lab page (here) has more details on how to access this.

## Bouncy Ball Simulation

We are going to start off with a simulation of a ball. Lets draw a ball, by using the following code in Processing:

`void setup() {  size(800, 800); //Define the size of our canvas/window. (width, height)}void draw() {  fill(255, 0, 0);  //Lets make the ball red! (red, green, blue)  ellipse(400, 400, 100, 100);  //Place the ball in the centre (400, 400), with a width and height of (100, 100). (x position, y position, width, height)}`

When we run this, we get a lovely ball, hovering in the centre of our window.

### Generalising the problem

To make this more useable later on, we can make this a bit more generic. Processing is based on Java, so we have all the benefits of Object Orientated Programming! As such, we are going to create a class called `Point`, which can store the x and y data for a given point:

`class Point {  private double x = 0;  private double y = 0;  public Point() {}  public Point(double xNew, double yNew) {    x = xNew;    y = yNew;  }  public void setPos(double xNew, double yNew) {    x = xNew;    y = yNew;  }  public double getX() {return x;}  public double getY() {return y;}}`

Whist this is useful for storing positions, velocities and forces, we need more information and detail to define a ball. As such, let's create a `Ball` class that utilises the `Point` class to store different factors and requirements. We will need to store the position, velocity and acceleration of the ball, as well as the mass, radius and colour of the ball. We will also need to update the ball, so we'll create a function for that...

`class Ball {  private Point position;  //Stores the current position of this ball  private Point velocity;  //Stores the current velocity of this ball  private Point acceleration;  //Stores the current acceleration of this ball  private final int radius = 100;  //The radius of this ball  private final double mass = 20000.0;  //The mass of this ball  private final color colour = color(255, 0, 0);  //The colour of this ball /* Define the starting point of the ball. It will have no initial velocity or acceleration */  public Ball(Point start) {    position = start;     velocity = new Point();    velocity.x = velocity.y = 0.0;     acceleration = new Point();    acceleration.x = acceleration.y = 0;  } /* Functions to get the data when needed later */  public Point getPos() {return position;}  public Point getVel() {return velocity;}  public Point getAcc() {return acceleration;}  public int getRadius() {return radius;}  public color getColour() {return colour;} /* Our update function, given a difference in time (dt), air drag coeficient (airDragCoef) and * the acceleration due to gravity (gravity) */  public void update(double dt, double airDragCoef, double gravity) {    //TODO: Define how we update the ball  }}`

Finally, lets put this ball object into the visualisation! To do this, we can modify the `setup` and `draw` functions we defined earlier... (new sections have been added in bold.)

`public Ball ball = new Ball(new Point());  //Our ball objectpublic final double dt = 0.1;  //A period of timepublic final double airDragCoef = 0.24;  //Average Air Drag Coefficient on Earthpublic final double gravity = 9.81;  //Acceleration due to Gravity on Earthvoid setup() {  /* ... previous code here ...*/  ball = new Ball(new Point(width/2, height/2));  //Make sure the ball starts in the right place}void draw() {  background(200);  ball.update(dt, airDragCoef, gravity);  //Update our balls position, velocity and acceleration   fill(ball.getColour());  //Get and set the colour of the ball  //Draw the ball!   ellipse((int) (width-ball.getPos().x),      (int) (height-ball.getPos().y),     ball.getRadius(),     ball.getRadius()  );}`

You may notice that this new version looks exactly the same as the old one, which is rather underwhelming. However, now that we have all this extra code, we can manipulate the ball more clearly. In the previous section, we had a function called update within the `Ball` class that was left blank. This is where we are going to add our simulation calculations.

First up, let's calculate the force of air resistance. We are going to use the generalised equation for this: $Force=(speed^2 * air resistance coefficient) * (-1 * velocity))$

where s is the speed of the ball, k is the air resistance coefficient and v is the velocity. Thus, when we translate that into code, it would look something like this:

`/* Calculate air resistance --> F=(speed^2 * air resistance coefficient) * (-1 * velocity)) */double speed = sqrt((float)(velocity.x * velocity.x) + (float)(velocity.y * velocity.y));  // <-- Pythagoras theorem!Point airResistance = new Point();airResistance.x = (speed * speed) * airDragCoef * (-1 * velocity.x);airResistance.y = (speed * speed) * airDragCoef * (-1 * velocity.y);`

We can then work out the total forces by taking the force from gravity away from `airResistance.y`:

`/* Gravity force down */double gravityYForce = mass * gravity;/* Sum forces (remember, +ve air resistance is up so would oppose gravity) */Point force = new Point();force.x = airResistance.x;force.y = gravityYForce - airResistance.y;`

From here, we can use Newtons second law ( $F=ma$) to work out the acceleration of the ball:

`/* Update x and y accelerations *///F = ma, therefore a = F/macceleration.x = force.x/mass;acceleration.y = force.y/mass;`

Then work out the velocity using $a=v/dt$. For this, we need to multiply it by -1 in order to act in the correct direction:

`/* Update x and y velocity *///Acc = vel/time, therefore vel = Acc*timevelocity.x += -1*acceleration.x*dt;velocity.y += -1*acceleration.y*dt;`

And finally, we can work out the position using $v=d/dt$:

`/* Update x and y positions *///Vel = dist/time, therefore distance = Vel*timeposition.x += velocity.x*dt;position.y += velocity.y*dt;`

What would you expect when you put all the code into the `update` function, and see how it compares to what you get.

You'll see that the ball currently falls off the edge of the canvas, which is not very bouncy. In order to make it bounce, we need to check whether the balls position goes below 0 in either axis, goes above the width in the x axis or the height in the y axis. We also need to invert the relevant velocity...

This code can be added to the `update` function:

`if (position.x < 0) {  position.x = 0;  velocity.x *= -1;} else if (position.x > width) {  position.x = width;  velocity.x *= -1;} if (position.y < 0) {  position.y = 0;  velocity.y *= -1;} else if (position.y > height) {  position.y = height;  velocity.y *= -1;}`

Give it another test, and see what happens...

### Displaying some Text

We now have a bouncing ball! Excellent! We can make the visualisation more complete, by displaying the position, velocity and acceleration. To do this (and not spam out stuff to the terminal), we can use a pre-installed library called ControlP5. This has a bunch of different buttons, sliders and other widgets, in a similar way that ipywidgets has a large collection of things. For this, we need to define a text module, and set it's text. Modify the `setup` and `draw` functions we defined earlier with the following code... (new sections have been added in bold.)

`public ControlP5 cp5; //Object to manage our widgetspublic Textarea details;  //Object to store data specific to the text area widgetvoid setup() {/* ... */  cp5 = new ControlP5(this);  //Setup the object for our widgets   //Create a Text Area, and specify where it is, how big, the font and colour details = cp5.addTextarea("details")               .setPosition(10,10)               .setSize(300,100)               .setFont(createFont("arial",12))               .setLineHeight(14)               .setColor(color(128));}void draw() {/* ... */  //Set the text to be displayed details.setText("Position: (" + ball.getPos().x + ", " + ball.getPos().y + ")\n" +       "Velocity: (" + ball.getVel().x + ", " + ball.getVel().y + ")\n" +      "Acceleration: (" + ball.getAcc().x + "," + ball.getAcc().y + ")"  );   //If the position isn't valid, stop our simulation! if (Double.isNaN(ball.getPos().x) || Double.isNaN(ball.getPos().y)) {   stop();   }}`

Putting this all together, we should have a bouncy ball simulation that will bounce off the floor and walls, can be given a starting position and velocity, and will display all the details about it!

### Exercise 1

Update the bouncy ball model such that:
• The ball has an initial velocity and/or acceleration.
• When the ball bounces, some energy is lost. Initially, this should be 5%, but can be altered later.
• The ball bounces from the edge of the canvas, rather than the centre.
• The air resistance, the acceleration due to gravity and the mass of the ball can be altered whilst the model is playing.

## Boids

Built in the mid-to-late 80's, Boids was an AI program designed to mimic flocking birds. Each "bird" has a set of rules it follows, given information about the "birds" it can see. From this principle, an emergent behaviour can be seen, which hasn't been hard coded, but occur because all the "birds" work individually. We see similar behaviours in the real world, whether it is traffic on a road or ants carrying leaves.

### Creating our Boid Objects

Just like our ball, we can represent each "bird" as an individual object. We'll keep the Point class from the bouncy ball example, but lets create a new class for our "birds", which we will refer to as `Boid`. It should have a structure similar to this:

`class Boid {  private Point position;  private Point velocity;  private Point acceleration;  private color colour;  private final double radius = 10.0;  private final double mass = 10.0;  private final double viewRange = 50.0;   public Boid(Point newPosition, Point newVelocity) {    //TODO (Ex2a): Set the position and velocity to the new position and velocity    //TODO (Ex2a): Set the acceleration to 0    //Set our colour for our boid to be a random colour    colour = color(random(0, 255), random(0, 255), random(0, 255));  }   public void update(Point desiredVelocity, double dt) {    //TODO (Ex2e): Update the acceleration, velocity and position by applying a force to get us closer to the desired velocity    //Rather than bouncing the particles, we are going to teleport them to the other side...    if (position.x > width) {      position.x -= width;    } else if (position.x < 0.0) {      position.x += width;    }    if (position.y > height) {      position.y -= height;    } else if (position.y < 0.0) {      position.y += height;    }  }   public void display() {    //TODO (Ex2a): Draw our individual Boid  }   public Point getPos() {return position;}  public Point getVel() {return velocity;}  public Point getAcc() {return acceleration;}  public color getColour() {return colour;}  public double getViewRange() {return viewRange;}}`

From here, we can generate an array of `Boid` objects, and draw each one...

`public final int numBoids = 1000;public final Boid[] boids = new Boid[numBoids];void setup() {  size(800, 800);   for (int i = 0; i < numBoids; i++) {    boids[i] = new Boid(      /* TODO (Ex2a): Define a random point for the position */,       /* TODO (Ex2a): Define a random point for the velocity */    );  }}void draw() {  background(200);   for (int i = 0; i < numBoids; i++) {            boids[i].display();  }}`

Currently, it won't show anything, as our display method is empty, and the boids position and velocity haven't been set. Therefore...

### Exercise 2a

Draw all our Boid objects by filling in the `TODO (Ex2a)` code blocks above

### Forces on the Boids

Now that we can see our boids, we can start applying forces to them to start getting them to change directions. There are many different forces we can apply to them, but all Boid simulations must include the following 3 forces as there base:

• Separation Force - moving away from others
• Alignment Force - all moving in the same general direction
• Cohesion Force - moving into valid gaps in the pack

#### Seperation Force The separation force ensures that areas of the visualisation do not get too crowded. If you think back to the original aim for this visualisation, birds wouldn't want to fly too close to each other for fear of hitting each other! Therefore, if a boid gets within the view range, we want to apply a force to move it away from it.

### Exercise 2b

Build a function called `separation`, that returns a `Point` object representing the force produced. The following can be used as a starting point:

`public Point seperation(Boid[] boids, int current) {  Point result = new Point();    //Iterate through all the boids    //If the one examined is the same as the current one, continue    //Otherwise, see if the examined boid can be seen by the current boid      //If it is, add the separation force to the result, and increment a counter  //Once we have iterated through all the boids...  //If the counter is not 0, divide the results by the counter   return result;}`

#### Alignment Force The alignment force ensures that all the boids move in the same direction. Again, if you think back to the simulations purpose, birds won't intentially travel into another bird, but instead will try and follow the flock. Therefore, we want to take average velocity of all the boids within view range, and try and move to align with it.

### Exercise 2c

Build a function called `alignment`, that returns a `Point` object representing the force produced. The following can be used as a starting point:

`public Point alignment(Boid[] boids, int current) {  Point result = new Point();    //Iterate through all the boids    //If the one examined is the same as the current one, continue    //Otherwise, see if the examined boid can be seen by the current boid      //If it is, add the alignment force to the result, and increment a counter  //Once we have iterated through all the boids...  //If the counter is not 0, divide the results by the counter   return result;}`

#### Cohesion Force The cohesion force ensures that the boids don't move too far away, by trying to go into gaps between all the boids it can see. In the birds scenario, the birds will not want to fall away from the flock. Therefore, we want to try and move towards the average of all boids within the view range.

### Exercise 2d

Build a function called `cohesion`, that returns a `Point` object representing the force produced. The following can be used as a starting point:

`public Point cohesion(Boid[] boids, int current) {  Point result = new Point();    //Iterate through all the boids    //If the one examined is the same as the current one, continue    //Otherwise, see if the examined boid can be seen by the current boid      //If it is, add the cohesion force to the result, and increment a counter  //Once we have iterated through all the boids...  //If the counter is not 0, divide the results by the counter   return result;}`

#### Combining our forces

We know where each force wants to send the boid, now we need to combine all of it together to form 1 complete desired velocity. As such, we are going to add all the x and y components together. To allow some tuning, we will be multiplying the velocities by a weght.

`public Point desiredVelocity(Point[] velocities, double[] weights) {  Point result = new Point();   for (int i = 0; i < velocities.length; i++) {    result.x += velocities[i].x * weights[i];    result.y += velocities[i].y * weights[i];  }   return result;}`

To combine all this into the `draw` function, we do the following (new code in bold):

`public final double[] weights = {0.5, 0.5, 0.5};public final double dt = 0.1;void draw() {  background(200);   for (int i = 0; i < numBoids; i++) {    Point[] desired = new Point[weights.length];    desired = separation(boids, i);    desired = alignment(boids, i);    desired = cohesion(boids, i);     Point desiredVel = desiredVelocity(desired, weights);     boids[i].update(desiredVel, dt);     boids[i].display();  }}`

### Updating our Boids

We now have our desired velocity we want to end up. However, we can't just set that as our new velocity, it would make the boids very jerky. Instead, we are going create a "steering force", by taking the difference between the desired velocity and the current velocity. We can then use this to slowly move the boid in the right direction, using the same method as the one for the ball.

All of this can be done within the `update` function and can look very similar to the `update` function in the `Ball` class.

### Exercise 2e

Build the `update` function for the `Boid` object (where `TODO (Ex2e)` is).

The boids should be moving and interacting now! It may take a bit of tweaking to get it right, so it would be cool if we can check each force, and even change the weightings of the force on the fly. Therefore, we are going to utilise the sliders provided by ControlP5. Below is the code that will add in 3 slides, 1 for each force, along with a function called `controlEvent`; that will capture the output of the widgets and set the appropriate weight:

`import controlP5.*;/* Some other code here! */public ControlP5 cp5;public Slider separationSlider;public Slider alignmentSlider;public Slider cohesionSlider;void setup() {  /* Previous code here */  //Create the sliders required, and specify there range, size, position and starting value cp5 = new ControlP5(this);  separationSlider = cp5.addSlider("Separation")  //Separation slider   .setRange(0.0,1.0)   .setValue(0.25)   .setPosition(30,30)   .setSize(100,15);  alignmentSlider = cp5.addSlider("Alignment")  //Alignment slider   .setRange(0.0,1.0)   .setValue(0.8)   .setPosition(30,50)   .setSize(100,15);  cohesionSlider = cp5.addSlider("Cohesion")  //Cohesion slider   .setRange(0.0,1.0)   .setValue(0.1)   .setPosition(30,70)   .setSize(100,15);}/* void controlEvent(ControlEvent theEvent) { if (theEvent.getController().getName()=="Separation") {   weights = theEvent.getController().getValue(); } else if (theEvent.getController().getName()=="Alignment") {   weights = theEvent.getController().getValue(); } else if (theEvent.getController().getName()=="Cohesion") {   weights = theEvent.getController().getValue(); }}`

It now should be easier to check each force, by having a slider set to 1, and the rest of the sliders set to 0.

### Refining our simulation

If you leave the program running for a while, you'll see that the boids will continually speed up, to the point that the boids barely become visible! This is because the forces will form a feedback loop. As such, it is worth adding a limit to the velocity, so that the boids stay at a reasonable speed.

### Exercise 2f

Update the Boids model such that:
• A limit to the velocity has been applied (this can be fixed or a slider, your choice!)
• The walls apply a force, rather than passing to the other side.
• The forces and/or desired velocity can be turned on and off whilst the model is playing.
• The different weights and the visual range can be adjusted whilst the model is playing.

## Further simulations

As always, this is only scratching the surface on what can be done! Another idea was discussed in the lecture slides, called a Force Field simulation. In this, the particles have a force applied by a grid of forces. These forces are applied in a random direction, and all forces act on each particle scaled to their distance (such that the closer the particle is to a force point, the greater the force that is proposed).

### Bonus Exercise

Implement the Force Field simulation with 1000 particles and a grid of 20x20 forces.