Torque 2D: Informal technical overview - discussion on networked collision detection.
This discussion offers a very brief overview of the problems associated with networked collision detection, and relates them to the steps we've taken so far Torque 2D to deal with these problems in the future. This information is part of a .plan file created during the development of Torque 2D.

Okay, I made a big deal out of the fact that T2D’s collision system is prepared for networked situations. But, what’s the big deal with networked collision detection anyway? If you haven’t thought about it much yet, read this quick aside and see why preparing for the inevitable move to networked simulation was so important for T2D.

Games are essentially simulations, and you model a game world with various degrees of fidelity, depending on your game design and your capabilities. In multiplayer games, the game simulation has to take place over a network, and most often over the most finicky, unreliable network of them all: the internet.

Creating a game that’s playable online means you always have to worry about latency in almost *every* aspect of your simulation. Internet-based communications are prone to high routing times, interrupted or late-arriving communications, data loss, and other fun stuff. Operating in this kind of environment makes it tough to perform any kind of simulation, let alone sims for fast-paced games where players expect to have an accurate view of the world, and to receive immediate feedback on their actions.

Of all the difficulties involved in this kind of scenario, collision detection is probably the hardest thing to handle. Collision detection is a complex, expensive process. It is highly timing-sensitive, and it’s tied to collision response / physics, another critical, expensive, sensitive game system. Moreover, it’s hard to fool people when it comes to collisions-- when collisions aren’t modeled accurately, objects don’t react the way they “should” and it just looks strange to the eye. So, creating a collision detection system that results in player perceptions of smooth dynamics in a situation where updates can be lost and are always delayed (by inconsistent, varying intervals) is quite a chore.

For example, say you have a simplistic collision detection system, where for each simulation tick, you simply check whether any objects are currently overlapping / interpenetrating. This kind of collision scheme can work sometimes. In the good old classic days of 2D gaming, this simple method of collision detection was fairly common. But how would simple schemes like this perform in a networked situation?

Well, it’d be pretty nasty. Imagine you are the collision resolver (the server, usually). Each tick, you check which objects are overlapping other objects, and when you find overlaps, you initiate some form of collision response. When you detect a collision between two objects and calculate their initial collision response, you send an update of these two objects to the clients who care about them. For clients experiencing high latency, this update may not arrive for 200ms or more, so without doing something special, the clients will see the objects collide and either watch them freeze there until the server update is received, or watch them continue to move into each other until the update is received. When the server update is received, the objects will warp to their real positions. This creates a very poor impression for the client.

Considering that client movement updates will naturally have transmission latency as well, such that actions / moves don’t actually happen on the server when the world is in the state that the client perceived, the overall effect of networked collision detection, response, and user interaction simulation can be very ugly and disconcerting to players. Without taking special precautions, players will notice objects warping frequently, and the player herself may collide against objects which she was previously unaware she was close to colliding with. The collision detection scheme used in a networked game has to be very carefully designed so that it can provide the best simulation of collision, given the lossy, laggy, unreliable nature of internet-based data communications.

There are several strategies available for dealing with these problems, however. For more information, I’d point you to the TNL doc’s fundamental networking problem-solution description. That page describes the techniques of movement interpolation, extrapolation, and client-side prediction to help alleviate the problems in perceived simulation fidelity which networked simulations are most susceptible to.

Many methods of dealing with networked simulation lay outside the realm of the collision detection system, so we won’t cover them in detail here. For the collision detection part though, sweeping an object’s collision representation across integration time steps is a powerful technique which can help improve the robustness of networked collision simulation. Sweeping involves determining the entire volume of space that an object occupied between two discrete points in time (collision detection ticks). By checking swept-objects vs swept-objects, one can simulate with a high degree of confidence whether objects collided at any time between ticks. Combined with client-side prediction, swept collision checks can provide very convincing collisions (and have the added benefit of avoiding collision tunneling).

Swept collision checks can be complicated, so it’s common that simplified collision representations (such as ellipsoids or simple bounding boxes) are used in sweeping calculations. Torque 2D, however, uses full swept-polygon vs swept-polygon collision checks in it’s narrow-phase collision detects, so that your primitive or custom collision polygons are checked exactly against each other over time, and precise collision results are returned. Yet, T2D's collision system is very fast and game worlds can easily consist of hundreds of objects.

As you should see, taking this step was important to assuring good networked collision detection behavior down the road!

For more information on networked simulation problems and solutions, check out Tim and Mark’s seminal paper, the TNL doc’s introduction to network programming, and Gamasutra’s interesting write-up on X-Wing vs TIE Fighter’s networking design.

-Josh Williams
GarageGames
Return to the T2D informal technical overview .plan