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

15

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

Exemple de diagramme

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.

t123
la source
1
le joueur peut-il se déplacer les uns sur les autres en une seule étape? par exemple, le jaune et le bleu peuvent-ils changer de place exactement à la même étape (le bleu va une tuile à gauche et le jaune va une tuile à droite)?
Ali1S232
Gajet oui pour l'instant. Mais à un moment donné, je ne voudrais pas que 2 joueurs voisins puissent changer de place directement
t123
alors ma réponse résout ce problème.
Ali1S232
2
EXTRÊMEMENT pertinent: consultez les règles de mouvement pour la diplomatie. en.wikipedia.org/wiki/Diplomacy_(game)#Movement_phase
TehShrike

Réponses:

11
  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é.

SimonW
la source
Oui, cela devrait fonctionner. Notez que vous ne voulez pas vraiment faire une boucle à plusieurs reprises sur la liste des joueurs; en pratique, il sera beaucoup plus efficace de résoudre les collisions par retour arrière.
Ilmari Karonen
16

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.

ultifinitus
la source
1
Oui mais si quelqu'un doit reculer, les autres devront aussi reculer ...
t123
2
Vous avez raison, mais encore une fois, cela dépend du type de jeu réel, plus d'informations seraient nécessaires et la situation changerait en fonction du type. Il s'agissait de la réponse la plus générique disponible.
ultifinitus
5
vous n'avez pas à résoudre toutes les collisions en une seule étape. déplacez tous les objets, vérifiez s'il y a des collisions, mouvements inverses liés à cette collision, répétez ce processus jusqu'à ce qu'il n'y ait plus de collision.
Ali1S232
4
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.

Kylotan
la source
3

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.

Ali1S232
la source
Je pense que vous avez quelque chose en tête ici, mais cela ne ressort pas de votre réponse. Comment l'utilisation d'une carte 2x résout-elle le problème de collision?
Zan Lynx
D'accord. Je pense que je vois la réponse. Deux pièces se déplaçant dans des directions opposées atterrissent sur le même carré et entrent en collision. Les pièces se déplaçant dans le sens des aiguilles d'une montre se déplacent en demi-pas, laissant toujours un espace ouvert pour qu'une autre pièce puisse y entrer.
Zan Lynx,
@ZanLynx: c'est exactement comme ça qu'il résout le problème, le seul problème sera quand deux pièces (disons vert et bleu) vont entrer en collision et une autre pièce (jaune) va remplir la dernière position du vert. dans des cas similaires à ceux-ci (s'ils sont possibles), vous devez résoudre les collisions comme le suggère l'ultifinitus.
Ali1S232
la mise en œuvre la plus simple que je connaisse pour la détection de collision est un mélange du mien et de l'ultifinitus. le mien est bon pour vérifier si les pièces se croisent et unltifinitus est bon pour résoudre d'autres types de collision.
Ali1S232
0

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);
    }
}
Charles Goodwin
la source
0

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.)

Ilmari Karonen
la source