Part II. Collision Detection Concept

This part will describe the terminologies found in Figure 1. The grayed box means it is not covered in this article. The 2D Physics Engine already discussed in part I.

Collision

Collision is defined as an event where two objects overlaps.

Collider

An object in game that can collide is called collider. There are three types of collider according to how it moves:

1. Static collider or fixed collider is a collider that cannot be moved and does not move at all thorough game no matter what happens. Static colliders are used for level geometry which always stays at the same place and never moves around. Incoming colliders will collide with the static collider but will never move static collider. For example: wall, floor, solid table. (Unity, 2016)
2. Passive collider is a collider that can be moved thorough game and can receive momentum and physics properly. They are called passive because they never induce or create any movement or force. They do not move by itself. They are usually the target of force or dynamics in physics, meaning that a character can move or push or carry the object. They can collide with other colliders including static colliders and active colliders. For example: boxes, crates, coins.
3. Active collider is a collider that can move either by AI or by programmable-fashioned way (such as from input controller or event-triggering). For example: main character, enemy characters, moving floor, gate/door.

Physical Property

Physical Property is a property that inherent to every collider so that collider can perform its function. There are many physical properties that can be added into collider but usually at minimum game should have these three properties of every collider:

Position

Position here means position or coordinate of the center of an object. It is stored in form of a vector. It can have dimension of meter or pixel or any custom unit.

Speed

Speed is the displacement made per second (or per one unit tick in game time). It is stored in form of a vector. Speed is closely related to momentum with a relation: 

Equation above means that momentum is mass of an object times its current speed. A direct change of speed in game is called impulse. The example of impulse in game is when a character at rest suddenly jumps (because player press jump key), a sudden speed change (both value and direction) occurred at that character because of impulse given programmatically in jump event code.

Acceleration

Acceleration is the change in speed per second (or per one unit tick in game time). Sometimes people confused between acceleration and force. Force is acceleration times mass of the object, in other words acceleration is force divided by mass. In some games, mass does not play any part so the game modifies acceleration directly, but mistakenly, its programmer said that he is applying force to object while actually he is directly modifying acceleration.

Gravity in game applies directly to acceleration to object (instead of force), this is because according to Newton’s law, gravity acceleration on this Earth is considered almost constant nearing the value of 9.8 m/s² for any object on surface of the Earth no matter the mass the object has. This value can only change if the object flies from Earth significantly (having different distance to the center of Earth). For simplification, mostly 2D games implement gravity by giving constant acceleration downward instead of using force.

Acceleration is better stored in a map of vectors. So for every object there is a map of vectors to store the information regarding what causes it. It is important to separate the acceleration vector of an object instead of just combining it into just one sum of vector of acceleration.

Geometry

Geometry in physics object is the collision boundary in form of a certain shape. Although there are many primitive geometry shapes such as triangle, pentagon, hexagon, etc but we only mention the most commonly used in 2D physics arcade games: rectangle and circle. Bounding rectangle and circle can comprehensively cover all the boundary of collider objects adequately. In most 2D arcade games these two boundaries can satisfy all collision geometry needs. While bounding polygon can define arbitrary shape better than these two, the complexity and mathematical calculation cost are relatively quite high compared to bounding rectangle and circle.

Line and Line Segment

Line is an infinite straight line while line segment is a line that is finite from one point to another point. Line is usually defined by equation either parametric or linear. While line is rarely used in game, line segment is used frequently to check collision. Line segment is defined by two points:  

Bounding Rectangle

Bounding Rectangle (or BoundRect) is a 2D rectangular boundary shape. In this context, square is also a rectangle. BoundRect is often used by many 2D arcade games because of its expressiveness to define boundary of many complex objects within game adequately. Rectangle can fit better for many types of objects when compared to circle or any other primitives. Figure 2 gives example of BoundRect compared to BoundCircle for several objects.

To define BoundRect in game we need several parameters. BoundRect primary parameters are center of rectangle and its dimension (width and height) along with its physical properties. Some additional parameters that can optionally be added (if game needs rotation) are: rotation degree, and pivot coordinate (center coordinate for rotation relative to center of rectangle itself).

