Bejeweled Next Melhor seleção de joias

Existe uma técnica de design de jogo que eu possa usar para remover completamente as situações 'Não há mais movimentos à esquerda'. ie o jogo não deve conter cenários impossíveis.

Tanto quanto eu acho que tudo depende de qual jóia e onde você dá ao usuário depois que um grupo de jóias de 3 ou 4 dissolve.

É possível ? An always infinitely solvable Bejewelled game?

Certamente é possível criar um jogo interminável de Bejeweled. O PopCap fez isso sozinho com o mais recente Bejeweled 3 (o modo é chamado de "Modo Zen").

Primeiro de tudo, você precisa ter certeza de que há pelo menos um movimento válido ao gerar o quadro pela primeira vez.

Sempre que um jogador faz um movimento, você deve calcular o tabuleiro resultante e procurar movimentos válidos. Se não houver nenhum, você deve controlar as gemas que serão geradas para restaurar um tabuleiro válido. Como (pelo menos) três gemas serão removidas com um movimento e você terá que gerar três gemas de substituição, você pode garantir que essas três gemas de substituição formarão outro movimento válido com a placa atual. Modo sem fim alcançado.

É claro que não é ideal que a nova jogada apareça com novas gemas, mas é uma maneira barata de garantir sempre um tabuleiro jogável. E, como criar movimentos válidos realmente significa trocar posições de gemas, não demorará muito para que outros movimentos sejam possíveis.

Como já mencionado, bombas e outros meios para limpar grandes partes do tabuleiro adicionarão mais variedade à jogabilidade, mas eles não são necessários para garantir um modo sem fim.

Sim. Isso seria de fato possível. Este não é um caso do problema de parada, conforme o caso é definido, não é arbitrário. Para responder a isso, duas partes devem ser respondidas; primeiro, se existe uma solução, ela pode ser encontrada; e, em segundo lugar, sempre haverá uma solução válida a ser encontrada.

A primeira parte é como encontrar um conjunto de peças de reposição (gemas) que produziriam um tabuleiro jogável. Isso pode ser conseguido através de métodos de força bruta, basta verificar todos os conjuntos de substituições possíveis até encontrar um que possa ser reproduzido (haveria métodos de força não bruta mais ideais também).

A segunda parte é determinar se sempre haverá um conjunto de substituição que produzirá um conjunto reproduzível. Qualquer conjunto de peças removidas em um único movimento será um superconjunto de conjuntos de três peças, portanto, no caso mínimo de apenas três serem removidas, se um conjunto reproduzível sempre puder ser encontrado, todos os padrões possíveis de peças removidas haverá um conjunto reproduzível, pois conterá todas as soluções para cada conjunto de três blocos removidos, que é um subconjunto dos blocos removidos.

No caso mínimo de limpar apenas três blocos em uma linha / coluna, um conjunto de substituição contendo dois blocos do tipo A separados por um bloco do tipo B (em que tipo A é o tipo de bloco acima ou abaixo do conjunto limpo de três no caso de uma coluna de três ou à esquerda ou direita no caso de uma linha de três). Isso produzirá um movimento em que trocar o centro desses três blocos pelo bloco A apropriado ao lado produzirá um conjunto de três. Isso mostra que sempre é possível encontrar um conjunto de blocos que produzirá um movimento válido ao longo da coluna / linha em que os blocos originais foram limpos. Restringir movimentos futuros para essa coluna ou linha seria, embora seja uma solução válida para um jogo jogável infinito, não seria muito divertido. Mas, usando todas as regras para jogos comuns de estilo com joias, é fácil mostrar que sempre existe uma solução que também permite movimentos fora dessa linha / coluna. Suponhamos que soltemos três peças do tipo A, onde A é uma das peças acima ou abaixo / esquerda ou direita do conjunto removido de três. Isso produzirá uma peça no estilo “bomba” que limpará uma área quando removida. Se, em seguida, colocarmos outro conjunto de peças de reposição, o que resultará em uma partida com essa bomba, uma área de peças será limpa. Essa área conterá um número de três subconjuntos de blocos em outras linhas, o que significa que as futuras jogadas não serão necessariamente limitadas a uma única linha / coluna. Isso produzirá uma peça no estilo “bomba” que limpará uma área quando removida. Se, em seguida, colocarmos outro conjunto de peças de reposição, o que resultará em uma partida com essa bomba, uma área de peças será limpa. Essa área conterá um número de três subconjuntos de blocos em outras linhas, o que significa que as futuras jogadas não serão necessariamente limitadas a uma única linha / coluna. Isso produzirá uma peça no estilo “bomba” que limpará uma área quando removida. Se, em seguida, colocarmos outro conjunto de peças de reposição, o que resultará em uma partida com essa bomba, uma área de peças será limpa. Essa área conterá um número de três subconjuntos de blocos em outras linhas, o que significa que as futuras jogadas não serão necessariamente limitadas a uma única linha / coluna.

Você abordou o problema da interrupção na ciência da computação.

Dada a descrição de um programa de computador arbitrário, podemos deduzir se ele será interrompido em algum momento ou executado para sempre? Há uma razão para isso ser chamado de "problema".

A resposta curta é: não, você não pode garantir que um jogo Bejeweled nunca terá movimentos ilegais. Porque para garantir isso levaria um tempo infinito de computação.