# How to avoid collision detection to enter infinite loop in this case?

I am writing a collision detection system which uses the logic mentioned by Trevor here

But I have anticipated a problem which I have shown as a diagram

How do we handle this problem?

Solution: You only detect and react to a collision on an object once per frame. This would move the second collision detection in step 3 to the next frame so that it will not enter an infinite loop and freeze.

Problems with the solution: If the two objects are not springs, but are instead solid objects you will see an age-old problem where it will look like the object shoots out at very high velocities from where it was. This may or may not be an issue either by the design of the game in question or simply because it would not matter if it does happen. Two common solutions when this happen, both of which require detection of the situation, is to remove the object either outright, or apply damage to it or the like or to alternately scan for the nearest 'open' area and move the object to that location.

Hope this helps

• Yes. I would be moving the object back to the point to contact. But just thought of this. Another thing, if I don't recheck for collision the object would draw itself over Spring1. Is this what should happen? Is there no better way? Jun 2, 2011 at 22:17
• Should happen. Its very easy to see this as a 'Woah I dont want that' when you look at it on a frame by frame basis.. But keep in mind that the average human reaction speed is 0.2s, and 60FPS is 0.01666s, and even 30FPS is 0.0333333s.. The next frame is going to happen in such Quick succession that it will not be an issue game play wise. Also, the eye is such a slow visualization tool (This is a good thing mind you, its what allows us to see motion :)) that a single frame of an object not reacting to a second collision will not be very apparent (if at all), let alone an issue. Jun 2, 2011 at 23:09

As James says, in many types of games, this sort of issue doesn't really matter much. But in others; particularly in games with fast-moving objects, it's critically important to get this right to handle complicated bounces in corners. So probably the smart thing to do is to ignore the problem unless it's actively causing problems for you. If it's causing problems, then here's how you handle it:

When your collision system is checking for collisions, instead of simply resolving collisions as you find them, you instead make a big list of all the collisions you find during the frame, and sort them according to the time-within-the-frame at which the collisions occurred. (your collision system will need to know about object velocities in order to calculate the time within the frame at which the collision occurred)

Once you have this sorted list, you resolve those collisions in order, from first to last. When performing the collision resolution, you need to use the "remaining frame time" as a parameter to the collision resolution function.

So here's a step-by-step version of this process, in the case of the situation shown in your diagram:

1. Find the collision between Obj and Spring2, which happened at (let's say) 3 milliseconds out of our 16 millisecond frame duration. No other collisions found.
2. No other collisions, so resolve that first collision, which results in Obj moving left from the collision point, with 13 milliseconds left of frame time remaining.
3. Since an object moved, we now need to check for collisions for the remaining 13 milliseconds of frame time. We find that now, Obj is colliding with Spring1, which happened at (let's say) 8 milliseconds out of our 16 millisecond frame duration.
4. No other collisions, so resolve the one collision we have, which results in Obj moving back to the right from the collision point, with 10 milliseconds of frame time remaining.
5. Repeat

Note that if implemented correctly, Obj should be moving a smaller and smaller distance with each bounce, because the collision resolution is covering a shorter period of time within the frame at each iteration, and so eventually, Obj will be bouncing a small enough distance to no longer collide with the opposite spring within the frame duration.

Also note that it's still possible to get into an infinite loop if Spring1 and Spring2 are immobile objects and are placed so closely together that Obj doesn't actually fit between them, so it's important to have some maximum number of times that your collision system will iterate per frame. The faster your objects can move, the more iterations you need to support, to handle common "complicated bounce" situations. But in general, four or five iterations is a reasonable maximum for most games.

The reason that this situation happens is because you didn't take away any kinetic energy from the object, which is unrealistic- you even added it and made it go further. When an object impacts a spring, it doesn't rebound further or even as far as it came from- it rebounds less. By simply returning the object with less velocity/force/energy than it came in with, you should be able to ensure that this case never happens.

• I believe the question is asking how to stop the game from freezing via an infinite loop in collision detection vs why the object itself would always be in an infinite loop between the two springs. Jun 2, 2011 at 23:55

If I were to solve this problem, I'd take these two steps.

Step1: Infinite collision detection: This scenario occurs when the Object repeats its collision with the same set of springs for unreasonable amount of time. So for every collision with a spring, I would check whether the last X no. of collisions(say 50 times), has occurred between the same set of springs. I'd just check between the current 2 collided springs with the last 2 collided springs and maintain a counter and when the counter reaches X, I'd call it as infinite loop.

Step2: Preventing the infinite loop: Once we identify the infinite loop, we can handle it however we want. Eg. Restarting the game or Stop the object from moving further or bringing the object to the starting position.

I'm new to game development. Feel free to correct me.