Geração de Terreno Procedimental 2D - Garantindo a conexão?

7

Estou trabalhando em um jogo de plataformas 2D no XNA. Uma das coisas que eu gostaria de ser uma característica principal do design é a geração processual de conteúdo. O primeiro passo disso é gerar procedimentalmente o terreno. Então, eu fiz muitas pesquisas sobre como gerar ruído Perlin, suavizar, tocar com parâmetros e todo esse jazz. Também passei muito tempo no pcg.wikidot.com. O problema que tenho é gerar um nível 100% conectado. Ou seja, é possível que o personagem passe da parte esquerda do nível até a parte direita.

No momento, eu uso o ruído perlin para gerar um sprite quando o valor do ruído nesse ponto é <0.

Aqui está um vídeo do problema que estou tendo (desculpe os problemas malucos de fundo e o fato de meu personagem ficar preso quando eu gerar um novo nível).

http://screencast.com/t/uWJsIGLoih

Como você pode ver no vídeo, o terreno parece interessante o suficiente, mas você não pode fazer muito porque o ruído Perlin compartimenta o nível em pequenas câmaras aleatórias.

Tentei fazer uma caminhada aleatória e sobrepor o ruído permanente em cima dela, para garantir um caminho da esquerda para a direita. O problema com isso é ilustrado abaixo: http://screencast.com/t/ilLvxdp3

Então, minha pergunta é: que tipos de coisas eu posso fazer para garantir que o jogador possa ir da parte esquerda do nível para a parte direita do nível?

SpaDusA
fonte

Respostas:

13

Ao usar a palavra conectividade , você encontra a ferramenta mais adequada para determinar uma solução: teoria dos grafos.

A conexão é uma propriedade dos gráficos. Os gráficos podem ser conectados ou desconectados (como você está experimentando, também conhecido como multigraph). Qualquer nível de jogo, em qualquer número de dimensões, pode ser representado como um gráfico e, logicamente, essa é geralmente a melhor maneira de manipulá-los. Seu mundo do jogo é um gráfico em termos da adjacência entre os blocos de construção individuais em seu mundo; e também no nível de conectividade entre suas várias áreas. Você pode usar o primeiro para derivar o último.

Há um ponto crucial a considerar ao trabalhar com níveis (2D) como gráficos, e isso é planaridade . Dependendo dos seus requisitos, a planaridade pode ou não ser uma preocupação. Dado o seu uso do ruído, espero o último, no entanto, descrevo as opções aqui para que você saiba quais são.

Gráfico planar - o exemplo mais simples é um labirinto. Um labirinto difere de um labirinto por não conter ramificações - é unicursal . Se você pegasse um bloco sólido de arbustos (!) E gerasse um labirinto através dele, então em nenhum momento a rotação que o labirinto leva, poderia correr para um caminho existente. É um pouco como um jogo de cobra, na verdade - se o caminho é o corpo da cobra, não é permitido que ele se morda / se cruze. Além disso , você pode ter um labirinto plano; isso iria se ramificar, mas em nenhum momento os galhos poderiam cruzar partes existentes do labirinto já gerado, assim como em um labirinto.

Gráfico não plano - O exemplo mais simples é um mapa de ruas da cidade. Uma cidade é essencialmente um labirinto. No entanto, é um labirinto altamente conectado, pois existem muitas rotas rodoviárias individuais para ir de um lugar para outro. Além disso, uma incorporação de gráfico não-plano permite cruzamentos, exatamente o que são as interseções. E como sabemos, uma cidade não é uma cidade sem cruzamentos. Eles são parte integrante do fluxo de tráfego. Nos jogos, isso pode ser bom ou ruim, dependendo de seus objetivos. Um bom nível de fluxo permite que a IA atue com mais facilidade e a exploração seja mais livre; enquanto, por outro lado, também permite que um jogador passe do ponto de partida para o gol rapidamente - potencialmente rápido demais.

Isso nos leva à sua abordagem, que é usar ruído. Dependendo da saída do ruído Perlin, é interpretada, ela pode ter algum nível de conexão como a escala macro, mas não foi projetada para a conexão 1 (um único gráfico). Isso deixa algumas opções para você.

  1. Abandone o uso do ruído Perlin e, em vez disso, gere um gráfico aleatório, plano (sem cruzamento). Isso fornece controle máximo de fluxo. No entanto, essa abordagem não é trivial, porque a planaridade do gráfico requer a identificação e a remoção dos subgráficos de Kuratowski K3,3 e K5; bem como produzir uma incorporação plana subsequente; ambos são problemas NP-completos. Essa é, sem dúvida, a abordagem mais difícil, mas foi preciso mencionar primeiro para saber onde você está. Todos os outros métodos são um atalho de algum tipo, em torno desse método, que é a matemática fundamental por trás da geração do labirinto.

  2. Abandone o uso do ruído Perlin e gere um gráfico aleatório não planar incorporado em uma superfície plana (AKA uma incorporação planar) - é assim que jogos como Diablo e roguelikes podem funcionar facilmente, pois ambos usam uma grade estrutura para subdividir um espaço plano (de fato, a grande maioria dos níveis nos roguelikes permite travessias, evidentes no número de cruzamentos de quatro vias). Algoritmos que produzem a conectividade entre células ou salas de modelos são freqüentemente chamados de "entalhadores" ou "tunnellers", porque esculpem espaço vazio de um bloco de rocha sólida, incrementalmente.

  3. Faça como opção (2), mas evite cruzamentos. Assim, a incorporação (geometria de nível) é plana e a topologia (fluxo de nível) também é plana. Você terá que tomar cuidado para não se transformar em becos sem saída, se desejar evitar cruzamentos.

  4. Gere seu mapa usando ruído. Em seguida, usando um algoritmo de preenchimento de inundação em todas as células do seu nível desconectado (que é um gráfico, embora com várias partes e com base em grade), você pode deduzir todos os subgráficos discretos e não conectados dentro desse multigrafo maior. Em seguida, considere como deseja conectar cada subgráfico individual. Se você preferir evitar cruzamentos, sugiro uma conexão seqüencial destes. Caso contrário, você pode conectá-los da maneira que desejar. Para fazer isso organicamente, em vez de produzir passagens duras e retas, eu usaria algum tipo de função de coerência para fundir os pontos mais próximos de cada par de subgráficos (se vinculando sequencialmente). Isso tornará a junção mais "líquida", o que está de acordo com a saída típica da Perlin. A outra maneira de ingressar em áreas seria empurrá-las para mais perto,

  5. Gere um mapa excessivamente grande usando ruído. Isole todos os subgráficos, conforme descrito na opção 3. Determine qual é o mais interessante, de acordo com certos critérios (pode ser o tamanho ou qualquer outra coisa, mas o tamanho seria mais fácil). Escolha e use apenas o subgráfico, que já está completamente auto-conectado. A dificuldade dessa abordagem é que você pode achar difícil controlar o tamanho dos gráficos resultantes, a menos que a força bruta gere um mapa realmente grande, ou muitos menores, para escolher o seu subgrafo perfeito. Isso ocorre porque o tamanho dos subgráficos realmente depende dos parâmetros Perlin usados ​​e de como você interpreta o resultado.

