Sacred Software - Collision tutorial. This series of tutorials presents a robust method for collision detection and response.
The concepts demonstrated apply equally well to both 2D and 3D simulations, and can be generalized for a wide variety of situations. Examples are in C-like pseudocode; basic familiarity C language syntax is assumed. A working example application is provided at the end to demonstrate the collision system in action. Penetration When two solid objects occupy overlapping physical space. Intersection Test Determination of whether two solid objects are penetrating each other in their current positions. Collision Response Changes to one or more objects' positions, velocities, etc. made to resolve an intersection between them. Simulation The virtual world to which collision detection is being applied. Framestep A single logic update to the simulation state, advancing the simulation by a small amount of time.
Timeslice A finite temporal interval of the simulation. Implementation Enough preamble, let's look at some code! Simple Intersection Tests For Games. Whether it's your car crossing the finish line at 180 miles per hour, or a bullet tearing through the chest of your best friend, all games make use of collision detection for object interaction.
This article describes some simple intersection tests for the most useful shapes: spheres and boxes. Sweep Tests for Moving Objects A common approach to collision detection is to simply test for whether two objects are overlapping at the end of each frame. The problem with this method is that quickly moving objects can pass through each other without detection. To avoid this problem, their trajectories can be subdivided and the objects checked for overlap at each point; however, this gets expensive if either object experienced a large displacement. A Sphere-Plane Sweep Test Figure 1 shows an example of a quickly moving sphere passing through a plane. More efficiently, we can store the plane in the form {n, D}, where The distance d is then calculated Listing 1. #include "vector.h" class PLANE. N Tutorial A - Collision Detection and Response. SECTION 0: General Introduction --= Collision Detection in Games =-- Typically, collision detection in games is carried out into two steps: (1) determine which pairs of shapes need to be tested for collision (broad phase) (2) determine collision results for each pair identified in step (1) (narrow phase) In N, step (1) is implemented using a uniform "loose" grid of square cells; each shape is stored in the cell which contains its center, and each shape is collided against any shapes in its current cell, or the 8 cells touching the current cell.
Later tutorials will explain this system in greater detail; this tutorial will explain how step (2) was implemented in N. The algorithms we used to handle this step are of use to any game which requires fast collision detection that provides more than a simple boolean result. --= Collision Response via Projection =-- Before thinking about how to detect collisions, we should first think about what should happen to two objects which collide. comments: N Tutorial B - Broad-Phase Collision. SECTION 3: Object Grid The grid structure described above can also double as a spatial database used to manage dynamic objects.
Just as each cell contains information about the tile located in that cell, it can also contain information about each dynamic object currently located in the cell. Each cell contains a list of dynamic objects; as an object moves through the grid, we insert/remove it from each cell's list as appropriate. There are two approaches that can be taken when using a grid with dynamic objects: "normal" grid: each object is associated with all of the cells it touches. . pros: each object needs to look in at most 4 cells to find other objects it might collide with . cons: each object needs to be inserted/removed from up to 4 cells every time it moves; also, additional logic needs to be added to the collision code to deal with a case where, for instance, two objects touch the same two cells.
In our implementation, each cell has: and each object has: --= more details =--