Déplacer des joueurs sur la même case simultanément?

Considérons une grille de carrés 2 x 2. Un joueur peut se déplacer sur une case si:

• aucun autre joueur ne veut entrer dans la case au prochain tour
• aucun autre joueur n'a attendu et occupe toujours la place ce tour-ci

J'ai inclus l'image ci-dessus pour décrire mon problème.

Les joueurs se déplacent simultanément.

Si 2 joueurs (ou plus) tentent de se déplacer sur la même case, aucun ne bouge.

1. Marquez tous les joueurs comme étant stationnaires ou en mouvement, selon qu'ils ont soumis un mouvement ce tour-ci.
2. Parcourez la liste des mouvements. Si deux mouvements pointent vers le même emplacement, supprimez-les de la liste et placez les joueurs à l'arrêt.
3. Parcourez la liste en supprimant tous les mouvements qui pointent vers un joueur immobile ou un autre obstacle. Répétez cette opération jusqu'à ce que la liste ne change pas lorsque vous la parcourez.
4. Déplacez tous les joueurs.

Je pense que cela devrait fonctionner. Cela fonctionne certainement pour le cas que vous avez publié, et quelques autres cas triviaux sur lesquels je l'ai testé.

Résolution des collisions, au lieu de la prévention des collisions.

Déplacez simplement les objets, puis vérifiez s'il y a eu des collisions. S'il y a eu une collision avec un autre bloc, revenez à la case précédente, ou selon le type de jeu, une case différente.

Move all players according to their request.
while there are still some squares multiply occupied:
    For each square that is now multiply occupied:
        For each player in that square that moved there this turn:
            Return them to their previous square
            Mark them as having not moved this turn

Cela nécessite que chaque joueur se souvienne d'où il vient de se déplacer, afin qu'ils puissent être renvoyés, et aussi qu'ils se souviennent s'ils ont bougé ce tour-ci. Cette deuxième vérification signifie que chaque pièce n'aura besoin d'être retournée qu'une seule fois et devrait garantir que l'algorithme se termine correctement. Cela garantit également que seuls les joueurs qui ont bougé sont renvoyés - l'occupant d'origine peut rester car ils ne sont pas pris en compte pour le retrait.

Une autre solution consiste à utiliser une carte 2x plus grande que ce que vous montrez. chaque fois que vous voulez déplacer des joueurs, vous les déplacez deux fois pour que les joueurs atterrissent toujours sur des tuiles de valeur égale pour X et Y. là encore, il y aura de rares cas qui nécessiteront plus d'attention mais la plupart des cas possibles sont résolus (comme celui que vous décrit) sans réfléchir à deux fois.

Enregistrez tous les mouvements demandés à l'aide d'un tableau ou d'une carte.

En cas de conflit, annulez la demande de déplacement en question. Si cela renvoie l'objet à un carré qu'un autre objet tente d'occuper, annulez la demande de l'objet demandeur.

Pseudo code:

int[][] game; // game board

var doMoves() {
    int[][] dest = [][]; // destinations; cleared each run

    for (obj in gameObjects)
        if (obj.moveRequest) {
            var o = dest[obj.moveX][obj.moveY];
            if (o) {
                // collision!
                o.doNotMove = true;
                obj.doNotMove = true;
            } else {
                dest[obj.moveX][obj.moveY] = obj;
            }
        }
    }

    // check move validity
    for (obj in gameObjects) {
        if (obj.doNotMove) continue;

        var o = game[obj.moveX][obj.moveY];
        if (o and o.doNotMove)
            revertRequest(obj, dest);
    }

    // process moves
    //etc
}

// recursive function to back up chained moves
var revertRequest(obj, dest) {
    if (!obj.doNotMove) {
        obj.doNotMove = true;
        var next = dest[obj.x][obj.y];
        if (next)
            revertRequest(next, dest);
    }
}

En s'appuyant sur la réponse de SimonW , voici un algorithme explicite:

Soit squaresun tableau indexé par les emplacements des joueurs et contenant, pour chaque emplacement possible, soit l'index d'un autre emplacement, soit la valeur spéciale NULL. (Vous souhaiterez peut-être le stocker en tant que tableau fragmenté.) Les valeurs possibles des entrées de ce tableau peuvent être interprétées comme suit:

• Si squares[S] c'est leNULL , le carré Sest libre de se déplacer.
• Si squares[S] == S , soit le joueur Sne peut pas ou ne veut pas bouger, soit deux joueurs (ou plus) ont essayé de se déplacer en Smême temps et ont tous deux été refusés.
• Autrement, squares[S] contiendra l'index du carré à partir duquel un joueur veut se déplacer vers le carré S.

À chaque tour, initialisez toutes les entrées de squaresto NULLpuis exécutez l'algorithme suivant:

for each player:
   current := the player's current location;
   target := the location the player wants to move to (may equal current);
   if squares[target] is NULL:
      squares[target] := current;  // target is free, mark planned move
   else
      // mark the target square as contested, and if necessary, follow
      // the pointers to cancel any moves affected by this:
      while not (target is NULL or squares[target] == target):
         temp := squares[target];
         squares[target] := target;
         target := temp;
      end while
      // mark this player as stationary, and also cancel any moves that
      // would require some else to move to this square
      while not (current is NULL or squares[current] == current):
         temp := squares[current];
         squares[current] := current;
         current := temp;
      end while
   end if
end for

Après cela, parcourez à nouveau la liste des joueurs et déplacez ceux qui sont capables de le faire:

for each player:
   current := the player's current location;
   if not squares[current] == current:
       move player;
   end if
end for

Étant donné que chaque mouvement ne peut être planifié qu'une seule fois et annulé au plus une fois, cet algorithme s'exécutera en temps O ( n ) pour n joueurs, même dans le pire des cas.

(Hélas, cet algorithme n'empêchera pas les joueurs de changer de place ou de se croiser en diagonale. Il pourrait être possible d'adapter l' astuce en deux étapes de Gajet , mais la façon complètement naïve de le faire ne fonctionnera pas et je suis trop fatigué pour trouver un meilleur moyen tout à l'heure.)