AABB 2D et résolution de collisions multiples

8

D'accord, c'est donc un problème que j'essaie de comprendre depuis un certain temps. Le mien est un jeu de plateforme 2D avec un monde composé (généralement) de tuiles immobiles et de sprites mobiles, qui utilisent tous deux des AABB pour représenter leurs hitbox. Ce jeu n'est PAS basé sur une grille en raison de certaines complications liées au déplacement des couches de tuiles.

Je peux détecter les collisions et déterminer facilement la profondeur de la collision. J'utilise la «méthode de l'axe le moins profond» pour déterminer la façon de résoudre une collision entre le sprite et la tuile. Si le sprite est plus profond horizontalement que verticalement, la direction à résoudre est soit vers le haut soit vers le bas. Si le sprite est plus profond verticalement qu'horizontalement, la direction à résoudre est à gauche ou à droite.

Diagramme # 1

C'est assez simple et cela fonctionne plutôt bien. Autrement dit, jusqu'à ce qu'un sprite entre en collision avec plusieurs tuiles. Comme, de par leur nature, chaque collision doit être vérifiée séparément, différentes collisions peuvent avoir une direction différente à résoudre. Par exemple, si un sprite essaie de traverser une rangée de tuiles, pour une image, il coupera la tuile suivante telle que la profondeur horizontale est plus courte que la profondeur verticale. Comme la collision dit "résoudre à gauche", elle sera repoussée et coincée dans le coin.

Diagramme # 2

Je réfléchis à ce problème, depuis un certain temps, et plusieurs solutions m'ont été proposées, mais toutes ont des défauts. Je pourrais marquer certains côtés comme inaccessibles, mais sans moteur basé sur une grille, déterminer "l'inaccessibilité" est remarquablement complexe, en particulier avec des couches de tuiles mobiles toujours une possibilité.

Une autre méthode possible serait de prédire les collisions avant qu'elles ne se produisent et de "reculer" le mouvement jusqu'au point de la collision, je suppose, mais je ne sais pas comment les calculs à ce sujet fonctionnent.

Je sens que je manque quelque chose d'incroyablement évident, d'autant plus que les jeux des années 80 ont déjà résolu ce problème.

Celarix
la source
Vous pouvez simplement changer l'emplacement du joueur en fonction de la tuile qui est arrivée en premier dans votre chèque
Chachmu

Réponses:

6

Le problème

Le problème réside dans votre méthode de résolution des collisions. Votre méthode se déroule comme suit:

  1. Déplacez le joueur.
  2. Vérifiez la collision.
  3. Déterminez la profondeur de collision la plus courte.
  4. Résoudre la collision.

Le problème avec cela, c'est qu'il peut facilement déplacer le joueur dans la mauvaise direction. Vous pouvez voir comment cela peut se produire dans l'image ci-dessous:

Bug de collision

Parce que le joueur descend vers la droite et est au-dessus du sol, vous vous attendez à ce que le joueur atterrisse au-dessus du sol (près de la boîte verte). Mais au lieu de cela, il est poussé hors du sol vers la gauche (représenté par la boîte rouge). Cela peut être un problème si le joueur essaie de sauter d'une plate-forme à une autre, car le joueur peut finir par mourir à cause d'un mauvais code de collision.

La solution

La solution à ce problème est en fait assez simple. Au lieu d'utiliser la méthode ci-dessus, vous résolvez la collision comme suit:

  1. Déplacez le joueur le long de l'axe X.
  2. Vérifiez les carreaux en collision.
  3. Résolvez la collision X.
  4. Déplacez le joueur le long de l'axe Y.
  5. Vérifiez les carreaux en collision.
  6. Résoudre la collision Y.

J'espère maintenant que vous n'avez pas jeté votre code de vérification de profondeur, car vous en aurez toujours besoin pour les étapes 3 et 6.

Pour résoudre la collision entre les tuiles sur l'un des deux axes (après avoir déplacé le joueur), vous obtenez d'abord la profondeur de la collision. Vous prenez ensuite la profondeur de la collision et la soustrayez des axes dont vous vérifiez actuellement la collision. Notez que la profondeur doit être négative si vous vous déplacez vers la gauche, afin que le joueur se déplace dans la bonne direction.

