Modelo V: Detección de colisiones

[Güarmigue]

Antes que nada agradecer a aquellos que votaron en la encuesta del foro y más aun a los que comentaron su opinión. Gracias por el apoyo y vuestros consejos.

Dado que la encuesta ha resultado en una aplastante victoria de los algoritmos, voy a centrarme más en ellos. Pero shephiroth me dio una idea que me gustó que es la de hablar de algoritmos pero mostrar aplicaciones prácticas y ejemplos. Procuraré traer un algoritmo o grupo de algoritmos nuevo cada semana, pero también habrá semanas que dedicaré a un modelo de juego o a ejemplos de juegos que aplican algoritmos ya vistos. Como siempre los comentarios, críticas y aportaciones son bien recibidas.

Hoy voy a hablar un poco de detección de colisiones y al final traigo una pequeña sorpresa, para los que sean capaces de leerlo completo :P

Definición: Tomaremos como Algoritmos de Detección de Colisiones (a partir de ahora ADC) aquellos que se ocupan de que, en la geometría de un juego, no haya intersecciones entre objetos. Además estos algoritmos pueden indicar cómo debe reaccionar determinado objeto en caso de intersecar a (chocar con) otro.

Dificultades técnicas: Los AGC son, si no los acotamos, algoritmos muy costosos, ya que tenemos que calcular la intersección de cada objeto con todos los demás y para cada caso tendremos que comprobar cada pixel o cada vértice de cada objeto... Esto los hace en principio muy costosos computacionalmente, y por eso son uno de los temas más tratados en programación de juegos. Para acotar el problema e incluso reducir su orden de complejidad tenemos que saber bien qué resultados queremos obtener y qué es lo que realmente necesitamos. Por ejemplo:

   * Si los enemigos y objetos del juego siguen un camino predefinido o son estáticos no necesitarán de estos cálculos y podremos aplicar el ADC sólo al jugador principal.
   * Si la forma de los objetos de nuestro juego es cercana a un cuadrado o un círculo (un cubo y una esfera en 3D) no necesitaremos algoritmos complejos y este será un problema casi resuelto.
   * Tenemos que saber cuánta exactitud queremos conseguir y cuanto sacrificio computacional representa.

Como dijo Jack el Destripador: Vayamos por partes...

Muchas librerías y motores traen funciones más que de sobra para hacer el trabajo sucio por ti. Si estás utilizando o pretendes utilizar cualquier motor o librería, lo que debes hacer es leer qué funciones te provee y cómo puedes utilizarlas para cumplir tu objetivo. Si eres un campeón y estás escribiendo tu juego desde cero o simplemente quieres aprender cómo va esto de la detección de colisiones... Sigamos ;)

Lo primero que debemos hacer, una vez evaluado nuestro problema, y si necesitamos velocidad y tenemos muchos objetos que comprobar, es dividir el escenario en una cuadrícula. Si tenemos un escenario 2D esto será fácil, si tenemos 3D, pero básicamente los movimientos son a lo largo y ancho de un escenario, podremos dividir igual que antes, el plano XY. Si no, tendremos que dividir en cubos. ¿Para qué hacemos esto? Para acotar el número de objetos con los que haremos cálculos. De todos los objetos que necesiten ser revisados por el ADC, eliminaremos aquellos que se encuentren en cuadros separados de la cuadrícula, con lo que ahorraremos mucho cálculo inútil. En el dibujo de ejemplo, solo calcularemos la intersección del jugador (azul) con los objetos rojo oscuro, que son los que se encuentran dentro de sus cuadrículas (verde).


Dibujo1: División del escenario.

Una vez reducido el número de objetos que necesitan comprobación pasaremos al test de intersección propiamente dicho. Aquí también hay muchas técnicas, voy ha hacer un pequeño repaso de peor a mejor:

   * Si estamos en 2D podemos comprobar pixel a pixel si dos sprites se superponen, esta es la técnica que afina al máximo, pero muy costosa.
   * Tanto en 2 como en 3 dimensiones podemos aplicar la técnica de cajas o esferas envolventes o bounding boxes/spheres. Esta técnica consiste en definir un cuadrado o círculo que acota completamente cada objeto. Hacer cálculos con éstas cajas es muy sencillo ya que son formas sencillas:

     
     Dibujo 2: Bounding boxes/spheres
         o - Para comprobar colisiones con el rectángulo del jugador, para cada vértice de un rectángulo objeto comprobamos:
           SI (xPunto > xJugador) Y (xPunto < xjugador + anchoJugador) Y (yPunto > yJugador) Y (yPunto < YJugador+largoJugador) ENTONCES El punto se encuentra dentro del rectángulo -> COLISIÓN DETECTADA.
         o - Para comprobar colisiones con círculos:
           SI (suma de los radios) > (distancia centroJugador, centroObjeto) ENTONCES COLISIÓN DETECTADA.
   * Si los objetos del juego están constituidos por vértices y aristas podemos aplicar funciones de intersección entre aristas, puntos y planos. Esta es una solución más costosa pero más certera que la anterior. Podríamos obstar por soluciones intermedias, como tener un modelo en muy baja poligonización para la detección de colisiones y otro para la representación gráfica. O tener al jugador dividido en partes y aplicar bounding boxes a cada parte para luego comprobar a nivel de superficie sólo las partes que dieron positivo en el primer test.
   * Podemos usar árboles BSP (partición binaria del espacio) para dividir recursivamente las BB y obtener más precisión

.
.
.

Hay decenas de técnicas, por ahora creo que está bien como introducción, más abajo dejo unos cuantos links para los que quieran profundizar. ¡¡Y ahora viene la sorpresa!!

