Mundos enormes de 'região selvagem' gerados processualmente

76

Tenho certeza de que todos vocês conhecem jogos como o Dwarf Fortress - imensas áreas selvagens e procedentes geradas por procedimentos. Algo assim, extraído deste artigo muito útil.

No entanto, eu queria saber como poderia aplicar isso em uma escala muito maior; a escala do Minecraft vem à mente (não é algo como 8x o tamanho da superfície da Terra?). Pseudo-infinito, acho que o melhor termo seria.

: D

O artigo fala sobre o ruído fractal perlin. Eu não sou um especialista nisso, mas entendo a ideia geral (é algum tipo de ruído gerado aleatoriamente que é semi-coerente, portanto, não apenas valores aleatórios de pixels).

Eu poderia apenas definir regiões X por X em tamanho, adicionar algumas coisas do tipo carregamento de região e ter um pouco de ruído gerando uma região. Mas isso resultaria em grandes quantidades de ilhas.

Por outro lado, acho que não posso realmente gerar uma folha supermassiva de ruído permanente. E seria apenas uma grande ilha, eu acho.

Tenho certeza de que o ruído Perlin, ou algum ruído, seria a resposta de alguma maneira. Quero dizer, o mapa é realmente bonito. E você pode substituir o ascii por ladrilhos e obter algo muito bonito.

O Pato Comunista
fonte
9
"resultaria em apenas grandes quantidades de ilhas" - ou gera terra com lagos, se você trocar terra / água.
3
Mesmo assim, você obteria uma grande quantidade de lagos, em um padrão bastante padrão.
The Duck Comunista
3
@Kylotan: Mincraft é infinito em tamanho (não muito, mas é muito grande ... volume total = long.MaxValue x 128 x long.MaxValue). Portanto, não gera o mundo inteiro de uma só vez, nem armazena o mapa inteiro na memória. Ele gera regiões de blocos 16x128x16 de forma assíncrona, caso não tenham sido visitados anteriormente, caso contrário, ele será carregado do disco.
Zfedoran 19/10/10
2
@ The Duck Comunista: Sim, isso é verdade, um jogo como o minecraft pode se safar usando de 2 a 4 bytes de dados por bloco, mas apenas um byte precisa ser salvo depois que não estiver mais visível (um byte descreve o tipo de bloco , os outros bytes descrevem a iluminação e outros dados que podem ser recalculados posteriormente). Aqui é onde fica interessante, você pode usar o RLE para reduzir drasticamente o tamanho armazenado para apenas alguns bytes, pois os blocos são um pouco coerentes, como você mencionou.
Zfedoran 19/10/10
4
'Realmente grande' não é o mesmo que infinito e você não pode usar os dois termos de forma intercambiável. Se você aumentar o mapa como e quando for descoberto, esse é um tamanho finito que cresce sob demanda - uma proposta bem diferente de ser infinito. Cada bit de crescimento pode ser gerado conforme necessário. Os dados do terreno no Minecraft são muito passíveis de compactação trivial, pois há um alto grau de coerência entre os dados. (por exemplo, RLE como mencionado.)
Kylotan 20/10/10

Respostas:

35

Acho que entendo melhor o que você está perguntando agora.

O ruído não é aleatório - é de aparência aleatória, mas é completamente baseado em uma fórmula matemática e é repetível. Toda a informação é codificada na fórmula. Isso significa que você pode ter uma fórmula que cubra potencialmente uma área infinita e apenas usar a fórmula nas coordenadas da área que você precisa. Quando você precisar de uma área adjacente, basta reutilizar a fórmula nas novas coordenadas e, como a fórmula gera valores contínuos, as áreas se unirão perfeitamente.

Aqui está um exemplo simplificado, usando seno em vez de ruído permanente para a geração de altura, e imaginando que o mundo é infinito no eixo X, mas apenas 1 unidade de altura nos eixos Y e Z.

A fórmula é: height(x,y) = sin(x/20)

