10

O jogo No Man's Sky ainda não lançou mas já estou curioso a respeito da técnica que eles utilizaram para gerar o terreno do planeta. Acredito que processar um planeta em escalas reais seria bem surreal, ainda mais com um terreno gerado de forma totalmente randômica como o jogo parece demonstrar.

Em 8m45s do vídeo percebam que em uma certa distância parece que o terreno do planeta não é renderizado até que o jogador esteja próximo o bastante. https://youtu.be/ltJqu9778g0?t=9m45s

Eu tenho duas hipóteses sobre como isto poderia funcionar:

1 - Antes que o jogador entre na atmosfera do planeta, o planeta é apresentado em uma forma esférica, sem terreno. Mas quando o jogador entra na atmosfera do planeta o jogador na verdade está navegando em um terreno plano.

2 - O planeta é realmente uma esfera, mas o que muda é a definição de polígonos ao se aproximar.

Mesmo assim, não consigo compreender muito bem como funciona a técnica de geração de terreno, pois como podemos ver, um planeta tem todas as formas de relevo possíveis, como planícies, planaltos, depressões, e até cavernas.

12
  • 4
    Você precisa pesquisar por "geração procedural". Jogos como Elite Dangerous e No Man's Sky produzem seus sistemas, sóis e planetas baseados em fórmulas matemáticas. Usualmente os planetas podem ser feitos com várias técnicas diferentes, uma delas, por exemplo, é um "cubo com faces arredondadas", se tornando de fato uma esfera, mas sem precisar de cálculos com coordenadas esféricas em todas as situações. Além disso, importante conhecer algoritmos de LOD, (Level Of Detail), que desenham mais detalhes à medida que você se aproxima dos objetos (isso vale mesmo para jogos 3D "convencionais".
    – Largato
    Commented 7/05/2016 às 2:31
  • 1
    Aqui uma outra técnica, boa para jogos do tipo "tabuleiro", mas num mundo esférico: vickijoel.org/hexplanet - E para uma galáxia inteira, o sistema do Elite Dangerous youtube.com/watch?v=iTBvpd3_Vqk
    – Largato
    Commented 7/05/2016 às 2:34
  • 2
    Notar que não é "randomico", mas sim procedural. Tem uma série de fórmulas constantes sempre, que regem as regras desses universos. Uma das mais comuns é o "Perlin Noise".
    – Largato
    Commented 7/05/2016 às 2:41
  • 1
    Pra ser sincero, uma das primeiras coisas que eu quero testar com o Unity, é se dá pra fazer isso. No Unreal Engine, que eu gosto muito, eu achei extremamente chata essa parte de terreno (definitivamente o Unreal não foi feito pra esse tipo de coisa, apesar de possível). No Unity eu ainda não consegui parar pra analisar profundamente, mas quem sabe um dia. Eu me interessei por geração procedural desde que vi o 1o elite, e tentava entender como poderiam caber coordenadas e nomes de mais de 2000 planetas num disquete só. Na hora que "caiu a ficha" eu me encantei com a idéia.
    – Largato
    Commented 7/05/2016 às 2:50
  • 1
    Para gerar cidades, esses caras fizeram algo genial: eles se baseiam em caracteristicas de vários tipos de cidade: circulos concentricos, quadriculados, densidade das regiões, etc. youtube.com/watch?v=NsNP8-S5ygE
    – Largato
    Commented 7/05/2016 às 2:52

1 Resposta 1

9
+100

Ok. Sua pergunta é interessante, mas na verdade tem mais de um assunto nela. Vou dividir a resposta em duas partes.

Geração Procedural de Conteúdo

Como o colega @Bacco já explicou nos comentários, o conjunto de técnicas utilizadas na criação de cidades, planetas, labirintos, plataformas, música (sim, até música!), enfim, qualquer tipo de "conteúdo" em um jogo ou simulador, é chamado tradicionalmente de Geração Procedural de Conteúdo (do inglês Procedural Content Generation). Atualmente é mais comum simplesmente utilizar Geração de Conteúdo porque nem toda técnica utilizada é simplesmente "procedural" (no sentido de ser um algoritmo determinístico).

Pra vc já entender essa diferença, considere o seu próprio exemplo. Os planetas e seus terrenos podem ser criados por um simples algoritmo, mas uma vez criados são fixos. Diferentemente, após criados os animais têm comportamentos complexos e precisam se adaptar às ações dos jogadores (e mesmo de outros animais também criados pelo computador). Essa última parte requer técnicas um pouco mais avançadas, oriundas da Inteligência Artificial.

