Conforme escrito em posts
recentes , lutei para obter os detalhes corretos do litoral no meu jogo
Dragons Abound . Minha decepção surgiu durante a implementação das
ilhas barreira . Para criar a ilha mais estreita possível, criei uma localização ampla - na figura abaixo, cada localização é um triângulo de Delaunay:
Isso foi bastante desagradável - tanto porque a ilha estava muito quebrada quanto porque o tamanho das peças era muito grande. Parecia que com um forte aumento no número de triângulos de Delaunay (isto é, com uma forte diminuição de tamanho), esse problema seria resolvido - mas a densidade de triângulos que eu precisava levou a uma falha no navegador.
Resolvi esse problema separando os contornos da terra da representação interna dos locais. Isso me permitiu desenhar ilhas de qualquer tamanho ou forma, independentemente da grade de localização subjacente:
Então o problema está resolvido! Isso me permitiu desenhar as ilhas barreira e, como o litoral não é mais necessário para seguir a grade básica, se necessário, um litoral mais detalhado pode ser criado da maneira usual e, em seguida, adicionar detalhes.
Mas ... como adicionamos detalhes ao litoral? Não é tão fácil quanto você imagina. Como eu queria criar um litoral fractal, considerei usar
fractais para adicionar detalhes ao litoral:
Tendo experimentado as configurações, pude adicionar muitos detalhes e coisas interessantes ao litoral. No entanto, o sistema não pôde criar algo parecido com esse mapa:
O ruído Perlin
pode criar esse tipo de terreno se houver uma grade de base suficientemente detalhada, mas isso pode ser feito
sem armazenar as alturas de elevação na grade de base com a resolução desejada (porque sei que isso quebrará meu código)? Até eu descobrir como fazê-lo. O litoral é essencialmente um caminho através de todos os pontos nos quais a função de ruído Perlin tem um valor zero. Embora possamos aprender diretamente com a função de ruído Perlin o valor em um local específico (X, Y), não podemos encontrar (digamos) "todos os locais em que a função tem um valor zero". Ou seja, é difícil ver como desenhar um contorno de alturas sem uma grade básica.
Pior ainda, perguntei a
Amit como fazer isso, e ele também não sabia a resposta. Uma coisa é que não posso dizer isso, mas quando mesmo uma pessoa tão inteligente não pode dar uma resposta, começo a pensar que isso não pode ser feito. Isso é triste Posso dar à costa a forma que precisar, mas não consigo as formas necessárias sem uma grade de base muito detalhada.
Então, como obtenho uma grade de alta resolução sem quebrar o código?
Uma das soluções que me veio à mente me lembra o que
Azgaar fez em seu gerador de cartões - células Voronoi de tamanho variável. A idéia principal é aumentar a densidade (e diminuir o tamanho) da malha base ao longo da costa e manter uma densidade menor nos oceanos e em outras áreas que não exigem detalhes. Com esta opção, terei muitas células de malha apenas nas áreas em que você precisa de detalhes. Essa mudança será bastante difícil de implementar em
Dragons Abound , mas quero ponderar sobre isso. Por outro lado, o próprio Azgaar
não ficou muito satisfeito com essa abordagem , portanto, isso também precisa ser levado em consideração.
Paralelamente, eu queria investigar as causas de uma falha do navegador ao processar uma pilha de triângulos. As ferramentas de desenvolvedor no Chrome me forneceram informações detalhadas de desempenho. Não sou especialista em usar essas ferramentas, mas muitas funções são simples o suficiente para qualquer um entender. Caso você queira descobrir a quantidade total de memória usada no programa, a guia Memória contém informações sobre a capacidade usada atualmente:
Nesse caso, abri a página da Web do Azgaar e ela ocupa 20 modestos de memória. Você pode usar esta ferramenta para descobrir quanta memória os
Dragons Abundam ocupam e para determinar quando a guia trava.
O parâmetro básico que controla a resolução da malha subjacente em
Dragons Abound é habilmente chamado de "npts" (Número de pontos). Para cada área de unidade do mapa (os mapas das regiões que eu costumo usar como exemplos têm uma área de 1 unidade).
Dragons Abound cria um determinado número de locais da grade base. Normalmente, uso 16K (16384) para npts, o que significa que cada local da grade corresponde a aproximadamente 70 pixels quadrados da tela em uma escala de zoom padrão.
Obviamente, a quantidade exata de memória usada depende do cartão, mas para o cartão mostrado acima com 16K pontos, você precisa de aproximadamente 92 MB:
Isso é menor do que eu esperava e, para ser sincero, um número bastante modesto.
Se você dobrar o número de pontos na grade base, a capacidade da memória aumentará para 138 MB:
O tamanho da memória ocupada não dobrou, porque parte dessa memória é ocupada por recursos e outras estruturas de dados cujo tamanho não foi alterado. 16K pontos adicionais "pesam" cerca de 50 MB de memória, ou seja, cada ponto como resultado ocupa aproximadamente 3 KB de memória. Isso é mais do que eu esperava, mas, em geral, o volume ainda é bastante modesto. Em um computador com 64 GB de memória, 150 MB é quase imperceptível.
Depois de fazer mais algumas duplas, descobri que a aba com
Dragons Abound geralmente falha em cerca de 128K pontos. Se o pegarmos antes de sair e verificarmos a memória, veremos o seguinte:
Supus que a guia travasse devido à memória ocupada, mas geralmente o problema não está na memória. Por que a guia trava? A única pista é que a guia não falha antes que o mapa termine, e isso é provavelmente uma indicação de que uma falha ocorre durante a renderização.
É lógico supor que o SVG que eu crie sobrecarregue o renderizador do navegador devido ao seu tamanho ou complexidade. Para começar, posso descobrir quantos elementos SVG crio. No D3, posso obter o número total de elementos SVG criados usando
svg.selectAll('*').size() .
Correndo a partir de 16K pontos e verificando o número de elementos SVG me mostrou o seguinte:
32K pontos têm 65457 elementos e 128K pontos têm 258823. Cada ponto adicionado à grade base adiciona dois elementos ao mapa. Eu acho que encontrei uma fonte de infortúnio.
Cada ponto da grade base adiciona elementos SVG devido à maneira como os
Dragons Abound processam a terra (e a água). O terreno é renderizado renderizando cada local de base como um polígono preenchido, seguido de um desfoque de todos eles. Isso permite que os
Dragons Abound dêem à terra um belo padrão ou usem a altura da terra para renderizá-la com sombreamento 3D, como mostrado aqui:
Você pode desativar a visualização de terra e oceano para verificar quantos elementos SVG são criados. Em 256K pontos:
Uau, o número de elementos SVG caiu significativamente. Como eu esperava, agora o mapa é renderizado sem bater! Ou seja, se você evitar usar uma grade para renderizar terra e água, poderá criar uma grade muito mais densa do que antes.
Agora que tenho uma grade de Voronoi muito mais densa, quero verificar se ela me permite gerar os elementos de alívio da terra de que preciso, como ilhas costeiras. A malha densa de Voronoi cria outros problemas (especialmente com rios), então desligarei tudo, exceto as costas, para acelerar os testes e focar neles. Aqui está a renderização original de algum litoral em 256K pixels e com ruído padrão:
Acontece que o mapa renderiza bem e já cria um litoral muito mais bonito.
Mesmo sem ajuste cuidadoso, o resultado é muito melhor. O barulho cria os tipos de linhas costeiras e ilhas costeiras que eu indiquei no mapa acima.
Aqui estão as ilhas com um aumento de 300%:
Com esse aumento, você pode observar artefatos de triângulos da grade base, mas, mesmo assim, as ilhas podem criar formas interessantes. Você pode usar a suavização de serrilhado (como eu faço na versão atual dos mapas) para se livrar de alguns dos artefatos mais visíveis dos triângulos. Na ampliação padrão, isso proporciona uma costa menos acidentada, mas também elimina alguns pequenos detalhes:
Você provavelmente precisa se sintonizar para obter um meio termo.
A maioria dos geradores de sushi processuais usa o ruído Perlin para criar um mapa de altura. Precisamos encontrar os parâmetros de ruído apropriados, selecionar uma semente e, em seguida, usar o valor do ruído em cada local (x, y) para definir a massa da terra. Um aspecto conveniente de fazer terra é que, se você precisar de mais detalhes sobre o litoral, poderá simplesmente ajustar os parâmetros de ruído.
No entanto,
Dragons Abound não cria terras dessa maneira. (Ou pelo menos cria mais do que isso.)
Dragons Abound usa muitos métodos diferentes para criar sushi. Embora todos usem o ruído em um grau ou outro, muito poucos criam terra diretamente a partir do ruído. Por exemplo, o jogo possui um procedimento para criar uma ilha, que cria uma máscara para a ilha (geralmente uma elipse), usa ruído para tornar a elipse mais natural e, em seguida, aplica um ruído diferente para aproximar o preenchimento da máscara. Cada mapa específico é geralmente criado por uma combinação de vários procedimentos diferentes. Portanto, adicionar detalhes ajustando os parâmetros de ruído para
Dragons Abound não
é muito adequado.
Para meus propósitos, é melhor abordar o problema de um ângulo um pouco diferente. Se eu tenho um mapa de elevação específico que define massas de terra, como adiciono detalhes às bordas dessas massas de terra? Isso pode nos levar à idéia de que precisamos reconhecer as margens das massas de terra e mascarar o resto do mapa, etc. Mas, por outro lado, não sou contra a adição de detalhes adicionais ao restante do mapa. Se a terra é um pouco mais irregular ou o fundo do oceano é um pouco mais áspero, isso é normal.
O que significa adicionar detalhes ao litoral? Um litoral é simplesmente uma linha de contorno na qual um mapa de altura tem um valor zero. (O valor é arbitrário, mas esse princípio é usado em todos os geradores de terra procedimentais.) Para tornar essa linha mais detalhada, é necessário deslocar um pouco a terra ao lado dessa linha de contorno um pouco para cima e para baixo, para que linhas costeiras simples se tornem mais complexas, partes da terra se projetem para o oceano e se tornem ilhas e assim por diante. Mas isso não deve acontecer por acaso, quero que as mudanças pareçam naturais. Resumimos tudo isso e parece que você precisa adicionar uma pequena quantidade de ruído a todo o mapa. E, na verdade, foi exatamente isso que fiz no exemplo original mostrado acima.
Obviamente, isso deve ser feito com cuidado para não apagar as massas de terra criadas e criar outros problemas. Essencialmente, preciso configurar três parâmetros.
O primeiro é a escala do ruído. Uma escala é simplesmente um intervalo de valores para esse ruído. No nosso caso, quero diminuir algumas áreas e aumentar algumas, para que a faixa de valores seja de negativa para positiva. No entanto, não quero adicionar novas montanhas ou criar um oceano longe da costa existente, portanto tornarei o valor máximo (absoluto) do ruído uma pequena fração da altura padrão da terra.
O segundo parâmetro é a principal frequência do ruído. A frequência determina a rapidez com que o ruído muda dentro do local. O ruído de baixa frequência muda muito lentamente, portanto uma área positiva com ruído de baixa frequência pode (por exemplo) cobrir o mapa inteiro. O ruído de alta frequência muda rapidamente, de modo que uma região positiva com ruído de alta frequência pode (digamos) ter o tamanho de uma pequena ilha. No nosso caso, a principal frequência de ruído determina os maiores elementos de alívio que veremos no ruído. Ou seja, se eu quiser que o ruído adicione (digamos) pequenas ilhas (mas nada maiores que elas) ao mapa, preciso selecionar a frequência principal do tamanho de uma pequena ilha.
Você pode pensar que isso é fácil de fazer (basta medir uma pequena ilha e atribuir esse tamanho à frequência principal). No entanto, a frequência é medida nas coordenadas da função de ruído, não nas coordenadas do mapa! Uma função típica de ruído pode ter um intervalo de 0 a 255 em cada coordenada, e um mapa pode ter um intervalo de -1 a 1. Em cada coordenada, o que é pior, as coordenadas de ruído são reduzidas e muitos usuários que usam ruído nem percebem isso. A tradução de uma unidade para outra e a determinação de frequências adequadas são confusas; portanto, geralmente é mais fácil experimentar apenas intervalos de frequência e escolher a que cria os elementos do cartão do tamanho certo.
O terceiro parâmetro é o número de oitavas de ruído. As oitavas são camadas adicionais de ruído. Cada camada geralmente dobra a frequência e reduz pela metade a escala de ruído. Ou seja, cada nova camada adiciona elementos de alívio duas vezes menos que a camada anterior, mas também duas vezes mais fraca. Ou seja, você precisa escolher o número de oitavas que fornece o mínimo de elementos necessários e, para isso, pode ser necessário ajustar a escala de ruído, porque ainda é forte o suficiente na oitava mais alta para aparecer no mapa. Como intencionalmente faço isso para tornar as costas muito complicadas, usarei algumas oitavas de ruído.
Vamos começar com a instalação. Para começar, gerarei um mapa de exemplo sem ruído adicional:
Obviamente, este é um litoral chato, com linhas suaves e apenas algumas ilhas grandes. Aqui está o mesmo litoral da amostra de ruído original:
O barulho mudou significativamente a forma do mapa, transformando grandes fragmentos de terra em um oceano e vice-versa. Muitas ilhas também apareceram, inclusive no mar. Tudo isso indica que a escala de ruído é muito grande. Os maiores elementos de alívio individuais adicionados pelo ruído devem ser do tamanho das pequenas ilhas do mapa original. Este é provavelmente o tamanho máximo novo dos elementos, provando que a frequência principal do ruído é aproximadamente escolhida corretamente. Por fim, muitos pequenos detalhes apareceram, até os limites do tamanho da tela, e isso mostra que há oitavas suficientes. (No entanto, o número de oitavas pode ser maior que o necessário. Isso não afeta a aparência do cartão, mas é ineficiente.) Parece que basicamente você precisa ajustar a escala de ruído.
Ajustar o ruído é uma operação bastante complicada, porque quero que esse ruído afete principalmente terra e água em uma linha de contorno com uma altura = 0. Ou seja, preciso de uma escala relativamente pequena, mas não está claro como escolher o número certo, porque em mapas diferentes, a distribuição das alturas varia. A solução é encontrar a escala certa em tempo real. Você pode pegar todos os valores absolutos das alturas no mapa, classificá-las e encontrar o ponto de corte que seleciona (digamos) 10% dos locais em torno de zero. Todos esses locais caem no intervalo (por exemplo) [-0,05, 0,05] e, em seguida, posso usar o valor 0,05 para determinar a escala do ruído adicionado.
(Escrevo "definições" porque, por várias razões, você não pode usar apenas 0,05. Primeiro, você precisa transformar a terra em água e vice-versa. A adição de (digamos) 0,002 a -0,05 não fará nenhuma alteração visível no mapa. Ou seja, o intervalo deve ser muito maior que 0,05 se eu quiser converter uma proporção significativa de locais com uma altura de -0,05 da água para a terra.Em segundo lugar, as funções de ruído não são
distribuídas uniformemente , portanto, com uma escala de 0,05, a função de ruído nunca retornará realmente o valor 0,05! Na prática, a dificuldade é que a escala deve ser muito maior do que os maiores valores que queremos ver com bastante frequência.)
Depois de experimentar, encontrei um valor que agrega complexidade às costas, sem alterá-las significativamente, e também cria um pequeno número de ilhas:
Como sempre, esses parâmetros no jogo podem levar um intervalo de valores, para que eu possa obter uma ampla variedade de mapas: de mapas com costas razoavelmente suaves a mapas com bancos complexos e quebrados. Deixando o programa selecionar os valores, obtive o seguinte resultado:
As costas estão no lado mais suave, mas ainda há a maior complexidade da escala média e um número suficiente de novas ilhas.
Ao implementar linhas costeiras fractais, percebi a capacidade de controlar o nível de fractalização usando a função de ruído, para que algumas áreas tenham costas suaves, enquanto outras terão linhas complexas. Eu pensei que isso aumentaria muito o interesse do mapa e pareceria menos "gerado", então adicionarei esse recurso aqui. A ideia é bastante simples - antes de adicionar ruído do litoral ao mapa, multiplico-o pela saída da segunda função de ruído, que varia de zero a 1. Onde essa função é pequena, pequenos detalhes serão adicionados ao litoral. Onde estiver próximo de 1, detalhes adicionais serão adicionados na íntegra. Selecionando a escala da segunda função de ruído, que varia lentamente ao longo do mapa, vou obter algumas áreas com linhas costeiras complexas, algumas com linhas simples e transições lógicas entre elas:
Aqui eu ampliei os parâmetros costeiros, para que a diferença seja mais visível. Vemos costas selvagens e acidentadas no nordeste e praias mais suaves no oeste.
Portanto, melhoramos significativamente a geração da costa, mas ainda não consigo gerar um mapa completo com tantos triângulos em Delaunay. Eu só mostro mapas de estrutura de tópicos porque muitos outros elementos do mapa estão quebrados. Ele precisa ser consertado.
O restante do programa não funciona bem com tantos triângulos de Delaunay (com as configurações atuais de 256K). O principal problema é que os
Dragons Abound desenham terra e água desenhando todos os triângulos individuais, e muitos elementos SVG fazem com que o navegador trave. Então eu tive que desativar completamente a renderização de sushi. Provavelmente existe uma maneira de contornar esse problema, mas ter tantos triângulos cria outros problemas. Por exemplo, algumas partes do programa devem processar o mapa inteiro. Cada um deles se torna dezesseis vezes mais lento em locais de 256K do que em locais de 16K. Também no código, existem partes (por exemplo, um novo modelo de precipitação) que se quebram ao trabalhar com tantos triângulos. E com a criação de uma grade tão detalhada de locais, não ganhamos nada - depois de gerar o litoral, nada melhora com a complexidade adicional. Portanto, embora eu possa revisar o programa e corrigir as áreas em que um grande número de locais diminui a velocidade ou quebra o código muito, parece mais fácil reduzir a resolução da grade do mapa após a criação de linhas costeiras.
Como mencionado acima, Azgaar já realizou um
trabalho para alterar a resolução da grade de Voronoi subjacente ao mapa. Ele percebeu a possibilidade de alterar a resolução da rede em tempo real no processo de geração, ou seja, ele poderia (por exemplo) aumentar a densidade de locais ao longo da costa. No entanto, uma mudança local na densidade tem suas desvantagens - em particular, cria estranhos triângulos ao longo da borda. Azgaar mais tarde
sugeriu que o sistema é muito complexo e não vale o esforço. Azgaar geralmente sabe do que está falando, então vou aceitar a palavra dele e não tentarei reembalar a malha finalizada.
Em vez disso, criei uma segunda grade com a resolução (inferior) desejada e copiei o mapa de elevação para essa nova grade. (Não se esqueça que
Dragons Abound agora armazena
linhas costeiras separadamente da grade, portanto, depois que elas são criadas, elas não dependem mais do ajuste exato da grade. Para fazer isso é um pouco complicado. Como a grade original tem uma resolução muito mais alta que a nova, muitos locais na original a grade será sobreposta em um local na nova grade. Cada um desses locais de origem tem uma altura diferente no mapa de altura, como posso copiá-los? Usar a média? ou a altura máxima (mínima)?
Para começar, basta selecionar um local aleatório para ver se a nova grade funciona com o restante do programa:
Tudo saiu surpreendentemente bem. Um pequeno erro ocorre quando novos locais não são adequadamente marcados como terra, costa ou água, mas depois de resolver esse problema, a geração do mapa funcionou bem. Você precisa limpar pequenas falhas (por exemplo, a etiqueta Palmanor que saiu na água), mas no geral parece boa. Até as pequenas ilhas ficaram lindas.
No final, decidi que, com uma diminuição na resolução da grade de Voronoi, cada local seria a média dos locais de base. Parece uma decisão sábia e, se necessário, sempre pode ser alterada. Esta imagem mostra como, como resultado, as costas foram separadas da malha finalizada:
Para resumir: em
Dragons Abound , uma grade de triângulos Delone de resolução muito alta é usada ao gerar o mapa de altura. Após sua conclusão,
Dragons Abound define
linhas costeiras rastreando transições de valores negativos para positivos no mapa de altura. Em seguida, o jogo copia a grade de alta resolução para uma grade de resolução muito mais baixa, calculando a média dos locais que se enquadram em um local da nova grade. Em seguida, a grade de alta resolução é descartada e o restante da geração e visualização de procedimentos continua na grade de baixa resolução. Uma questão interessante é se o uso da malha de Delaunay tem algum valor nesse estágio; pode valer a pena copiar para uma grade de hexágonos ou algo semelhante.