Is it possible to have concurrent collision detection where every entity acts at exactly the same time?

Question

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?

Answer 1

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.

Answer 2

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!