Jump to content
  • Advertisement
Sign in to follow this  
Derakon

Detailed and fast 2D collision detection

This topic is 4666 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a scripted sprite-based 2D engine in C++, and I've gotten to the point where I really need to start improving the performance. Currently I can't handle more than about 40-50 sprites onscreen before performance takes a nosedive (on a 1.43GHz Mac Mini with 512MB RAM; I want this game to be runnable on less). I discovered that one of the major performance hits I'm taking is with my collision detection; I'm using bounding polygons instead of bounding boxes because I want to be able to do detailed collision reactions (e.g. labelling one side of a sprite as damaging and another side as not, or obtaining the surface normal of a sprite for bouncing). Of course I perform a bounding box check as well before going into the bounding polygon check, and I'm using a quadtree to cull out my list of sprites. If I just ditch the bounding-polygon collision, then I roughly triple the maximum onscreen sprites before slowdown occurs. But I don't want to do that. Does anyone have any recommendations or guides for faster collision detection algorithms that aren't as ham-handed as bounding boxes?

Share this post


Link to post
Share on other sites
Advertisement
How often do your sprites touch each other,
if too much you could try programming AI so sprites give each other some personal space, for example if you use any sort of weighted AI make it so even though than can keep going until they hit the other sprites bounding polygon they prefer to stay out of the bounding box and thereby reducing the number of time you need to run the algorithm

EDIT:
if its mainly for hit detection of bullet like projectiles you could also make sprites cheat and when hitting the player decide where exactly they hit through a random number insted of full bounding polygon hit detection
im not exactly sure how your game works but the bounding polygon test shouldnt need to be used very offten if you program it right

Share this post


Link to post
Share on other sites
An interesting approach, but not one that ultimately will be much use for me. The engine I'm working on is as fully general as I can make it, which means that I can't anticipate what sorts of games will be made with it (heck, I hacked together a slideshow with it once). I am working on adding a "class" field so I can have an option such that sprites of the same class don't collide (e.g. if you're making a space shmup, chances are you don't care if two enemy sprites are touching each other). However, that's a workaround at best.

I should have specified earlier - the current bounding polygon algorithms I'm using are entirely self-developed without any reference to external materials (except for a lot of paper and pencil to work out the use cases and simple algebra). In other words, it's not what you would call optimized. So if you know of a guide to fast bounding polygon collision detection, that'd be helpful too.

Share this post


