Détection de collision ne doit pas faire l'objet téléporter jusqu'à

Question

Résolu, voir en bas de poste pour algorithme final

Contexte: Je travaille sur un jeu de plateforme 2D à l'aide JS et l'élément canvas HTML. La carte de niveau est basée sur les cases, mais le joueur n'est pas fixé aux tuiles. J'utilise un algorithme de détection de collision décrit dans "Tiny Platformer" on Code inComplete. Il fonctionne en grande partie à l'exception d'un cas de bord (ou «cas de« rebord »).

Le problème:

Le joueur est en train de tomber et se déplaçant aussi droit, dans le mur. En tombant, il se téléporte jusqu'à la hauteur du rebord. Au lieu de cela, le joueur devrait tomber normalement sans se téléporter.

Y at-il un moyen de modifier l'algorithme pour empêcher ce comportement? Si non, pouvez-vous suggérer un autre algorithme de détection de collision? Idéalement, toute correction ne supposerait pas que le joueur tombe toujours, car dans le jeu, la direction de chute du joueur bascule entre haut/bas/gauche/droite.

L'algorithme:

1. nouvelle position est calculée en supposant qu'aucune collision du joueur. (Non montré dans le code ci-dessous)

2. Une fonction appelée getBorderTiles prend un objet (le joueur) et retourne les tuiles touchant chacun des 4 coins du joueur. Puisque le joueur n'est pas plus grand qu'une tuile, ces tuiles de frontière sont nécessairement les seules tuiles que le joueur touche. Notez que certaines de ces tuiles peuvent être identiques. Par exemple, si le joueur n'occupe qu'une colonne, les tuiles gauche-haut/droite-haut seront les mêmes, tout comme les tuiles gauche-bas/droite-bas. Si cela se produit, getBorderTiles renvoie toujours les quatre tuiles, mais certaines seront identiques.

3. Il vérifie ces tuiles de bordure dans la carte de niveau (un tableau 2D) pour voir si elles sont solides. Si une tuile est solide, l'objet entre en collision avec cette tuile.

4. Il teste la collision haut/bas/gauche/droite. Si le joueur descend et entre en collision avec une tuile descendante sans entrer en collision avec la tuile montante correspondante, le joueur est en collision. Si le joueur se déplace à gauche et entre en collision avec une tuile gauche sans entrer en collision avec la tuile droite correspondante, il est en collision à gauche. Etc. Les contrôles haut/bas sont effectués avant les contrôles gauche/droite. Les variables qui stockent les tuiles de bordure sont ajustées s'il y a une collision haut/bas avant d'effectuer la vérification gauche/droite. Par exemple, si le joueur entre en collision, il sera poussé dans les tuiles vers le haut, de sorte que les tuiles BL/BR sont maintenant les mêmes que les tuiles TL/TR.

5. Les paramètres x, y et vitesse du lecteur sont ajustés en fonction des directions dans lesquelles il entre en collision.

Pourquoi l'algorithme échoue:

La tuile en bas à droite est solide, mais en haut à droite est pas, donc (étape 4), le joueur entre en collision vers le bas et (étape 5) il est poussé vers le haut. De plus, il entre en collision avec la tuile BR mais pas BL, donc il entre en collision droite et est poussé vers la gauche. A la fin, le joueur est rendu juste au-dessus et à gauche du rebord. En effet, il est téléporté.

Tentative à la solution: J'ai essayé de résoudre ce problème, mais cela n'a créé qu'un autre problème. J'ai ajouté un contrôle de sorte que le joueur ne se heurte à une tuile que s'il y a une certaine distance à l'intérieur de cette tuile (disons 3px). Si le joueur était à peine dans la tuile BR, l'algorithme n'enregistrerait pas de collision, donc le joueur ne se téléporterait pas. Cependant, si le joueur est tombé sur le sol dans un autre scénario, il n'a pas reconnu la collision jusqu'à ce que le joueur soit assez loin dans le sol. Le joueur a tremblé quand il est tombé un peu dans le sol, a été repoussé vers le haut du sol, est tombé à nouveau, etc.

Merci d'avoir lu jusqu'ici. J'apprécie vraiment vos commentaires.

Code de l'algorithme actuel:

