https://heathstein.github.io/random-collision

The objective of the collision detection game is to see what happens when you give advantage to a few objects (in this case size). We want to see how often these objects will come out on top. The game uses Angular 2 ,Typescript and HTML Canvas. This game is pretty simple, we randomly place between 100 and 300 white dots on the screen. These white dots have a mass between .5 and 1. We then randomly place three colored dots on the screen, these dots have a mass of 6. The dots are then all put into motion heading the same direction, when they reach edge of the canvas their direction is reversed (dot.x =- dox.x and dot.y =-dot.y). If a collision is detected between two dots then the larger dot will eat the smaller dot. When there is one dot left the game is over.

The collision detection algorithm used here is very basic. We have an outer loop that loops over all objects, then an inner loop that loops over the objects again checking to see if the objects intersect. As you can imagine this is an expensive operation which gets more expensive the more objects that are added. There are a number of different algorithms like a Quadtree that can be used to cut down on the amount of processing. But for this simple game I used the collision detection algorithm below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
collideTestLoop(dot) { for (var i = 0; i < this.dotArray.length; i++) { var dot2 = this.dotArray[i]; var hit = this.collideTest(dot, this.dotArray[i], 0, 0); if (hit) { this.handelCollision(dot, this.dotArray[i]) } } } collideTest(dot1,dot2,d1x,d1y) { if (dot1.index !== dot2.index) { var dx = (dot1.x - d1x) - (dot2.x - d1x); dy = (dot1.y - d1y) - (dot2.y - d1y), distance = Math.sqrt(dx * dx + dy * dy); return this.checkHit(distance,dot1,dot2) } } checkHit(distance,dot1,dot2){ if (distance < dot1.radius + dot2.radius) { return true; }else{ return false; } } handelCollision(dot1,dot2){ if (dot1.radius > dot2.radius) { dot1.radius += dot2.radius * this.massPresent; var index = _.findIndex(this.dotArray, {index: dot2.index}); dot1.eat(dot2); this.dotArray.splice(index, 1); } else { dot2.radius += dot1.radius * this.massPresent; var index = _.findIndex(this.dotArray, {index: dot1.index}); this.dotArray.splice(index, 1); } } |

Using the Window.requestAnimationFrame and moving each dot at 1 pixel per frame the game is pretty accurate. You will see that when you increase the number of dots to 300 that the White Dots have a chance at coming out on top. The issue is that when you increase the speed (moving the dots at more then 1 pixel per frame) we start missing collisions on the smaller dots causing the larger colored dots to always come out on top.

The next version of the game I would like to introduce the **Quadtree** algorithm. A Q**uadtree** is a tree data structure in which each internal node has exactly four children. **Quadtrees** are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. By using a **Quadtree **we can drastically cut down on the number of checks we need to perform. Using the **Quadtree **algorithm we can also check and see if objects moving at a high rate of speed have collided by checking if objects in the same quadrant have crossed paths. Basically looking back in time.