Uruguay Gamer » Elaboración » Detección de Colisiones
Detección de Colisiones
-
Andaba diseñando un juego arcade "tipo supermario" y tuve una duda enorme sobre la detección de colisiones.
Que manera tengo para controlar colisiones sin tener que hacer una comparacion "cartesiana" entre todos los objetos del nivel (que pueden ser muchos) (100obj x 100obj = 10000comparaciones/frame)
Me parece extremadamente ineficaz (y no quiero hacer un juego tipo supermario y que se me tranque!!)
Así que tiro un ejemplo:
Como hacer para comparar cada objeto con sus proximidades solamente?Es una idea muy en el aire, si alguno tiene alguna forma eficaz de detectar colisiones me serviría pila que me la explicara!!
//uso C++ (POO) y SDL
-
Tenes varias formas, en 2d lo mas fácil es utilizar una matriz de dos dimensiones . La idea es poner todos los objetos en los diferentes cuadrantes, y después solo tenes que comparar con los cuadrantes adyacentes al objeto en movimiento. Los objetos que se mueven se tiene que actualizar en la matriz para mantenerla coherente.
El concepto que buscas se llama broad phase por si queres buscar otras soluciones.
-
Hace unos meses para un juego tuvimos que investigar esto, si googleas "broad-phase" y "narrow-phase" aparece de todo, pero el mejor artículo por lejos es el de metanet Software y su juego N.
http://www.metanetsoftware.com/technique/tutorialB.html
Es ActionScript pero los conceptos se aplican igual.Saludos,
Fernando. -
@fsansberro escribió:
Hace unos meses para un juego tuvimos que investigar esto, si googleas "broad-phase" y "narrow-phase" aparece de todo, pero el mejor artículo por lejos es el de metanet Software y su juego N.
http://www.metanetsoftware.com/technique/tutorialB.html
Es ActionScript pero los conceptos se aplican igual.
Saludos,
Fernando.Ese esta muy bueno porque no es muy lagro y te da mucha de la información mínima que precisas para colisiones pero para mi ese articulo le falta hablar un poco de la resolución de la colisión. Hace poco encontré un blog buenísimo, que es un gran complemento al articulo de esta gente.
http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/
http://www.wildbunny.co.uk/blog/2011/04/06/physics-engines-for-dummies/
El segundo link si fuera un capitulo en un libro probablemente seria el mejor capitulo del libro.
-
La parte 2 es excelente.
Lo básico del "bread phase" ya lo entendí. Puedo detectar posibilidades de colisión (cosa bastante simple).
Ahora esos tutoriales que me pasaste ahí están excelente para detectar si hay una colisión efectivamente.
//Lastima que me va a costar un montón entender y aplicar eso ya que mis conocimientos de geometría y física son bastante escasos...P.D. El capitulo 2 es excelente!!
-
Si la cantidad de objetos es muy elevada, te recomiendo que utilices una técnica llamada Quadtree, básicamente consiste en una división recursiva de la escena, hasta alcanzar que cierta cantidad de objetos queden dentro de un rectángulo, con lo que se logra que solo se calcule colisiones para los objetos que están dentro del mismo rectángulo.
Otra cosa a favor es que es fácil modificar y de utilizar para ambientes 3D (en este caso se llama Octree).
Esta es una imagen de mi engine usando Octree, las divisiones de la escena son las lineas amarillas.
-
Vi esta técnica... Pero lo que me está costando ahora es como "organizar" todos estos objetos de manera que pueda consultar sus posiciones facilmente... MÁS SI HAY "ENEMIGOS RANDOM!!!"
Imaginate que tengo 2 pisos y 3 "bichos". Estas 5 entidades tienen un rectangulo asignado que indica su posición a grandes razgos.
Ahora, cuando quiero consultar sus posiciones (rectangulo) para ver si están en una posible colisión, ¿Tengo que consultar una y otra ves esos elementos hasta descartar que estén en colisión (o que estén)?Como dije, si hay vichos random O gran cantidad de bichos, no me lo imagino como codificarlo (como hacerlo en si!). Osea lo único que me imagino (que es muy ineficiente) es hacer un arbol gigante de condicionales viendo objeto por objeto si está en posible colisión...
Ya el rendimiento mejoró respecto a mi primera idea... Pero sigo sin idear algo "generico"! -
Divide y conquistaras, esa frase es muy importante en el tema de las colisiones. Como me parece que no captaste básicamente la idea, va de nuevo paso a paso y bien básico.
Lo que llamo escena, es lo que ve la persona que esta jugando tu juego, supongamos que esa escena tiene un tamaño de 800 x 600 pixeles.
Ahora en esa escena tenes 20 objetos (entidades) de varios tipos, jugadores, enemigos, objetos, items, decorado, etc. todos con posibilidades de colisión y repartidos por toda la escena.
Ahora, es evidente que efectuar un chequeo de 20 objetos es algo ineficiente, porque sabes que hay objetos que están en otras posiciones y difícilmente choquen. Por esa razón lo que hacemos es dividir la escena en cuatro partes (o mas, según sea necesario), así que nuestra escena de 800x600 quedara dividida en 4 cuadrados imaginarios de 400x300 cada uno.
Cada uno de esos cuadro (1, 2, 3, y 4) sera una lista (de punteros) con los objetos que estén dentro de ese cuadro. La primera vez esa lista se llena tomando las posiciones (X,Y) de los objetos y según su posición se les asigna al cuadro correcto. Cuando el juego este corriendo, la forma correcta de actualizarlo es sabiendo que objeto se movió, osea, nuestro objeto tendrá una función onMove() y esa función le avisara al cuadrado que el objeto cambio de posición y hay que revisar en que cuadrado quedo ese objeto.
Ahora teniendo a las listas que representan nuestro cuadrados, podemos realizar menos chequeo para saber si un objeto colisiona con otro objeto. Si tenemos un objeto en el cuadrado 1, ese objeto no puede colisionar con un objeto que este en otro cuadrado (por ej. el cuadrado 2) solo podrá colisionar con un objeto dentro de su mismo cuadrado.
Esta es una explicación muy básica, con el objetivo de que entiendas como podes disminuir la cantidad de chequeos por colisión. Supongo que te abras dado cuenta que un problema de este sistema es que es posible que algún objeto este en los cuatro cuadrados al mismo tiempo, porque es muy grande o porque justo cae donde se cortan los 4 cuadrados.
-
Salado! Ahora entendí bien esa tecnica... Que problema el de los 4 cuadrados, me lo había imaginado... Puede que exista multiples colisiones en cuadrados diferentes!! AHHH!!! Que mutante!!!
A veces ves cosas como Unity que te resuelven todo, y uno para hacer un motorcito gráfico bien malo se arranca los pelos... Igual quiero hacerlo!!!
Voy a tratar de hacer un programa simple que integre colisiones... Capaz que así veo como ir solucionando los problemas.
"Muchisimas" gracias por la ayuda!!!
Reply
You must log in to post.