Tiled Based Games - Deteccion De Colisiones

[josette]

    Como se implementa un sistema de colisiones en un tiled based game?

  Lo mas inmediato es tomar todos los elementos que estan en la capa del player y detectar colisiones con el resto de elementos de esa capa.´

  Pero eso requiere mucho tiempo si hay muchos elementos. Se me ocurre de hacer que cada sprite ponga sea apuntado desde todos aquellos tiles del mapa que ocupa y al detectar colisiones solo hay que mirar si en los tiles que ocupa hay algo que tb es colisionable. A mas elementos mas comprobaciones, pero no incrementa tanto el tiempo, pero tb esta gestion es mas compleja ya que hay que ir actualizando los punteros a objetos en los tiles del mapa.

  ¿Como se hace normalmente la deccion de colisiones en este tipo de juegos?

[TheAzazel]

 Normalmente, lo mas rapido es hacer un bounding box entre los elementos colisionables.
Luego si quieres pixel perfect collision, los que den positivo en el bb...les haces el test de por pixel, este ya es mas lento pero el bb es rapidisimo.

Tambien, dependiendo de la forma de tus objetos, se puede variar y en vez de utilizar un bb..se puede hacer por una aproximacion circular que tambien va como un tiro(en comparacion con hacerlo pixel a pixel).

Como siempre, todo depende segun lo que quieras hacer y conseguir, un juego de plataformas a lo sonic por ejemplo y si no me equivoco solo hacia bb y a que casi no se notaba? yo porque lo ponia al limite para ver como leches detectaba las colisiones... jeje.

Por cierto, sabeis ya lo que quereis conseguir? y el engine que utilizareis?
Y no es por nada, pero un juego de plataformas no es tan sencillo como parece... si yo fuera vosotros empezaba por lo mas basico de lo basico: un pong. Asi cogeis un poquito de experiencia tanto del engine a usar como de toda la logica del juego. Y esto no os retrasaria mucho, en un par de semanas a lo sumo, lo podeis tener terminado y si disponeis de mucho tiempo...en un par de dias estara listo :)

[marcode]

 La segunda opción está bien, además te puede servir para más cosas.

En cuanto  a su complejidad no es tanta, solo tendrías que actualizar la celda sobre la que haya un objeto que acaba de actualizar su posición, y hacerlo de manera que uno a otro se apunten mutuamente. Antes debes de desapuntar la celda a la que apunte el objeto.

Seguramente tendrás que hacer un array de apuntadores a objetos en cada celda para que puedan haber varios a la vez.

[tamat]

 más o menos como tu dices, se usa un contenedor donde los datos se almacenen en función de su posición, cuando el objeto se mueve por el mundo se actualiza su posición en el contenedor. Puedes usar por ejemplo un array en el que cada posición tiene una lista enlazada de objetos (sprites), decides que cada posición del array ocupará una cantidad de espacio del mundo, por ejemplo 500 pixeles de ancho. Entonces si un objeto está en la posición x=730 pues lo metes en la posición 1 del array ya que la cero va de 0 a 500, la 1 de 500 a 1000, etc.

Luego a la hora de calcular colisiones te limitas a mirar en tu casilla del array, eso sí, cuando desplaces los objetos tienes que actualizar su posición en el contenedor.

Nunca recuerdo el nombre de este contenedor, Space nosequé.

[zupervaca]

 Antes de nada hay que mirar que tipo de juego se esta haciendo ya que muchas veces los enemigos no tienen por que realizar colisiones, es decir, siguen caminos prefijados, en la mayoria de los juegos es asi, no obstante uses lo que uses solo debes de comprobar o mover los sprites u objetos que esten dentro de un rango, si te fijas antiguamente los juegos solo hacian scroll en un sentido y nunca se podia volver atras, este motivo (a parte de otros) es que los sprites solo se creaban cuando se llegaba a una posicion determinada del scroll y eran destruidos cuando salian por el extremo contrario, actualmente un juego que solo deje el scroll en un sentido hacer perder jugabilidad con lo que este sistema queda descartado, la solucion es hacer que todo aquel sprite que este funcionando se desactive al estar a cierta distancia del personaje principal o el que esta haciendo scroll, cuando sale de esta distancia debes de poner en su posicion del mapa un bloque o tile que indique que ese enemigo esta ahi (por ejemplo un int con el indice de enemigos o el puntero a el, ademas debes de tenerlo preparado para que varios enemigos puedan estar ahi), cada vez que se hace scroll superior al tamaño del ancho y alto de los tiles se debe de comprobar dentro del rango del mapa si algun tile tiene un indice a un enemigo, si esto es asi se debe de volver a activar.

