Collision Detection

 

The collision detection is a quite old problem within the field of computer simulations and can be described as follows: How do algorithms have to work whose purpose will be to detect the overlapping of two (rigid) objects, especially in dynamic situations? Such kind of problems are of relevance for video games, for instance. As an example: In a car racing game it might be important to detect an accident between two cars. The solutions for the problem of collision detection can be quite complex. However, for ActionScript developers here's the good news: ActionScript provides a pre-defined method that is capable with that problem. In the following exercise I want to introduce this method. The animation I programmed has a quite simple setup: A ball that is moving with a constant speed is surrounded by walls. Each time the ball collides with one of these walls it will be reflected in the mirror direction.

 

 

 

 

Actually, we will see that the most complicated part of this application will be to calculate the new, mirror reflected motion direction of the ball, since the collision detection itself will be performed by means of a simple function call.

I used two different layers for my application in the Flash editor: One layer (Basics) I predominantly used for the functions that will calculate the mirror direction. The other one (Ball) will contain the graphical elements of our animation (the ball and the walls) and the related code for these objects.

 

The graphical setup

So, let's start with the graphical setup of our application and place the objects on the stage of the layer Ball: First, I inserted the four walls, i.e., I used one rectangle for each edge of the stage. Then I converted each of these walls into a MovieClip and gave them individual instance names (topBar, rightBar, downBar, and leftBar). And next, I placed a colored disk at an arbitrary position of the stage, converted it into a MovieClip and gave it the name Ball. And that's all we have to do for the graphical setup of our animation.

 

Calculating the mirror direction

And now for the more sophisticated part of our application: The programming of the functions we need to calculate the mirror direction, after the ball hit one of the walls. Probably everybody knows the rule incident angle = reflected angle, which is the way light behaves when it is reflected by a mirror, for instance. And since there are already models that deal with such light effects in computer graphics, I took the easy way and adopted parts of a lighting model. More precisely, I adopted a part of the Phong [1] model—a well-known model within that field that has been already developed in the 70ies. For calculating the mirror direction we will use the following equation: The vector that points to the mirror direction is the same as the product of the surface normal of the wall (or mirror) and the doubled dot product between the surface normal and the incident direction vector minus the incident direction vector. In order to implement this equation I first programmed some auxiliary functions: One function for calculating the dot product between two vectors, another one that calculates the length of a vector and a last one that normalizes a vector, i.e., that sets the length of that vector to 1 unit.

I wrote all of those functions in the ActionScript window of the layer Basics. First the function that will calculate and return the dot product between two vectors (by the way: I programmed all functions that way that they can be used for n-dimensional vector spaces, and not only for the two-dimensional case that we need here):

 


function dotProduct(a:Array, b:Array):Number
{
	var sp:Number = 0;
	if(a.length != b.length)
		return 0;
		
	for(var i:Number = 0; i < a.length; i++)
	{
		sp = sp + a[i]*b[i];		
	}	
	return sp;
}

 

The auxiliary functions:

a) Calculating the dot product

The function dotProduct needs two vectors as arguments, that will be array objects. Within that function we will first declare a variable that represents the dot product. The purpose of the next two code lines it to check whether both vectors have the same length (i.e. the same number of elements). In case that they don't have identical numbers of elements, the function will stop further calculations and return the value 0. The for-loop will then calculate the dot product: Each element of one vector will be multiplied with the corresponding element of the second vector, and the single products will be summed up. The last code line returns that value.

 

b) Determining the vector length

The next auxiliary function (vectorLength) will calculate the length of a vector that has to be passed as the argument of that function. The vector length is the same as the square root of the sum of the squared elements of that vector:

 


function vectorLength(a:Array):Number
{
	var vl:Number = 0;
	for(var i:Number = 0; i < a.length; i++)
	{
		vl = vl + a[i]*a[i];		
	}
	var erg:Number = Math.sqrt(vl);
	return erg;	
}

 

 

c) Normalize the vector

The last function will normalize a vector that has to be passed as its argument. For this purpose one simply has to divide each element by the length of the vector. The result will be returned as a new vector (array).

 


function vectorNormalize(a:Array):Array
{
	var erg:Array = new Array();
	var vl:Number = vectorLength(a);
	for(var i:Number = 0; i < a.length;i++)
	{
		erg[i] = a[i]/vl;		
	}
	return erg;	
}

 

The core function

Using these auxiliary functions, we can program the core function of our application which I called vectorReflect. This function needs two vectors as arguments: The original motion direction vector of the ball and the surface normal vector of the wall from that the ball may be reflected. The surface normal of surface is defined as the vector that is perpendicular to that surface. So, let's have a look at that function in its entire beauty:

 


function vectorReflect(vector:Array, normale:Array):Array
{
	normale = vectorNormalize(normale);
	for(var i:Number = 0;i < vector.length;i++)
	{
		vector[i] = -vector[i];		
	}
	var erg:Array = new Array;
	for(var i:Number = 0;i < vector.length;i++)
	{
		erg[i] = 2*dotProduct(normale,vector)*normale[i]-vector[i];
	}
	return vectorNormalize(erg);	
}

 

