Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

There are many algorithms that can be used for collision detection. In many cases we check for an overlap in coordinates of an entity.

If we make a triangle a,b and c. We have 2 entities at a and b heading for a collision at c but each of them are moving at exactly the same time, what kind of algorithm could work?

It seems more like a chess game where you would have to predict every move that the other entity would have to make, if they swerve to the left to avoid a collision will they also run the chance to collide. Is it possible or is it too complex? Would it work for thousands and millions of entities in the same search space?

share|improve this question
    
I'm confused. Are you trying to predict a collision before it happens so that you can avoid it? –  John McDonald Aug 26 '11 at 21:41
    
Yes, I'm wondering if I can use OpenCL to simulate thousands of entities moving in random directions with a worker per entity without creating some kind of deadlock. The problem is more convoluted as the entities are organic, in that they can move in any direction not in a straight line that ray collision detection could solve. –  Sycren Aug 26 '11 at 21:46
add comment

2 Answers

In your second paragraph, you bring up the issue of simultaneous movement. This is how objects move in the real world (obviously), and if you're interested in physical accuracy you would need to solve your collisions by taking this into account. However, this can very quickly become expensive, so most games perform collision detection by moving objects sequentially (move A then B or B then A, then check for collision). The unrealistic nature of sequential detection tends to be a non-issue and greatly simplifies the computation.

In the third paragraph, you bring up the types of movement the objects might perform on their way to location C. Since the movement step for most games is fairly small, simplifications and restrictions on an object's movement are often employed so that calculations become much easier. An example would be the stipulation that during a single time step, objects are only allowed to move with a constant velocity and cannot rotate.

So, overall, I'd say that the answer to your question is that simultaneous, complex motions of objects can probably be simulated by a computer depending upon exactly what they're doing, but it is unlikely that such computations are feasible or necessary to perform in a real-time application. Using a simplified movement model with a sequential movement of objects greatly simplifies the calculations and still looks correct under most circumstances.

share|improve this answer
    
Physical collisions never happen simultaneously anyway, so not taking such into account is the correct way to go about things. –  Martin Sojka Aug 27 '11 at 15:06
    
Not sure if we're on the same page about what "sequential" means in the context of a computer application, but iterating through a list of objects and updating their positions one after the other, then checking for collisions, is not a physically correct model. –  user_123abc Aug 27 '11 at 22:27
    
You don't update the positions one after another, you check for collisions one after another, and re-calculate the positions, then change them all at the same time. There never will be a collision which happens at exactly the same time as another one (not in reality, anyway; in computer programs, you have to watch out for precision problems), so it's OK to calculate their effects one after another too. –  Martin Sojka Aug 27 '11 at 23:54
add comment

The more pertinent question is, does anything in the real world happen simultaneuously? That all depends on what division of time you go down to; seconds, milliseconds, nanoseconds, picoseconds and so on. Eventually you will reach a point where things aren't happening simultaneously, because the degree to which you can subdivide time is infinite. This would also also be the case with any theoretical computer system, even one designed for that purpose, due to the fact that no matter how high a timing resolution you specify as a parameter for your hardware design, there is always a higher resolution.

Modern collision detection systems work, both inside and outside of the field of games, because it doesn't matter, so long as the collisions happen at what is perceptually the same time. The human brain has it's limits to what it can perceive as continuous. Generally frame rates in games don't need to exceed about 60fps for this reason -- same as a flourescent lights running at 50-60Hz AC. And 60Hz is, from what I understand, well above the limits of our rate-of-perception, in order to appear continuous even in worst-case scenarios.

EDIT: This post describes the practical realities, however see Martin Sojka's comment re the theory of time divisibility, below. Thanks Martin!

share|improve this answer
    
You can't actually subdivide time infinitely (see: Planck Time), but at lower scales, it doesn't matter anyway: Relativistic effects make sure there is no "simultaneousness". –  Martin Sojka Aug 29 '11 at 9:29
    
Ah, thank you for that insight and interesting link, @Martin Sojka. –  Nick Wiggill Aug 29 '11 at 9:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.