var borderTiles = getBorderTiles(object), //returns 0 (a falsy value) for a tile if it does not fall within the level 
 
     tileTL = borderTiles.topLeft, 
 
     tileTR = borderTiles.topRight, 
 
     tileBL = borderTiles.bottomLeft, 
 
     tileBR = borderTiles.bottomRight, 
 
     coordsBR = getTopLeftXYCoordinateOfTile(tileBR), //(x, y) coordinates refer to top left corner of tile 
 
     xRight = coordsBR.x, //x of the right tile(s) (useful for adjusting object's position since it falls in middle of 4 tiles) 
 
     yBottom = coordsBR.y, //y of the bottom tile(s) (useful for adjusting object's position since it falls in middle of 4 tiles) 
 
     typeTL = tileTL ? level.map[tileTL.row][tileTL.col] : -1, //if tileTL is in the level, gets its type, otherwise -1 
 
     typeTR = tileTR ? level.map[tileTR.row][tileTR.col] : -1, 
 
     typeBL = tileBL ? level.map[tileBL.row][tileBL.col] : -1, 
 
     typeBR = tileBR ? level.map[tileBR.row][tileBR.col] : -1, 
 
     collidesTL = typeTL == TILETYPE.SOLID, //true if the tile is solid 
 
     collidesTR = typeTR == TILETYPE.SOLID, 
 
     collidesBL = typeBL == TILETYPE.SOLID, 
 
     collidesBR = typeBR == TILETYPE.SOLID, 
 
     collidesUp = false, 
 
     collidesDown = false, 
 
     collidesLeft = false, 
 
     collidesRight = false; 
 

 
//down and up 
 
     if (object.vy < 0 && ((collidesTL && !collidesBL) || (collidesTR && !collidesBR))) { 
 
     collidesUp = true; 
 
     /*The object is pushed out of the bottom row, so the bottom row is now the top row. Change the collides__ 
 
     variables as this affects collision testing, but is it not necessary to change the tile__ variables. */ 
 
     collidesTL = collidesBL; 
 
     collidesTR = collidesBR; 
 
     } else if (object.vy > 0 && ((collidesBL && !collidesTL) || (collidesBR && !collidesTR))) { 
 
     collidesDown = true; 
 
     /*The object is pushed out of the bottom row, so the bottom row is now the top row. Change the collides__ 
 
     variables as this affects collision testing, but is it not necessary to change the tile__ variables. */ 
 
     collidesBL = collidesTL; 
 
     collidesBR = collidesTR; 
 
     } 
 

 
     //left and right 
 
     if (object.vx < 0 && ((collidesTL && !collidesTR) || (collidesBL && !collidesBR))) { 
 
     collidesLeft = true; 
 
     } else if (object.vx > 0 && ((collidesTR && !collidesTL) || (collidesBR && !collidesBL))) { 
 
     collidesRight = true; 
 
     } 
 

 
     if (collidesUp) { 
 
     object.vy = 0; 
 
     object.y = yBottom; 
 
     } 
 
     if (collidesDown) { 
 
     object.vy = 0; 
 
     object.y = yBottom - object.height; 
 
     } 
 
     if (collidesLeft) { 
 
     object.vx = 0; 
 
     object.x = xRight; 
 
     } 
 
     if (collidesRight) { 
 
     object.vx = 0; 
 
     object.x = xRight - object.width; 
 
     }

MISE À JOUR: Résolu avec la solution de maracas. L'algorithme est ci-dessous. Fondamentalement, il teste (x puis y) et les collisions résolues, puis il teste (y puis x) et résout les collisions de cette façon. Quel que soit le résultat du test, le joueur qui se déplace sur une distance plus courte est celui qui finit par être utilisé.

Il est intéressant de noter qu'il faut un cas spécial lorsque le joueur entre en collision dans les deux sens. Peut-être cela est-il lié au fait que la coordonnée (x, y) du joueur est dans son coin supérieur gauche. Dans ce cas, le test qui entraîne le déplacement du joueur à une distance PLUS LONGUE doit être utilisé. Il est clair dans ce gif:

Le joueur est la boîte noire et la boîte jaune représente l'endroit où le joueur serait si elle avait utilisé l'autre test (le test qui a entraîné le joueur à déplacer une plus distance). Idéalement, le joueur ne devrait pas se déplacer dans le mur, et il devrait plutôt être là où se trouve la boîte jaune. Ainsi, dans ce scénario, le test à plus longue distance devrait être utilisé.

Voici l'implémentation rapide et sale. Ce n'est pas du tout optimisé mais j'espère que cela montre clairement les étapes de l'algorithme.

