colisiones en 2D?

Archivado
hola, estoy desarroyando un juego para psp en 2d usando sdl y tal. Para los que no conozcan esta librería te permite trabajar con secciones de memoria y mostrarlas en la pantalla. Lo que es cargar imagenes y dibujarlas y poco más la verdad ( hay extensiones pero no viene al caso).

Mi problema cargo una imagen con un color key un color no visible y por eso me gustaría hacer colisiones entre 2 imagenes distintas con una velocidad aceptable. En cada frame supongo que solo tendría unos 4 personajes de unos 50 x 50 pixeles. Me gustaría encontrar un método para realizar las colisiones de una manera relativamente precisa y rápida.

El método de partir las imagenes en varios cuadrados no lo veo viable las imagenes deberían entrar enteras. y colisionar con el cuadrado exterior de la imagen no lo veo la mejor solución.

Un heurístico que se me ha ocurrido sería preprocesar las imagenes de tal manera de que una vez comprovado que 2 imagenes se interescan ( comprobación del cuadrado relativamente rápida) pasar a hacer una comprobación de por donde chochan solo procesando los pixeles que se juntan en el caso de encontrar una colision envia la posición de la misma y se finaliza la ejecución digamos que este algoritmo estaría basado en una poda ( si no estás en la sección de otra imagen no hagas nada ) si estas comprueba.... pero esto tiene un fallo puede hacerlo muy lento?. En mi caso las imagenes son de 50 x 50 más o menos con secciones blancas que no son demasiado grandes 5-10 pixeles en la periferia
por lo tanto calculo que serían unos 10*10= 100 comparaciónes en un segundo. que incluso se podría simplificar más el cálculo y sólo mostrar en caso de que se esté golpeando y se quiera hacer alguna accion ya que tengo pensado que los personajes puedan moverse libremente sin que se interrumpan unos con otros.
El método que indicas parece el más viable, aunque sigue siendo demasiado costoso si compruebas la colisión píxel por píxel: en una imagen de 64x64 píxeles en el peor de los casos tienes que hacer 64x64 = 4096 comparaciones. Si agrupas los píxeles en cuadrados de 4x4 no pierdes mucha precisión y reduces el número de comparaciones a 16x16 = 256.
pero nunca pasará que introduzca una imagen así, la imagen representa un personaje de unos 50 x 50... calculando la interseccion con otra imagen creo que sería un rectangulo de en el peor de los casos 20x20 ( muy muy muy en el peor de los casos ) 400 operaciones pero vamos sería muy raro lo normal que comprobaría creo que serían del orden de 50 o 100 aún así son muchas :( pero he estado leyendo por internet y tal y se ve que justamente el método que mas se gasta es el de envoltura con cajas y para más precision es envoltura con cajas + colision pixel a pixel que sería este. lo de dividir el espacio en varios bloques estaría en las mismas porque cuando entrasen en colision 2 cajas tendría que comprobarlas así que mejor comprobar solo la colision entre las dos imagenes creo que sería el mínimo.
Si empiezas a comprobar las dos imágenes directamente antes de comprobar la colisión por cajas vas a perder muchísimos ciclos. Si supones desde un principio que todas las imágenes van a tener el mismo tamaño, se puede comprobar la colisión entre dos cajas de forma eficiente:

if(abs(x2 - x1) <= tamX && abs(y2 - y1) <= tamY)
comprobarPorPixel(...);

Esta sentencia sólo usa 4 comparaciones en el peor de los casos, la pérdida de ciclos es mínima.

Por otra parte, te recomiendo que el tamaño de la imagen sea potencia de 2: el compilador sustituye automáticamente las multiplicaciones, divisiones y módulos de un número potencia de 2 por desplazamientos y operaciones lógicas, ahorrándote muchos ciclos. Un cuadrado de 64 pixels sería el tamaño ideal para una imagen.
Yo no me complique la vida y uso cajas, creo una caja del tamaño q quiero y donde quiero q colisione, por ejemplo la cabeza, aunque el sprite sea de 50x50, por ejemplo la cabeza estara a x=15 y=15, hasta x=35 y = 10.
De forma q creo un cuadro con esas medidas y compruebo si colisiona con algo, de esa forma obtengo la precision q yo quiero sin q la cosa se vaya de madre. Lo demas es buscarle tres pies al gato
Eskematico escribió:Yo no me complique la vida y uso cajas, creo una caja del tamaño q quiero y donde quiero q colisione, por ejemplo la cabeza, aunque el sprite sea de 50x50, por ejemplo la cabeza estara a x=15 y=15, hasta x=35 y = 10.
De forma q creo un cuadro con esas medidas y compruebo si colisiona con algo, de esa forma obtengo la precision q yo quiero sin q la cosa se vaya de madre. Lo demas es buscarle tres pies al gato


si lo haces así no podras tener diferentes personajes o tendrás que crearlos tu a mano... lo que quiero es tener una comparación genérica. Al final me quedaré con la poda esta que creo que irá bastante bien solo analizas por pixel la región de corte.
El método que presentas es el más adecuado.

Primero descartas las colisiones con la intersección de los rectangulos que envuelven al sprite.
Si el resultado de la interseccion existe, utilizas este para calcular el area de colision de los rectangulos, y los consecuentes pixeles de cada superficie que se intersectan. Solo tendrias que comprobar que no exista en la misma posición relativa dos pixeles (uno de cada superficie) con color diferente al ColorKey.

Si solo tienes cuatro sprites no necesitas ordenar el array de sprites ni nada, pero en caso de que fuera un plataformas con muchos enemigos, quizás si te interesaria para crearte una especie de "partición espacial" y ahorrarte comparaciones.

El problema lo veo en tener que comprobar los pixeles de la superficie (o sea bloquearla acceder, etc, además de que estaria en vram), asi que te aconsejo que al cargar la superficie, te crees una especie de cache en la ram (un array de int, por ejemplo) que y pongas ahi la información de colisión (0 colorkey, 1 otro color, por ejemplo), lo que te ahorria tiempo de acceso a la hora de comprobar los pixeles.
Hay muchos trucos, por ejemplo utilizar valores 2^n (2,4,8,16,32,...) y en vez de crearte una array, utilizas los bits de uno o varios int para almacenar la información de colision (1 si, 0 no) luego puedes hacer un:

if ((datosA & datosB) != 0) {
// Existe colisión
} else {
// No existe colisión
}

Si sabes utilizar bien las operaciones booleanas y los desplazamientos, puedes ahorrate muchas operaciones y comparaciones (ya que en una operación de estas puedes llegar hasta a comprobar 64pixeles de la zona de intersección, uno por cada bit).


Bueno, espero que te sirva de ayuda.
Un saluo.
6 respuestas
Archivado
Volver a Desarrollo