Há inúmeras abordagens para a criação de conteúdo, e descrevê-las todas aqui seria impossível. Mas dá pra te passar uma ideia geral. Um dos algoritmos clássicos é o Jogo da Vida, um dos primeiros autômatos celulares. Esse algoritmo funciona assim:

  1. O tabuleiro é uma matriz bidimensional (representando espaços para células vivas/mortas).

  2. Nele, sorteia-se (ou o usuário define) um conjunto de células iniciais (isto é, marca-se as células que estão preenchidas/vivas).

  3. O jogo aplica um conjunto de regras simples pra ir do estado atual para um próximo estado, em que algumas células "morreram" e outras "nasceram".

  4. Se houve alguma mudança, o jogo retorna ao passo 3 e faz a aplicação das regras novamente. Se não houve mudança, o jogo alcançou um estado de equilíbrio e se encerra.

O conjunto de regras que o Jogo da Vida utiliza é:

  • Qualquer célula viva com menos do que duas células vizinhas vivas morre (como se sofresse de solidão ou dos efeitos de baixa população).
  • Qualquer célula viva com dois ou mais células vizinhas vivas continua vivendo na próxima geração.
  • Qualquer célula viva com mais do que três células vizinhas vivas morre (como se sofresse dos efeitos de excesso de população - qualquer semelhança com a realidade é assustadora hehehe).
  • Qualquer célula morta com exatamente três células vizinhas vivas renasce (como se fosse resultado de reprodução na população).

Com um algoritmo simples assim, é possível gerar efeitos muito bonitos, como por exemplo o da Arma (Gun) de Gosper:

inserir a descrição da imagem aqui

Apesar desse exemplo particular nunca convergir (isto é, nunca "concluir" a geração de algo), há formas de garantir a convergência. Você pode limitar o número de iterações ou de tempo de execução, por exemplo. O resultado final vai ser algo gerado arbitrariamente.

É importante observar que arbitrário é diferente de aleatório. Algo escolhido de forma arbitrária pode parecer aleatório, mas teve regras por trás de cada escolha. Se alguém te pedir pra chutar um número de 1 a 10, vc pode chutar qualquer um e achar que não teve influência alguma nessa escolha, mas teve. Aleatoriedade mesmo só existe na natureza. De fato, uma escolha de termo melhor pra dizer a respeito do conteúdo gerado automaticamente por tais técnicas é emergente (mais a respeito no decorrer da resposta).

Técnicas similares são são os Algoritmos Genéticos, mas você pode essencilalmente criar de qualquer forma procedural se tomar cuidado com as regras. As regras são essenciais para de fato não deixar o conteúdo gerado simplesmente aleatório, e naturalmente vão ser mais ou menos complexas conforme o domínio do problema (isto é, o tipo de jogo).

A geração de ilhas em uma imagem, por exemplo, poderia ser feita da seguinte forma: em uma imagem em branco, sorteie aleatoriamente alguns pixels para serem "pintados" de preto; então, utilize um algoritmo de clusterização (como o K-Médias, explicado nesta minha outra resposta, por exemplo) para juntar os pixels aleatoriamente escolhidos em grupos (as potenciais ilhas); finalmente, desenhe elipses ao redor desses agrupamentos. A regra entra justamente no algoritmo de clusterização, em que você define, por exemplo, o número de ilhas desejado.

Outro exemplo clássico, e fácil de implementar, é a criação dinâmica de labirintos. A Wikipedia em inglês tem uma descrição bastante detalhada desse problema, com diferentes tipos de algoritmos, como o baseado em grafos (os pontos originais - em azul - servem para criar as salas que, quando ao serem representadas por outro grafo - em amarelo - permitem a construção de um caminho pela eliminação de arestas redundantes):

inserir a descrição da imagem aqui

P.S.: essa imagem também é um gif animado, mas sem loop. Você vai precisar recarregar a página para vê-lo em execução novamente.

Dependendo do conteúdo a ser gerado, há inúmeros algoritmos e opções. Música, por exemplo, comumente se baseia numa abordagem similar à do Jogo da Vida em que as notas musicais são as células e o tabuleiro é o pentagrama da partitura (as linhas e espaços onde as notas são posicionadas). Terreno já utiliza regras de movimentação dos personagens ou objetos do jogo (até onde alcança, onde pode ir, etc) e de atribuições físicas da fantasia (como, por exemplo, num mundo similar ao real, a água parada sempre se encontra em partes mais baixas do terreno e os rios sempre fluem das partes mais altas para as mais baixas, etc). Mas podem utilizar também regras de mais alto nível, principalmente quando envolvem a construção de cidades (os prédios precisam ser mais ou menos acessíveis de acordo com sua função, eles também precisam ser construídos próximas a fontes de água, etc).