Sobre el tema del hilo, para comprobar colisiones en un juego 2d sobre el mapa, lo primero es mirar si el tile es pasable o bloqueante, cuando es pasable no hay que hacer nada, pero si es bloquenate deberias de comprobar en que direcciones bloquea, es decir, izquierda, arriba, abajo y/o derecha, si por ejemplo el tile no deja pasar a la izquierda siempre que un sprite vaya en esa direccion deberia de pararse.
Otro sistema es el tener una imagen de colision del tile, es decir, un tile en blanco y negro por ejemplo que indique la colision, otro sistema derivado de este que es el que mas me gusta usar es tener 4 arrays de colision por tile que definen la posicion colisionable del tile, cada uno de estos arrays indica las colisiones por arriba, abajo, izquierda y derecha, con un tile de 8 de ancho tendriamos un tamaño de 8 a los dos arrays de arriba y abajo, en estos arrays meteriamos el offset de colision a la posicion del tile, es decir, si el tile esta en las coordenadas 100, 100 y el sprite en las 105, 101 tendriamos que mirar lo primero el tile con el que puede estar colisionando, si colisiona miramos el array de colision arriba segun la posicion x del sprite menos la posicion x del tile (105-100=5), dentro del array de colision arriba en la posicion 5 puede tener un valor entre 0 y la altura del tile que seria el incremento de colsion a comprobar para saber a que altura debe de estar el sprite, es decir, si tiene 3 el sprite puede bajar hasta 100+3=103, el sprite seguiria cayendo hasta llegar a la coordenada 103, si supera esta altura debe de ponerse inmediatamente en la 103.

Espero que se entienda, los sistemas que indico pueden ser algo complicados, pero a la larga ganas mucha velocidad, sobre todo en mapas muy grandes.

[josette]

 zupervaca, el sistema de colision que mencionas a lo ultimo es el que he usado en el 'juego' que puedes descargar desde mi web(no reirse, esta en desarrollo), aunque no funciona bien. Ademas cuando se inicia este juego el player empieza a caer y cae tres veces por lo menos y es porque el incremento de posicion sobre pasa dos tiles y claro lo que hay por medio no lo detecta y es como si no hubiera nada y por eso cae.

  Mi idea era la de poner a todo aquel que colisione en una misma capa asi cuando compruebo colisiones me evito comparaciones innecesarias. Otra cosa que tengo duda es como hacer para detectar colision en un tile solo por un lado. Tiene que ver algo la posicion por la que entro en el bloque?


TheAzazel: Lo de que engine usar todavia lo tenemos que ver. Sugieres alguno?

[_XUTI_H_]

 Yo me decanto también por tener un mapa off-screen que tenga información sobre las colisiones o cualquier otro "efecto físico del escenario". Así podrias tener un "physic layer" por llamarlo de alguna manera, donde cada tile tenga información de la posición relativa de colision respecto al tile, etc. (lo que ha comentado zupervaca antes), y además cualquier propiedad especial que pueda tener el tile en cuestion (lava que quema, estar por debajo/superfice de agua, etc..).
Si el tamaño de los tiles es potencia de 2, saber que tile corresponde a un punto es muy facil y rapido, solo tienes que realizar el desplazamiento n a la derecha de la coordenada original (donde n es la potencia de 2).

El tema de plataformas y otros objetos moviles es sencillo de optimizar si puedes mantener los objetos ordenados por sus coordenadas. Por ejemplo (lexicograficamente) por coordX y/o por coordY.
Si mantienes en un array (o lista enlazada en su defecto podria funcionar muy bien, las STL son muy utiles en estos casos) todos los objetos que puedan interactuar entre ellos, al buscar las posibles colisiones puedes reducir el numero de comprobaciones, ya que:
- Si recorremos el array (lista en su defecto) de forma ordenada cada uno de los elementos solo podrá colisionar con los objetos anteriores o con los posteriores hasta llegar a uno con una coordX mayor que nuestra coordX + anchura. En eeste momento el bucle se rompe y podemos seguir con el siguiente elemento. Un ejemplo en pseudocódigo podria ser:

