Algorithms | Quark's musings

In the post Linear motion we saw how vectors can be used to represent the position and velocity of a moving object. Here we look at how they can be used to simulate the shot fired from a medieval cannon as shown here.

When the cannon is fired the cannon ball will have an initial direction and speed (depending on the barrel elevation and the amount of gunpowder used).

We can see that the cannon ball’s direction (angle) changes throughout it’s flight due to gravity and air resistance so using speed/angle would be computationally demanding. So we are going to use vectors (Processing’s PVector class) to represent the ball’s position and velocity.

So we need some variables to store this data –

int cannon_angle;           // degrees
PVector cannon_pos;

// Cannon ball data
PVector ball_pos, ball_vel;
float speed = 300;         // cannon-shot speed

So the cannon is fired, the first job is to calculate the initial position and velocity of the cannon ball. We can do that with

ball_pos.set(cannon_pos);
float angle = radians(cannon_angle);
ball_vel.set(speed * cos(-angle), speed * sin(-angle));

The first line initialises the position of the ball to that of the cannon. The angle data is stored in degrees because that is what the human user understands but we must convert it to radians for the trigonometric functions, that is done in the second line. Finally we initialise the velocity vector using the speed and angle. Notice that we negate the angle because the barrel rotation is anti-clockwise.

At each frame we need to update the ball’s velocity to take into account gravity and air resistance, both of which can be represented as vectors. In this sketch we use

gravity = new PVector(0, 100);
air = new PVector(-40, 0);

The gravity will only affect the vertical component of the velocity and the air resistance will only affect the horizontal component.

So we update the velocity with

ball_vel.add(PVector.mult(gravity, elapsedTime));
ball_vel.add(PVector.mult(air, elapsedTime));
ball_vel.x = max(ball_vel.x, 0);

where elapsedTime is the number of seconds since the last frame.

The last line prevents the cannon ball reversing its horizontal velocity due to air resistance. In the physical world this is impossible but in our simplistic model, it is a possibility we should guard against.

We can now use this velocity to update the ball’s position with

ball_pos.add(PVector.mult(ball_vel, elapsedTime));

I hope this demonstrates the usefulness of using vectors to represent positions, velocities and forces (gravity and air resistance) to plot non-linear movement.

You can download the sketch used in the production of the movie above here. It is compatible with both Processing 2 & 3.

One of the hardest types of error to debug is the logic error. Your code compiles, your code runs but it doesn’t do what it is supposed to do. There is no error message pinning down a syntax error or helpful exception message showing where the program stopped and why, you just have to examine your code for your mistake.

In this post I want to present such a situation. The program (Processing sketch) is straightforward – there is a ball bouncing inside a box at constant speed. To make sure it is constant the sketch uses the elapsed time between frames to calculate the distance the ball should move. If the ball hits the left or right sides then the horizontal velocity is reversed by multiplying by -1. The same logic is applied if the ball hits the top or bottom sides when we multiply the vertical velocity by -1.

float ballSize = 20;
float ballX, ballY, ballVX, ballVY;
float speed = 500;
float left, right, top, bottom;

int currTime, prevTime;  // milliseconds
float elapsedTime;       // seconds

void setup() {
  size(600, 400);
  left = 40; 
  right = width-40; 
  top = 40; 
  bottom = height-40;
  rectMode(CORNERS);
  ballX = random(left + 2 * ballSize, right - 2 * ballSize);
  ballY = random(top + 2 * ballSize, bottom - 2 * ballSize);
  float angle = random(TWO_PI);
  ballVX = speed * cos(angle);
  ballVY = speed * sin(angle);
  // This should be last line in setup
  currTime = prevTime = millis();
}

void draw() {
  // Using elapsed time between frames to guarantee the ball moves at constant speed.
  currTime = millis();
  elapsedTime = (currTime - prevTime) / 1000.0;
  prevTime = currTime;  // set it up for the next frame
  updateBallPosition(elapsedTime);
  rebound();
  // Draw the frame
  background(255);
  stroke(0);
  strokeWeight(2);
  fill(250);
  rect(left, top, right, bottom);

  fill(0, 140, 0);
  ellipse(ballX, ballY, 2 * ballSize, 2 *ballSize);
}

void updateBallPosition(float et) {
  ballX += ballVX * et;
  ballY += ballVY * et;
}

void rebound() {
  if (ballX - ballSize < left || ballX + ballSize > right)
    ballVX *= -1;
  if (ballY - ballSize < top || ballY + ballSize > bottom)
    ballVY *= -1;
}

The program logic makes sense but it doesn’t work properly. If you copy and paste the code into Processing and run the sketch long enough you will eventually see the ball do something peculiar (it might take several minutes so be patient). If nothing happens on your computer then this video shows the results of running the sketch on mine.

Before you read the explanation give the problem some thought and see if you can work out why this is happening.
If you haven’t worked it out yet don’t worry it took me a while too when it first happened to me.

Explanation
The ball moves at constant speed but the elapsed time between frames is not. This means that the distance traveled by the ball between frames can vary. Now consider the ball approaching the right wall, eventually the ball hits the wall and the X velocity is multiplied by -1. On the next frame the ball moves left but what happens if the condition

ballX + ballSize > right

is still true. The velocity is reversed again so on the next frame the ball moves right. The X velocity will be reversed each frame so the ball jiggles horizontally until it gets back inside the box. You can see what I mean here –

The Solutions
If we can explain the problem then we can develop appropriate solutions. Obviously the algorithm used in the rebound function has a logic error. I will present 3 alternative algorithms which solve this problem.

Solution 1
This the simplest algorithm to implement and only involves changing the velocity. If the ball hits the left wall then make the X velocity positive and if hits the right wall make the X velocity negative, then do a similar thing for the top and bottom walls. We can see this algorithm in action here –

It also means that if the ball starts outside the box, no matter how far outside, it will end up bouncing inside the box.

Solution 2
This algorithm is a simple variation of the original one. After multiplying by -1 reversing the velocity we update the ball position again using the same elapsed time. This has the effect of bringing the ball back inside the box.

Solution 3
Like solution 1 we test each wall separately but we still multiply the velocity by -1. The difference is that we move the ball inside the box so that it is just touching the wall. On the next frame, the ball will move further into the box.

In this solution there will one frame where the ball is in contact with the wall on every rebound. This can give a slightly better ‘visual bounce’ than the other algorithms.

Conclusion
Notice that in all three solutions the ball trajectory after rebounding is different and none of them represent a real world rebound, they are all an approximation. There are solutions that provide more ‘accurate’ rebounds but they are computationally more intensive so you have to balance accuracy against efficiency.
Logic errors can be hard to find but it is important to understand what is happening in your code if you want reliable solutions.

Quark's musings

Category Archives: Algorithms

Cannon Fire

The Logic Error