|
Author
|
||||
|
Related articles
|
||||
|
More in Development
|
||||
This article originally appeared in Dev.Mag Issue 28, released in January 2009
Almost every video game needs to respond to objects touching each other in some sense, a practice commonly known as collision detection. Whether it's simply to prevent the player character from walking through the walls of your maze with a simple collision grid array, or if it's to test if any of the hundreds of projectiles fired by a boss character in a top-down shoot-'em-up have struck the player's ship, your game will likely require a collision detection system of one sort or another.
So there comes a time in almost every game's development cycle when an important choice needs to be made: how accurate should the collision detection be, and which method should be used to achieve that accuracy. This is a decision that is not made lightly, since it can drastically affect both gameplay and performance of your game.
Unfortunately, there's often no avoiding the mathematics behind collision detection. However, anyone with so much as a secondary-school maths education will be able to follow the collision detection explanations in this article.
A sprite with visible circular collision bounds
Bounding sphere/circle test
The simplest of all methods for detecting intersections between objects is a simple bounding sphere test. Essentially, this represents objects in the world as circles or spheres, and test whether they touch, intersect or completely contain each other. This method is ideal when accuracy is not paramount, for objects roughly circular in shape, or in instances where these objects do a lot of rotations.
Each object will have a bounding circle defined by a centre point and a radius. To test for collision with another bounding circle, all that needs to be done is compare the distance between the two centre points with the sum of the two radii:
- If the distance exceeds the sum, the circles are too far apart to intersect.
- If the distance is equal to the sum, the circles are touching.
- If the distance is less than the sum of the radii, the circles intersect.
CircleCircleCollision Input Center1 x/y pair of floating points Centre of first circle R1 Floating point Radius of first circle Center2 x/y pair of floating points Centre of second circle R2 Floating point Radius of second circle Output True if circles collide Method // Calculate difference between centres distX = Center1.X – Center2.X distY = Center1.Y – Center2.Y // Get distance with Pythagoras dist = sqrt((distX * distX) + (distY * distY)) return dist <= (R1 + R2)
The above method can be optimized somewhat by comparing the square distance with the square of the sum of the radii instead, saving a comparatively slow square root operation, as shown below.
// Get distance with Pythagoras squaredist = (distX * distX) + (distY * distY) return squaredist <= (R1 + R2) * (R1 + R2)
|
Words from the readers
|
||||
|
ffs ur a homo
Posted by Sam at 07:51:06 on 11 May 2010
arrrrrrrrrrhhhhhhhh!
Posted by Sam at 07:50:53 on 11 May 2010
lets start over. My names sam and I'm a pirate.
Posted by Sam at 07:50:38 on 11 May 2010
fuck you
Posted by Sam at 07:49:29 on 11 May 2010
ur gay
Posted by Sam at 07:49:21 on 11 May 2010
by John Amato - Pixelsplash Software
Collision detection in 2D graphics is fairly straight-forward. You are normally trying to see whether two rectangular areas are in any way touching or overlapping each other. The rectangles to test for overlapping are the vertical and horizontal extents of the two bitmap images you want to perform collision detection on. A simple implementation of this method, using our existing sprite engine, is as follows: // Object-to-object bounding-box collision detector: short int Sprite_Collide(sprite_ptr object1, sprite_ptr object2) { int left1, left2; int right1, right2; int top1, top2; int bottom1, bottom2; left1 = object1->x; left2 = object2->x; right1 = object1->x + object1->width; right2 = object2->x + object2->width; top1 = object1->y; top2 = object2->y; bottom1 = object1->y + object1->height; bottom2 = object2->y + object2->height; if (bottom1 < top2) return(0); if (top1 > bottom2) return(0); if (right1 < left2) return(0); if (left1 > right2) return(0); return(1); }; Going this route usually works fairly well, but it has a major flaw in that for most normal images, it will tend to "overdetect" collision. The problem here is obvious, and Figure 1 shows a classic example. Figure 1 shows two perfect circles - balls let's say - which we want to detect collision on. Because of the roundish shape of the images, the corners of each bitmap contain empty space. But the bounding rectangles of each image are clearly intersecting, so a traditional collision detecting algorithm (like the one listed above) would flag this as a hit. Figure 1: ____________ | ** | | ******** | |**********| |**********| | ********_|________ | ** | | ** | -----------******** | |**********| |**********| | ******** | | ** | ------------ This annoys gamers a great deal, and so some game designers decide to define a somewhat smaller rectangle than the full extents of the image, and use this smaller rectangle for the collision detection. A good figure to use is 80 percent of the full bounding box of the image. First, we add four new fields to the sprite data type, called col_width, col_height, col_x_offset, and col_y_offset. During initialization, wherever we are defining our sprite widths and heights, we will also calculate the col_widths and col_heights to be 20% smaller. Then we will define the offset fields to describe where to set the bounding box relative to the object's coordinates. This will look something like this: object->width = <ACTUAL BITMAP WIDTH>; object->height = <ACTUAL BITMAP HEIGHT>; object->col_width = object->width * 0.80; object->col_height = object->height * 0.80; object->col_x_offset = (object->width - object->col_width) / 2; object->col_y_offset = (object->height - object->col_height) / 2; Then, we can rewrite the above Sprite_Collide() to the following: // Object-to-object, reduced bounding-box collision detector: short int Sprite_Collide(sprite_ptr object1, sprite_ptr object2) { int left1, left2; int right1, right2; int top1, top2; int bottom1, bottom2; left1 = object1->x + object1->col_x_offset; left2 = object2->x + object2->col_x_offset; right1 = left1 + object1->col_width; right2 = left2 + object2->col_width; top1 = object1->y + object1->col_y_offset; top2 = object2->y + object1->col_y_offset; bottom1 = top1 + object1->col_height; bottom2 = top2 + object2->col_height; if (bottom1 < top2) return(0); if (top1 > bottom2) return(0); if (right1 < left2) return(0); if (left1 > right2) return(0); return(1); }; Posted by Sam at 07:49:13 on 11 May 2010
by John Amato - Pixelsplash Software
Collision detection in 2D graphics is fairly straight-forward. You are normally trying to see whether two rectangular areas are in any way touching or overlapping each other. The rectangles to test for overlapping are the vertical and horizontal extents of the two bitmap images you want to perform collision detection on. A simple implementation of this method, using our existing sprite engine, is as follows: // Object-to-object bounding-box collision detector: short int Sprite_Collide(sprite_ptr object1, sprite_ptr object2) { int left1, left2; int right1, right2; int top1, top2; int bottom1, bottom2; left1 = object1->x; left2 = object2->x; right1 = object1->x + object1->width; right2 = object2->x + object2->width; top1 = object1->y; top2 = object2->y; bottom1 = object1->y + object1->height; bottom2 = object2->y + object2->height; if (bottom1 < top2) return(0); if (top1 > bottom2) return(0); if (right1 < left2) return(0); if (left1 > right2) return(0); return(1); }; Going this route usually works fairly well, but it has a major flaw in that for most normal images, it will tend to "overdetect" collision. The problem here is obvious, and Figure 1 shows a classic example. Figure 1 shows two perfect circles - balls let's say - which we want to detect collision on. Because of the roundish shape of the images, the corners of each bitmap contain empty space. But the bounding rectangles of each image are clearly intersecting, so a traditional collision detecting algorithm (like the one listed above) would flag this as a hit. Figure 1: ____________ | ** | | ******** | |**********| |**********| | ********_|________ | ** | | ** | -----------******** | |**********| |**********| | ******** | | ** | ------------ This annoys gamers a great deal, and so some game designers decide to define a somewhat smaller rectangle than the full extents of the image, and use this smaller rectangle for the collision detection. A good figure to use is 80 percent of the full bounding box of the image. First, we add four new fields to the sprite data type, called col_width, col_height, col_x_offset, and col_y_offset. During initialization, wherever we are defining our sprite widths and heights, we will also calculate the col_widths and col_heights to be 20% smaller. Then we will define the offset fields to describe where to set the bounding box relative to the object's coordinates. This will look something like this: object->width = <ACTUAL BITMAP WIDTH>; object->height = <ACTUAL BITMAP HEIGHT>; object->col_width = object->width * 0.80; object->col_height = object->height * 0.80; object->col_x_offset = (object->width - object->col_width) / 2; object->col_y_offset = (object->height - object->col_height) / 2; Then, we can rewrite the above Sprite_Collide() to the following: // Object-to-object, reduced bounding-box collision detector: short int Sprite_Collide(sprite_ptr object1, sprite_ptr object2) { int left1, left2; int right1, right2; int top1, top2; int bottom1, bottom2; left1 = object1->x + object1->col_x_offset; left2 = object2->x + object2->col_x_offset; right1 = left1 + object1->col_width; right2 = left2 + object2->col_width; top1 = object1->y + object1->col_y_offset; top2 = object2->y + object1->col_y_offset; bottom1 = top1 + object1->col_height; bottom2 = top2 + object2->col_height; if (bottom1 < top2) return(0); if (top1 > bottom2) return(0); if (right1 < left2) return(0); if (left1 > right2) return(0); return(1); }; Posted by Sam at 07:49:06 on 11 May 2010
dude, your such a rager. just go quit life while your at it
Posted by Sam at 07:47:48 on 11 May 2010
fuck this, I'm going
Posted by Sam at 07:47:29 on 11 May 2010
yeh
Posted by Sam at 07:47:16 on 11 May 2010
nah
Posted by Sam at 07:47:11 on 11 May 2010
nah, u are
Posted by Sam at 07:47:04 on 11 May 2010
ur a lil bitch
Posted by Sam at 07:46:57 on 11 May 2010
lol
Posted by Sam at 07:46:49 on 11 May 2010
Might be, I'll have to ask my mum. brb
Posted by Sam at 07:45:55 on 11 May 2010
I dunno man. yoou crazy or something?
Posted by Sam at 07:45:40 on 11 May 2010
why am I talking to myself?
Posted by Sam at 07:45:20 on 11 May 2010
ur gay
Posted by Sam at 07:44:28 on 11 May 2010
lol
Posted by Sam at 07:44:22 on 11 May 2010
Dude, I'm a homo and I like stuff.
Posted by Sam at 07:44:13 on 11 May 2010
Hi, my name is James and I'm a pirate. :)
Posted by Sam at 07:42:51 on 11 May 2010
It's all pseudocode, for ease of translating between languages.
Posted by Chippit at 16:53:33 on 20 May 2009
Which language is used in this tutorial?
Posted by Mozira at 16:41:09 on 20 May 2009
Have your say:
|
||||