En utilisant cette méthode, vous n'aurez pas seulement à vous soucier des bogues de collision comme celui du scénario dans l'image ci-dessus, mais cette méthode peut également gérer la collision avec plusieurs tuiles.

Exemple de code:

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();
}
Lysol
la source
Intrigant, mais je vois toujours un problème. Dans mon deuxième scénario, le sprite entre en collision avec une rangée de tuiles. Si je vérifie d'abord les collisions X, il y aura une détection incorrecte dans ce scénario, et elle serait toujours résolue à gauche de manière incorrecte.
Celarix
@Celarix Le deuxième scénario ne devrait pas se produire parce que vous ne vérifiez pas seulement l'axe X en premier, vous le déplacez d'abord. Le sprite ne serait jamais dans une rangée de tuiles, parce que le test de collision Y du mouvement précédent vous empêcherait d'entrer en collision avec une rangée de tuiles comme ça. Assurez-vous simplement que les collisions sont toujours résolues correctement. J'ai eu une fois des problèmes causés par le fait que j'utilisais floats pour stocker mes coordonnées. Alors ça faisait trembler. La solution a été d'arrondir les coordonnées lorsque j'ai fini de résoudre la collision.
Lysol
Vous avez raison, et je pense que cela pourrait être la solution à mon problème de près de deux ans. (Je suis un développeur lent.) Merci beaucoup!
Celarix
Il y a quelques problèmes avec ma réponse. Cela fonctionne pour la plupart des situations, mais notez qu'il y aura des résultats différents selon que vous vérifiez d'abord la collision X ou la collision Y d'abord. Gardez également à l'esprit que le tunneling est un problème; cela échouera avec les objets à grande vitesse car ils sauteront les tuiles.
Lysol
Je pense que je suis d'abord allé avec X pour que les pentes fonctionnent correctement. Le papier à puce n'est pas vraiment un problème dans mon jeu de plateforme car rien ne se déplace presque assez rapidement pour passer à travers les tuiles. Merci pour la contribution supplémentaire!
Celarix
0

Vous surestimez le problème et confondez quelques problèmes. Mais ça va parce que, comme vous l'avez dit, c'est un problème très résolu avec beaucoup de bonnes réponses.

Décomposons-le:

  1. Tilemaps . Votre premier exemple est celui d'un sprite marchant sur un tas de carreaux disposés horizontalement (ou glissant sur un mur de carreaux disposés verticalement, ils sont isomorphes). Une solution très élégante à cela consiste simplement à ne pas vérifier les bords des carreaux où nous savons qu'un sprite ne peut pas accéder, tels que les bords qui sont "souterrains" ou les bords qui bordent un autre carreau complètement solide.

    Vous avez raison de dire que le sprite descendrait à cause de la gravité, puis se déplacerait latéralement, puis resterait coincé ... mais la réponse est de ne pas se soucier des bords gauche ou droit des tuiles qui sont souterraines . De cette façon, votre routine de résolution de collision ne déplace le sprite que verticalement - et votre sprite peut continuer son chemin joyeux.

    Consultez les didacticiels de tuiles Metanet pour une explication étape par étape. Vous dites dans votre question que vous n'utilisez pas un tilemap traditionnel, mais ça va aussi: les tuiles statiques sont dans le tilemap et se mettent à jour comme ci-dessus, tout en déplaçant les plates-formes et une telle mise à jour comme # 2 ci-dessous.

  2. Autres AABB . Vous ne rencontrerez un problème que si, dans une seule image, votre sprite peut se déplacer sur une distance supérieure à la largeur / hauteur de la plupart des AABB de votre jeu. Si ce n'est pas le cas, vous êtes en or: résolvez les collisions une par une et cela fonctionnera très bien.

    Si les AABB peuvent se déplacer très rapidement dans une seule image, vous devez "balayer" le mouvement lors de la vérification des collisions: découpez le mouvement en fractions plus minuscules et vérifiez les collisions à chaque étape.

drhayes
la source