¿Qué es un buen algoritmo de detección de colisiones en 2D rectángulos solo?

Question

Estoy diseñando un tutorial de un juego de detección de colisiones para adultos jóvenes, por lo que quiero que sea lo más simple posible para que sea más fácil de explicar.

Los requisitos son muy simples. El mundo es 2D y contiene solo rectángulos (de tamaños arbitrarios). BSP e incluso quadtrees parece que sería excesivo (de nuevo, el énfasis está en la simplicidad) pero me gustaría algo más eficiente que el forzado bruto a través de todas las n (n-1)/2 posibles colisiones.

2D, solo rectángulos y simple.

¿Alguien puede apuntar a un algoritmo que puedo buscar? ¿Es un algoritmo quadtree lo que estoy buscando?

EDITAR: Además, los rectángulos nunca se rotarán (lo estoy manteniendo simple). Y para darle una idea de en qué escala estoy trabajando, habrá unos cientos de rectángulos ejecutándose en la computadora portátil/escritorio de su usuario típico (menos de 5 años) implementada en Python con Pygame.

Answer 1

En mi experiencia, todos los algoritmos de detección de colisiones de banda ancha son relativamente sutiles y difíciles de entender. Teniendo en cuenta qué tan barata es la prueba de colisión rectangular, estructuraría la lección utilizando el algoritmo n^2, luego como material de bonus, tal vez introduzca la idea de la indexación espacial. Con menos de cientos de rectángulos, apostaría que el camino tonto es lo suficientemente rápido.

Un quadtree estaría bien para sus propósitos, pero recuerde que cuando se trata de no puntos, debe colocar el rectángulo en un nodo que contenga todos los cuadrantes que interseca. Entonces, cuando se prueba algo que está en un nodo bajo, ¡tienes que probar contra todas las rectas en ese nodo y en todos sus antepasados!

También podría considerar un algoritmo de ordenación y barrido, ya que lo que ya tiene son recuadros delimitadores alineados al eje.

Answer 2

Una estrategia simple que acelera la detección de un primer intento de un simple juego en 2D era mantener una lista ordenada por la fase más larga de colisión dimension.The consistía en algo como esto:

for i in 0..n 
    j = i+1 
    while rect[j].left < rect[i].right 
     check for collision in y 
     j=j+1 
    endwhile 
endfor 

Answer 3

Aquí es un simple algoritmo que acelerará un poco las cosas y funciona en rectángulos alineados con el eje.

Elija uno de los ejes como el "eje ordenado". Para esta descripción, diré que el eje X está ordenado. Especifique cada rectángulo como dos nodos, un nodo "enter" y un nodo "exit" en el eje ordenado. Los nodos enter siempre deben tener un valor menor en el eje que los nodos de salida.

Crea una lista ordenada de todos los puntos de entrada y salida.

Camine por la lista ordenada. Al presionar cada nodo "enter", agréguelo a una lista de rectángulos "ingresados" y luego realice una detección de colisión de fuerza bruta contra todos los otros nodos en la lista "ingresada". Cuando golpee cada nodo de "salida", elimínelo de la lista "ingresada".

A continuación, puede llevar al lector por un ejercicio en el que la lista "ingresada" está ordenada en el eje Y con los puntos "enter" y "exit" en el eje Y.