Algoritmo de jogos de quebra-cabeça de três combinações

Estou tentando escrever um jogo de combinar três como 'call of Atlantis'. O algoritmo mais importante é descobrir todas as possibilidades possíveis de combinar três. Existe algum projeto de código aberto que possa ser referenciado? Ou alguma palavra-chave para o algoritmo? Estou tentando procurar um algoritmo mais rápido para calcular todas as possibilidades.

Regras:

• Diagonais não contam.
• O tamanho é 8x8

Obrigado.

Ajudei a portar um desses jogos para uma plataforma portátil. Olhando para trás em seu código de IA para encontrar potenciais: sim, é complicado, brutal (loop aninhado quadruplicado, se chama recursivamente ocasionalmente etc.), e não parece amigável à cache à primeira vista.

(Parte dessa complexidade vem da tentativa de avaliar a força da mudança no contexto: avaliar cadeias mais longas mais altas, procurar combos etc.)

Mas isso realmente não precisa ser "ideal"; nem tocamos no código quando o transportamos. Ele nunca apareceu no criador de perfil.

Olhando agora, mesmo em uma palavra de 32 bits por célula (e acho que eles realmente usaram um byte por célula), toda a placa caberá em um cache L1 minúsculo, e você poderá fazer muitas leituras em excesso de coisas armazenadas em cache sem causar impacto framerate demais. Especialmente porque você só precisa fazer todo esse processo uma vez cada vez que a configuração da placa é alterada. (Um teta grande pairando ao redor n^2não é tão horrivelmente ruim com um muito baixo n, para não mencionar o pequeno multiplicador, dada a memória em cache.)

Dito isto: por diversão, vamos tentar paralelizar o problema. Começando com operações bit a bit.

Suponha que você tenha uma máscara de bits representando todas as peças (as chamaremos de pedras) em uma linha de um tipo específico (usaremos cores para distinguir tipos). Começaremos a olhar apenas para as pedras vermelhas e nos preocuparemos com o custo do cálculo da máscara de bits posteriormente.

// Let's assume top right indexing.
// (The assumption is not necessary, --
//    it just makes the left-shift and right-shift operators 
//    look like they're pointing in the correct direction.)

// this is for row 2
col index  76543210
color      BRRGYRBR // blue, red, red, green, yellow, ...
"red" bits 01100101

Nós estamos olhando para a série que precisam apenas uma troca para tornar-se uma série de 3. Cortesia Kaj, esta é uma das três combinações, basicamente: XoX, oXXou XXoonde Xé uma pedra de correspondência e oé outra coisa.

(Essa idéia é emprestada do maravilhoso livro Hacker's Delight ; veja também o fxtbook se essas coisas o agradam.)

// using c-style bitwise operators:
// & is "and"
// ^ is "xor"
// | is "or"
// << and >> are arithmetic (non-sign-extending) shifts

redBitsThisRow = redBitsRows[2]

// find the start of an XoX sequence
startOfXoXSequence = redBitsThisRow & (redBitsThisRow << 2);
// for our example, this will be 00000100

// find any two stones together in a row
startOfXXSequence = redBitsThisRow & (redBitsThisRow << 1);
// for our example, this will be 01000000

É mais útil conhecer as posições das pedras ausentes, não o início da sequência XX ou XoX:

// give us any sequences that might want a stone from the left
missingLeftStone = startOfXXSequence << 1;
// for our example, this will be 10000000

// give us any sequences that might want a stone from the right
missingRightStone = startOfXXSequence >> 2;
// for our example, this will be 00010000

// give us any sequences that might want a stone from the top or bottom
missingTopOrBottomStone = missingRightStone | missingLeftStone | (startOfXoXSequence >> 1)
// for our example, this will be 10010010

(Cerca de 1 carregamento e 9 instruções ALU - 5 turnos, 2 ou 2, e 2 - com uma CPU terrível que não inclui um deslocador em linha. Em muitas arquiteturas, esses turnos podem ser gratuitos.)

Podemos preencher esses lugares desaparecidos?

// look to the left, current row
leftMatches = redBitsThisRow & (missingLeftStone << 1)

// look to the right, current row
rightMatches = redBitsThisRow & (missingRightStone >> 1)

// look on the row above
topMatches = redBitsRow[1] & missingTopOrBottomStone

// look on the row below
bottomMatches = redBitsRow[3] & missingTopOrBottomStone

(Outras 2 cargas e 6 instruções ALU - 4 e 2 turnos - com uma CPU ruim. Observe que a linha 0 e a linha 7 podem causar problemas - você pode optar por ramificar esses cálculos ou evitar a ramificação alocando espaço para duas linhas extras, uma antes de 0 e uma depois das 7 e deixe-as zeradas.)

Agora temos vários vars de "correspondências" que indicam a posição de uma pedra que pode ser trocada para fazer uma correspondência.

Isso pressupõe um método interno intrínseco ou muito barato "zeros à direita":

swapType = RIGHT_TO_LEFT;
matches = leftMatches;
while ( (colIdx = ctz(matches)) < WORD_BITS ) {
   // rowIdx is 2 in our examples above
   workingSwaps.insert( SwapInfo(rowIdx, colIdx, swapType) );
   // note that this SwapInfo construction could do some more advanced logic:
   //   run the swap on a temporary board and see how much score it accumulates
   //   assign some sort of value based on preferring one type of match to another, etc

   matches = matches ^ (1<<colIdx); // clear the match, so we can loop to the next
}
// repeat for LEFT_TO_RIGHT with rightMatches
// repeat for TOP_TO_BOTTOM with topMatches
// repeat for BOTTOM_TO_TOP with bottomMatches

Observe que nenhuma dessa lógica de bits deve ser quebrada em ambientes little-endian vs big-endian. Torna-se muito mais complicado para placas maiores que o tamanho da palavra da sua máquina. (Você pode experimentar algo parecido std::bitsetcom isso.)

E as colunas? Pode ser mais fácil ter apenas duas cópias da tabela, uma armazenada em ordem de linha e outra armazenada em ordem de coluna. Se você tiver acesso a getters e setters, isso deve ser trivial. Não me importo de manter duas matrizes atualizadas, afinal um conjunto se torna rowArray[y][x] = newType; colArray[x][y] = newType;e isso é simples.

... mas gerenciar rowBits[color][row]e colBits[color][col]se tornar desagradável.

No entanto, como um aparte rápido, se você tiver rowBitse colBits, poderá executar o mesmo código com rowBits apontando para colBits. Pseudocódigo, assumindo largura da placa = altura da placa = 8 neste caso ...

foreach color in colors {
    foreach bits in rowBits, colBits {
        foreach row in 0..7 { // row is actually col the second time through
            // find starts, as above but in bits[row]
            // find missings, as above
            // generate matches, as above but in bits[row-1], bits[row], and bits[row+1]
            // loop across bits in each matches var,
            //    evaluate and/or collect them, again as above
        }
    }
}

E se não quisermos nos preocupar em converter uma boa matriz 2D em bits? Com uma placa 8x8, 8 bits por célula e um processador com capacidade para 64 bits, podemos ser capazes de se safar: 8 células = 8 bytes = 64 bits. Agora estamos bloqueados para a largura da nossa placa, mas isso parece promissor.

Suponha que "0" esteja reservado, as pedras começam em 1 e vão para NUM_STONE_TYPES, inclusive.

startOfXXSequence = rowBytes ^ (rowBytes << (8*1))
// now all bytes that are 0x00 are the start of a XX sequence

startOfXoXSequence = rowBytes ^ (rowBytes << (8*2))
// all bytes that are 0x00 are the start of a XoX sequence

Observe que isso não precisa de um passe por cor. Em BRBRBRGYobteremos um startOfXoXSequenceque pode ser algo como 0x00 00 00 00 aa bb cc dd- os quatro bytes principais serão zero, indicando que uma possível sequência começa aí.

Está ficando tarde, então irei embora daqui e possivelmente voltarei mais tarde - você pode continuar com esse xors e "detectar o primeiro byte zero", ou pode procurar em extensões SIMD inteiras .

Você está pensando demais no problema. Em uma única linha de 8, existem 6 posições possíveis para um match-3; portanto, para todo o tabuleiro 8x8, existem apenas 96 possíveis match-3. A verificação de 96 possibilidades utiliza uma quantidade insignificante de tempo de CPU. Você provavelmente está usando milhares de vezes mais ciclos de relógio apenas desenhando um quadro.

Se você estiver procurando por movimentos de swap-dois-adjacentes que possam fazer a correspondência 3s ... Para cada posição possível, se já houver 2 peças correspondentes, existem no máximo 3 swaps possíveis que podem fazer a correspondência 3. Por uma linha, existem no máximo 23 movimentos a serem considerados e, para toda a diretoria, há 112 movimentos a serem considerados. A verificação de 112 movimentos também é uma quantidade insignificante de tempo de CPU.

Existem apenas algumas combinações que podem combinar. XX com um abaixo ou acima do centro (e girado 90 graus) e xx. com um à direita ou no topo do '.' (e a rotação e o espelhamento nas variantes de ambos os eixos. Isso resulta em 14 padrões de pesquisa diferentes que precisam corresponder a uma grade (máx. 4x3) à grade 8x8. Eu precisaria de força bruta e deslizaria o padrão ao longo da grade 8x8 e verificaria se os lugares onde há um x são os mesmos. Se assim for, é um conjunto que pode criar um triplo.
Então, basicamente, (por exemplo) de slides

....
xx.x
....
ou (anotheher exemplo)
. x.
x. .
. x.

em toda a linha - se todas as três posições x tem o mesmo ícone que é uma possível transferência.
E isso vezes 14 para todos os movimentos possíveis.

Se a velocidade é realmente um problema, eu diria para tentar algo como:

• Itere toda a grade, iniciando do canto superior esquerdo.

• Em todos os pontos da grade até e incluindo a 6a coluna, marque um bloco à direita e para baixo (você não precisa verificar a esquerda e a cima porque fez isso)

• Quando você atingir a 7ª coluna, verifique apenas. (Não há espaço para três quando houver apenas 2 colunas)

• Se eles corresponderem, tente verificar mais um bloco ao longo / baixo. Caso contrário, passe para o próximo bloco.

• Quando você terminar a 8ª coluna, desça uma linha.

Mas para uma grade 8x8, não há muita otimização necessária. Uma forma mais fácil seria (semelhante):

• Itere toda a grade, iniciando do canto superior esquerdo.

  • Em todos os pontos da grade até e incluindo a 6a coluna, marque um bloco à direita e para baixo (você não precisa verificar a esquerda e a cima porque fez isso)

  • Se eles corresponderem, tente verificar mais um bloco ao longo / baixo. Caso contrário, passe para o próximo bloco. Manipule os erros fora da placa como 'não iguais'.

  • Quando você terminar a 8ª coluna, desça uma linha.

Isso permitiria um código muito mais simples no loop for, pois você não possui uma estrutura if com algum código de um lado e um código ligeiramente aprimorado abaixo dele.

Não é muito bonito ou elegante, mas escrevi um jogo de combinar 3 em JavaScript . Código-fonte no GitHub, você visualiza a lógica do match-3 diretamente no seu navegador da web: https://github.com/richtaur/bombada/blob/master/htdocs/js/match3.js#L184