Artigos

Conhecendo e implementando algoritmos de geração procedural e randômica para jogos digitais

Escrito por Luiz Fernando Reinoso publicado 13 de Março de 2017 às 22:27.

Mensagem do Pixel arte:

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

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?

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.

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 optimizar 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 algorítimo 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 numero de regras e estruturas disponíveis.

Qual abordagem utilizar? Entenda bem, certos momentos podemos ter a randomização, outros não, imagine criar um algorítimo 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 numero 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 algorítimo 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 algorítimo, 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 numero qualquer entre 0 e 10, e notamos um tendência a sair o numero 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;
}

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 algorítimos 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>

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>

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">
  <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] = Math.random();
      ctx.fillStyle = "#CCCCCC";
      ctx.beginPath();
      ctx.arc(Math.random() * 300, Math.random() * 300, P[i] * 10,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);
  }

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

Jogo RogueLike com geração procedural

O jogo a seguir não foi desenvolvido por min, foi desenvolvido por um membro do fórum da Scirra, empresa que desenvolve e distribui a engine de criação de jogos Construct 2, você pode baixar a ferramenta e rodar o projeto do jogo, que é fornecido pelo autor juntamente com o artigo postado por ele.

Para ajudar a comunidade e contribuir para com este artigo, ao invés de implementar um game eu traduzi inteiramente o artigo disponibilizado pelo autor, contribuindo assim com este artigo e com a comunidade sensacional da Scrirra que existe no Brasil. Em resumo, o tutorial ensina os passos para criação de um game roguelike, onde você cria desde as salas aos corredores, inimigos e itens coletáveis. Vale a pena o estudo.

Você pode acessar o artigo versão pt-br aqui: https://www.scirra.com/tutorials/1112/gerao-procedural-de-uma-dungeon-um-jogo-estilo-roguelike/pt-br.

Jogo RogueLike com auto geração.

Figura 1 - Roguelike game com geração procedural (Scirra, 2014).

 

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, em uma ferramenta como a Unity. O que faríamos seria a remodelagem dos algoritmos para a linguagem suportada pela ferramenta e as funções de geração deveriam 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.

O jogo disponibilizado, foi colocado para mostrar que é possível até mesmo com ferramentas como o Construct 2, onde a programação direta meio que inexiste, pois a ferramenta objetiva a orientação a eventos, encapsulam e/ou possibilitam a lógica procedural. Pois demonstrando uma exemplificação como esta, torna-se factível o uso da autogeração e sua visão fica mais clara.

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 25 de Janeiro de 2017 às 17:28, última modificação 13 de Março de 2017 às 22:27.
Marcadores: Desenvolvimento   Tutorial  

Licença Creative Commons
O trabalho Conhecendo e implementando algoritmos de geração procedural e randômica para jogos digitais de Luiz Fernando Reinoso está licenciado com uma Licença Creative Commons - Atribuição-NãoComercial-CompartilhaIgual 4.0 Internacional.
Podem estar disponíveis autorizações adicionais às concedidas no âmbito desta licença em AUTORIZACOES.
0 Comentarios:
Publicidade
Publicidade
Publicidade
Publicidade