Jump to content
  • Advertisement
Sign in to follow this  
PATrainwreck

Collision detection

This topic is 3773 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 don't know much about collision detection which is why I'm posting this (obviously). I'm hoping someone can point me in the right direction. I want to learn how to implement good 2d collision detection. Something where I could have a collection of objects and get events when there is a collision between two of those objects. I'm using c++ and I would say I'm decent at programming with it (beginner to intermediate skill level). I've taken some classes at college including a data structures class. Hopefully someone could give me a link to some good tutorials or even a link to some theory and I could try to implement it myself (I'd actually prefer to implement it myself because that would be good practice). Also any info on how to react to collisions would be a plus. :) Thanks in advance for any help.

Share this post


Link to post
Share on other sites
Advertisement
There are a few kinds of collisions. I don't know the technical names, but...
Collision among rectangles.
Collision among irregular polygons (harder).
Collision among circles (easiest).
Collision combining two or three of the above.
And collision I forgot.

What are you interested in? I could describe all three and end up wasting my time because you only need one.

Share this post


Link to post
Share on other sites
I already know about those kinds of collision. I'm looking for how to implement it on a larger scale, collisions between many objects. The only thing I can think of doing is having a giant for loop and check each object against every other object but there has to be a better way.

Share this post


Link to post
Share on other sites
Ultimately your loop can't avoid starting with 'test every object against every other' but there are ways of structuring your data so that many of the tests can be avoided. General object-object collision tests can be expensive, so you should seek easier (quicker) ways of eliminating collisions that can't possibly occur.

As a simple example, imagine your game 'level' is a 2D world containing lots of potentially interacting geometrically complex but small objects. You could test collisions pairwise between every combination of two objects, but due to the indivisually complex nature of the objects each test may be expensive. You could simplify matters by partitioning the level into regions somehow. Then you know that objects in regions that are far away from each other can't possibly collide within your per-frame timestep. Computing this simpler region-region test is much quicker than testing per-object, so you have optimised away much of the collision detection overhead.

The trick is to find the best way to arrange the data of your game world in order to avoid the most computationally expensive collision tests in favour of the broad-brush simpler tests. As mentioned, there are various well-documented spatial partitioning structures you could google.

I would say however that if you're writing a relatively simple game (Space Invaders, Asteroids etc) you probably won't need to do anything particularly sophisticated to organise your collision tests, as the number of active potential colliding objects will be quite small at any time.

Share this post


Link to post
Share on other sites
I was wondering about this too. So, in a general, quick, probably inaccurate statement, you test the players position against the position of all the objects within a certain range and/or a certain section of the game world? (just checking to see if I understand)

Share this post


Link to post
Share on other sites
I did a collision detection and response assignment in uni. Mine was in 3D but many of the same principles apply. It can get pretty complex if you want to optimize it.

Anyway, here's some things to note when you have lots of objects.

Calculate (potential) new positions of all objects.
Run your detection code on all objects against other objects.
Move objects to new positions.

The important thing to realise here is that you are not moving your objects before you perform collision detection. The reason for this is that depending on what happens, your objects will end up in different positions.

Imagine you have 3 balls heading toward each other at different velocities. In the next frame you detect that they will all overlap, however, you know that out of these 3 only 2 of them actually collide. Now you need to measure the exact point at which each of them would have collided and take the one that happens first. (this would be so much easier with a diagram :))

The response part is a whole different ball game (no pun intended :)). Should the balls bounce off each other? Should they stick together? Explosions? That will vary from game to game and object to object.

Now for the hard part. Optimizing your collision detection can be a lot of work. You need to decide how important it is based on how many objects are you going to have moving around your screen. Some ideas to consider:

- Objects that are not moving don't need to be included in the detection against each other.
- Objects that are moving need to be included against other moving and non-moving objects.
- Once you have detected that there is NOT a collision, move on.
- Objects that are far away from each other don't need to be included against each other (that's where BSP comes in)
- Use the least expensive algorithm first even on complex objects, usually distance + radius (circles and spheres)

Get the basics working first, you might find it's good enough if you've only got a few moving objects.

Good luck. It's definitely good practice doing your own collision detection. You'll learn a lot.

Share this post


Link to post
Share on other sites
Yeah, basically. It's a question of how many tests you're going to end up doing. If you're writing Pong I wouldn't worry about it, but once you end up with lots of object-object pairs to test you're going to have to come up with a way of quickly discounting collisions that can't possibly happen, and only devote your full-on collision code to those pairs that might actually collide. Think of it as a hierarchy of tests, for example: are the two objects near each other at all? Then, are they within each others' bounding volumes? Then, do they actually collide? Your tests for each step will end up being progressively more computationally expensive, but the number of tests required will diminish rapidly at each step, so you end up making a big saving compared with testing each and every pair.

Share this post


Link to post
Share on other sites
Quote:
Use the least expensive algorithm first even on complex objects, usually distance + radius (circles and spheres)


That's another very good point: don't bother implementing anything vastly clever if the player won't notice. Bounding box/sphere tests are probably sufficient for basic shoot-em-ups. If your baddie is basically rectangular then just test against a rectangle unless there's a good reason to be more detailed. Think about what you can get away with!

Share this post


Link to post
Share on other sites
Thanks everyone. octree and BSP are pretty much what I was looking for.

I'll come back here if I have any more questions on collision detection (or anything else).

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!