Explorando algoritmos de geração procedural e aleatória para aprimorar jogos digitais

  728 vizualizações

Fev 18, 2023 por Calango Team

Imagine um mundo onde as possibilidades só dependem da extensão e flexibilidade de suas regras, onde praticamente qualquer forma é possível, constantemente se transfonando, remodelando e readaptando-se conforme sua própria vontade ou entendimento?

Pesoal, pesquiso a geração procedural a muito tempo, este artigo teve sua primeira versão em 2017, aprimorei e o atualizei somente na atualidade. O original, escrito também por min, encontra-se no Internet Archive, escrito em 13 de Março de 2017 às 22:27.Sendo esta a referência principal da atualização.

Se deparar com tal reflexão no inicio de um artigo pode ser difícil até mesmo para os veteranos do desenvolvimento de jogos ou da própria Inteligência Artificial (IA), pois tal pergunta poderia gera ainda mais interrogações. Gostaria então de convidar você a ler um artigo instigante, mas não somente conteudista, uma leitura técnica, com material para você criar sua proporia "Fórmula", entender e utilizar o poder da autogeração.

Mensagem do pixelarte:

Para acessarmos a criatividade, teremos que ignorar, grande parte dos processos conhecidos, passando por uma reciclagem daquilo que já existe, para finalizarmos descobrindo aquilo que irá existir.

Ivan Teorilang

Auto geração e a indústria de jogos

Há algum tempo temos visto vários jogos incríveis com a temática de geração automática ou procedural, O Minicraft da Mojang Synergies AB é um modelo a ser seguido, você inicia um novo jogo (um novo game save) e um novo mapa é criado, com novas possibilidades, construções, recursos e está lá esperando você explorar e construir o que bem entender se tiver habilidade para isso. O tempo em que Minecraft tem sobrevivido no mundo dos games prova o quanto uma abordagem deste tipo tem potencial, uma nova categoria tem sido criada em cima desta perspectiva, são chamados "Jogos Criativos", games que permitem o jogador dar vida a imaginação, controlar o andamento do jogo, modificando o mundo a sua volta, seus elementos e até mesmo sua história.

Talvez poucos de vocês saiba, mas esse tipo de jogo já vem sendo estuado e desenvolvido a muito mais tempo, em 1980, tivemos o game Rogue, devido a limitação de vídeo da época o jogo inteiro era desenrolado em prompt de comando com caracteres da tabela ASCII. O game era bem popular e praticamente infinito e gerou uma subcategoria de jogos de videogame, os chamados "Roguelike". Diversos jogos surgiram a partir deste game, como Tales of Maj'Eyal, NetHack, Ancient Domains of Mystery, WazHack, um mais recente e bem conhecido,The Binding of Isaac entre outros da categoria.

Outro grande titulo que fez uso da autogeração é o game Tetris (1984), pois a fase a ser gerada deveria ter peças encaixáveis e deveriam ter montagens diferentes baseadas em regras como nível de dificuldade, numero de encaixes e outras métricas de geração. Não poderíamos esquecer neste artigo de citar um game de ação baseado em RPG, que fez uso da autogeração de forma a deixar seu nome na história, Diablo (1996), criado pela Blizzard Entertainment, modernizou o estilo rogueulike com elementos únicos e conquistou milhares de fãs.

Nos últimos anos diversos games tem utilizado a capacidade de autogeração, como Spelunky, No Man's Sky, Scrap Mechanic, Stardew Valley entre outros que não devo ter conhecido/citado até agora. Minha primeira dica deste tutorial é para você estudar estes jogos, entender seus conceitos e seu funcionamento na forma estética, dinâmica e mecânica, ou seja, conhecer o lado gameplay dos jogos para pensar em como reaproveitar essas técnicas em seu futuro jogo e assim criar seu algoritmo de geração, sua própria formula como disse anteriormente.

Geração randômica VS Procedural

Bom, muitos de vocês devem ter olhado a lista de jogos que passei e pensado, "Mas isso não usa autogeração sempre!!! É sempre o mesmo cenário!", este é o primeiro confronto de nosso estudo, devemos entender que a autogeração não existe apenas para criar terrenos e cenários, podemos criar desde o personagem a uma complexa história, depende apenas do algoritmo que implementarmos. O designer de jogos tem sido abençoado com a autogeração, facilitando a criação de terrenos, cenários, objetos, musicas, história e muito mais!

