Experiment 2: Collision Detection

Sections in this Article:

Circle In Circle Collision Detection

In this section we will look at collision detection using circles. The assumption is the region of game object [or character] can be represented by a circle. In this example we will look at the mathematics of detecting when one circle is 'entirely' within another, analogous to a enemy bullet colliding with the player!

There are always compromises when trading performance with accuracy, take for example the ‘ship’ character in the image above, clearly the circle doesn’t accurately represent the entire ship – what would happen if an enemy bullet fell within the circle but wasn’t within the ship? This will be covered in later experiments but for this experiment, we’ll now look at the math to detect when a circle is entirely within another.

The Math

This problem is really a mathematical one. There isn’t really any clever algorithms to come up with, just an understanding of the geometry of circles and when they intersect.

Two circles, c1 [the big one in the diagram below] and c2 [the small one, inside c1] positioned at x1, y1 and x2, y2 respectively.
Circle c2 will 'poke' outside of circle c1 when the radius (r2) of circle c2, added to the distance between the centre points of circles c1 and c2 are bigger than the radius (r1) of circle c1, or, mathematically when r2+H > r1; [that's the important bit right there!]
H can be calculated using Pythagoras theorem H²=a²+b² with the right angled triangle being defined as sides a and b, where a = x1-x2 and b = y1-y2

Yuk, I don't like all this math stuff myself so hopefully the picture below will make this more obvious...

To see a live example of this in action, mouse over or touch the image below to position the smaller circle. When the smaller circle is entirely within the larger circle, the smaller circle will change colour to red.

Code - Circle in Circle

The full code for the Circle in Circle demonstration is listed below.

1(function() {
2    // create svg element in div element with name "demo"
3    var host = document.getElementById("demo-circle-in-circle");
4    
5    var svg = document.createElementNS('http://www.w3.org/2000/svg', 'svg');
6    svg.setAttribute("width","100%");
7    svg.setAttribute("height","400");
8    svg.setAttribute("style", "background-color: silver;");
9    host.appendChild(svg);
10
11    // create objects to keep track of where the circles are...
12
13    // add circle c1
14    var circle1 = {
15        "id": "circle1",
16        "x": 200,
17        "y": 200,
18        "r": 100,
19        "fill": "green"
20    };
21
22    // create an SVG circle based on the definition of circle1
23    var c1 = createCircle(circle1, svg);   
24
25    // add circle c2
26    var circle2 = {
27        "id": "circle2",
28        "x": 30,
29        "y": 30,
30        "r": 40,
31        "fill": "yellow"
32    };
33
34    // create an SVG circle based on the definition of circle2
35    var c2 = createCircle(circle2, svg);
36
37    // add mouse move handler to svg
38    svg.addEventListener('mousemove',function(e) {
39        var loc = cursorPoint(e);
40        c2.setAttribute("cx", loc.x);
41        c2.setAttribute("cy", loc.y);
42
43        circle2.x = loc.x;
44        circle2.y = loc.y;
45
46        if( isCircleContained(circle1, circle2)) {
47            c2.setAttribute("fill", "red");
48        } else {
49            c2.setAttribute("fill", circle2.fill);
50        }
51      },false);
52
53    // need to translate the position to the SVG coordinate space
54    var svgPoint = svg.createSVGPoint();
55    function cursorPoint(evt){
56        svgPoint.x = evt.clientX;
57        svgPoint.y = evt.clientY;
58        return svgPoint.matrixTransform(svg.getScreenCTM().inverse());
59    }
60
61    // here's where the maths is applied...
62    function isCircleContained(parent, child) {
63        // triangle sides
64        var a = child.x - parent.x;
65        var b = child.y - parent.y;
66
67        // apply Pythagoras...
68        var h = Math.sqrt( Math.pow(a,2) + Math.pow(b,2));
69
70        // now the detection part
71        return parent.r > (h + child.r);
72    }
73
74    function createCircle(circle, svg) {
75        var element = document.createElementNS('http://www.w3.org/2000/svg', 'circle');
76        element.setAttribute("id", circle.id);
77        element.setAttribute("cx", circle.x);
78        element.setAttribute("cy", circle.y);
79        element.setAttribute("r", circle.r);
80        element.setAttribute("fill",circle.fill);
81        element.setAttribute("fill-opacity","80%");
82        svg.appendChild(element);
83        return element;
84    }
85})();

Walk Through

Hopefully the code is self-explanatory, but here's the walk through; most of it is really around getting the demo running and interactive. The actual collision detection is a very simple function.

Line 1 Definition of a self-invoking function to get everything up and running when the JavaScript begins execution.
Line 3 Everything will be rendered in a element in the document with the Id demo-circle-in-circle.
Lines 5-9 Create an svg element within the host element - see Line 3.
Lines 14-20 Create an object to represent circle c1.
Line 23 Call to a helper method to create the circle element within the svg for circle c1 defined in lines 14-20.
Lines 26-32 Create an object to represent circle c2.
Line 35 Call to a helper method to create the circle element within the svg for circle c2 defined in lines 26-32.
Lines 38-51 Hooking up a listener for mouse move events to position the smaller circle and perform the collision detection.
Line 39 Call to a helper function to translate the mouse position to the actual position within our svg.
Lines 40-41 Move the smaller circle to the position where the mouse move event was detected by setting the centre x and y attributes of the smaller circle.
Lines 43-44 Cache the location of the smaller circle in the internal object model.
Lines 46-50 Perform the collision detection by calling the method isCircleContained and depending on the function return, adjust the fill colour of the small circle to red if it is entirely within the larger circle. If not, return the circle back to its original fill colour.
Lines 54-59 Function to translate of the mouse pointer to the coordinate space of the SVG.
Lines 62-72 All the maths outlined in the text above wrapped into a function; this is where the collision detection happens.
Lines 74-84 A helper method for creating svg circle elements. The circle is represented in an internal object mode (see lines 13-32), this function takes that information and creates a circle within the SVG. The opacity of the circles is set to 80%, this is really to aid the user experience of the demo as it permits the intersection of the circles to be seen.
Line 85 I personally don't like how JavaScript results in code like this, but this completes the anonymous method created on Line 1.

Continue on reading to Circle To Circle Collision Detection...