Geek Answers Handbook

Collision Detection Around HTML5 Canvas Circle

I want to check if the circles collide with each other.

I know that I can do this by going the distance between the two centers of the circles and subtracting the radius of each circle from this distance and seeing that the "distance"> 1.

How can I do this efficiently though, say, 1000 laps? Maybe I can somehow get the next 20 laps or something like that and check them out? I do not know how I will begin to do this effectively, either.

Any ideas?

Here is an example:

http://experiments.lionel.me/blocs/

+4
source share
4 answers

Before you start calculating the exact differences in distances, you can at least compare the positions of the x / y centers vs the radii. This information is implicitly available in the circle and requires only simple comparisons and addition / subtraction.

This will allow you to compare simple distances in x / y between all pairs of circles and throw away any that are clearly not candidates for collision, for example.

abs(x2 - x1) > (r2 + r1) abs(y2 - y1) > (r2 + r1)

... if the distance in X or Y between the centers of the circle is greater than the sum of the radii, then they cannot collide.

Once you have removed the possible colliders, THEN you make a formal exact Cartesian distance, which includes the "heavy" material of reproduction / division.

+6
source

Consider saving the coordinates of the centers of circles in a square tree, then you only need to check whether the circle intersects with other circles in this quadrant or neighboring quadrants.

One caveat is that you need to make sure that the nodes of the leaves of the square tree have a minimum radius diameter of your largest circle, otherwise you will have to check more than just the neighboring nodes for the intersection.

http://en.wikipedia.org/wiki/Quadtree

If your circles are well scattered, then a simple optimization you can do is to keep the circles sorted by the x or y axis, then you only need to check the circles whose x or y coordinates are within the radius of the circle.

+2
source

Efficiency will relate to the speed of the algorithms you use, for example, the speed of the square root algorithm with which you calculate the distance, and your data structures will determine the memory efficiency, in addition to the algorithms. Another way to speed up calculations would be to reduce the accuracy of distance calculations.

The best way to determine if circles collide, as you said, is to store the coordinates and radius of the circle in variables and calculate whether the distance between the centers is equal to zero when subtracting the radii.

0
source

I highly recommend the Keith Peter AdvancED ActionScript 3.0 Animation book, where you can find a specific implementation of the Quadtree algorithm in ActionScript.

Here are the basic steps:

  • First create a two-dimensional grid and randomly scatter all the balls in the field.

     private function createGrids():void { _grids = new Array(); for (var i:int = 0; i< stage.stageWidth / GRID_SIZE; i++) { _grids[i] = new Array(); for (var j:int = 0; j< stage.stageHeight / GRID_SIZE; j++) { _grids[i][j] = new Array(); } } }

  • Assigning balls to mesh cells

     private function assignBallsToGrid():void { for (var i:int = 0; i< numBalls; i++) { var ball:Ball = Ball(_balls[i]); var xpos:int = Math.floor(ball.x / GRID_SIZE); var ypos:int = Math.floor(ball.y / GRID_SIZE); _grids[xpos][ypos].push(ball); } }

  • Make sure the two balls collide in the same cell, and then check the balls in adjacent cells. Since Charles Ma mentioned a single consideration, the mesh cell size must be greater than or equal to the largest diameter of the ball.

     private function checkOneCell(x1:Number, y1:Number):void { var _cell:Array = _grids[x1][y1] as Array; for (var i:int = 0; i< _cell.length-1; i++) { var ballA:Ball = _cell[i] as Ball; for (var j:int = i+1; j< _cell.length; j++) { var ballB:Ball = _cell[j] as Ball; checkCollision(ballA, ballB); } } } private function checkTwoCell(x1:Number, y1:Number, x2:Number, y2:Number):void { if (x2 < 0) { return } if (x2 >= _grids.length) { return } if (y2 >= _grids[x2].length) { return } var _cell0:Array = _grids[x1][y1] as Array; var _cell1:Array = _grids[x2][y2] as Array; for (var i:int = 0; i< _cell0.length; i++) { var ballA:Ball = _cell0[i] as Ball; for (var j:int = 0; j< _cell1.length; j++) { var ballB:Ball = _cell1[j] as Ball; checkCollision(ballA, ballB); } } } private function checkCollision(ballA:Ball, ballB:Ball):void { var dx:Number = ballB.x - ballA.x; var dy:Number = ballB.y - ballA.y; var dist:Number = Math.sqrt(dx*dx + dy*dy); if (dist < ballB.radius + ballA.radius) { // do something } }

  • Here's how it looks like the main method:

     private function checkBallsCollision():void { for (var i:int = 0; i< _grids.length; i++) { for (var j:int = 0; j< _grids[i].length; j++) { checkOneCell(i, j); checkTwoCell(i, j, i+1, j); checkTwoCell(i, j, i, j+1); checkTwoCell(i, j, i-1, j); checkTwoCell(i, j, i+1, j+1); } } }

Note:

The code is written in ActionScript, but can be easily implemented in Javascript.

0
source

More articles:


All Articles