Esta semana me puse un ratillo y completé el menú y el sistema de fases de un juego inspirado en el Asteroids que comencé hace tiempo. La verdad es que quería añadir algunos detalles más, sobre todo gráficamente para explotar un poco el pequeño sistema de partículas que implementé, pero hacía tiempo que no lo cogía y le había perdido ganas, así que por ahora estoy contento con poder mostrar un juego cerrado. Es totalmente procedural, como todos mis jueguecillos hasta ahora (nada de imágenes, solo código).

La detección de colisiones es a nivel de aristas, Java provee de funciones para el cálculo de intersecciones entre aristas y rectángulos y decidí utilizar las aristas ya que los polígonos de los meteoros y la nave están almacenados como listas de vértices. No divido la pantalla ni en cuadros ni nada de eso ya que el juego no requiere demasiado y yo no quería meterme en más fregados (a mi no me consume ni un 10% de CPU, comentadme que tal os va).

Espero que os divertáis un poco, si os picáis dejadme comentada vuestra puntuación máxima. ;) Yo no he podido jugar mucho, ni siquiera he llegado a los octaedros, me quedé en los 32000 puntos. :P

El juego: Podéis jugar desde el Blog o pinchando AQUÍ

(Para jugar es necesario tener instalado el JRE 1.6 - Java Runtime Enviroment -)

Enlaces para ampliar: (en inglés, encontré poco que rascar en español...)

GamesPP - Varios tutoriales, desde lo más básico a técnicas avanzadas.
N toturials - Explicaciones básicas con código y un bonito Applet de ejemplo.
Team gamma - Más técnicas, papers, videos...
Esto mismo en BLOG - algo mejor formateado y más accesible :)

[Mars Attacks]

A mí el juego no me va (los controles no responden, para ser exactos).

Ubuntu Feisty, firefox, etc.

De nuevo, sigue con los temas. Quedará una recopilación chula para los recién llegados al mundillo :)

[Güarmigue]

Mars Attacks, ¿no te va el ratón o el teclado? Yo uso firefox en windows y un amigo lo ha probado en exprorer, pero nade en Linux que yo sepa

¿Alguien con linux que comente que tal le va?

[senior wapo]

A mi me pasa igual en Linux. Ubuntu Feisty con jre 1.6. El ratón va, elijo el menu de jugar pero la nave no responde al teclado. Ni en Firefox ni en Opera.

Probando otros juegos java en Internet me funciona perfectamente el teclado.

[Güarmigue]

Mmm estoy mirando un poco en google y por ahora no encuentro porqué podría ser... En la documentación del KeyEvent no habla de ninguna incompatibilidad y no encuentro apenas resultados de foros o problemas similares.

Mi código es bastante simple en este aspecto:

public void keyPressed(KeyEvent e) {
      
      //variables locales
      int letra = e.getKeyCode();
      
      
      //codigo
      switch(letra){
         case KeyEvent.VK_W: jugador.setAcelerar(true); break;
         case KeyEvent.VK_S: jugador.setFrenar(true); break;
         case KeyEvent.VK_A: jugador.setGirarIzquierda(true); break;
         case KeyEvent.VK_D: jugador.setGirarDerecha(true); break;
.
.
.

Simplemente recibe el KeyPressed, toma el código de teclado y comprueba qué tecla se pulsó... ¿Alguién sabe qué puede ser?

[shadow_of__soul]

hi,

yo tengo ubuntu 6.10 y no anda el teclado ademas que en el medio dnd esta la nave hay una ventana muy chica q apenas se ve pero se puede agrandar y todo y cuando la cerras se regenera xD

By Shadow

[Güarmigue]

:shock: ¿ventana chica que se regenera?

:evil: Odio Linux :P

Editado: Se me ocurre... Si podéis probar ESTE JUEGO o ESTE OTRO Y decirme si os funcionan me haríais un favor. Son otros dos mini juegos mios y cada uno de ellos utiliza el teclado de forma distinta, a ver si os funcionara alguno  :wink:

[senior wapo]

En los enlaces que pones no hay donde pinchar para jugar el juego, solo hay para bajarte el archivo .jar

Si me intento crear un .html para cargarlos desde el navegador me sale "Invalid Bytecode".

Ponlos como el meteoros, en una página donde se pueda jugar desde el navegador :p

[shadow_of__soul]

:shock: ¿ventana chica que se regenera?

:evil: Odio Linux :P

Editado: Se me ocurre... Si podéis probar ESTE JUEGO o ESTE OTRO Y decirme si os funcionan me haríais un favor. Son otros dos mini juegos mios y cada uno de ellos utiliza el teclado de forma distinta, a ver si os funcionara alguno  :wink:

El problema no es linux, es el programador  :twisted:

ponlo en una pagina y te lo pruebo

:lol:

By Shadow

[Güarmigue]

jajaja, hombre no he usado nada raro, KeyEvent y keyListener no deberían dar problemas no?? ;)

Solo tienes que clickar en DOWNLOAD y luego hacer doble click sobre el .jar,  no son applets, son ventanas, exigencias de la JAVA4k...

[senior wapo]

Abriéndolos por separado si que funcionan. En ambos va bien el teclado.

Para los que quieran probar en Ubuntu: Haciendo doble click sobre los .jar los abre como archivos .ZIP (total, es lo que son) asi que para ejecutarlos hay que escribir desde consola:

Código [Seleccionar] Expand

java -jar archivo.jar

O eso o cambiar la acción de la asociación .jar del explorador de archivos.

[Güarmigue]

Si, de hecho yo tuve que cambiar también la asociación de archivo en windows... nunca lo recuerdo, gracias senior_wapo.

Tomo nota de los fallos en Ubuntu. Aun no he podido arreglarlo, pero indagaré en el tema ;)