AABB 2D y resolución de colisiones múltiples

Bien, entonces este es un problema que he estado tratando de resolver por bastante tiempo. El mío es un juego de plataformas en 2D con un mundo compuesto (generalmente) de fichas inmóviles y sprites móviles, los cuales usan AABB para representar sus hitboxes. Este juego NO está basado en cuadrículas debido a algunas complicaciones con el movimiento de capas de fichas.

Puedo detectar colisiones y determinar fácilmente la profundidad de la colisión. Utilizo el "método del eje menos profundo" para determinar la forma de resolver una colisión entre el sprite y el mosaico. Si el sprite es más profundo horizontalmente que verticalmente, la dirección para resolver es hacia arriba o hacia abajo. Si el sprite es más profundo verticalmente que horizontalmente, la dirección para resolver es izquierda o derecha.

Esto es bastante simple y funciona bastante bien. Es decir, hasta que tenga un sprite que choca con más de una ficha. Como, por su naturaleza, cada colisión debe verificarse por separado, las diferentes colisiones pueden tener una dirección diferente para resolver. Por ejemplo, si un sprite está tratando de caminar a través de una fila de fichas, para un cuadro se cruzarán con la siguiente ficha. que la profundidad horizontal es más corta que la profundidad vertical. Como la colisión dice "resolver a la izquierda", se retrasará y quedará atascado en la esquina.

He estado reflexionando sobre este problema una y otra vez durante bastante tiempo, y se me han ocurrido varias soluciones, pero todas tienen fallas. Podría marcar ciertos lados como inalcanzables, pero sin un motor basado en la cuadrícula, determinar la "inalcanzabilidad" es notablemente complejo, especialmente con la posibilidad de mover capas de mosaicos.

Otro método posible sería predecir colisiones antes de que sucedan y "retroceder" el movimiento hasta el punto de la colisión, supongo, pero no estoy seguro de cómo funcionan las matemáticas.

Siento que me falta algo increíblemente obvio, especialmente porque los juegos de los años 80 ya han resuelto este problema.

El problema

El problema radica en su método de resolución de colisiones. Su método es el siguiente:

1. Mueve al jugador.
2. Verifique la colisión.
3. Determine la profundidad de colisión más corta.
4. Resolver colisión.

El problema con esto es que puede mover fácilmente al jugador en la dirección equivocada. Puede ver cómo puede suceder esto en la imagen a continuación:

Debido a que el jugador se está moviendo hacia abajo a la derecha y está por encima del suelo, es de esperar que el jugador aterrice en la parte superior del suelo (junto al cuadro verde). Pero en cambio, se empuja fuera del suelo hacia la izquierda (representado por el cuadro rojo). Esto puede ser un problema si el jugador está tratando de saltar de una plataforma a otra, porque el jugador puede terminar cayendo a su muerte debido a un código de colisión incorrecto.

La solución

La solución a este problema es realmente bastante simple. En lugar de utilizar el método anterior, resuelve la colisión de esta manera:

1. Mueve al jugador a lo largo del eje X.
2. Verifique si hay azulejos colisionantes
3. Resolver X colisión.
4. Mueve al jugador a lo largo del eje Y.
5. Verifique si hay azulejos colisionantes
6. Resolver colisión Y.

Ahora espero que no haya tirado su código de verificación de profundidad, porque todavía lo va a necesitar para los pasos 3 y 6.

Para resolver la colisión entre fichas en cualquiera de los dos ejes (después de mover al jugador), primero obtienes la profundidad de la colisión. Luego, toma la profundidad de la colisión y la resta de los ejes que actualmente está buscando para colisión. Tenga en cuenta que la profundidad debe ser negativa si se mueve hacia la izquierda, de modo que el jugador se mueva en la dirección correcta.

Con este método, no solo no tendrá que preocuparse por errores de colisión como el del escenario en la imagen de arriba, sino que este método también puede manejar la colisión con múltiples mosaicos.

Código de ejemplo:

void move(velocity)
{
    top = player.y / TILE_HEIGHT;
    bottom = top + (player.height / TILE_HEIGHT);
    left = player.x / TILE_WIDTH;
    right = left + (player.width / TILE_WIDTH);

    // Check X

    player.x += velocity.x;
    player.updateAABB();
    for(int tx = left - 1; tx <= right + 1; tx++)
    {
        for(int ty = top - 1; ty <= bottom + 1; ty++)
        {
            aabb = world.getTileAABB(tx, ty);
            if(aabb.collidesWith(player.aabb))
            {
                depth = player.aabb.getXDepth(aabb);
                player.x -= depth;
            }
        }
    }

    // Now check Y

    player.y += velocity.y;
    player.updateAABB();
    for(int tx = left - 1; tx <= right + 1; tx++)
    {
        for(int ty = top - 1; ty <= bottom + 1; ty++)
        {
            aabb = world.getTileAABB(tx, ty);
            if(aabb.collidesWith(player.aabb))
            {
                depth = player.aabb.getYDepth(aabb);
                player.y -= depth;
            }
        }
    }

    player.updateAABB();
}

Está pensando demasiado en el problema y combinando un par de problemas. Pero está bien porque, como dijiste, este es un problema muy resuelto con muchas respuestas geniales.

Vamos a desglosarlo:

1. Tilemaps . Su primer ejemplo es de un sprite caminando sobre un montón de fichas dispuestas horizontalmente (o deslizándose por una pared de fichas dispuestas verticalmente, son isomorfas). Una solución muy elegante para esto es simplemente no verificar los bordes de los mosaicos donde sabemos que un sprite no puede llegar, como los bordes que están "bajo tierra" o los bordes que bordean otro mosaico completamente sólido.

   Tienes razón en que el sprite descendería debido a la gravedad, luego se movería lateralmente, luego se atascaría ... pero la respuesta es no preocuparse por los bordes izquierdo o derecho de las fichas que están bajo tierra . De esa manera, su rutina de resolución de colisión solo mueve el sprite verticalmente, y su sprite puede seguir su camino alegre.

   Consulte los tutoriales en mosaico de Metanet para obtener una explicación paso a paso de esto. Usted dice en su pregunta que no está utilizando un mapa de mosaico tradicional, pero eso también está bien: los mosaicos estáticos están en el mapa de mosaico y se actualizan como se indica arriba, mientras se mueven plataformas y se actualizan como # 2 a continuación.

2. Otros AABBs . Solo tendrás un problema si, en un solo cuadro, tu sprite puede moverse una distancia mayor que el ancho / alto de la mayoría de los AABB en tu juego. Si no puede, eres dorado: resuelve las colisiones una por una y funcionará bien.

   Si los AABB pueden moverse muy rápido en un solo cuadro, entonces debe "barrer" el movimiento al verificar las colisiones: fragmente el movimiento en fracciones más pequeñas y verifique las colisiones en cada paso.