A autogeração pode ser utilizado como um recurso de gameplay, como ocorre no Minecraft, onde um novo mundo é gerado, ou como ferramental de designer, para este último, a finalidade é reduzir e otimizar a criação de um jogo, por exemplo, vamos criar um grande terreno 3D de um jogo em mundo aberto, colocaríamos montanhas, arvores, vulcões, crateras, água, lagoas, cavernas e uma diversidade de outros elementos, poderíamos simplesmente gerar um algoritmo que construísse esse cenário e em cima dele iriamos modificar o que foi gerado, fazendo melhorias e readaptando o que foi gerado a nossa vontade, como um ajuste fino, ou seja, a autogeração aqui seria utilizada para diminuir o tempo do level design.

No estudo de autogeração você irá se deparar com duas vertentes de pensamento, a geração Randômica e a Procedural. A geração randômica compreende uma possibilidade praticamente infinita, limitada apenas pelos recursos disponíveis, como espaço de memória, disco, processamento e etc., enquanto a Procedural é interpretada como um conjunto de estruturas e regras (procedimentos) que são combinadas e readaptadas, cada interação dessa gera uma nova possibilidade, porém estas são limitadas pelo número de regras e estruturas disponíveis.

Qual abordagem utilizar? Entenda bem, certos momentos podemos ter a randomização, outros não, imagine criar um algoritmo livre de limites, este poderia usar mais memória que devido ou criar um mundo grande demais para qualquer pessoa se interessar. Logo, o mecanismo procedural vem para fazer justamente esse tipo de controle, Minecraft tem possibilidades gigantescas de mundos, centenas, milhares ou até bilhares, mas mesmo sendo um número alarmantemente grande, ele é limitado, isso garante o funcionamento do jogo dentro de padrões esperados, como por exemplo, criar um mundo "DESDE QUE" use um máximo de memória e gerencie uma quantidade X de inimigos, pois o game foi desenvolvido para vários sistemas e consoles e criar um algoritmo de geração preocupado com tais aspectos é o melhor a fazer no designer e desenvolvimento de jogos.

Com isso, podemos através da geração procedural controlar os resultados de um algoritmo, controlar os limites de um procedimento randômico para que ele não saia do controle e ter de certa forma, maneiras de corrigir (uma vez que conhecemos as regras, podemos depura-las) e criar perspectiva em cima de um algoritmo, temos uma possibilidade de inserir mecanismo para mensurar nosso projeto de autogeração.

O uso de "SEMENTES" (Seed) para randomização

A utilização de números randômicos, valores gerados aleatoriamente, é bem comum, mas tem um problema persistente, por exemplo, imaginemos que queremos um número qualquer entre 0 e 10, e notamos uma tendência a sair o número 4, ou seja, temos uma sequência gerada sempre da mesma maneira ou tendenciosa, seria ruim e em certo termo ou até mesmo injusto com o jogador, temos que ter certa uniformização na saída deste valor aleatório. Para mudar isso, vamos alimentar a função randômica com uma semente/alimentação, com um número, que é o "tempo atual" (como a maioria dos autores chama). O exemplo a seguir é um código C++ que tem esta funcionalidade, você pode baixar o DevC++ e testa-lo:

// Geração randômica de valores

#include <iostream>
#include <stdlib.h> 
#include <math.h>

using namespace std;

int main(){
	// Aqui chamamos os srand(100) que semeia a próxima chamada randômica.
	srand(100);
	while (true){
		cout << "Pressione enter para gerar um valor randômico:";
		cin.get();

		// Gerando valor randômico inteiro
		int randomInteger = rand() % 201 + 50;

		cout << randomInteger << endl << endl;
	}

	return 0;
}

Teste o algoritmo:

Geração Procedural

Logo, você começa a entender que existe o uso da randomização e que ela pode ser controlada, medida e gerenciada, sendo estas possibilidades disponibilizadas pela linguagem utilizada ou pelo desenvolvedor. O que queremos quando dizemos que vamos criar um jogo com funcionalidade procedural é que iremos ter um jogo que com alguns "módulos" disponíveis pelos desenvolvedores, utilizando-os de forma dinâmica, transformando-os, remodelando ou até mesmo juntando-os possamos criar algo novo, ou em outro contexto ensinar a própria máquina como fazer isso, tais módulos são nossos procedimentos, nossas ferramentas, que tornam isso possível.

A seguir será disponibilizado e demonstrado algoritmos que criamos para você entender o funcionamento e criação da funcionalidade procedural. O estudo e conhecimento a seguir é a base para seu entendimento de como criar jogos com autogeração. Por isso, comente o artigo, faça uso do que é compartilhado aqui e crie seus jogos de forma a treinar esse pensamento.

