¿Mover jugadores a la misma casilla simultáneamente?

15

Considere una cuadrícula de cuadrados de 2 x 2. Un jugador puede moverse a una casilla si:

  • ningún otro jugador quiere pasar a la casilla el próximo turno
  • ningún otro jugador ha esperado y todavía está ocupando la casilla este turno

Diagrama de ejemplo

He incluido la imagen de arriba para describir mi problema.

Los jugadores se mueven simultáneamente.

Si 2 (o más) jugadores intentan moverse a la misma casilla, ninguno se mueve.

t123
fuente
1
¿Puede el jugador moverse a las fichas de los demás en un paso? por ejemplo, ¿pueden los lugares amarillo y azul cambiar exactamente en el mismo paso (el azul va un mosaico a la izquierda y el amarillo va un mosaico a la derecha)?
Ali1S232
Gajet sí por ahora. Pero en algún momento no me gustaría que 2 jugadores vecinos puedan intercambiar lugares directamente
t123
entonces mi respuesta resuelve ese problema.
Ali1S232
2
EXTREMADAMENTE relevante: revisa las reglas de movimiento para Diplomacia. en.wikipedia.org/wiki/Diplomacy_(game)#Movement_phase
TehShrike

Respuestas:

11
  1. Marque a todos los jugadores como estacionarios o en movimiento, dependiendo de si presentaron un movimiento este turno.
  2. Ir a través de la lista de movimientos. Si dos movimientos apuntan a la misma ubicación, elimínelos de la lista y coloque a los jugadores estacionarios.
  3. Recorre la lista eliminando todos los movimientos que apuntan a un jugador estacionario u otro obstáculo. Haga esto repetidamente hasta que la lista no cambie cuando la pase.
  4. Mueve a todos los jugadores.

Creo que eso debería funcionar. Ciertamente funciona para el caso que publicó, y en un par de otros casos triviales en los que lo probé.

SimonW
fuente
Sí, esto debería funcionar. Tenga en cuenta que en realidad no desea recorrer repetidamente la lista de jugadores; en la práctica, será mucho más eficiente resolver colisiones retrocediendo.
Ilmari Karonen
16

Resolución de colisión, en lugar de prevención de colisión.

Simplemente mueva los objetos, luego verifique si ha habido alguna colisión. Si ha habido una colisión con otro bloque, retrocede a la casilla anterior o, según el tipo de juego, una casilla diferente.

ultifinitus
fuente
1
Sí, pero si uno tiene que pasar por aquel entonces otros tendrán que volver demasiado ...
T123
2
Estás en lo correcto, pero nuevamente depende del tipo de juego real, se requeriría más información y la situación cambiaría según el tipo. Esta fue la respuesta más genérica disponible.
ultifinitus
55
No tiene que resolver todas las colisiones en un solo paso. mueva todos los objetos, verifique si hay colisiones movimientos inversos relacionados en esa colisión, repita este proceso hasta que no quede colisión.
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

Esto requiere que cada jugador recuerde de dónde se acaba de mover, para que puedan ser devueltos, y también recuerde si se movieron este turno. Esta segunda verificación significa que cada pieza solo tendrá que devolverse una vez y debe garantizar que el algoritmo termine correctamente. También garantiza que solo se devuelvan los jugadores que se mudaron: el ocupante original puede permanecer ya que no se considera su remoción.

Kylotan
fuente
3

Otra solución es usar un mapa 2 veces más grande de lo que está mostrando. cada vez que quieras mover jugadores, los mueves dos veces para que los jugadores siempre caigan en fichas con un valor par para X e Y. De nuevo, habrá algunos casos raros que necesitarán más atención, pero la mayoría de los casos posibles se resuelven (como el que descrito) sin pensarlo dos veces.

Ali1S232
fuente
Creo que tienes algo en mente aquí, pero no está llegando en tu respuesta. ¿Cómo el uso de un mapa 2x resuelve el problema de colisión?
Zan Lynx
Bueno. Creo que veo la respuesta. Dos piezas que se mueven en direcciones opuestas aterrizan en el mismo cuadrado y chocan. Las piezas que se mueven en el sentido de las agujas del reloj se mueven medio escalones, dejando siempre un espacio abierto para que se mueva otra pieza.
Zan Lynx
@ZanLynx: así es exactamente como resuelve el problema, el único problema será cuando dos piezas (digamos verde y azul) van a chocar y otra pieza (amarilla) va a llenar la última posición del verde. en casos similares a estos (si son posibles) debe resolver las colisiones como sugirió el ultifinitus.
Ali1S232
La implementación más fácil que conozco para la detección de colisiones es una combinación de mina y ultifinitus. el mío es bueno para verificar si las piezas se cruzan entre sí y unltifinitus es bueno para resolver otros tipos de colisión.
Ali1S232
0

Registre todos los movimientos solicitados utilizando una matriz o mapa.

Si hay un conflicto, revierta la solicitud de movimiento en cuestión. Si eso devuelve el objeto a un cuadrado que otro objeto está tratando de ocupar, revierta la solicitud del objeto solicitante.

Pseudocódigo:

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
fuente
0

Sobre la base de la respuesta de SimonW , aquí hay un algoritmo explícito:

Sea squaresuna matriz indexada por las ubicaciones del jugador y que contenga, para cada posible ubicación, el índice de otra ubicación o el valor especial NULL. (Es posible que desee almacenar esto como una matriz dispersa). Los posibles valores de las entradas en esta matriz pueden interpretarse de la siguiente manera:

  • Si squares[S]es así NULL, el cuadrado Spuede moverse libremente.
  • Si squares[S] == S, o el jugador Sno puede o no se moverá, o dos (o más) jugadores intentaron moverse al Smismo tiempo y ambos fueron denegados.
  • De lo contrario, squares[S]contendrá el índice del cuadrado desde el cual un jugador quiere moverse al cuadrado S.

En cada turno, inicializar todas las entradas de squaresa NULLy ejecute el siguiente algoritmo:

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

Después de eso, recorra la lista de jugadores nuevamente y mueva los que puedan hacerlo:

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

Dado que cada movimiento solo se puede planificar una vez y cancelar como máximo una vez, este algoritmo se ejecutará en tiempo O ( n ) para n jugadores, incluso en el peor de los casos.

(Por desgracia, este algoritmo no impedirá que los jugadores cambien de lugar o se crucen en diagonal. Podría ser posible adaptar el truco de dos pasos de Gajet , pero la forma completamente ingenua de hacerlo no funcionará y estoy demasiado cansado para encontrar una mejor manera ahora).

Ilmari Karonen
fuente