Bounding Circle

Bounding circle (or BoundCircle) is often used for expressing collision boundary for round or circle object (such as bullet). BoundCircle is very popular among developers because of its mathematical simplicity. We can begin by examining this simplicity by knowing the fact that the only parameters that define a circle are its center position and its radius. Detecting collision between two circles is done by comparing distance between centers and reducing it with sum of radius of both circles. If this comparation results in negative then a collision occurred, if positive no collision occurred, and if zero means both circles are touching.

Bounding Polygon

Bounding polygon is used to represent a complex object in which the collision needs to be calculated accurately. Polygon can be convex or concave. Some algorithms to detect collision between polygons differentiate between convex and concave one.

Bounding Complex

Bounding complex consists of several basic bounding shapes. For example a human body character can consist of a circle (for head) and five rectangles (for body and its limbs) for more accurate collision detection than just simple bounding rectangle. These basic bounding shapes create a group that is called bounding complex. These bounding complex parts act as single bounding shape for outer collision detection while, if necessary, these parts act as different parts for self collision detection.

Bounding Motion

Bounding motion is the area of trace motion of a moving object. When an object is moving from interval delta T (from t0 to t1), it creates a trailing area to the direction of the movement. The trailing area created is called bounding motion. This bounding motion is at of great importance to collision detection algorithm. (John F. Hughes, 2013) If the intersection of the bounding motion and other object is not empty, a collision might occurred during that interval therefore a further inspection at what time it first collides must be calculated. It is used especially for fast-moving object such as bullet from gunfire. Figure 3 displays an illustration of a bounding circle moving from time t0 to t1 creating a bounding motion (illustrated in dashed red line).

Bounding motion of a circle creates a shape like 2D capsule while bounding motion of a rectangle creates a shape either a rectangle (if axis-aligned) or a 4-sided polygon (if non-axis aligned). To calculate these bounding motions (capsule and 4-sided polygon) with another bounding shape we require complex mathematic that is beyond this paper to describe.

Rigid Body

A rigid body is an idealization of a solid body in which deformation is neglected. In other words, the distance between any two given points of a rigid body remains constant in time regardless of external forces exerted on it. Even though such an object cannot physically exist due to relativity, objects can normally be assumed to be perfectly rigid if they are not moving near the speed of light. The position of a rigid body is determined by the position of its center of mass and by its attitude. In two dimensions the orientation of any object (line, vector, or plane figure) is given by a single value: the angle through which it has rotated. There is only one degree of freedom and only one fixed point about which the rotation takes place. (Lorenzo Sciavicco, 2000). Rigid body differs from soft body where soft body can deform and change its shape if external force is applied to it. Most objects in 2D arcade games are rigid body.

Soft Body

Soft body dynamics is a field of computer graphics that focuses on visually realistic physical simulations of the motion and properties of deformable objects (or soft bodies). The applications are mostly in video games and films. Unlike rigid body, the shape of soft body can change, meaning that the relative distance of two points on the object is not fixed. While the relative distances of points are not fixed, the body is expected to retain its shape to some degree (unlike a fluid). The scope of soft body dynamics is quite broad, including simulation of soft organic materials such as muscle, fat, hair and vegetation, as well as other deformable materials such as clothing and fabric. (Nealen, 2005)

This paper does not discuss soft body in detail as it is rarely used in 2D arcade video games and also very complex to implement correctly.

Self Collision

Self collision is a collision among parts of a bounding complex. Self collision examples are: character’s hair touching its own shoulder or character’s hand touching its body, or butterfly’s wings touching each other, etc. The algorithm to perform this self collision detection can be made by applying the same collision detection algorithm for each pair of parts in the bounding complex.

2D Physics Engine

2D Physics engine is the way the game deal with motion/movement of objects in 2D world. There are at least 2 types of dealing motion according to when to calculate the position of objects: fixed-step type and frame-step type.

Motion Calculation Period

