Geração aleatória de níveis interessantes de quebra-cabeças?

8

Estou fazendo um jogo parecido com o Sokoban, ou seja, há uma grade com algumas caixas que você pode empurrar e você precisa colocar as caixas nas cruzes para ganhar o nível (embora eu vá adicionar alguns elementos extras). Existe algum algoritmo geral ou material de leitura que eu possa ver como eu poderia gerar níveis interessantes (como não são fáceis de resolver) para esse estilo de jogo? Estou ciente de que existem geradores de nível aleatório para o Sokoban, mas estou tendo problemas para encontrar as descrições dos algoritmos.

Estou interessado em fazer um jogo em que a máquina possa gerar muitos níveis para mim, classificados por dificuldade. Estou disposto a restringir as regras do jogo para facilitar a geração de níveis (por exemplo, provavelmente limitarei o tamanho da grade para cerca de 7x7). Eu suspeito que existem algumas maneiras gerais de gerar níveis aqui, como eu já vi, por exemplo, jogos do tipo Engarrafamento (onde você precisa mover blocos ao redor do bloco) com milhares de níveis, onde cada um tem uma solução única.

Uma idéia que tive foi gerar um mapa aleatório em seu estado final (ou seja, onde todos os caixotes estão no topo de suas cruzes) e, em seguida, o computador puxaria (em vez de empurrar) esses caixotes para criar um nível. A boa propriedade aqui é que sabemos que o nível é solucionável. No entanto, eu precisaria de algumas heurísticas para garantir que o nível fosse interessante.

game-design level-design random puzzle procedural
fonte
Essa ideia que você tem para gerar níveis é muito interessante. Honestamente, eu apenas iria em frente e tentaria isso, em vez de esperar por uma discussão sobre isso. Suponho que você possa ajustar a dificuldade dos níveis gerados definindo o número de puxões, e uma heurística que você provavelmente desejaria é distribuir os puxões por várias caixas, ambas para que cada caixa seja movida uma quantidade razoável, mas também para que o jogador às vezes precise ir e voltar entre caixas (acho que esse tipo de lógica entrelaçada é mais interessante do que uma caixa de cada vez).
Jhocking

Respostas:

6

Veja o artigo: Criação automática de problemas de Sokoban

Do resumo:

Este documento descreve nosso programa que cria problemas com o Sokoban automaticamente. Sokoban é um dos quebra-cabeças de uma pessoa inventados no Japão. O programa consiste em três etapas: geração, verificação e avaliação. Primeiro, os candidatos a problemas são gerados aleatoriamente por um protótipo e três modelos. Segundo, candidatos insolúveis são removidos pelo solucionador Sokoban. Finalmente, candidatos triviais ou desinteressantes são removidos pelo avaliador. Os problemas que o programa criou são julgados bons por especialistas humanos. A criação de arte por computador é um importante alvo da Inteligência Artificial. Nosso trabalho pode ser caracterizado como uma das tentativas de criar algumas artes por computadores.

CeeJay
fonte
1

Para quebra-cabeças solucionáveis, geralmente é fácil jogar o jogo ao contrário, começando de um estado resolvido e fazendo movimentos não planejados, planejados ou aleatórios (ou em um editor).

Sokoban se encaixa muito bem nessa abordagem e será muito mais fácil de implementar do que uma estratégia de exclusão e solução.

John Haugeland
fonte