Uma pequena lista que eu mantenho com artigos interessantes sobre geração de conteúdo pode ser encontrada aqui. Ela contém essencialmente material sobre conteúdo estático, mas está em uma página de IA pra jogos, onde vc pode achar mais dos assuntos que trato a seguir também.

Em relação à geração de conteúdo para agentes autônomos (que simulam inteligência), ai então há muito mais estudos e definitivamente foge do espaço que temos disponível aqui. Mas vale a pena citar o seguinte:

  • Steering Behaviours. Os Steering Behaviours (que poderia ser traduzidos como "Comportamentos de Condução", mas é melhor deixar no original porque geralmente não é mesmo traduzido) trata-se de algoritmos bastante simples para a implementação de alguns controles de movimentação em jogos. Tudo começou com o trabalho de Reynalds, mas o melhor local pra você aprender é nesse artigo do Game Development (em inglês). A ideia é que usando matemática vetorial simples e alguns conceitos de física, vc pode fazer um objeto ou personagem perseguir outro, fugir, evitar, ancorar (como uma nave/embarcação chegando num porto) ou até mesmo simular comportamento de rebanho (algo chamado de Boids). O comportamento de rebanho (que vc vê em cardumes de peixes, revoadas de andorinhas, e até em humanos durante o horário de rush do metrô - hahaha) pode ser simulado com três comportamentos simples continuamente executados por cada indivíduo de um grupo: separação (se afastar do ponto médio dos vizinhos mais próximos), alinhamento (girar no sentido médio dos vizinhos mais próximos) e coesão (se mover para o ponto médio dos vizinhos mais próximos).

  • Arquitetura de Subsunção. A Arquitetura de Subsunção (do inglês Subsumption Architecture) é amplamente utilizada em robótica. Ela advém do trabalho de Brooks, em que ele defende que animais conseguem ter comportamentos complexos sem precisar necessariamente representar e raciocionar lógicamente sobre o mundo. A ideia básica é que os comportamentos do agente são programados em camadas hierárquicas, de forma a mapear as percepções às ações de uma forma inteligente e adaptativa. Cada camada implementa um nível de adaptação, e a hierarquia decorre da importância de cada comportamento. Uma camada mais baixa (e assim, mais prioritária) poderia ser "procurar alimento". Ela poderia estar ativa em um dado momento, mas poderia ser "suprimida" (ou "subsumida") por uma camada inferior mais importante que fosse ativada, algo como "fugir de predador". As camadas recebem todas as percepções e funcionam em paralelo, gerando as saídas que são utilizadas na decisão das ações pelo agente. Apesar de ser essencialmente reativa, essa arquitetura é bastante interessante até mesmo para comportamentos mais complexos, e já foi utilizada em jogos de estratégia como o Diplomacy.

  • Arquitetura BDI. A Arquitetura BDI (do inglês Belief-Desire-Intention, ou Crença-Desejo-Intenção), já é um modelo simbólico que utiliza os conceitos de crenças (o que o agente sabe do mundo, geralmente atualizadas com base em percepções e também no resultado de ações), desejos (o que o agente precisa ou quer alcançar, seus objetivos de projeto) e intenções (aspectos objetivos similares aos desejos, mas com um caráter mais "prático" e que se traduz em planos de execução). Os planos de execução são realmente instruções (ou passos) que podem ser implementados em código. Essa é uma abordagem bem mais rebuscada do que as anteriores, mas já chegou a ser utilizada para simular a IA jogando jogos de tabuleiro e até para criar dinamicamente as narrativas em jogos digitais.

Como eu disse anteriormente, faz sentido chamar apenas de Geração de Conteúdo porque o comportamento de personagens inteligentes controlados pelo computador também precisa ser criado dinamicamente pelo jogo do seu exemplo. Ainda assim, quando vc ver por ai o termo "Geração Procedural", ele comumente trata apenas de elementos fixos. Mesmo envolvendo personagens, há elementos fixos que precisam ser criados. O jogo Black & White, por exemplo, utilizou algoritmos genéticos para determinar os objetos que cada criatura pode comer (algo que não muda necessariamente durante a execução do jogo) e até mesmo as características das diferentes criaturas. Essa distinção é importante para a próxima parte.

Técnicas de Melhoria de Desempenho

Tendo tudo isso em mente, é importante observar que a criação de conteúdo nem sempre é efetuada dinamicamente conforme o jogo é executado. Caso contrário, o processador do seu videogame ficaria o tempo todo ocupado apenas com isso e não teria capacidade para processar mais nada. Grande parte da geração de conteúdo é efetuada antes do jogo ser executado, particularmente durante a construção do jogo, mas também em um passo inicial caso o jogo precise ter variedade a cada nova execução.