In a first step, the surface normal vector will be normalized, that means its length will be set to 1 unit, since the calculation of the mirror direction will only work with normalized vectors. For the next step I used a for-loop that simply exchanges the sign of the elements of the original direction vector. This is necessary because in the Phong model [1] this vector represents the direction to the light source. However, here we need the motion direction of the ball that is heading for the wall. So we need to reverse the direction of that vector. In the following code line we declare a new (empty) vector as an array object that will represent the (yet to calculate) mirror direction vector. The core calculation will be done in the next code block, using the above-mentioned equation: I used a for-loop in order to assign the new value to each component of the vector. The resulting vector will then be normalized and returned.

 

Global variables

You may ask: Where do we get the vectors that must be passed to that function as arguments? Well, this is actually a good question! And the answer is: We need to define them first. At the top of the ActionScript sheet I added some variable definitions: First, we have to define the surface normal vector for each of our walls that determine the boundaries of our scene. I used the short version for creating an array object that contains the x- and y-component for the direction of each surface normal vector ([x, y]). Next I defined the starting vector for the motion direction of the ball, that means this vector (direction) represents the motion direction of the ball when the application is started. You can use different values for the elements of that vector, if you like. And finally, I defined the variable increment, a single value that represents the speed of the ball. This value determines the step size between two frames, if you want. The actual motion vector of the ball will be the product of the direction vector and this speed value. All vectors and values that I defined in this code block are declared as global variables (with the prefix _global.), that means that all of these variables will be available throughout the entire application.

 


_global.rightBarDirection = [-1,0];
_global.downBarDirection = [0,-1];
_global.leftBarDirection = [1,0];
_global.topBarDirection = [0,1];
_global.direction = [1,1];
_global.increment = 10;

 

Adding sound

Finally, I added another function to my application, a function that produces a tic sound that will be called each time the ball hits a wall. The first thing to do here is to import the audio file that contains that sound. You can simply drag it to the library sheet of the Flash editor. After this file appeared in the library one has to click that symbol with the right mouse button and select the option “Linkage”. Here, we can give that audio file an Identifier, a name that we will use to call that file later on. I gave it the name BallHitsBar and the implementation of that audio in our application will be done in the following code block:

 


var ballHitsBar: Sound = new Sound();
ballHitsBar.attachSound("BallHitsBar");

function hitSound():Void
{	
	ballHitsBar.start();
}

 

First, we have to build an instance of a Sound object that I called ballHitsBar. In the next step we have to link the audio file to this Sound object: We must call the instance name together with the method attachSound and then pass the identifier of the file as the argument. After this is done, we will write another function (hitSound) that will start the sound and will be called each time the ball hits the wall.

 

Link the functions to the objects

That was the groundwork for our application. The last thing to do is to connect our functions with our objects. In order to do so, we will switch to the layer Ball and click the MovieClip object Ball. In the ActionScript window for this object we will write the following code:

 


onClipEvent(enterFrame)
{
	this._x = this._x + direction[0]*increment;
	this._y = this._y + direction[1]*increment;
	
	if(this.hitTest(_level0.rightBar))
	{
		direction = _level0.vectorReflect(direction,rightBarDirection);
		_level0.hitSound();
	}
	if(this.hitTest(_level0.downBar))
	{
		direction = _level0.vectorReflect(direction,downBarDirection);
		_level0.hitSound();
	}
	
	if(this.hitTest(_level0.leftBar))
	{
		direction = _level0.vectorReflect(direction,leftBarDirection);
		_level0.hitSound();
	}
	
	if(this.hitTest(_level0.topBar))
	{
		direction = _level0.vectorReflect(direction,topBarDirection);
		_level0.hitSound();
		
	}	
}

 

In this code block we first linked the Ball object to the enterFrame event, i.e., this code will be executed each time the application enters the first frame (which will happen 120 times per second, because I set the frame rate for this application at a value of 120 fps). In the first two code lines within that block the new position of the ball will be calculated, separately for the x- and the y-coordinate of the ball and according to the motion vector of the ball (the product of the motion direction and the speed value). Finally, the collision detection function comes into play: For each of the four walls I check with an if-condition whether a collision between that wall and the ball has taken place. The method hitTest is used in the following way: First, we need to call the ball object, which is represented by this within that function, together with the method hitTest. As the argument for this method we simply have to pass the instance name of the wall object (rightBar, for instance, that has to be called with the level specifier _level0.). In case the result of this test is positive, i.e., the function call returns true, the core function vectorReflect will be called that returns the new, mirror reflected motion direction vector. This vector will replace the old direction vector, stored in the global array direction. At the same time, after a collision was detected, the function hitSound will be called and the tic sound will be played.

And that's it! If you want to reproduce this exercise with your Flash editor you may even want to extend that application. You could add further and more complex obstacles to the scene, add another ball or let the user come into action with some key or mouse events. I shall be delighted to watch your results!

 

[1] Phong B. T.(1975). Illumination for computer generated pictures. Communications of the ACM, 18, 311–317. crossref.

 

© 2011 G. Wendt



Write a comment
Name: Note: Your email address will not be displayed on this site nor otherwise published!
Email:
Comment:
Anti-Spam:
Color & Font
Color tool

You have difficulties finding a balanced color combination and appropriate font formats for your website?


Use the tool Color & Font on this website in order to interactively create the color and font properties of your own site. The results of your settings can be easily included as CSS listing in your web project.

Archive
MTWTFSS
1234567
891011121314
15161718192021
22232425262728
2930