The personal website of @erikwittern

Gravity Quest - Collision implementation

August 29th 2014

Other posts in this series:

In the previous article of this series, I discussed the basic design and implementation of Gravity Quest's gameplay. In this article, I will extend the discussion of the implementation with a focus on collision detection. Collision detection proved to be an fundamental aspect of developing Gravity Quest and is required in many other games as well.

In Gravity Quest, various collisions may occur. The astronaut may collide with thermoactive asteroids, which can be targeted by the gravity gun, with dwarf novae, which cannot be targeted by the gravity gun, or with aliens, which chase the astronaut if she passes them too closely. In all these cases, the astronaut is killed, requiring solid collision detection.

Phaser's physics engines

Phaser comes with three different physics engines which include collision detection:

  • Phaser's own Arcade engine is generally optimized for fast performance. Its features cover many basic requirements game developers have, but do not necessarily suffice when more complex needs arise.
  • Phaser further packages the P2 physics engine (P2 physics engine's GitHub repository). It offers various advanced features like polygon bodies for collision detection, constraints, or springs. Demos of these features can be found at the P2 homepage.
  • Finally, Phaser includes the Ninja physics engine. It shines when creating virtual landscapes with slopes or rounded corners. Typical games profiting from the Ninja engine are platformers (think of old versions of Super Mario or Sonic).

P2 as an initial choice

For Gravity Quest's purposes, initially, P2 was the engine of choice by ruling out the other ones. The Ninja engine was ruled out because it targets a different style of games. The Arcade engine offers many of the features required for Gravity Quest, for example, functions for accelerating objects to one another. However, it does only support collision detection between rectangles, whereas in Gravity Quest most of the objects requiring collision detection are circles. Asteroids, novae, aliens - all these are somehow round in my mind. P2 provided everything I needed out of the box, except an accelerateToObject function which I was aware of from the Arcade engine and which is fundamental to Gravity Quest's gameplay. I reproduced this function as shown in listing 1 and discussed in this forum thread.

1
...
2
accelerateToObject: function (obj1, obj2, speed) {
3
  if (typeof speed === 'undefined') { speed = 60; }
4
  var angle = Math.atan2(obj2.y - obj1.y, obj2.x - obj1.x);
5
  obj1.body.force.x = Math.cos(angle) * speed;
6
  obj1.body.force.y = Math.sin(angle) * speed;
7
}
8
...
 Listing 1: accelerateToObject function for P2 bodies.

Almost throughout the whole development process of Gravity Quest, I happily stuck with my choice of P2. I always intended to publish the game for iOS initially, due to the comparatively small amount of devices to test for. Still, while developing the game, I mostly tested it on my iPhone 5. When the game was nearly finished, however, I started to test it also on some of my friends' Apple devices such as the iPhone 4 and iPhone 4s. And, unfortunately, I found that performance was lacking: framerates dropped (depending on the complexity of the level I tested) to under 30, which was enough to make Gravity Quest feel sluggish. I performed some tests to identify the performance bottleneck, initially suspecting the frequent distance calculations in the update function (see the implementation described in the previous article). These tests revealed, however, that P2 was too heavy, at least in the way I used it, for older devices. (Please note: in no way do I want this statement to be generalized - this was just my experience and must not hold in other cases and does certainly not speak against the high quality of P2.) Based on this insight, I decided to follow another route.

Given Gravity Quest's need for a physics engine, for example to accelerate objects, I decided to switch to using Phaser's faster Arcade engine. Because it does, however, not provide collision detection between rectangles and circles or circles and circles, I implemented my own solution, which I will describe in the following.

Collision between circles and circles

One possible type of collisions in Gravity Quest concerns that of circular objects with other circular objects. For example, the collision of two aliens, both circular, results in their explosion.

Listing 2 shows how the collision detection between two circles is implemented. The two functions, collidesCircleCircle and getPowDistance, can be defined as methods of the state object where they are required in. The collidesCircleCircle function takes as input two Arcade physics bodies, called body1 and body2. Note: these bodies are rectangles, the only type of body supported by the Arcade physics engine. It is assumed, however, that these bodies belong to circular sprites, implying that the bodies are square (their width equals their height). It is further assumed that these bodies' anchors are centered both vertically and horizontally.

1
...
2
/* 
3
 * Determines whether two circles collide or not.
4
 * Input: 2 square Arcade physics bodies with centered anchors
5
 * Output:
6
 * - true, if collision is detected
7
 * - false, if no collision is detected
8
 */
9
collidesCircleCircle: function(body1, body2){
10
  var radius1 = body1.width * 0.5;
11
  var radius2 = body2.width * 0.5;
12
  if(Math.abs(body1.x - body2.x) < radius1 + radius2 &&
13
    Math.abs(body1.y - body2.y) < radius1 + radius2){
14
    var distance = this.getPowDistance(body1.x, body1.y, body2.x, body2.y);
15
    if (distance < (radius1 + radius2) * (radius1 + radius2)){
16
        return true;
17
    }
18
  }
19
  return false;
20
},
21


22
/* 
23
 * Helper function to determine the distance between
24
 * two points using Pythagorean theorem 
25
 */
26
getPowDistance: function(fromX, fromY, toX, toY){
27
  var a = Math.abs(fromX - toX);
28
  var b = Math.abs(fromY - toY);
29
  return (a * a) + (b * b);
30
}
31
...
 Listing 2: collision detection between 2 circular bodies.

Initially, as shown in listing 2, the radii of these bodies is derived from their width. In the first if-statement, a fast check is performed to determine if collision is possible - that is, whether the horizontal and vertical distance between the two bodies is smaller or equal to the sum of their radii. If this condition does not hold, two circles cannot collide, as exemplarily shown in case 1 in image 1. If the condition holds, collision may occur, for example if the two bodies are vertically or horizontally aligned as shown in case 2 in image 1, but must not as shown in case 3 in image 1. Thus, a second condition is necessary. It uses the Pythagorean theorem to determine the distance between the two bodies' anchors. The collision detection returns true, if the determined distance is smaller than the sum of the two radii. Based on this second condition, collision in case 3 in image 1 is excluded and collision in case 4 in image 1 is detected.

Image 1: example of circle collisionImage 1: example of circle collision

Collision between rotated rectangles and circles

Another type of collisions in Gravity Quest is that of rotated rectangular objects and circular objects. For example, the astronaut is rectangular and can collide with circular thermoactive asteroids, dwarf novae, or aliens.

Listing 3 shows how the collision detection between a rotated rectangle and a circle is determined. Again, the function collidesRectCircle can be defined as a method of the state object where it is required in.

1
...
2
/* 
3
 * Determines whether two circles collide or not.
4
 * Input: 
5
 * - rect: an Arcade physics body with centered anchor
6
 * - circle: a square Arcade physics bodies with centered anchor
7
 * Output:
8
 * - true, if collision is detected
9
 * - false, if no collision is detected
10
 */
11
collidesRectCircle: function(rect, circle){
12
  var radius = circle.width * 0.5;
13
  var upperRectRadius = Math.max(rect.width, rect.height) * 0.75;
14


15
  // quick check, whether collision is actually possible:
16
  if(Math.abs(circle.x - rect.x) < radius + upperRectRadius &&
17
    Math.abs(circle.y - rect.y) < radius + upperRectRadius){
18


19
    // adjust radians:
20
    var rotation = rect.rotation > 0 ? -1 * rect.rotation : -1 * rect.rotation + Math.PI;
21


22
    // rotate circle around origin of the rectangle:
23
    var rotatedCircleX = Math.cos(rotation) * (circle.x - rect.x) - 
24
        Math.sin(rotation) * (circle.y - rect.y) + rect.x;
25
    var rotatedCircleY  = Math.sin(rotation) * (circle.x - rect.x) + 
26
        Math.cos(rotation) * (circle.y - rect.y) + rect.y;
27


28
    // get upper left position of the rectangle:
29
    var rectX = rect.x - (rect.width * 0.5);
30
    var rectY = rect.y - (rect.height * 0.5);
31


32
    // find closest point in the rectangle to the rotated circle's center:
33
    var closestX, closestY;
34


35
    if (rotatedCircleX  < rectX){
36
      closestX = rectX;
37
    } else if (rotatedCircleX  > rectX + rect.width){
38
      closestX = rectX + rect.width;
39
    } else {
40
      closestX = rotatedCircleX;
41
    }
42


43
    if (rotatedCircleY < rectY){
44
      closestY = rectY;
45
    } else if (rotatedCircleY > rectY + rect.height) {
46
      closestY = rectY + rect.height;
47
    } else {
48
      closestY = rotatedCircleY;
49
    }
50


51
    // check distance between closest point and rotated circle's center:
52
    var distance = this.getPowDistance(rotatedCircleX, rotatedCircleY, closestX, closestY);
53
    if (distance < radius * radius){
54
      return true; // Collision
55
    }
56
  }
57
  return false;
58
}
59
...
 Listing 3: collision detection between a rotated rectangular and a circular body.

Initially, as shown in listing 3, the given circle's radius is determined. Also, an approximate upper bound upperRectRadius of the radius of a circle surrounding the given rectangle is determined. Using these radii, similar to collision detection between two circles, a quick check is performed to determine whether collision is possible at all.

The following, more expensive, collision detection is a JavaScript translation of the method described in a post about Circle and Rotated Rectangle Collision Detection. Its basic idea is to compensate for the rectangle's rotation by shifting the circle's center around the rectangle's center by the same amount.

To do so, after having adjusted the radian rotation as described in a comment by Brad Greens in the article Circle and Rotated Rectangle Collision Detection, the circle's anchor is rotated around the rectangle's anchor to compensate for the rectangle's rotation using basic algebra. This procedure results in coordinates of the rotated circle's center, denoted by rotatedCircleX and rotatedCircleY.

Next, the X and Y coordinates of the closest point within the rectangle to the rotated circle's center are determined in the if-else-statements. Finally, using again the Pythagorean theorem, the distance between the determined closest point in the rectangle and the center of the rotated circle is determined. If this distance is smaller than the circle's radius, collision is detected.

Using custom collision detection in the game

Having the basic mechanisms in place, they can be used for collision detection. To exemplify this, the source code from the previous article is extended to support collision detection between the rectangular astronaut and some novae. Upon collision, the game's single state is restarted.

As shown in listing 4, the corresponding assets are loaded in the preload function.

1
...
2
game.load.image('nova', 'assets/nova.png');
3
...
 Listing 4: loading an asset for the novae.

Next, in the create function, as shown in listing 5, three novae are randomly placed in the world and added to a novae group. As in the previous article, a border of 100 pixels is left out for positioning the novae.

1
...
2
this.novae = game.add.group();
3
for (var i = 0; i < 3; i++) {
4
  var nova = game.add.sprite(
5
    game.rnd.integerInRange(100, game.world.width - 100),
6
    game.rnd.integerInRange(100, game.world.height - 100),
7
    'nova');
8
  nova.anchor.setTo(0.5, 0.5);
9
  this.novae.add(nova);
10
};
11
...
 Listing 5: place novae at random positions.

Finally, in the update function, collision is checked for as shown in listing 6. The novae group is iterated and every nova is checked against collision with the astronaut in the above described collidesRectCircle function. If collision is detected, the main state is restarted.

1
...
2
this.novae.forEach(function(nova){
3
  if(this.collidesRectCircle(this.astronaut, nova)){
4
    game.state.start('main');
5
  }
6
}.bind(this));
7
...
 Listing 6: check collision in the update function.

Demo

Press the button below to play a demo where collision detection is implemented as described above. If the astronaut collides with one of the novae, the game is restarted.

Play demo...

Conclusion

Collision detection is a standard feature of many game development frameworks, certainly also of Phaser. In the case of Gravity Quest, however, the combination of requirements for a lightweight physics system and collision detection between circular bodies drove me to a custom solution. The here presented implementation, though far from being perfectly optimized, produces the desired outcome: the game performs well also on older iOS devices and collision detection works properly. The source code for the collision detection demo is available in this GitHub repository. In the next article, I will discuss how I created Gravity Quest's visuals and sound.

Resources linked in this article