O jogo começa e geramos alturas para a área próxima, ou seja. (0,0) a (9,0):

[0.0, 0.05, 0.10, 0.15, 0.20, 0.25, 0.30, 0.34, 0.39, 0.43]

Temos uma colina, subindo para a direita. Digamos que caminhamos até o final e precisamos gerar os valores de (10,0 a 19,0) agora:

[0.48, 0.52, 0.56, 0.61, 0.64, 0.68, 0.72, 0.75, 0.78, 0.81]

Observe como a colina continua subindo constantemente, e que o valor em (10,0) segue muito bem o valor em (9,0). Isso ocorre porque a função seno é contínua, o que basicamente significa que, se você inserir 2 números adjacentes, obterá 2 resultados adjacentes - para uma determinada definição de adjacente. Portanto, se você usar as coordenadas do seu mundo como parâmetros para a função que define o seu mundo, obterá um cenário contínuo que se encaixa, independentemente de quanto dele seja gerado de uma vez. Quando você gera novas peças, elas fluem automaticamente das peças existentes, porque as alturas já são pré-determinadas.

Se o mundo não vai mudar, você nem precisa armazenar nada, pois é possível calcular exatamente qual é a altura em qualquer ponto da fórmula. Obviamente, com algo como Minecraft, o mundo é totalmente deformável, então você apenas salva cada pedaço à medida que o cria. Dado que existe um alto grau de coerência entre os pedaços adjacentes (ou seja, se um bloco for grama, é mais provável que o bloco ao lado seja também grama), você pode compactar os dados com muita eficiência - a codificação do comprimento da execução funcionaria bem, mas quase todos os algoritmos de compressão padrão.

Enquanto eu falei sobre altura como o valor mais óbvio, você pode usar o mesmo sistema para gerar qualquer característica que desejar. Use uma função matemática com propriedades contínuas e onde as entradas são as coordenadas do seu mundo e que podem decidir a presença de pontos de referência, depósitos minerais, pontos de reprodução, o que você quiser. (Obviamente, os valores de uma fórmula podem afetar a outra - não faz sentido colocar um depósito de carvão no ar, então você gera o mapa da altura do mundo e calcula apenas as possibilidades de carvão para os blocos que estão suficientemente longe do solo.)

Kylotan
fonte
Você definitivamente ajudou a esclarecer as coisas, obrigado. :) Mas algo como uma função de ruído não seria contínuo. E o AFAICS, se for contínuo, não receberia um mundo 'aleatório'. Ou estou faltando alguma coisa aqui?
The Duck Comunista
Desculpe pelo comentário duplo, mas sinto que o exposto acima é separado disso. Quando você diz 'use as coordenadas do mundo para o ruído permanente', isso seria o mesmo tipo de efeito que gerar a 'enorme' folha de ruído, mas em partes? Hoje sinto-me um pouco lento com a aceitação.
The Duck Comunista
Bem, sua geração de ruído certamente pode ser contínua, e geralmente é, porque você a suaviza. Para suavizar as fronteiras, talvez você precise ler um pouco além da fronteira, mas o princípio permanece o mesmo. Se o ruído em questão precisar de dados pseudo-aleatórios, você o gera a partir de quantidades conhecidas - ou seja. um hash do seu mundo coordena. As saídas são previsíveis.
Kylotan
2
Quanto à aleatoriedade, cada mundo pode ter seu próprio valor de semente, que é usado nos cálculos. por exemplo. sin (x + seed) em vez de sin (x), no meu exemplo acima. Cada semente diferente irá gerar um mundo diferente. E em relação à folha enorme ... não tenho certeza da relevância que isso tem. Não importa quanto ou quão pouco você gera ou quando o faz. O estado inicial do mundo é definido pela fórmula matemática, e você apenas usa essa fórmula para descobrir esse estado como e quando precisar.
Kylotan
32

Este tutorial que escrevi anos atrás pode oferecer algo parecido com o que você deseja:

