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.

The next step is to translate the algorithm into code.