Link to post
Share on other sites
Can you tell us a little about your algorithm and what sort of intersection information it returns? Also, are these polygons always convex? (I'm guessing they are since you describe them as 'bounding polygons'.) In any case, I'm guessing that switching to another algorithm (such as a carefully optimized SAT implementation) would solve your problem.

Share this post


Link to post
Share on other sites
I don’t know much about bounding polygon algorithms but most fps I have seen have several bounding boxes that are connected to the skeleton of the model, also not sure how that’s handled and if its generated automatically or not. But you should be able to have fairly good collision/hit detection on most models with a dozen or so simple geometric shapes like boxes, cylinders and spheres but you may need to make the user of you engine manually define them though I think some programs that can do that already exist (milkshape?)

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Can you tell us a little about your algorithm and what sort of intersection information it returns? Also, are these polygons always convex? (I'm guessing they are since you describe them as 'bounding polygons'.) In any case, I'm guessing that switching to another algorithm (such as a carefully optimized SAT implementation) would solve your problem.
Sure, more information makes it easier to get help. :) The algorithm actually doesn't require convex polygons right now. It basically just takes two polygons - one with velocity vector v and one at rest. The endpoints of the moving polygon's lines are projected backwards along v to generate two more lines. Each line is then tested for intersection with the at-rest polygon. If an intersection exists, then the component c of v that must be subtracted from the line's position to get it to not intersect is calculated. After all is said and done, the line with the largest c is the one that had the first collision; the surface normal of the line it collided with, c, and the line's "color" are returned (the color of a line classifies its in-game effects, e.g. on fire, safe to walk on, poisonous, powerup, and so on).

Edit: the direction of the surface normal is determined by the velocity vector - surface normals always "oppose" the velocity of the line.

I'll need to research SAT; I'm not familiar with how it works. It could well be that my best bet is to decompose the polygons I start with into convex polygons and do faster piecewise detections instead of one big test.

And Kaze - this is a 2D engine, not 3D. For 2D, the only really fast collisions are bounding box to bounding box, with bounding sphere as a reasonably close second. Neither are sufficient to my needs.

Share this post


Link to post
Share on other sites
Quote:
Original post by Derakon
The algorithm actually doesn't require convex polygons right now. It basically just takes two polygons - one with velocity vector v and one at rest. The endpoints of the moving polygon's lines are projected backwards along v to generate two more lines. Each line is then tested for intersection with the at-rest polygon. If an intersection exists, then the component c of v that must be subtracted from the line's position to get it to not intersect is calculated. After all is said and done, the line with the largest c is the one that had the first collision; the surface normal of the line it collided with, c, and the line's "color" are returned (the color of a line classifies its in-game effects, e.g. on fire, safe to walk on, poisonous, powerup, and so on).
I see (although I'm not sure why you say the line endpoints of the moving polygon are projected backwards along v - wouldn't you want to project them forwards, in the direction of motion?). It seems though that this method could miss collisions. Imagine an axis-aligned box heading straight towards a considerably smaller axis-aligned box; it could be that the boxes do collide during the timestep, but none of the vertices of the first box ever intersect the smaller box. Perhaps I'm misunderstanding your method though.

In any case, the SAT is a good solution and can be made to be quite efficient, but in general it is resricted to convex objects. You could decompose your objects into convex sub-objects, or you could just treat the objects as collections of line segments and perform the SAT test between these segments. This is just an idea - I've never actually tried this approach, so I can't say from experience how well it would work.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by Derakon
The algorithm actually doesn't require convex polygons right now. It basically just takes two polygons - one with velocity vector v and one at rest. The endpoints of the moving polygon's lines are projected backwards along v to generate two more lines. Each line is then tested for intersection with the at-rest polygon. If an intersection exists, then the component c of v that must be subtracted from the line's position to get it to not intersect is calculated. After all is said and done, the line with the largest c is the one that had the first collision; the surface normal of the line it collided with, c, and the line's "color" are returned (the color of a line classifies its in-game effects, e.g. on fire, safe to walk on, poisonous, powerup, and so on).
I see (although I'm not sure why you say the line endpoints of the moving polygon are projected backwards along v - wouldn't you want to project them forwards, in the direction of motion?). It seems though that this method could miss collisions. Imagine an axis-aligned box heading straight towards a considerably smaller axis-aligned box; it could be that the boxes do collide during the timestep, but none of the vertices of the first box ever intersect the smaller box. Perhaps I'm misunderstanding your method though.
Whether you project forwards or backwards makes little difference; it's just a matter of when you do the collision detection - before or after you try to move the polygon? If before, then you project forwards; if after, then you project backwards.

As far as your example, you're correct that the large box wouldn't collide with the small box. However, the small box would collide with the large box; when I have to collide an object at rest with a moving object, I change my frame of reference so that the first object is moving and the second is at rest. This is a bit hackish but it covers the case you pointed out, and others besides.

I'll look into SAT and see how hard it would be to decompose a potentially concave polygon into a set of convex polygons. Thanks for the recommendation.

Share this post


Link to post
Share on other sites
Quote:
Original post by DerakonAs far as your example, you're correct that the large box wouldn't collide with the small box. However, the small box would collide with the large box;
...
I think that's part of your problem. Consider 5 objects in a node,
4+3+2+1 = 10 tests when a specific object-object test is done only once;
5*4 = 20 tests when a specific object-object test is done from each perspective.

Once an object is tested against another, they generally should not be tested against each other again(unless there is some cost in figuring out if two objects have been tested).

Quote:
...I'll look into SAT

What's SAT?

Share this post


Link to post
Share on other sites
Quote:
Original post by RolandofGilead
Quote:
Original post by DerakonAs far as your example, you're correct that the large box wouldn't collide with the small box. However, the small box would collide with the large box;
...
I think that's part of your problem. Consider 5 objects in a node,
4+3+2+1 = 10 tests when a specific object-object test is done only once;
5*4 = 20 tests when a specific object-object test is done from each perspective.

Once an object is tested against another, they generally should not be tested against each other again(unless there is some cost in figuring out if two objects have been tested).

Quote:
...I'll look into SAT

What's SAT?


Separating Axis Theorem

and Swept SAT, with added test for moving polygons.


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!