Os exemplos foram criados em HTML5 e JavaScript, devido a expansão do uso desta linguagem e sua simplicidade, bem como o paradigma orientado a objetos. Para que possamos ter um SEED eficiente para geração de valores em nosso código, como explicado no tópico anterior, no JavaScript fazemos uso de uma biblioteca open soruce chamada 'seedrandom', você pode obtê-la aqui.

Gerando terrenos retangulares

Este primeiro exemplo, mostra uma forma de geração de salas (definimos seu numero) de tamanhos aleatórios em um ambiente (este com certo tamanho) para um jogo roguelike. Perceba que o código está comentado para seu estudo. A função que inicia toda a construção das salas é o 'init();', sendo esta função chamada quando carregamos a página. Você pode executar o código no frame abaixo, clique em recarregar para ver novos resultados:

Código fonte:

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Geração Procedural - Salas Retangulares</title>
	<meta name="author" content="Luiz Fernando Reinoso">
    <script type="text/javascript">
      // Primeiro nosso modelo de retangulo
      function Retangulo(x, y, w, h, fill) {
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
        this.fill = fill;

        // Verifica interseções
        this.intersecao = function intersecao(sala) {
          return (this.x < sala.x + sala.w &&
              this.x + this.w > sala.x &&
              this.y < sala.y + sala.h &&
              this.h + this.y > sala.y);
        }
      }

      //função de inicialização e geração
      function init() {
        //canvas
        var c = document.getElementById("canvas");
        var ctx = c.getContext("2d");

        //Primeiro geramos as salas
        gerarSalas(c, ctx, 10);
      }
      
      /**
      * Gerar salas.
      *
      * @param {number} - numero de salas
      */
      function gerarSalas(c, ctx, numSalas) {
        var salas = new Array();

        for (var i = 0; i < 10; i++) {
              console.log("loop " + i);
              size = getRandomArbitrary(10, 30) * 2 + 1;
              //retriangulacao = getRandomArbitrary(0, 1 + size ~/ 2);
              largura = size;
              altura = size;
              x = getRandomArbitrary(1, ((c.width - largura) / 2) * 2);
              y = getRandomArbitrary(1, ((c.height - altura) / 2) * 2);
              sala = new Retangulo(x, y, largura, altura, "#333");

              // conferimos se a nova sala está a colidir
              // Isso garante que não teremos sobreposição
              // mas podemos cometar essa parte se desejamos interseções
              var sobreposicao = false;
              for (var i = 0; i < salas.length; i++) {
                if (sala.intersecao(salas[i])) {
                  console.log("colision");
                  sobreposicao = true;
                  break;
                }
              }

              if (sobreposicao) continue;

              //caso tudo de certo colocamos o retangulo na lista
              salas.push(new Retangulo(x, y, largura, altura, "#333"));

              // desenhamos o retangulo
              ctx.fillRect(x, y, largura,altura);
        }
      }

      /**
      * Impede de ocorrer interseções entre salas (opcional).
      *
      */
      function retriangulacao() {
        FatorRetriangulacao = getRandomArbitrary(0, 1 + size / 2);
        if (rng.oneIn(2)) {
          width += rectangularity;
        } else {
          height += rectangularity;
        }
      }
      /**
      * Funcao RANGE - intervalo de valor randomico.
      *
      * @param {number} - menor valor para o intervalo
      * @param {number} - maior valor para o intervalo
      */
      function getRandomArbitrary(min, max) {
        return Math.random() * (max - min) + min;
      }
    </script>
  </head>
  <body onload="init();">
    <canvas id="canvas" width="600" height="600" style="border: 1px solid black;"></canvas>
  </body>
</html>

Teste o algoritmo:

Gerando terrenos sob uma esfera

No exemplo a seguir, fazemos um processo similar ao anterior, mas aqui respeitamos um raio para gerar nossos objetos:

Código fonte:

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Geração Procedural - Salas Sob um circulo</title>
	<meta name="author" content="Luiz Fernando Reinoso">
    <script type="text/javascript">
      function init(){
        //canvas
        var c = document.getElementById("canvas");
        var ctx = c.getContext("2d");

        ctx.beginPath();
        ctx.arc(150,150,150,0,2*Math.PI);
        ctx.stroke();

        for (var i = 1; i < 100; i++){
          r = circleNumber(ctx, 150);
        }
    }

    /* Funcao RANGE - intervalo de valor randomico.
    *
    * @param {number} - raio do circulo
    */
    function circleNumber(ctx, raioCirculo) {
      angulo = 2*Math.PI*Math.random();
      raio = Math.random() * raioCirculo * raioCirculo;
      x = Math.sqrt(raio) * Math.cos(angulo);
      y = Math.sqrt(raio) * Math.sin(angulo);

      // 150 no fillRect poderia ser substituido por = c.width / 2, sendo c o canvas
      ctx.fillRect(x + 150 ,y + 150,4,4);
    }

    </script>
  </head>
  <body onload="init();">
    <canvas id="canvas" width="300" height="300" style="border: 1px solid black;">
    </canvas>
  </body>
</html>

Teste o algoritmo:

Gerando uma galáxia

O algoritmo a seguir é a base de funcionamento de muitas visões sobre a geração procedural, aqui, obviamente exemplificamos o procedimento, a criação completa de uma galáxia, como o já citado No Man's Sky poderia ser neste sentido se os desenvolvedores quisessem.

Código fonte:

<!DOCTYPE html>
<html>

<head>
  <meta charset="utf-8">
  <!-- Inclusao do seedrandom, https://github.com/davidbau/seedrandom-->
  <script src="seedrandom.min.js"></script>
  <title>Geração Procedural - Galaxia</title>
  <meta name="author" content="Luiz Fernando Reinoso">
  <script type="text/javascript">
    const xMax = 10;
    const yMax = 10;
    const d = 0.5;

    const minPlanets = 2;
    const maxPlanets = 10;

    function init() {
      //canvas
      var c = document.getElementById("canvas");
      var ctx = c.getContext("2d");
      var rdnV = Math.random();
      var estrelas = createStars(rdnV, ctx); // vator de esttrelas
      var planetas = createPlanets(rdnV, ctx); // numero de planetas

      console.log(estrelas);
      console.log(planetas);
    }

    /**
    * Cria estrelas.
    *
    * @param {number} - valor Seed para criarmos nosso Random-Unit
    * @return {Array} - vetor de estrelas geradas
    */
    function createStars(v, ctx) {
      var g = new Array(xMax + 1); // criamos as linhas da matrix G
      for (var i = 0; i < (xMax + 1); i++) { // alocamos as colunas para linhas em G
        g[i] = new Array(yMax + 1);
      }
      Math.seedrandom(v); // Semente no Random, Random-Unit

      for (var x = 0; x < xMax; x++) {
        for (var y = 0; y < yMax; y++) {
          if (Math.random() < d) { // caso o valor seja menor que a densidade
            g[x][y] = Math.random(); // criaos a estrela no local
            ctx.fillStyle = "#FF0000";
            ctx.fillRect(x * 30, y * 30, g[x][y] * 5, g[x][y] * 5);
          } else {
            g[x][y] = 0; // senão o local é vazio
          }
        }
      }
      return g;
    }

    /**
    * Crai nossos planetas, geralmente mesmo valor Seed das estrelas é passado como referência.
    *
    * @param {number} - valor Seed para criarmos nosso Random-Unit
    * @return {Array} - vetor de planetas gerados
    */
    function createPlanets(v, ctx) {
      Math.seedrandom(v);
      var p = getRandomInt(minPlanets, maxPlanets);
      var P = new Array(p); // Planetas a serem gerados
      for (var i = 0; i < p; i++) {
        P[i] = Array(Math.random() * 10, Math.random() * 300, Math.random() * 300);

        // a partir do segundo elemento devemos verificar colisoes!
        if (i > 1) {
            // enquanto tivermos colisao devemos encontrar nova posicao
            while(checkCollisions(P, P[i], i)){
                P[i] = Array(Math.random() * 10, Math.random() * 300, Math.random() * 300);
            }
        }

        ctx.fillStyle = "#CCCCCC";
        ctx.beginPath();
        ctx.arc(P[i][1], P[i][2], P[i][0], 0, 2 * Math.PI);
        ctx.stroke();
      }
      return P;
    }

    /**
    * Pegamos um random de ponto flutuante (float) entre um `min` and `max`.
    *
    * @param {number} min - menor numero desejado
    * @param {number} max - maior numero desejado
    * @return {float} valor randomico de ponto flutuante devolvido
    */
    function getRandom(min, max) {
      return Math.random() * (max - min) + min;
    }

    /**
    * Pegamos um random inteiro entre um `min` and `max`.
    *
    * @param {number} min - menor numero desejado
    * @param {number} max - maior numero desejado
    * @return {int} valor randomico inteiro
    */
    function getRandomInt(min, max) {
      return Math.floor(Math.random() * (max - min + 1) + min);
    }

    /**
    * Verificamos a colisao entre arcos `a` and `b`.
    *
    * @param {Array} vet - Array arc
    * @param {Array} a - arc data
    * @param {number} a - qtd quantidade existeste de planetas
    * @return {bool} valor verdadeiro/falso
    */

    function checkCollisions(vet, a, qtd) {
        var colission = false;
        for (var i = 0; i < qtd -1; i++){ // desconte o ultimo pois e o proprio `a`
            console.log(i);
            var dx = vet[i][1] - a[1];
            var dy = vet[i][2] - a[2];
            var dist = Math.sqrt(dx * dx + dy * dy);
            if(dist < vet[i][0] + a[0]){
                colission = true;
            }
        }
      
      return colission; // verdadeiro ou falso
    }

  </script>
</head>

<body onload="init();">
  <canvas id="canvas" width="300" height="300" style="border: 1px solid black;">
  </canvas>
</body>

</html>

Teste o algoritmo:

Uma atualização para esta versão remasterizada do artigo é o procedimento de verificação de colisão 'checkCollisions', que garante que os planetas não sejam criados se colidindo, poderíamos fazer o mesmo com as estrelas, mas considerei que elas podem estar anos luz dos planetas. E é aqui que temos uma linha de intersecção no randômico, desenvolvendo de fato algo procedural, vejam que desenvolvi um conjunto de regras que delimitam até onde a randômico pode atuar e gero conflito caso ele tente gerar algo fora do padrão esperado. No nosso caso, mando refazer o planeta em outro local e somente depois de satisfeito o mesmo é gerado.

Jogo estilo rogue-like

O estilo Rogue é muito referenciado quando falamos em sistemas procedurais. Diferente de quando iniciei este estudo, temos muitos materiais de qualidade na internet atualmente, então resolvi trazer uma visão externa ao invés de criar todo um projeto, em minhas buscas fui atrás de algo completo para você e me deparei com o vídeo abaixo do canal Thoughtquake:

 

Se desejarem posso fazer uma pesquisa acerca de como estruturar este tipo de projeto. Por incrivel que pareça, sistemas procedurais podem fazer parte de uma camapanaha de jogo com inicio e fim. Veja a saga de Diablo. Estamos fortemente atrelados a franquias como Minecraft e similares, o que por vezes causa aquela sensação de que a ideia e variar ambientes, inimigos e da apenas um remexida para variar o game, acredite, por de ser mais que isso.

Considerações finais

A pesquisa realizada objetivou mostrar um pouco do uso e função da autogeração, abordando os principais conceitos, técnicas e práticas, claramente, o artigo é incisivo, listando jogos, algoritmos e exemplificando cada passo, porém ainda é bem limitado quando comparado as potencialidades da auto geração e verticalizações que podemos ter com a sua abordagem, como por exemplo, poderíamos ter a subversão deste estudo em uma ambiente 3D. O que faríamos seria a remodelagem dos algoritmos para a nova realidade  e as funções de geração passarão a mapear um mundo pela altura, largura e profundidade.

O que quero deixar claro é que as técnicas e práticas ensinadas são independentes de linguagem ou ferramenta, você precisar estudar e entender isso, pois senão estará aproveitando apenas uma compreensão superficial de uma construção automática. Caso essa visão ainda não esteja clara, por favor, comente este estudo, debata e aprofunde-se na discussão dos conceitos ensinados, este afinal é mais um objetivo compreendido pelo artigo.

Espero que tenham gostado do estudo e que ele colabore para sua evolução, aguardo comentários e até mesmo debates suficientes para novos artigos ou evolução deste. Obrigado pela leitura!


Trabalho submetido 17 de Fevereiro de 2023 às 15:32, última modificação 18 de Fevereiro de 2023 às 14:31.
Marcadores: Tutorial   Game Design  

Licença Creative Commons
O trabalho Explorando algoritmos de geração procedural e aleatória para aprimorar jogos digitais de Calango Team está licenciado com uma Licença Creative Commons - Atribuição-NãoComercial-CompartilhaIgual 4.0 Internacional.
Baseado no trabalho disponível em FONTE.
Podem estar disponíveis autorizações adicionais às concedidas no âmbito desta licença em AUTORIZACOES.
0 Comentarios:

Procurar


Siga-nos

Itch.io Patreon Facebook Youtube Twitch TikTok
Quer colocar sua publicidade/apoio/parceria aqui!

Entre em contato pelo Facebook para conversar!