Como um aparte das duas últimas, tenho certeza de que você já fez, mas só por precaução: crie um caso de teste de ruído Perlin mínimo no Flash. Brinque com os parâmetros até obter um maior grau de conectividade entre as áreas da "ilha". Eu não acho que isso possa resolver seu problema 100% em todas as gerações, já que o ruído Perlin não tem garantia inerente de conexão. Mas isso poderia melhorar a conexão.

O que você não entender, pergunte e eu esclarecerei.

Engenheiro
fonte
Esta é uma excelente resposta.
tenpn 5/09/11
11
Então, você deve cortar a árvore mais poderosa do forrest ... com ... um arenque!
Jonathan Connell
Hahaha ... sim.
coordenador
Ainda não implementei nenhuma dessas soluções, mas as informações fornecidas me fizeram repensar algumas coisas e acho que respondeu melhor às minhas perguntas. Então, eu estou marcando isso como a resposta. Obrigado a todos.
SpaDusA
5

Abordagens gerais para esse problema:

  1. Construa o mapa de uma maneira que garanta a conexão desde o início. Muitos dos geradores de masmorras no wiki do PCG funcionam dessa maneira.
  2. Gere um mapa potencialmente desconectado e depois escreva algo (talvez um descobridor) que verifique a conexão. Jogue fora os mapas que não funcionam.
  3. Gere um mapa potencialmente desconectado e corrija-o sempre que não estiver conectado. Sempre que seus algoritmos de verificação encontrarem uma área intransitável, explodam túneis, construam pontes, adicionem teleportadores, etc.
  4. Gere um mapa potencialmente desconectado e, em seguida, forneça ao player ferramentas para conectar coisas quando necessário. Transforme o bug do mapa desconectado em um recurso. Terraria, Minecraft, etc. faça isso.
  5. Gere um mapa potencialmente desconectado e faça o jogador reiniciar ou passar para um nível diferente se o nível não puder ser completado. Eu acredito que alguns roguelikes fazem isso.

Concordo com Kylotan que uma função de ruído provavelmente não é ideal, mas as funções de ruído podem fazer muito e você pode consertá-la de alguma forma. Veja este artigo para algumas idéias.

amitp
fonte
2

Esse vídeo é apenas confuso, e não consigo entender o que você está tentando mostrar para ser honesto. Mas eu sugeriria que o ruído Perlin é provavelmente o algoritmo errado para o trabalho. Ele foi projetado para entidades contínuas sem ondulações, enquanto você tenta criar entidades dispersas e discretas. O que provavelmente funcionaria melhor é usar valores aleatórios para reorganizar e ajustar os arranjos projetados à mão das plataformas para garantir que a área resultante seja reproduzível.

Há algumas informações sobre como Spelunky fez isso aqui: http://tinysubversions.com/2009/09/spelunkys-procedural-space/

Kylotan
fonte
0

Tente modificar o valor do perlin com base na altura, ou seja, na parte inferior, adicione 1 ao valor do ruído, na parte superior subtraia 1 do valor do ruído e entre interpolar linearmente entre 1 e -1. Dessa forma, na parte inferior, você quase terá a garantia de obter um valor> = 0 e, na parte superior, quase a garantia de obter um valor <= 0.

Isso pressupõe que valores <0 devem ser ar. Se a sua descrição estiver correta, você terá que trocá-la.

Felicidades.

Lingfors
fonte
11
Então, tentei o método e obtive o seguinte resultado: screencast.com/t/vxnc0LHbLGPQ Não tenho muita certeza de que isso tenha ajudado meu problema. Eu ainda tenho que pós-processo para garantir a conexão.
SpaDusA 4/11
0

Uma abordagem simples e fácil de você adotar, considerando o código existente, é continuar gerando mapas aleatórios até que um atenda à sua restrição de conexão.

Você provavelmente pode verificar rapidamente sua restrição de conexão usando um preenchimento de inundação na posição inicial. Ele preenche todo o caminho até um ponto final legal?

Você provavelmente pode fazer milhares dessas verificações por segundo, portanto é provável que seja um hack perfeitamente aceitável.

Vai
fonte