texto alternativo

Se você fizer a modificação da ilha na última etapa, ela tenderá a uma única massa terrestre que não alcança a borda do mapa.

maravilhoso
fonte
7
Ótimas visualizações!
Zfedoran
3
Lembro-me de usar este tutorial ao fazer minha dissertação de mestrado sobre a simulação de fenômenos naturais. Eu usei o exemplo "hill" para criar a cúpula do céu sobre o meu mundo 3D. Excelente introdução ao conceito de geração de terrenos.
C.McAtackney
1
Louco, isso é demais! Eu não sabia que alguém realmente o usou.
munificent
1
AMD !!! Eu também usei isso em um projeto anterior ... a maneira mais simples de gerar terrenos que já encontrei !!!
War
15

Para criar uma ilha grande, você não precisa gerar tudo de uma vez. Eu criaria regiões de forma assíncrona quando você as visitar.

Em vez de usar uma máscara para criar a ilha como o artigo descreve, uma coisa que você pode fazer é brincar com os comprimentos de onda da oitava de ruído permanente para obter a aparência desejada. Geralmente, a primeira oitava descreve a forma geral do terreno. Todas as oitavas após ele simplesmente adicionam mais detalhes de grão fino. Portanto, brinque com o comprimento de onda da primeira oitava para controlar o tamanho das massas terrestres. Se você deseja que a massa de terra esteja no centro, você pode simplesmente reduzir o mapa de altura em uma quantidade crescente à medida que se afasta do centro e normaliza o ruído. Por exemplo, imagine combinar esses dois para criar sua ilha:

primeira oitava detalhes

Este artigo deve ajudar: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

Se você quiser aprender sobre mundos 3D infinitos e sobre vários truques que pode usar para alterar a aparência do terreno jogando com a entrada e saída de ruído, dê uma olhada neste artigo: http://http.developer.nvidia.com /GPUGems3/gpugems3_ch01.html

Pode ser um pouco difícil de ler se você não estiver familiarizado com a programação de pipeline e sombreador de gráficos.

zfedoran
fonte
O tipo de efeito que eu quero alcançar é algo como uma 2D em cima do mapa do Minecraft (não jogo) ... se eu usasse menos oitavas, ainda não precisaria gerar uma enorme folha de ruído permanente? Ou de alguma forma eu poderia gerar apenas uma quantidade muito, muito pequena?
The Duck Comunista
Eu acho que você ainda pode estar um pouco confuso sobre como o ruído permanente funciona. Você pode gerar blocos individuais de 16x16 blocos enviando à função as compensações das coordenadas xey para o ruído permanente. Observe como a função PerlinNoise_2D (float x, float y) recebe as coordenadas xe y. Em outras palavras, gera ruído para alguma posição (x, y). Além disso, gerar menos oitavas não é o mesmo que alterar o comprimento de onda das oitavas. Menos oitavas => Menos detalhes de grão fino. Comprimento de onda mais longo => mais ampliado.
zfedoran
Além disso, aqui está um artigo com o código que mostra como implementar Zoom / comprimentos de onda mais longos: dreamincode.net/forums/topic/66480-perlin-noise
zfedoran
7

O barulho e os amigos de Perlin são um bom ponto de partida, mas você provavelmente quer dar um passo adiante. A maioria dos geradores populares baseados em ruído fornecerá resultados bastante desinteressantes. Para tornar o terreno realista, você deseja dar uma olhada nos algoritmos que simulam os efeitos da erosão. Um dos simuladores mais avançados do mundo do jogo - o Dwarf Fortress - faz a simulação de erosão como uma das etapas de construção do mundo.

Uma das soluções bem legais que eu vi foi descrita no artigo "Advanced Particle Deposition" no Game Programming Gems 7. Existem muitas outras disponíveis na Internet, portanto há muitos recursos para extrair (por exemplo, 1 ou 2 ) .

Dominik D
fonte