by
kirupa | 12 August 2005Collision detection is an important feature in various
applications ranging from games to particle modeling. The basic idea
behind collision detection is to determine when objects collide and
to react appropriately. There are
already several tutorials on this site that address various portions
of collision detection, and this tutorial extends the earlier
tutorials with information on how to detect collisions among
multiple objects.
|
Note |
While the tutorial is intended for Macromedia
Flash, the first half of the tutorial discusses general topics
that can be applied to any language. |
|
In prior tutorials, you had a good idea about which objects would
collide with each other. The Flash code was often tailored to simply
detecting when those particular objects would collide, and that was
great for most cases. What about situations where you have
multiple objects to check for collisions against? The answer to that
requires a new tutorial - this one!
The following animation is an example of the
collision detection code in action:
[ check out the
collision detection ]
Notice that when a pair of circles in the above animation
collide, they change directions. I have no prior knowledge of which
pair of circles would collide or when/where they would collide. That
uncertainty better resembles a situation you would face in real
life, and our code should take into account such vagueness.
Less Efficient Method
Normally, I would first provide the directions for recreating the
above animation in Flash. I am going to take the road less traveled
and start by explaining how to approach this problem. I am certain
you would encounter similar situations in your future Flashing
endeavors.
Let's say our environment is represented by the
following graphic with 5 circles that each have the ability to move
around:
Our goal is to detect when any of the circles
collide with each other. In order to detect a collision, we could check Circle 1, Circle
2, Circle 3, Circle 4, Circle 5, and Circle 6 with each other to
check for a collision. In order to do so many repetitive tasks, you
would use a loop. I will use a for loop, because it provides
me with greater control over the starting and end conditions of the
loop.
Our code for checking each circle with each other can be written as:
- totalObjects
=
target_mc.length;
- for (i=0;
i<totalObjects;
i++)
{
- circleA
=
target_mc[i];
- for (j=0;
j<totalObjects;
j++)
{
- circleB
=
target_mc[j];
- circleA
=
eval(circleA);
- circleB
=
eval(circleB);
- if
(circleA.hitTest(circleB))
{
- // your code here
- }
- }
- }
For the purposes of this tutorial, the names of our circle movie
clips are stored in an array called target_mc. Notice that I am using two
for loops
in the above code. Remember that in order to check for one
collision, you need two objects. Since each object is stored as an
array, by using two for loops, I am able to quickly scan
through each circle and check for a collision against all other
circles on the
stage.
Adding a simple trace statement to check for which circles
are accessed during just ONE run of our collision detection function
produces 36 lines. I have provided a copy of the trace command, and
I also went ahead and highlighted those tests that I feel are
unnecessary:
circle0 and circle0 are
checked for collisions.
circle0 and circle1 are checked for collisions.
circle0 and circle2 are checked for collisions.
circle0 and circle3 are checked for collisions.
circle0 and circle4 are checked for collisions.
circle0 and circle5 are checked for collisions.
circle1 and circle0 are
checked for collisions.
circle1 and
circle1 are checked for collisions.
circle1 and circle2 are checked for collisions.
circle1 and circle3 are checked for collisions.
circle1 and circle4 are checked for collisions.
circle1 and circle5 are checked for collisions.
circle2 and circle0 are
checked for collisions.
circle2 and circle1 are checked for collisions.
circle2 and circle2 are
checked for collisions.
circle2 and circle3 are checked for collisions.
circle2 and circle4 are checked for collisions.
circle2 and circle5 are checked for collisions.
circle3 and circle0 are
checked for collisions.
circle3 and circle1 are checked for collisions.
circle3 and circle2 are checked for collisions.
circle3 and
circle3 are checked for collisions.
circle3 and circle4 are checked for collisions.
circle3 and circle5 are checked for collisions.
circle4 and circle0 are
checked for collisions.
circle4 and circle1 are checked for collisions.
circle4 and circle2 are checked for collisions.
circle4 and circle3 are checked for collisions.
circle4 and
circle4 are checked for collisions.
circle4 and circle5 are checked for collisions.
circle5 and circle0 are
checked for collisions.
circle5 and circle1 are checked for collisions.
circle5 and circle2 are checked for collisions.
circle5 and circle3 are checked for collisions.
circle5 and circle4 are checked for collisions.
circle5 and
circle5 are checked for collisions.
The items highlighted in Blue are unnecessary because you are
checking if an object is colliding with itself. The items in Yellow
are also unnecessary. For every yellow colored line, you will see its equivalent
collision check a few lines earlier. In fact, a check between
circles 4 and 0 is the same as a check between circles 0 and 4. The
ordering of the circles being checked isn't important in our
case.
Remember, your collision detection function will itself be called
numerous times in a second. Your for loop doesn't need to
re-run itself automatically. In other words, it is in our best
interests to keep the list of circles checked for a collision in our
for loop as short and complete at the same time as possible.
Also, beyond being repetitive, another issue with
the above code lies in the complexity. Since each
object checks for a collision with every other object, you are
basically exponentially (n^2) increasing the number of checks
required to
test for a collision for each object you add.
|
page 1 of 3 |
|
|