Beautiful Algorithms 3: 1D Collisions

“1D Collisions” might sound a little bit strange, but the goal of Beautiful Algorithms 3 is to explore algorithms for collision physics.  Collisions in 2 or 3 dimensions are naturally more complex than a single dimension, so let’s look at this first.  I’ll explain what mathematics and physical laws are required (don’t worry, you understood all of this when you were 13), and then explain how to write a Ruby program to simulate this.

Newton’s Laws

You probably did simple experiments in science classes at school whereby objects were rolled down ramps, and their bounces were measured.  This is a physical exploration of Newton’s second and third laws of motion.

• Newton’s second law of motion: Momentum = mass * velocity
• Newton’s third law of motion: For every force there is an equal and opposite force
• Newton’s law of impact: The difference between velocities before impact is proportional to the difference between their velocities after impact
  

In the Ruby Shoes example, we’ll draw two balls and make them collide.  Calculating their position for a given frame of animation will require the second law.  Collisions will use the third law and law of impact to calculate the velocities after impact.

Velocity

Velocity is the rate of change of position: speed and direction are combined as a vector.  Vectors aren’t scary — in this example we’ll use an array to model velocity for the speed going left or right and up or down.

The velocity will change after impacts according to the second law of impact and third law: that is, the velocity should be reversed after impact, transferring some of its energy in the process.

Required Variables

According to the brief and possibly inaccurate summary of high school Newtonian physics above, each ball will have the following variables:

• Mass
• Velocity (as an array) — negative values will mean left or up
• X and Y co-ordinates
• A value for the coefficient of restitution — basically the amount of energy lost in each impact

Required Methods

We’ll need to know when balls bounce off each other or the walls of the scene.  We’ll also want to update the position for each frame of animation.

• check_collisions(set of balls)
• hit?(ball) — check if the ball has bounced off another one
• collide — if a collision has been detected, alter the velocity according to the laws above
• move — move the ball

Collision Detection

The algorithm works like this:

1. Calculate the distance between two balls using Pythagoras’ Theorem by subtracting their positions to create a common frame of reference, then calculating the hypotenuse
2. If this value is less than or equal to the combined radius of each ball, they’ve bounced
3. If the ball has moved to the end of the window, it has bounced

The first step sounds a little bit complicated.  Basically:

x = absolute value of: ball_a.x - ball_b.x - x_velocity
y = absolute value of: ball_a.y - ball_b.y - y_velocity
hypotenuse = square root of (x squared + y squared)

Main Loop

The main loop will look like this (example requires JavaScript to display):

Putting it Together

The final example is available here: ball-1D.rb.  You can run it with Shoes.  Note that there’s no friction or gravity, bodies simply bounce until their collisions reduce their velocity enough.

Try playing around with the velocity and mass settings to see what happens.  I’ll be back on Monday with a 2D collision example!