Código [Seleccionar] Expand

for (int i = 0; i < tam_array; i++) {
   for (int j = 0; j < tam_array; j++) {
       if (i == j)
           continue;

       if (colisiona(array_objs[i], array_objs[j])
           interacciona(array_objs[i], array_objs[j]);

       if ((array_objs[i].x + array_objs[i].w) < array_objs[j].x)
           break;
   }
}


Algunas anotaciones sobre esta idea:
+ se llama tanto a interactua(i, j) como a interactua(j, i);. Si esto no es lo requerido, es decir, basta con llamar a una de las dos funciones, podemos modificar el código para evitarnos estas comprobaciones.
+ ¿Se podria optimizar más?, puede, realizando particones espaciales quizás, o manteniendo punteros que relacionen los objetos con los tiles que ocupan como se proponia en un principio (pero cuando se muevan dichos objetos el coste de computación aumenta).
+ La ordenación. Esto supone un coste extra, pero puede ahorrarnos mucho más dependiendo de la organización (y tb cantidad de sprites/objetos/enemigos/etc) del nivel actual. Si se opta por almacenar los datos en un array se podria sacar provecho del qsort, aunque otros algoritmos podrian venir mejor si tenemos en cuenta que los objetos que se muevan no se desordenarán demasidas posiciones (por normal general) de la que ocupaban en el frame anterior.

Nueno, y con esto y un bizcocho ...
Espero que te haya servido de ayuda
Y si alguien detecta un fallo en el planteamiento o una posible optimización estaria muy interesado en escuchar vuestra opinión al respecto.

Un salu2

PS: al final el pseudo-código se ha quedado más bien en C-ódigo :P

EDIT: acabo de leer esto

Ademas cuando se inicia este juego el player empieza a caer y cae tres veces por lo menos y es porque el incremento de posicion sobre pasa dos tiles y claro lo que hay por medio no lo detecta y es como si no hubiera nada y por eso cae.

Mi idea era la de poner a todo aquel que colisione en una misma capa asi cuando compruebo colisiones me evito comparaciones innecesarias. Otra cosa que tengo duda es como hacer para detectar colision en un tile solo por un lado. Tiene que ver algo la posicion por la que entro en el bloque?

A ver, en mi opinión:
1) lo de comparaciones innecesarias se solucionaria con el método propuesto anteriormente para los objetos moviles (colisiones entre si).

2) Te conviene guardar la posicion anterior de tus sprites o la velocidad en su defecto. Con esto podrias saber por que lado del tile colisionas. Además de poder interpolar las coordenadas para saber si has atravesado algo. Sule venir bien un bresenham modificado (algoritmo que sirve para dibujar lineas pixel a pixel) para recorrer este trayecto, y además es muy rápido.

[josette]

 

Además de poder interpolar las coordenadas para saber si has atravesado algo. Sule venir bien un bresenham modificado (algoritmo que sirve para dibujar lineas pixel a pixel) para recorrer este trayecto, y además es muy rápido

Esto es interesante para movimientos con mucho desplazamieto. Esto es interesante (ole).

Ok como se ha dicho con esto y un bizcoho ya hay para rato.

Voy a modificar mi web y voy a poner las novedades que voy haciendo asi podeis ver los progresos. Tb dejare el coigo fuente.

[AgeR]

 josette, yo te recomiendo que pruebes al menos la librería de TheAzazel o la Looverlib (la de [EX3] supongo que no porque es para VB). Echales un ojo a los ejemplos y a la documentación, y haz algunas pruebas antes de hacer nada. Si no me equivoco, seguramente las dos tengan rutinas para detección de colisiones como las que quieres.

[josette]

 Ya les he echado un vistazo y he cogido algunas ideas de los fuentes, una de ellas lo del StaticWindowProc.