function handleCollision(object) { 
 
    var borderTiles = getBorderTiles(object), //returns 0 (a falsy value) for a tile if it does not fall within the level 
 
     tileTL = borderTiles.topLeft, 
 
     tileTR = borderTiles.topRight, 
 
     tileBL = borderTiles.bottomLeft, 
 
     tileBR = borderTiles.bottomRight, 
 
     coordsBR = getTopLeftXYCoordinateOfTile(tileBR), //(x, y) coordinates refer to top left corner of tile 
 
     xRight = coordsBR.x, //x of the right tile(s) (useful for adjusting object's position since it falls in middle of 4 tiles) 
 
     yBottom = coordsBR.y, //y of the bottom tile(s) (useful for adjusting object's position since it falls in middle of 4 tiles) 
 
     typeTL = tileTL ? level.map[tileTL.row][tileTL.col] : -1, //if tileTL is in the level, gets its type, otherwise -1 
 
     typeTR = tileTR ? level.map[tileTR.row][tileTR.col] : -1, 
 
     typeBL = tileBL ? level.map[tileBL.row][tileBL.col] : -1, 
 
     typeBR = tileBR ? level.map[tileBR.row][tileBR.col] : -1, 
 
     collidesTL = typeTL == TILETYPE.SOLID, //true if the tile is solid 
 
     collidesTR = typeTR == TILETYPE.SOLID, 
 
     collidesBL = typeBL == TILETYPE.SOLID, 
 
     collidesBR = typeBR == TILETYPE.SOLID, 
 
     collidesUp = false, 
 
     collidesDown = false, 
 
     collidesLeft = false, 
 
     collidesRight = false, 
 
     originalX = object.x, //the object's coordinates have already been adjusted according to its velocity, but not according to collisions 
 
     originalY = object.y, 
 
     px1 = originalX, 
 
     px2 = originalX, 
 
     py1 = originalY, 
 
     py2 = originalY, 
 
     vx1 = object.vx, 
 
     vx2 = object.vx, 
 
     vy1 = object.vy, 
 
     vy2 = object.vy, 
 
     d1 = 0, 
 
     d2 = 0, 
 
     conflict1 = false, 
 
     conflict2 = false, 
 
     tempCollidesTL = collidesTL, 
 
     tempCollidesTR = collidesTR, 
 
     tempCollidesBL = collidesBL, 
 
     tempCollidesBR = collidesBR; 
 

 
    //left and right 
 
    //step 1.1 
 
    if (object.vx > 0) { 
 
    if (collidesTR || collidesBR) { 
 
     vx1 = 0; 
 
     px1 = xRight - object.width; 
 
     conflict1 = true; 
 
     tempCollidesTR = false; 
 
     tempCollidesBR = false; 
 
    } 
 
    } 
 
    if (object.vx < 0) { 
 
    if (collidesTL || collidesBL) { 
 
     vx1 = 0; 
 
     px1 = xRight; 
 
     conflict1 = true; 
 
     tempCollidesTL = false; 
 
     tempCollidesBL = false; 
 
     collidesLeft = true; 
 
    } 
 
    } 
 
    //step 2.1 
 
    if (object.vy > 0) { 
 
    if (tempCollidesBL || tempCollidesBR) { 
 
     vy1 = 0; 
 
     py1 = yBottom - object.height; 
 
    } 
 
    } 
 
    if (object.vy < 0) { 
 
    if (tempCollidesTL || tempCollidesTR) { 
 
     vy1 = 0; 
 
     py1 = yBottom; 
 
     collidesUp = true; 
 
    } 
 
    } 
 
    //step 3.1 
 
    if (conflict1) { 
 
    d1 = Math.abs(px1 - originalX) + Math.abs(py1 - originalY); 
 
    } else { 
 
    object.x = px1; 
 
    object.y = py1; 
 
    object.vx = vx1; 
 
    object.vy = vy1; 
 
    return; //(the player's x and y position already correspond to its non-colliding values) 
 
    } 
 

 
    //reset the tempCollides variables for another runthrough 
 
    tempCollidesTL = collidesTL; 
 
    tempCollidesTR = collidesTR; 
 
    tempCollidesBL = collidesBL; 
 
    tempCollidesBR = collidesBR; 
 

 
    //step 1.2 
 
    if (object.vy > 0) { 
 
    if (collidesBL || collidesBR) { 
 
     vy2 = 0; 
 
     py2 = yBottom - object.height; 
 
     conflict2 = true; 
 
     tempCollidesBL = false; 
 
     tempCollidesBR = false; 
 
    } 
 
    } 
 
    if (object.vy < 0) { 
 
    if (collidesTL || collidesTR) { 
 
     vy2 = 0; 
 
     py2 = yBottom; 
 
     conflict2 = true; 
 
     tempCollidesTL = false; 
 
     tempCollidesTR = false; 
 
    } 
 
    } 
 
    //step 2.2 
 
    if (object.vx > 0) { 
 
    if (tempCollidesTR || tempCollidesBR) { 
 
     vx2 = 0; 
 
     px2 = xRight - object.width; 
 
     conflict2 = true; 
 
    } 
 
    } 
 
    if (object.vx < 0) { 
 
    if (tempCollidesTL || tempCollidesTL) { 
 
     vx2 = 0; 
 
     px2 = xRight; 
 
     conflict2 = true; 
 
    } 
 
    } 
 
    //step 3.2 
 
    if (conflict2) { 
 
    d2 = Math.abs(px2 - originalX) + Math.abs(py2 - originalY); 
 
    console.log("d1: " + d1 + "; d2: " + d2); 
 
    } else { 
 
    object.x = px1; 
 
    object.y = py1; 
 
    object.vx = vx1; 
 
    object.vy = vy1; 
 
    return; 
 
    } 
 

 
    //step 5 
 
    //special case: when colliding with the ceiling and left side (in which case the top right and bottom left tiles are solid) 
 
    if (collidesTR && collidesBL) { 
 
    if (d1 <= d2) { 
 
     object.x = px2; 
 
     object.y = py2; 
 
     object.vx = vx2; 
 
     object.vy = vy2; 
 
    } else { 
 
     object.x = px1; 
 
     object.y = py1; 
 
     object.vx = vx1; 
 
     object.vy = vy1; 
 
    } 
 
    return; 
 
    } 
 
    if (d1 <= d2) { 
 
    object.x = px1; 
 
    object.y = py1; 
 
    object.vx = vx1; 
 
    object.vy = vy1; 
 
    } else { 
 
    object.x = px2; 
 
    object.y = py2; 
 
    object.vx = vx2; 
 
    object.vy = vy2; 
 
    } 
 
}

