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ê.
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.
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.
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.
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,
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.
Abordagens gerais para esse problema:
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.
fonte
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/
fonte
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.
fonte
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.
fonte