Ey piratas.
Estoy haciendo un engine raycaster 2.5D en C porque no echan nada en la tele y aun no hay liga.
Estoy metido con el tema de las colisiones. Detecto correctamente cualquier tipo de colisión, pero no consigo responder correctamente a ellas. En concreto, haciendo ciertos movimientos, me cuelo en las esquinas:
Si suena la flauta y alguno teneis idea de como puedo solucionar el asunto, me haríais muy feliz. Podeis echar un vistazo a la función que responde a las colisiones aquí.
#1 Normalmente cuando las paredes no son planos de 1px, puedes utilizar algunas técnicas de restitución de la posición cuando se detecta que estas atravesándolo. Normalmente la detección de colisiones se ve afectada por el paso/iteración de las fisicas del sistema. Esos pasos, aunque se pretenda hacerlos constantes a veces fluctuan minimamente, viandose la física afectada.
Mi experiencia es 100% con 3D pero bueno...Lo que yo creo es que dada la anchura(casi inexistente) de las paredes, en algún momento los valores se van de madre y te introduces en el cuerpo. Dado que es tan estrecho, no te dará tiempo en la vida a aplicar técnicas de restitución al jugador. Mis consejos son dos:
Échale un ojo a técnicas de restitución que igual podrían solucionarte cosillas,aunque lo veo díficil por la anchura. Pero si detecta la colisión perfectamente, podrías aplicar un pequeño 'rebote' (como sucede en la vida real) para evitar que tu personaje penetre en las paredes...
A ver si sacas algo claro de aqui:
http://gamedevelopment.tutsplus.com/tutorials/how-to-create-a-custom-2d-physics-engine-the-basics-and-impulse-resolution--gamedev-6331
Para detectar si dos AABB colisionan es muy fácil y eficiente:
def AABBvsAABB(boxA, boxB):
boxA_position = boxA.get_position()
boxB_position = boxB.get_position()
if(abs(boxA_position.x - boxB_position.x) >= (boxA.halfWidths.x + boxB.halfWidths.x)): return False
if(abs(boxA_position.y - boxB_position.y) >= (boxA.halfWidths.y + boxB.halfWidths.y)): return False
return True
Una vez detecto dicha colisión, verificando todos los AABB de la escena 2 a 2, excepto consigo mismo, comienza una fase de resolución de colisiones.
Para resolver el AABB vs AABB, me invente este algoritmo de boli y papel, que es algo lento, pero funciona:
def AABBvsAABBResolution(boxA, boxB):
center = boxB.get_position()
intMin = copy.copy(boxA.aabbMin)
intMin.x = intMin.x - boxB.halfWidths.x
intMin.y = intMin.y - boxB.halfWidths.y
intMax = copy.copy(boxA.aabbMax)
intMax.x = intMax.x + boxB.halfWidths.x
intMax.y = intMax.y + boxB.halfWidths.y
points = ( (((center.x), (intMax.y)), (0,1)),
(((intMax.x), (center.y)), (1,0)),
(((center.x), (intMin.y)), (0,-1)),
(((intMin.x), (center.y)), (-1,0)))
float_big = 999999.0
distance_min = float_big
normal_sel = (0, 0)
for p, normal in points:
direction = Vector3(p[0] - center.x, p[1] - center.y)
distance = direction.LengthSq()
if distance < distance_min:
distance_min = distance
normal_sel = normal
if(distance_min < float_big):
return center + (Vector3(normal_sel[0], normal_sel[1]) * math.sqrt(distance_min))
else:
return center
Esta función tiene como precondición que A y B colisionan. La función devuelve la nueva posición de B, que resuelve la colisión, desplazandolo por el lado más corto, muy simple.
Ok vamos a dar un poco más de contexto.
Mi algoritmo está basado en este paper que describe un algoritmo para detección de colisiones en 3D de elipsoides contra triangulos. Simplemente lo he reducido a dos dimensiones.
El jugador está representado por un "Mobile": un vector posición, un vector velocidad y un radio. En cada tick del juego, si no hay colisiones, la nueva posicion del jugador es simplemente:
new_pos = old_pos + velocity;
Las paredes están representadas por segmentos. Un segmento no es más que un punto inicial y un punto final, representados por vectores.
Hasta ahora, los únicos structs importantes:
typedef struct Vector {
double x, y;
} Vector;
typedef struct Mobile {
Vector pos, vel;
double radius;
} Mobile;
typedef struct Segment {
Vector start, end;
} Segment;
A vista de pájaro el algoritmo tiene dos fases, Deteccion y Respuesta.
Detección:
Dado un Mobile y un array de Segments, obtener el Segment con el que menos distancia hay que recorrer para colisionar, y el punto de colisión.
Respuesta:
Moverse un poquito menos que la distancia hasta la colisión (para evitar meterse por accidente en la pared), calcular la velocidad restante.
Calcular la tangente al círculo del Mobile en el punto de colisión, y proyectar la velocidad restante sobre esta dirección.
Repetir el proceso (deteccion y respuesta) con esta nueva velocidad, hasta que no haya colisiones o la velocidad sea muy pequeña.
Esta teoría funciona perfectamente excepto en el caso del gif. Tiene que ser culpa de la fase de respuesta porque si la reduzco a "si hay colision -> no te muevas", nunca me cuelo por nada.
Se que es mucha tela, he posteado más que nada por frustración xD llevo bastantes horas dandome cabezazos con esto, y ni si quiera he conseguido crear un test que me reproduzca el fallo.
Igual te estoy contando algo que ya has probado mil veces, pero has probado algo así, por cada frame:
for _ in range(8):
for obj1 in rigid_bodies:
for obj2 in rigid_bodies:
if obj1 != obj2:
if obj1.is_collision(obj2)
obj2.set_position( resolve_collision(obj1, obj2) )
Lo interesante es la primera linea, es decir repetir todo tu algoritmo N veces. En physX o Havok esa constante es la llamada "solver iteration count", que suele ser 4 u 8, pero algunos ragdoll conflictivos pueden necesitar valores como 30.
Me fuí el finde a la piscina y en el agua se me ocurrió la solución!
El problema es que seleccionaba la colisión más cercana mediante la distancia posicion_jugador <-> punto_de_colisión, pero lo que importaba era seleccionar la colisión para la que había que moverse menos distancia!
Ahora no me cuelo jamás por ningún sitio, aunque en cierto tipo de esquinas "tiemblo", pero es mucho menos crítico. Este problema está relacionado con el número de veces que itero (lo que dice #5) pero es mucho menos molesto y lo tengo más o menos acotado.
WebM en glorious 640x400: