javascript - colisión - Circle Collision Detection HTML5 Canvas

colisión js

Question

Quiero comprobar si los círculos están colisionando entre sí.

Sé que puedo hacer esto al obtener una distancia entre los dos centros de los círculos y restar el radio de cada círculo de esa distancia y ver si ''distancia'' es> 1.

¿Cómo puedo hacer esto de manera eficiente aunque, digamos, con 1000 círculos? Tal vez de alguna manera puedo obtener los 20 círculos más cercanos o algo así y comprobar esto? No sé cómo empezaría a hacerlo de manera eficiente, aunque tampoco ...

¿Algunas ideas?

Aquí hay un ejemplo:

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

Answer 1

Antes de comenzar a calcular las diferencias exactas en distancias, al menos puede comparar las posiciones x / y de los centros con los radios. Esa información está implícitamente disponible en el círculo y solo requiere algunas comparaciones simples y sumas / restas.

Eso te permitirá comparar las distancias simples en x / y entre todos los pares de círculos, y tirar cualquier que obviamente no sea candidato a colisión, por ejemplo

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

... si la distancia en X o Y entre los centros del círculo es mayor que la suma de los radios, entonces no pueden estar colisionando.

Una vez que has reducido los posibles colisionadores, ENTONCES haces la distancia cartesiana exacta formal, que es donde entran las cosas "pesadas" de multiplicación / división.

Answer 2

Considere almacenar las coordenadas de los centros de los círculos en un árbol cuádruple, entonces solo necesitaría verificar si el círculo se cruza con otros círculos en ese cuadrante o cuadrantes adyacentes.

La única advertencia es que debe asegurarse de que los nodos de las hojas del árbol cuádruple tengan un diámetro mínimo del radio de su círculo más grande, de lo contrario, deberá verificar más que los nodos adyacentes para la intersección.

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

Si sus círculos están bien dispersos, entonces una optimización simple que puede hacer es almacenar sus círculos ordenados en los ejes xey, entonces solo necesita verificar con círculos quién es x o y la coordenada está dentro del radio del círculo.

Answer 3

La eficiencia se relacionará con la velocidad de los algoritmos que está utilizando , por ejemplo, la velocidad del algoritmo de raíz cuadrada con el que calcula la distancia, y sus estructuras de datos determinarán la eficiencia de la memoria, además de los algoritmos. Otra forma de acelerar los cálculos sería reducir la precisión de los cálculos de distancia.

El mejor método para detectar si los círculos están colisionando es, como dijiste, almacenar las coordenadas del centro de los círculos y el radio en variables y calcular si la distancia entre los centros es o no equivalente a 0 cuando se restan los radios.

Answer 4

Recomiendo encarecidamente el libro de animación AdvancED ActionScript 3.0 de Keith Peter, donde puede encontrar la implementación concreta del algoritmo Quadtree en Actionscript.

Aquí están los pasos básicos:

• Primero crea una cuadrícula bidimensional y dispersa todas las bolas al azar en el campo.

  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();
          }
      }
  }

• Asignar bolas a las celdas de la grilla

  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);
      }
  }

• Compruebe si dos bolas están colisionando en una sola celda, luego verifique las bolas en las celdas adyacentes. Como Charles Ma mencionó la única consideración aquí, la dimensión de las celdas de la grilla debe ser mayor o igual que el diámetro de la bola más grande.

  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
      }
  }

• Así es como se ve el método principal:

  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);
          }
      }
  }

NOTA:

El código está escrito en Actionscript pero puede implementarse fácilmente en Javascript.