Mover jogadores para o mesmo quadrado simultaneamente?

15

Considere uma grade 2 x 2 de quadrados. Um jogador pode passar para um quadrado se:

  • nenhum outro jogador quer entrar na praça no próximo turno
  • nenhum outro jogador esperou e ainda ocupa a praça neste turno

Exemplo de diagrama

Eu incluí a imagem acima para descrever o meu problema.

Jogadores se movem simultaneamente.

Se 2 (ou mais) jogadores tentarem entrar no mesmo quadrado, nenhum deles se moverá.

t123
fonte
11
o jogador pode se mover para as peças uns dos outros em uma etapa? por exemplo, amarelo e azul podem mudar de lugar exatamente no mesmo passo (o azul fica um ladrilho à esquerda e o amarelo um ladrilho à direita)?
Ali1S232 29/09
Gajet sim por enquanto. Mas em algum momento eu não gostaria 2 jogadores vizinhos para ser capaz de lugares de swap diretamente
T123
então minha resposta resolve esse problema.
Ali1S232 29/09
2
EXTREMAMENTE relevante: confira as regras de movimento para Diplomacia. pt.wikipedia.org/wiki/Diplomacy_(game)#Movement_phase
TehShrike

Respostas:

11
  1. Sinalize todos os jogadores como estacionários ou em movimento, dependendo se eles enviaram um movimento neste turno.
  2. Percorra a lista de movimentos. Se dois movimentos apontarem para o mesmo local, remova-os da lista e coloque os jogadores parados.
  3. Percorra a lista removendo todos os movimentos que apontam para um jogador parado ou outro obstáculo. Faça isso repetidamente até a lista não mudar quando você passar por ela.
  4. Mova todos os jogadores.

Acho que deve funcionar. Certamente funciona para o caso que você postou e para alguns outros casos triviais em que eu testei.

SimonW
fonte
Sim, isso deve funcionar. Observe que você realmente não deseja repetir repetidamente a lista de jogadores; na prática, será muito mais eficiente resolver colisões retornando.
Ilmari Karonen
16

Resolução de colisão, em vez de prevenção de colisão.

Simplesmente mova os objetos e verifique se houve alguma colisão. Se houve uma colisão com outro bloco, volte para o quadrado anterior ou, dependendo do tipo de jogo, um quadrado diferente.

ultifinito
fonte
11
Sim, mas se alguém tem que mover para trás, em seguida, outros terão que voltar também ...
T123
2
Você está correto, mas, novamente, depende do tipo de jogo real, mais informações seriam necessárias e a situação mudaria com base no tipo. Essa foi a resposta mais genérica disponível.
Ultifinitus
5
você não precisa resolver todas as colisões em uma única etapa. mova todo o objeto, verifique se há colisões ou movimentos reversos relacionados nessa colisão, repita esse processo até que não haja mais colisão.
Ali1S232 29/09
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

Isso requer que cada jogador se lembre de onde eles acabaram de se mudar, para que possam ser devolvidos e também se lembre se eles se mudaram neste turno. Essa segunda verificação significa que cada peça precisará retornar apenas uma vez e deve garantir que o algoritmo termine corretamente. Ele também garante que apenas os jogadores que se mudaram sejam devolvidos - o ocupante original permanece como eles não são considerados para remoção.

Kylotan
fonte
3

Outra solução é usar um mapa 2x maior do que o que você está mostrando. cada vez que você deseja mover jogadores, mova-os duas vezes para que os jogadores sempre apareçam em peças com valor par para X e Y. novamente, haverá alguns casos raros que precisarão de mais atenção, mas a maioria dos casos possíveis será resolvida (como o que você descrito) sem pensar duas vezes.

Ali1S232
fonte
Eu acho que você tem algo em mente aqui, mas não está aparecendo na sua resposta. Como o uso de um mapa 2x resolve o problema de colisão?
Zan Lynx
OK. Eu acho que vejo a resposta. Duas peças movendo-se em direções opostas pousam no mesmo quadrado e colidem. As peças que se movem no sentido horário movem-se meio degraus, sempre deixando um espaço aberto para outra peça se mover.
Zan Lynx
@ZanLynx: é exatamente assim que resolve o problema, o único problema será quando duas peças (digamos verde e azul) colidirem e outra peça (amarela) preencherá a última posição do verde. em casos semelhantes a esses (se possível), é necessário resolver colisões como sugerido pelo ultifinito.
Ali1S232 30/09
a implementação mais fácil que conheço para a detecção de colisões é uma mistura de mina e ultifinito. o meu é bom para verificar se as peças estão se cruzando e o unltifinitus é bom para resolver outros tipos de colisão.
Ali1S232 30/09
0

Registre todos os movimentos solicitados usando uma matriz ou mapa.

Se houver um conflito, reverta a solicitação de movimentação em questão. Se isso retornar o objeto a um quadrado que outro objeto esteja tentando ocupar, reverta a solicitação do objeto solicitante.

Pseudo-có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
fonte
0

Com base na resposta do SimonW , aqui está um algoritmo explícito:

Seja squaresuma matriz indexada pelos locais dos jogadores e contendo, para cada local possível, o índice de outro local ou o valor especial NULL. (Você pode armazenar isso como uma matriz esparsa.) Os possíveis valores das entradas nessa matriz podem ser interpretados da seguinte maneira:

  • Se squares[S]for NULL, o quadrado Sestá livre para entrar.
  • Se squares[S] == S, ou o jogador Snão puder ou não se mover, ou dois (ou mais) jogadores tentaram se mover ao Smesmo tempo e ambos foram negados.
  • Caso contrário, squares[S]conterá o índice do quadrado do qual um jogador deseja mover para o quadrado S.

Em cada turno, inicializar todas as entradas de squaresa NULLe, em seguida, execute o seguinte 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

Depois disso, percorra a lista de jogadores novamente e mova aqueles que são capazes de fazê-lo:

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

Como cada jogada só pode ser planejada uma vez e cancelada no máximo uma vez, esse algoritmo será executado em O ( n ) tempo para n jogadores, mesmo no pior caso.

(Infelizmente, esse algoritmo não impedirá os jogadores de trocar de lugar ou de cruzar na diagonal. Pode ser possível adaptar o truque de duas etapas do Gajet a ele, mas a maneira completamente ingênua de fazer isso não funcionará e eu estou cansado demais para descobrir uma maneira melhor agora.)

Ilmari Karonen
fonte