There are two types in which the physics properties and position of each object in game are calculated. The first one is fixed-step and another one is frame-step. It is mutually exclusive so developers must choose only one that suit best for their need.

Fixed-step Motion Calculation Period

Fixed-step motion calculation period is period in which calculation of physics properties and object’s position is made every fixed amount of time (e.g. every 100 ms or depending on the game configuration). Every time the frame is about to render, the position of each object is interpolated between the previous and next projected position.

This type of calculation can have several advantages:

1. The physics computation and objects data can all be stored and processed in another thread/process, thus it can utilize parallelism more efficient and can be made server-client type where server stores all objects data and also calculates all physics and client requests new value of objects data (such as location) for every frame to be rendered onto screen. Interpolation calculation is performed in server. Note that server and client can be on the same computer.
2. Because it can be performed on server, any porting of game to multiplayer will also be possible and easier (because it possesses server-client-like structure).
3. The geometry accuracy of collision detection and response is better and more realistic. Real physics simulation usually made using this type of calculation. This is because the calculation is made every fixed amount of millisecond, closer to our real physics world mechanism.

It also possesses several disadvantages:

1. It is harder to implement because frame rendering happens in between physics calculation, thus a mathematical interpolation of each object location (especially moving object) must be made for each frame about to be rendered.
2. It is slower than frame-step if performed in single-threaded-processor computer because additional interpolation mathematical calculation for every object. It can be slower if performed in same computer because not only interpolation calculation must be performed but also the same computer must request and respond (acts as server and client) to query data for each frame.

Frame-step Motion Calculation Period

Frame-step motion calculation period is period in which calculation of physics properties and object’s position is calculated every time frame is about to be rendered (just before rendering stage). This frame-step type is the favorite choice of many game engines we have observed. It has several advantages:

1. It is simple to implement. Any game developer beginner who want to make fast and simple physics engine will instinctively choose this method.
2. It does not require interpolation technique.

This mechanism also has several disadvantages:

1. If collision detection is calculated using only initial and projected position (instead of using bounding motion) then there will be a case where an object can bypass an obstacle. This can happen when there is a significant delay in frame rate or frame rate drop such as when there is another heavy load in the same processor. Because the longer the delay between each frame the greater the increment of object’s position.
2. It heavily depend on client side, it is impossible to make further parallelism or separate the process in different thread or computer, thus making server-client structure impossible.
3. Because server-client structure is impossible to made, this also means online games cannot use this type of physics calculation.

Collision Detection Event

Event On Touching

This event is triggered when a collider touches another collider.

Event On Keep Touching

This event is triggered every time a collider stays in touch with another collider. Usually the amount of time it contact is needed. An example where we need this event is when a character hit spike floor, the character is damaged as long as this character keeps touching with spike floor.

Event On Separate

This event is triggered when a collider separates with another collider (that were touching each other).

An algorithm is necessary to handle all these correctly. There are essentially two ways to handle collision events: either send an event every update while two objects are touching (and continuously while they’re still touching), or send events both when the objects collide and when the objects separate. In almost all cases it is wiser to pick the latter option, since it is simply an optimized version of the first. If we know when the objects start and stop touching, then we can assume that the objects are still touching between those two moments in time. So long as the system also informs us of peculiar cases in separation (such as if one object is destroyed, or teleports away while they’re still touching), then we have everything we need for a collision event system. (Dickinson, 2013) The idea of the algorithm is to determine if a pair of objects have either collided or separated during each step, and if so, broadcast the corresponding event. The algorithm is described as follows:

1. For every motion calculation period, create two empty list PrevList and NowList.
2. Create PotCollideList as potential collision list and populate it with all pairs that need to be checked for collision.
3. For each pair of objects in PotCollideList, check if the pair are touching. If so, add the pair to NowList.
4. Find this pair in PrevList, if this pair not found then broadcast Event On Touching.
5. After iteration complete, create MissList that contains only the missing collision pairs between NowList and PrevList.
6. For each pair in MissList, broadcast a separation event.
7. Overwrite content of PrevList with NowList.

For the last part , we will discuss more detail about collision detection phase.