Answer 1

Cela arrive parce que vous devez d'abord détecter les collisions dans les deux sens et vous ajuster ensuite la position. "haut/bas" est mis à jour en premier (direction de la gravité). Ajuster "gauche/droite" d'abord ne fera qu'aggraver le problème (après chaque chute, vous pourriez être téléporté à droite ou à gauche).

La seule solution rapide et sale que je pouvais venir avec (invariante gravitation):

1. Calculer la collision des deux points pertinents dans un sens (par exemple en allant à gauche que la question deux points à gauche). Réglez ensuite la vitesse et la position dans cette direction.

2. Calculez la collision des deux points pertinents (ajustés) dans l'autre direction. Ajuster la position et la vitesse de cette direction en cas de collision.

3. S'il n'y a pas eu de collision à l'étape 1., vous pouvez persister les modifications et revenir. Sinon, calculez la distance dx + dy par rapport à la position d'origine avant l'étape 1.

4. Répétez les étapes 1. à 3. mais cette fois, commencez par l'autre sens.

5. Effectuez le changement avec la plus petite distance (sauf si vous avez déjà trouvé une bonne modification à l'étape 3.).

EDIT: Exemple

sizes: sTile = 50, sPlayer = 20 
old position (fine, top-left corner): oX = 27, oY = 35 
speeds: vX = 7, vY = 10 
new position: x = oX + vX = 34, y = oY + vY = 45 => (34, 45) 
solid: tile at (50, 50) 

1.1. Checking x-direction, relevant points for positive vX are the ones to the right: 
    (54, 45) and (54, 65). The latter gives a conflict and we need to correct the 
    position to p1 = (30, 45) and speed v1 = (0, 10). 

2.1. Checking y-direction based on previous position, relevant points: (30, 65) and 
    (50, 65). There is no conflict, p1 and v1 remain unchanged. 

3.1. There was a conflict in step 1.1. so we cannot return the current result 
    immediately and have to calculate the distance d1 = 4 + 0 = 4. 

1.2. Checking y-direction first this time, relevant points: (34, 65) and (54, 65). 
    Because the latter gives a conflict we calculate p2 = (34, 30) and v2 = (7, 0). 

2.2. Checking x-direction based on step 1.2., relevant points: (54, 30) and (54, 50). 
    There is no conflict, p2 and v2 remain unchanged. 

3.2. Because there was a conflict in step 1.2. we calculate the distance d2 = 15. 

5. Change position and speed to p1 and v1 because d1 is smaller than d2.