Os planetas que vc vê no vídeo que referenciou são quase que certamente modelos construídos antes daquele momento. Mas a diferença de renderização que você bem observou (e que é bem mais visível no apareceimento gradual das ilhas no minuto 0:40) é decorrente de uma abordagem (ou técnica) que objetiva dar ainda mais desempenho de execução ao jogo, e que não tem necessariamente a ver com a geração procedural de conteúdo.

O melhor exemplo é um jogo de corrida. Imagine um jogo de corrida simples, em que a pista é ladeada de coqueiros. Os coqueiros que são apresentados ao longe, estão pequenos devido à distância. Assim, não faz sentido já incluir um modelo tridimensional de uma árvore ali, e sim apresentar uma imagem bidimensional (chapada mesmo) com baixa resolução. Em primeiro lugar, o jogador não vai dar atenção àquele coqueiro, porque sua atenção está no carro e nos arredores dele. Em segundo lugar, o carro vai demorar pra chegar até ali, então sequer os cálculos necessários para checar colisão (se o carro bateu na árvore) precisarão ser efetuados. Logo, basta a imagem simples.

Conforme o carro se aproxima, o código do jogo decide por trocar essa imagem por uma imagem (ainda bidimensional) de mais alta resolução (isto é, com mais detalhes), apenas por uma estética visual melhor. De fato, essa imagem (mais "pesada", porque ocupa mais memória, demora mais tempo pra carregar, etc), poderia já estar sendo carregada em outra thread enquanto o jogo utilizava a imagem mais simples, de forma a fazer o jogo correr bem sem precisar daquelas telas chatas de "loading...". Quando o carro chega mais próximo, o jogo decide por já colocar um modelo 3D da árvore, mas ainda sem um colisor (colisores são estruturas internas, não visíveis ao jogador, que auxiliam nos cálculos de colisão entre objetos em um jogo). Afinal, o carro ainda está longe, e não faz sentido fazer o jogo ficar calculando testes de colisão pra algo impossível de ocorrer. Finalmente, conforme o carro se aproxima realmente da árvore, o jogo adiciona o colisor ao modelo tridimensional, pois agora há chances de uma colisão que precisará ser detectada.

Essa técnica pode envolver qualquer tipo de mudança/melhoria dinâmica. Mesmo os modelos 3D podem ter níveis de detalhes diferentes e serem trocados confome a mudança de foco do jogador. Como no caso do seu jogo, pode envolver também a troca de texturas por algo mais detalhado até precisar construir o modelo 3D (terreno) somente quando o jogador (a nave) estiver mais próximo. Há inúmeras outras, e os game designers comumente trabalham juntamente com os programadores para ter soluções criativas. Ao invés de usar uma tela de "aguarde, carregando o jogo", o jogo Batman Arkham Asylum, por exemplo, tem uma cena em que o personagem (o Batman! Seja sempre o Batman! rs) entra em um prédio com um grande campo aberto. No centro, sobre uma cabine, o Coringa faz um discurso eloquente. Esse discurso, além do uso na história do jogo, serve também para convergir a atenção do jogador para o centro da cena enquanto as texturas nas laterais e, principalmente, atrás do avatar estão sendo carregadas (uma técnica que os mágicos já conhecem de cor e salteado).

Considerações Finais

A geração dinâmica de conteúdo tem o objetivo de permitir a produção de conteúdos diversos, diferentes e até mesmo inesperados para um jogo. De certa forma ela provê variedade, evitando a mesmice. Mas isso não tem necessariamente a ver com os truques de melhoria de desempenho. Alguns jogos antigos, como muitos do Atari, costumavam empregar geração automatizada de conteúdo simplesmente pra gerar novas fases, mas isso tem o problema de não garantir que todas as fases sejam de fato divertidas. Os jogos modernos têm level designers que utilizam ferramentas de geração de conteúdo como apoio, muito embora eles é que garantam que a fase é divertida com trabalho manual.

Ou seja: vale notar que os game designers geralmente não gostam de adaptação totalmente dinâmica e automatizada em jogos, porque isso tira deles o controle sobre a experiência dos jogadores.

Ainda assim, há todo um esforço crescente na indústria e na universidade para a criação de jogos vastos (o que é comumente chamado de "mundo aberto"), com muita variedade, ou com narrativas ou personagens que se alteram conforme o jogador atua no jogo. Esse tipo de abordagem se chama gameplay emergente (no sentido de que emerge, de que surge). Se você tiver interesse, um livro fantástico sobre esse assunto que cobre um pouco de tudo que eu explorei nesta resposta (e mais!) é o livro Emergence in Games (sem tradução para o Português ainda - até onde eu sei).

inserir a descrição da imagem aqui

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .