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
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á.
turn-based
t123
fonte
fonte
Respostas:
Acho que deve funcionar. Certamente funciona para o caso que você postou e para alguns outros casos triviais em que eu testei.
fonte
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.
fonte
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.
fonte
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.
fonte
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:
fonte
Com base na resposta do SimonW , aqui está um algoritmo explícito:
Seja
squares
uma matriz indexada pelos locais dos jogadores e contendo, para cada local possível, o índice de outro local ou o valor especialNULL
. (Você pode armazenar isso como uma matriz esparsa.) Os possíveis valores das entradas nessa matriz podem ser interpretados da seguinte maneira:squares[S]
forNULL
, o quadradoS
está livre para entrar.squares[S] == S
, ou o jogadorS
não puder ou não se mover, ou dois (ou mais) jogadores tentaram se mover aoS
mesmo tempo e ambos foram negados.squares[S]
conterá o índice do quadrado do qual um jogador deseja mover para o quadradoS
.Em cada turno, inicializar todas as entradas de
squares
aNULL
e, em seguida, execute o seguinte algoritmo:Depois disso, percorra a lista de jogadores novamente e mova aqueles que são capazes de fazê-lo:
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.)
fonte