O trabalho de programação, gráficos e sons em alguns jogos novos acabou - apenas os níveis permanecem. Trabalho fácil e agradável, mas por alguma razão vem com grande dificuldade. Talvez o efeito da fadiga geral.
Pensando em como simplificar sua vida, surgiu a idéia de geração processual. É claro que também terá que ser escrito, mas como foi dito em uma obra bem conhecida, "é melhor perder um dia, depois voar em cinco minutos".
Atenção! Sob o corte, muitos textos e gifs "gordos".
Introdutório
Os níveis ainda serão polidos manualmente, portanto, não há requisitos especiais para memória, velocidade ou mesmo a qualidade dos níveis resultantes.
Inicialmente, planejei que o gerador jogasse apenas salas e portas, e todo o refinamento adicional (enredo, cenário e inimigos) fosse realizado no modo manual. Mas, por enquanto, acho que o gerador pode fazer muito mais. No entanto, a sintonia manual ainda permanecerá - é necessário que os jogadores sintam que pelo menos um pouco de amor é investido nos níveis.
Analisei minha base de conhecimento no game dev e escrevi links para artigos sobre geração de procedimentos em um documento separado. A maioria, é claro, trata de gerar labirintos clássicos ou de gerar terreno (a propósito, os resultados são muito impressionantes), o que não é adequado para um jogo de tiro em 3D. Mas alguns estavam perto do que eu precisava (com um asterisco, notei aqueles que me pareciam mais adequados):
Decidi começar pelos dois últimos - eles estão sendo implementados e dão bons resultados.
Estrutura do gerador
De fato, não cheguei a essa estrutura imediatamente, mas no processo de inúmeras refatorações e reescritas, mas escrevo sobre isso imediatamente, para que fique claro o que está acontecendo:
- Geração da geometria inicial (para escolher - "BSP" ou layout da sala).
- Limpeza de seções de lixo (seções que não podem existir no jogo).
- Construindo conexões.
- Limpeza de subgráficos de lixo (grupos de seções interconectados, mas não há conexão com as seções restantes).
- Limpando conexões desnecessárias (construindo uma árvore de abrangência , é fornecido um link para a árvore de abrangência mínima , porque existe uma imagem lá, mas para o gerador não é necessário o mínimo).
- A randomização das conexões é a restauração de algumas conexões remotas (para um nível mais "humano"), bem como a transformação de outras em passagens entre seções (que mescla várias seções em uma forma mais complexa).
- Geração de quarto secreto.
- Geração de um “cenário” (onde estarão as seções inicial e final e qual caminho deverá ser percorrido para passar da inicial para a final).
- Otimização de conexão.
- Criando portas e janelas.
- A escolha da ação a ser executada nesta seção (pressione o botão, levante a tecla ou encontre a parede secreta).
Ainda existem cerca de 12 pontos, mas eles ainda não foram concluídos (quando eu terminar, escreverei um post separado sobre eles).
Geração inicial de geometria: "BSP"
Esta tradução foi tomada como base. Não tenho certeza do quanto isso acontece nesse algoritmo é próximo ao BSP real, então escrevo "BSP" entre aspas.
O algoritmo é bastante simples. Inicialmente, crie um retângulo do tamanho de todo o campo de jogo:
Em seguida, dividimos-o aleatoriamente em duas partes - horizontal ou verticalmente. Onde a linha de separação ocorrerá, também escolhemos aleatoriamente:
Recursivamente, fazemos o mesmo para os novos retângulos:
E de novo e de novo, até certo ponto:
Então, em cada retângulo, selecionamos uma “sala” - um retângulo do mesmo tamanho que o original ou menor (mas não inferior a 3x3 - mais sobre o que está abaixo).
Em seguida, os quartos são conectados por corredores. Mas não cada um, mas um pouco complicado, porque eles são armazenados em uma estrutura semelhante a "BSP" (consulte o algoritmo original para obter mais detalhes).
O corredor que liga as seções roxas e brancas.
No algoritmo original, as salas e os corredores são da mesma cor (ou seja, são equivalentes); portanto, os corredores são simplesmente desenhados em cima das salas. No meu caso, os quartos originais devem ser preservados, para que os corredores sejam desenhados como se estivessem "atrás" dos quartos.
Além disso, se a sala (turquesa na figura) cruzar o corredor, ela deverá ser dividida em duas seções diferentes (portanto, o mesmo corredor pode ser desenhado em cores diferentes):
E aqui está o resultado:
Em seguida, começa a fase de marcação das células de lixo:
Como já escrevi, nenhum setor pode ser menor que células 3x3. Isso ocorre porque o setor deve estar cercado por paredes (pelo menos 1 célula de cada lado) e deve ter pelo menos uma célula de espaço livre:
Portanto, todas as células que não se encaixam nessa regra são rotuladas. Mas pegue e você não poderá removê-los - muitas conexões desaparecem e o nível é muito escasso.
Em vez disso, para cada célula rotulada, o setor no qual ela pode ingressar é pesquisado (observando a regra 3x3):
Se a célula ainda não puder ser atribuída a nenhum setor, ela será excluída (mas não neste caso - está tudo bem aqui).
No último estágio, essa bela imagem é vetorizada, e os setores desenhados se transformam em caixas de polígono - polígonos nos quais cada aresta é estritamente vertical ou estritamente horizontal (provavelmente existe um nome mais científico):
Geração inicial da geometria: layout da sala
Outro artigo foi tomado como base. Este algoritmo é um pouco mais complicado que o anterior, mas também não é um foguete.
Primeiro, o campo de jogo é preenchido com um certo valor de parada e, em seguida, uma área retangular é limpa aleatoriamente:
A etapa de limpeza de um retângulo aleatório é realizada mais um número (também aleatório) de vezes e, como resultado, os contornos externos do nível são obtidos:
No espaço livre, os pontos de crescimento da sala são espalhados aleatoriamente (o tamanho mínimo da sala é 3x3):
O primeiro estágio do crescimento da sala começa - para cada sala, o lado maior é selecionado, que ainda pode crescer, e cresce em 1 célula (se houver vários lados com o mesmo comprimento - um aleatório). Os quartos são movidos por sua vez, para que não haja cruzamentos.
Em seguida, os quartos são convertidos em polyboxes:
E o segundo estágio do crescimento começa - nesse estágio, o lado pode ser dividido em várias partes. Ao contrário do primeiro estágio, ele não cresce uma célula de cada vez, mas imediatamente até a parada máxima - isso evita a "escada" nas juntas dos quartos. Se após a passagem por todas as salas ainda houver células vazias, o ciclo se repete.
O resultado é um espaço totalmente preenchido:
Em seguida, as policarboxes são desenhadas na forma de uma varredura e (como no caso do gerador "BSP"), o estágio de marcação das células "lixo" começa:
E juntando-os aos setores existentes:
Aqui não foi possível anexar todas as células - as extras foram removidas.
O resultado é convertido novamente em polyboxes:
Limpeza de seções de lixo
Às vezes, surgem seções dentro das quais a regra 3x3 não é respeitada:
Você pode tentar "restaurar" essas seções, mas eu segui o caminho mais simples e as apague:
Construindo conexões
Para cada seção, seus vizinhos são pesquisados e, nos locais de contato de tais seções, conexões são criadas. As conexões são criadas nos dois lados - se a seção A estiver em contato com a seção B, haverá uma conexão de A a B e de B a A. O resultado é um gráfico bidirecional.
Compensação de subgráficos de lixo
Às vezes, como resultado da limpeza das seções de lixo, obtemos não um gráfico, mas vários independentes, como neste exemplo:
Nesse caso, o subgráfico é selecionado como o principal, cuja “área” das seções é máxima e o restante é excluído (a “área” está entre aspas, porque, embora seja possível calcular a área real da caixa de polivinil, simplifiquei a tarefa e considero a área da caixa delimitadora - isso está errado, mas é adequado para um gerador).
Remoção de excesso de compostos
Se houver uma passagem de cada setor para cada um com o qual está conectado, haverá muitas portas no nível e será mais fortemente sentido que ele é gerado. Portanto, nesse estágio, as conexões em excesso são removidas:
Para mais randomização, não gero uma árvore de abrangência no número mínimo de passes, mas excluo uma aresta aleatória de cada vez (escolhendo-a aleatoriamente dentre todas as possíveis na etapa atual).
Embora, quando escrevo isso, pareceu que seria bastante aleatório selecionar o setor inicial e remover as bordas do algoritmo já mais eficiente.
Randomização de conexão
A seguir, as ilustrações virão de outra geração, porque no anterior houve um erro no gerador, devido ao qual outras imagens estavam incorretas.
Mas um nível em que não há uma única conexão supérflua também não parece muito humano; portanto, é introduzido um caos:
- Algumas arestas excluídas são restauradas.
- E alguns se transformam em corredores.
Além disso, as seções entre as quais as passagens foram formadas se fundem em uma:
Se lhe pareceu que nesta ilustração as conexões excluídas na etapa anterior reapareceram - pareceu-lhe :). Quando li o texto, também me pareceu assim, mas, olhando atentamente a ilustração anterior, fica claro que está tudo bem.
Geração de quarto secreto
Os setores que possuem apenas uma conexão são selecionados no gráfico:
Se houver vários desses setores, todos eles se reunirão em uma matriz e serão classificados por "área". Em seguida, essa matriz é truncada aleatoriamente (mas para que pelo menos um elemento permaneça nela). Esses setores se tornarão salas secretas:
Geração de scripts
Primeiro, os setores com o número mínimo de conexões livres (ou seja, os mais próximos da "aresta" do gráfico) são selecionados:
Nesta ilustração, um setor é selecionado, mas se houvesse mais, de qualquer maneira um seria selecionado (aleatoriamente).
NB Durante a revisão do artigo, pude me deparar com uma situação em que um setor com um número mínimo de conexões livres não estará apenas no limite, mas atribuir um script a ele levará a um nível intransitável. De fato, você pode escolher qualquer setor, mas apenas um, após o qual o gráfico não se enquadra em vários subgráficos.
Em seguida, selecione os setores que estão conectados ao setor atual e que possuem apenas uma conexão gratuita. Eles, com alguma probabilidade, serão usados para continuar o script. Por exemplo, se o gráfico for o mesmo da ilustração abaixo, o setor indicado pela pergunta poderá ser incluído na lista.
A sala secreta está marcada em cinza, as cruzes são aquelas conexões que deveriam ter sido removidas no gráfico original e o setor de origem é uma vantagem.
NB Durante a revisão do artigo, pareceu-me que a condição para a presença de apenas uma conexão era muito rígida, a mesma que na etapa anterior seria suficiente - para que, após a exclusão desse setor, o gráfico não se decomponha.
Em seguida, o número do script é atribuído a essa lista de setores (apenas um número, nesse estágio não significa nada específico), e as conexões nas bordas dessa lista de setores são marcadas como fechadas por esse script.
Nestas ilustrações, cenários diferentes terão cores de preenchimento de setor diferentes. Eles não têm nada a ver com a cor da borda do setor (nas próximas etapas será corrigido, mas nesta etapa é mais conveniente para mim).
Em seguida, o próximo setor é selecionado, uma lista é compilada e essa lista é marcada com um novo cenário:
Preste atenção aos pequenos pontos azuis dentro dos quadrados vermelhos - é assim que o abridor de cenário é desenhado - ou seja, em algum lugar dentro da seção com o script vermelho, haverá uma chave ou chave que abrirá a passagem para setores com um script azul.
Isso continua até que não haja setores livres restantes:
O setor mais recente não recebe um script, mas apenas um abridor de cenário. Este setor será o setor em que o jogador inicia o jogo.
Para este nível:
- O jogador começa no setor inicial, em algum lugar lá encontra um "abridor de garrafas" para o setor amarelo, vai para lá.
- No setor amarelo, abre o setor azul, vai lá.
- No setor azul abre verde, vai lá.
- No setor verde abre roxo, vai lá.
- Em roxo abre vermelho.
- Em vermelho - azul.
- Onde ele encontra a chave de nível final.
Esquematicamente, isso pode ser mostrado da seguinte maneira:
Um "abridor" pode ser uma chave ou um comutador, ou qualquer outra coisa, por exemplo, uma tarefa para destruir todos os inimigos em qualquer setor (mas não planejo que, em um futuro próximo, o gerador ou o motor suporte isso).
Otimização de conexão
Nesta etapa, para cada conexão, um lado é selecionado (como você se lembra, inicialmente as conexões são geradas nas duas direções). Isso é necessário para que o nível pareça mais "manual" e para simplificar as próximas etapas (mas, para um tipo de nível ainda mais interessante, em um futuro próximo, planejo dar o passo de "desotimizar" algumas conexões) .
Criando portas e janelas
Para cada setor, todas as suas conexões são visualizadas (que após a etapa anterior parecem apenas em uma direção), e portas e janelas são colocadas em cada conexão visualizada.
- Primeiro, um ponto é selecionado na junção, de preferência mais perto do centro.
- Então, nesse ponto, uma porta ou uma janela é colocada (e, se for uma conexão com uma sala secreta, uma parede secreta).
- Se uma porta for colocada, ela poderá ter de 1 a 3 células (uma é uma porta comum, duas ou três são uma porta hermética grossa, que se abre após pressionar um botão).
- Além disso, a conexão é dividida em duas partes - a parte antes do ponto selecionado e a parte depois. E, se houver espaço restante antes ou depois, a função será chamada recursivamente.
Para tornar o nível mais interessante, em diferentes etapas, há uma probabilidade diferente de colocar uma porta ou janela:
- Na primeira etapa, a porta é sempre colocada, porque qual é a utilidade da conexão se houver apenas janelas lá.
- No segundo passo, com uma probabilidade mais alta (75%), uma janela é colocada que uma porta.
- Se houver uma terceira etapa (por exemplo, a conexão é longa), uma janela deverá ser colocada nela.
- No caso do quarto passo, a porta ou janela é colocada igualmente provável.
- Se a conexão for extra longa, o gerador retornará à segunda etapa.
Seleção de ação
Embora isso não esteja relacionado à geração, a visualização muda nesta etapa - agora a borda do setor é pintada na cor do script:
O setor inicial é cinza claro, o setor final é azul. Observe também que, em vez da porta da sala secreta (cinza escuro à esquerda), uma parede é desenhada - tudo está correto, essa é uma parede secreta.
Em seguida, selecione os setores nos quais você pode colocar as chaves:
Eles são selecionados simplesmente:
- Se essa é uma sala secreta, não pode haver "abridor" nela e a chave não pode ser colocada lá.
- Você também não pode colocar a chave no setor final, porque é final.
- Além disso, a chave não pode abrir portas duplas e triplas - devido às características do motor, elas só podem ser abertas com o interruptor (não existem setores na ilustração acima) .
Depois disso, o número de chaves em um nível (de zero a três) é selecionado aleatoriamente e, em seguida, aleatoriamente, na lista de setores disponíveis, são selecionados aqueles em que haverá chaves.
Nos demais setores, haverá interruptores.