Algorithms

In the last section we looked at how to approach an entire program by dividing and conquering.

Within our program there may be some tricky pieces of code. These sections of code are not necessarily the entire program and in fact may be a small section of code, but they are difficult and require some serious thought before beginning implementation.

As an example, I want to have 100 balls on a screen all moving in random directions. When they hit an edge they reverse direction. When they collide with each other they reverse direction.

An algorithm isn't the specific code, it is how we will solve the problem. The algorithm can be implemented in any language. We write algorithms in pseudocode. There is no standard for pseudocode. It may resemble English or be somewhat similar to the language you will implement it in.

Let's try to solve the above problem.

It is helpful to initially identify all of the data in the program. Firstly, we have 100 objects. Since they are all the same, except for their positions and direction, we can store them in an array. Let's create variables for the objects:

var objectX
var objectY
var objectDX
var objectDY

Next, we want to update each object independently and we will treat each object the same, therefore we can use a loop. When writing pseudo code there is no need to work out the correct for loop you write something such as:

Loop through all objects with i
    
End loop

Each time through the loop we want to update the object position based on its velocity:

Loop through all objects
    Add objectDX to objectX
    Add objectDY to objectY
End loop

Note that we are not concerned with correct array accessing and so on, we just interested to know that we are adding the velocity to the position.

We also need to check if the object has hit a wall and reverse direction:

Loop through all objects
    Add objectDX to objectX
    Add objectDY to objectY

    if objectX > width OR objectX < 0 then reverse direction of objectDX
    if objectY > height OR objectY < 0 then reverse direction of objectDY
End loop

Note that we are not using correct if statement syntax, or specifying how exactly we reverse direction, that is an implementation detail.

Next we need for check for object collisions. There are 100 objects we need check collisions between all of them! That means we need a nested loop to check all of the neighbouring objects:

Loop through all objects
    Add objectDX to objectX
    Add objectDY to objectY

    If objectX > width OR objectX < 0 then reverse direction of objectDX
    If objectY > height OR objectY < 0 then reverse direction of objectDY

    Loop through all neighbouring objects
        If neighbouring object is not the current object then
            If the neighbouring object and current object are overlapping then
                Reverse the direction of objectDX for the current object
                Reverse the direction of objectDY for the current object
                Reverse the direction of objectDX for the neighbouring object
                Reverse the direction of objectDY for the neighbouring object
        End if
    End loop
End loop

Even though the algorithm requires more work to translate into a workable JavaScript program, it makes the overall structure of the algorithm easy to read and understand. In this form we should be able to find logic errors.

Generally speaking the algorithm should capture the control structures in the program, i.e. loops and if statements (and later functions). Line by line syntax is not required nor is specific calculations. However, certain difficult maths should be worked out before implementation and can be included in the formula.

Below is an example of a difficult calculation that may only require a single line of code but requires some thinking.

Calculations

Problem: I want to move an object along a trajectory such that it models gravity.

How are we going to solve this problem?

Firstly, what is gravity? Most students should be aware that gravity causes objects to accelerate 9.8 metres per second per second, when falling. It decelerated objects by the same amount when they are moving upwards.

So we need to apply a deceleration/acceleration component to our object as it moves.

Secondly, how fast is the object moving initially? The object will have an initial speed and as it moves upwards it will decelerate until it stops and begins to accelerate to earth.

Let's presume that the initially velocity is v0 and it will be represented in metres per second. The current velocity will be represented by v.

Every second v0 must decrease by gravity, i.e. 9.8 metres per second. Let's assign our 9.8 m/s/s to the variable g.

So it might be tempting to think that we just need to reduce the velocity v by g:

v = v - g;

However, p5.js renders at 30fps. So the amount the object changes per frame will be 1/30th of what it would be per second, the change in velocity per frame will be:

v = v - g / frameRate();

The vertical position of the object will be stored in y. We need to add v to y each second. But once again our frame rate is much higher so we need to add 1/30th of the velocity to y:

y = y + v / frameRate();

As the object shoots across the screen the vertical axis changes with gravity. But what about the x axis?

The x axis will change at constant speed. It is not affected by gravity. There will be a different velocity for the x axis:

x = x + vX / frameRate();

What happens when the object hits the ground? Will it bounce? How much will it bounce? Will an object travel horizontally forever without slowing down?

We can model friction to slow the object down both vertically and horizontally. Friction is a force. Force can be represented as mass x acceleration. In other words it can simply be a deceleration applied to the x axis.

vX = vX - frictionX / frameRate();

When the ball bounces the velocity of the y axis will reverse. If we want the next bounce not to be as high, we can make the velocity a proportion of the existing velocity, e.g.:

if (y < 0) {
    vY = -vY * 0.8;
}

In this example the bounce velocity is only 80% of the initial velocity.

Given our units are in metres, we need to think about how this translates to pixels. Is one pixel a metre? Or 10 pixels? We need to divide or multiple our co-ordinates accordingly.