Rastreo de colisión de píxeles

Question

Tengo un personaje que dice, 20 por 10 píxeles grandes y tengo un mapa de colisión basado en píxeles (piense en gusanos).

¿Cuál es la mejor manera de rastrear la colisión para el personaje dada una velocidad superior a 1 píxel por cuadro? ¿Existe una solución mejor que iterar a través de cada píxel a lo largo del vector de velocidad?

Estoy haciendo esto en Lua (Love 2D) pero una solución genérica sería ideal.

Answer 1

Combinaría la colisión de la caja delimitadora y la colisión de perfección de píxeles.

Entonces, todas las entidades en su juego tendrían cajas limitantes, solo marcos iguales al ancho y la altura de su sprite. Use esto como su prueba de colisión de primer nivel. Después de que esto se haga, y tiene una colisión, luego use los mapas de colisión para obtener un nivel de detalle más fino.

Esta optimización ayudará con la velocidad y agrega la flexibilidad al motor que no todas las colisiones tienen que ser perfectas.

En cuanto al algoritmo de colisión perfecto de píxeles perfectos, lo que describe funcionaría. Sin embargo, si va a acelerar, es posible que desee probar esto:

Presente una masa de bits para cada sprite (como un mapa de píxeles, pero solo un bit por píxel), por ejemplo:

00000000
00100000
01100000
01110000

Cuando un sprite choca con otro, cree una nueva masa de bits de la masa de bits más pequeña del mismo tamaño de la más grande y 'compensarla' por la diferencia de posición entre los sprites.

Una vez hecho esto, en cuanto a bits 'y' todos los bytes en estas dos máscaras. Si algún resultado de byte> 0, tiene una colisión.

Answer 2

Su solución es la más simple: iterar sobre cada píxel.

Solo asegúrese de verificar solo los "nuevos" píxeles en cada iteración.

Digamos que el personaje se está moviendo hacia la derecha y hacia abajo al mismo tiempo:

*****   .....       .....        * = "Present"
*****   .*****      .****#       . = "Old and now empty"
*****   .*****  =>  .****#        # = "New"; check these on iteration 2
*****   .*****      .****#
         *****       #####

It. 1   It. 2      "New" pixels

En cada iteración a lo largo del movimiento hay poca diferencia en los píxeles para verificar; Solo los marcados como "nuevos" necesitan verificar el impacto. Verifique que, y si no hay colisión, continúe moviéndose. Puede usar eso para optimizar muchos cálculos.