Colisiones en una CPU saturada

[mi-go]

Buenas!!

Tengo una duda con las colisiones.

El control básico de colisiones que he visto hasta ahora, tanto en 2D como en 3D, es el de ver si la posición a la que se tiene que mover un objeto está ya ocupada o no por otro objeto y si no lo está entonces se puede mover a esa posición.

Bien, ahora parto de la base de que los movimientos de los objetos se basan en el tiempo que pasa entre un ciclo y otro de nuestro main game loop para que el movimiento sea siempre correcto en el tiempo.
Pero se me plantea el caso (en mi cabeza  :D ) de que, en un estado de saturación de la CPU, haya pasado tanto tiempo que el objeto que tenemos que mover pueda atravesar otro objeto debido a un movimiento que casi podríamos llamar teletrasportación  :D

Me explico con un ejemplo llevado al extremo para que se vea claro:
Tenemos una bola que avanza 1 posición por segundo hacia una pared fina que se encuentra a 5 posiciones de distancia.
En un buen estado de la CPU actulizará la posición de la bola 30 veces por segundo por lo menos, así que cuando llegue a la pared la detectará sin problema (le han sobrado muchas comprobaciones).
Pero si la CPU estuviera muy cargada y cada ciclo del game loop tardara 10 segundos en ejecutarse (es un caso extremo para el ejemplo) la actualización de la posición de la bola sería posicionarla 10 posiciones hacia delante, comprobando antes que hay no chocara con nada, y lo haría!!!   habría atravesado la pared!!!

¿esta comprobación de colisiones que tanto he visto no es correcta??

[Pogacha]

Hay un monton de approaches para el problema que planteas y cada uno va a ser mejor o peor en distintos tipos de circunstancias.



Te puedo ayudar con el tema de la variacion del frame rate:

Código [Seleccionar] Expand

while( t < MIN_TIME )  t = tiempo_transcurrido();

while( t > 0)
{
  if( t > MAX_TIME  )
  {
     Update(  (MAX_TIME+MIN_TIME)/ 2  );
     t -= (MAX_TIME+MIN_TIME)/ 2 ;
  } else {
    Update( t );
    t = 0.0f
  }
}

Draw();

Para lo de las detecciones de colisiones va a depender de tantas cosas que no te puedo decir nada ... te toca investigar mas alternativas ...

[davidgf]

Buenas!

Si lo implementas tu solito tendrás que buscarte la vida!
En las librerías de física depende:
En ODE, que es una librería discreta en tiempo, no comprueba eso, por esa razón no se le puede decir a ODE que simule de golpe un salto de medio segundo, ya que pasa lo que dices tu, se pasa de la pared.
En cambio y si no me equivoco Bullet es contínua y intenta evitar eso mismo.

Saludos!

[Vicente]

Si no estoy muy espeso ese efecto que comentas se llama "tunneling". Buscando un poco salen bastantes artículos del tema que lo mismo te pueden ayudar :)

Un saludo!

Vicente

[mi-go]

Gracias a todos!

He encontrado este artículo:
http://www.gamasutra.com/features/20000330/bobic_01.htm

En el apartado The Big Picture trata este tema con varias soluciones. Todas más complejas y más costosas para la CPU   :D

No pienso hacer eso, porque no lo necesito, pero por lo menos he aliviado mi duda y me pregunto que juegos usaran esas técnicas y cuales no, jeje.
A la hora de usar un motor de físicas sería interesante saber si usa alguna de estas técnicas o no.

[mi-go]

Bueno, quería añadir que según http://www.gamasutra.com/view/feature/4199/book_excerpt_game_engine_.php?page=5 el motor de físicas Havok guarda el estado anterior de todos los objetos para cosas como estas.

Another benefit of state caching is that we can linearly interpolate between the previous and next states in order to approximate the state of an object at any moment between these two points in time. The Havok physics engine maintains the previous and current state of every rigid body in the simulation for just this purpose.