Neste post, descreverei o algoritmo para geração procedural de níveis de uma masmorra bidimensional com uma estrutura predeterminada. Na primeira parte, será apresentada uma descrição geral e, na segunda, a implementação do algoritmo.
1. Introdução
O algoritmo foi escrito como parte
de um trabalho de bacharelado e é baseado em um artigo de
Ma et al (2014) . O objetivo do trabalho era acelerar o algoritmo e complementá-lo com novas funções. Estou muito feliz com o resultado, porque fizemos o algoritmo rápido o suficiente para usá-lo durante a execução do jogo. Depois de concluir o trabalho do bacharel, decidimos transformá-lo em
um artigo e enviá-lo para a conferência Game-ON 2018.
Algoritmo
Para criar um nível de jogo, o algoritmo recebe como entrada um conjunto de blocos de construção poligonais e um gráfico de conectividade de nível (topologia de nível). Os nós do gráfico indicam as salas e as bordas determinam as conexões entre elas. O objetivo do algoritmo é atribuir a cada nó do gráfico a forma e a localização da sala, para que não haja duas formas de divisão, e cada par de salas vizinhas possa ser conectado por portas.
a)
b)
c)
d)
As figuras (c) e (d) mostram os diagramas gerados a partir do gráfico de entrada (a) e dos blocos de construção (b).
Usando o gráfico de conectividade, um designer de jogos pode controlar facilmente o fluxo da jogabilidade. Você precisa de um caminho comum para a sala dos chefes com vários caminhos laterais opcionais? Comece com o gráfico do caminho e especifique alguns nós nos quais o jogador pode escolher: ou siga o caminho principal ou explore o caminho lateral, com possíveis tesouros e / ou monstros esperando por ele. Você precisa cortar o caminho? Basta selecionar os dois nós no gráfico e adicionar uma estrada curta conectando-os. As possibilidades deste esquema são infinitas.
Exemplos de gráficos de entrada. O caminho principal é mostrado em vermelho, os caminhos auxiliares são azuis, o caminho curto é laranja.O algoritmo não apenas permite que os designers de jogos gerenciem a estrutura de alto nível dos mapas gerados, mas também fornece a capacidade de controlar a aparência de salas individuais e como conectá-las umas às outras.
Formas diferentes para salas diferentes
Eu mencionei a sala dos chefes no final do nível. Não queremos que a sala dos chefes pareça com nenhuma outra sala comum, certo? O algoritmo permite definir formulários para cada sala. Por exemplo, podemos criar uma sala no início do nível e uma sala de chefe, que deve ter seus próprios conjuntos de formas de sala e um conjunto comum para todas as outras salas.
Dois circuitos gerados a partir do gráfico de entrada, nos quais uma forma especial de salas está associada ao número da sala 8.
Posições explicitamente indicadas da porta
Imagine que você tenha um script de reunião de chefia de alta qualidade e que precisamos que o jogador entre na sala do chefe a partir de um bloco específico. Ou podemos ter um modelo de sala em que alguns ladrilhos são reservados para paredes e outros obstáculos. O algoritmo permite que os projetistas definam explicitamente possíveis posições da porta para formatos de salas individuais.
Mas, às vezes, o objetivo pode ser o oposto. Podemos criar modelos de sala de forma que as portas para eles possam estar em quase qualquer lugar. Devido a isso, impomos menos restrições ao algoritmo; portanto, ele geralmente roda mais rápido, e os esquemas gerados podem parecer menos monótonos e mais orgânicos. Para tais situações, é possível simplesmente indicar o comprimento das portas e a que distância elas devem estar dos cantos. A distância dos cantos é uma espécie de compromisso entre o arranjo manual de todas as portas e a presença de portas em qualquer lugar.
a)
b)
A Figura (a) ilustra os diferentes tipos de localização das portas - uma sala quadrada possui 8 posições de porta claramente definidas e uma sala retangular usa comprimento e distância dos cantos. A Figura (b) mostra um diagrama simples gerado com as formas das salas na Figura (a).
Corredores entre quartos
Quando falamos sobre os níveis das masmorras, muitas vezes imaginamos salas conectadas por corredores estreitos. Gostaria de assumir que as conexões no gráfico de entrada indicam os corredores, mas não são. Eles simplesmente garantem que todos os nós vizinhos sejam conectados diretamente por portas. Se queremos que as salas sejam conectadas por corredores, precisamos inserir um novo nó entre todos os pares de salas vizinhas e fingir que essas são salas de corredor (com certas formas de salas e posições de portas especificadas).
a)
b)
Uma ilustração de como podemos modificar o gráfico de entrada para adicionar corredores entre salas. A figura (a) mostra o gráfico de entrada antes de adicionar as salas do corredor. A Figura (b) mostra o gráfico de entrada criado a partir de (a) adicionando novas salas entre todas as salas adjacentes do gráfico original.
Infelizmente, isso complica muito a tarefa do algoritmo, porque muitas vezes o número de nós dobra. Portanto, implementei uma versão do algoritmo que leva em consideração os corredores, o que permite reduzir a diminuição no desempenho ao organizar as salas dos corredores. No momento, o algoritmo suporta corredores entre todas as salas ou a completa ausência de corredores, mas no futuro pretendo torná-lo mais flexível.
Exemplos
Vários esquemas gerados a partir de diferentes conjuntos de blocos de construção e com corredores ligados.Vários esquemas gerados a partir de diferentes conjuntos de blocos de construção com corredores ligados e desligados.Na segunda parte do post, falarei sobre a operação interna do algoritmo.
Também estou trabalhando em um plugin do Unity para geração de masmorras procedurais, que incluirá esse algoritmo. Faço isso porque, apesar da possibilidade de usar esse algoritmo diretamente no Unity (está escrito em C #), a conveniência de trabalhar com ele está longe de ser ideal. Leva muito tempo para criar modelos de sala sem uma GUI e é necessário muito código para converter a saída do algoritmo na representação usada dentro do jogo.
Como eu próprio não sou desenvolvedor de jogos, meu objetivo é tornar o plug-in suficientemente bom para que outras pessoas o usem. Se tudo correr bem, tentarei publicar atualizações quando tiver algo interessante a dizer. Eu já tenho algumas idéias sobre o gerador em si e sobre o teste de seus recursos.
Capturas de tela do plugin Unity (o projeto está em desenvolvimento)Parte 2. Implementação do algoritmo
Nesta parte, falarei sobre as idéias básicas estabelecidas na base do algoritmo descrito na primeira parte do post. Inicialmente, eu queria descrever os conceitos básicos, juntamente com as principais melhorias necessárias para que o algoritmo fosse rápido o suficiente. No entanto, como se viu, mesmo os conceitos básicos são mais que suficientes para este post. Portanto, decidi revelar melhorias de desempenho em um artigo futuro.
Motivação
Antes de prosseguir para a implementação, quero mostrar o resultado do que faremos. O vídeo abaixo mostra 30 circuitos diferentes gerados a partir de um gráfico de entrada e de um conjunto de blocos de construção. O algoritmo sempre para por 500 ms após a geração do circuito e, em seguida, tenta gerar o próximo.
Como isso funciona
O objetivo do algoritmo é atribuir a forma e a posição da sala a cada nó no gráfico, de modo que não haja duas salas que se cruzem e as salas vizinhas sejam conectadas por portas.
Uma maneira de conseguir isso é tentar todas as combinações possíveis de formas de salas e suas posições. No entanto, como você pode imaginar, isso será muito ineficiente e provavelmente não conseguiremos gerar circuitos, mesmo com base em gráficos de entrada muito simples.
Em vez de procurar todas as combinações possíveis, o algoritmo calcula como conectar corretamente todas as salas individuais (os chamados espaços de configuração) e usa essas informações para direcionar a pesquisa. Infelizmente, mesmo com essas informações, ainda é bastante difícil encontrar o esquema certo. Portanto, para um estudo efetivo do espaço de pesquisa, usamos uma técnica de otimização probabilística (neste caso, simulação de recozimento). E para acelerar ainda mais a otimização, dividimos a tarefa de entrada em subtarefas menores e mais fáceis de resolver. Isso é feito dividindo o gráfico em partes menores (chamadas cadeias) com a criação subsequente de esquemas para cada uma delas em ordem.
Espaços de configuração
Para um par de polígonos em que um é fixado no lugar e o outro pode se mover livremente, o espaço de configuração é o conjunto de posições de um polígono livre no qual dois polígonos não se cruzam e podem ser conectados por portas. Ao trabalhar com polígonos, cada espaço de configuração pode ser representado como um conjunto de linhas possivelmente vazio e calculado por ferramentas geométricas simples.
a)
b)
Configurações de espaço. A Figura (a) mostra o espaço de configuração (linhas vermelhas) de um retângulo livre em relação a um polígono fixo em forma de L. Ele determina todos os locais do centro da praça em que os dois blocos não se cruzam e se tocam. A Figura (b) mostra a interseção (pontos amarelos) dos espaços de configuração de um quadrado móvel em relação a dois retângulos fixos.
O algoritmo a seguir é usado para calcular o espaço de configuração de um bloco fixo e um bloco livre. Selecionamos um ponto de referência no bloco móvel e consideramos todos os locais no
, de modo que, ao mover o polígono para que seu ponto de referência esteja localizado nesse local, os blocos móveis e os blocos fixos se tocam, mas não se cruzam. O conjunto de todos esses pontos forma o espaço de configuração de dois blocos (Figura (a) acima). Para obter o espaço das configurações do bloco móvel em relação a dois ou mais blocos fixos, é calculada a interseção dos espaços de configuração individuais (Figura (b) acima).
O algoritmo usa espaços de configuração de duas maneiras. Primeiro, em vez de tentar as posições aleatórias de salas individuais, usamos espaços de configuração para procurar posições que levam ao maior número possível de salas adjacentes conectadas pelas portas. Para fazer isso, precisamos obter a interseção não vazia máxima dos espaços de configuração dos vizinhos. Em segundo lugar, usamos espaços de configuração para verificar se todos os pares de salas vizinhas podem ser conectados com portas. Isso é feito verificando se a posição da sala está dentro do espaço de configuração de todos os seus vizinhos.
Como as formas das salas não mudam durante a execução do jogo, podemos pré-calcular os espaços de configuração de todos os pares de formas de salas antes do início do algoritmo. Graças a isso, todo o algoritmo é significativamente acelerado.
Esquema incremental
Ao resolver um problema complexo, uma das abordagens possíveis é dividi-lo em subtarefas menores e mais simples e resolvê-las. É exatamente isso que faremos com a tarefa de colocar quartos individuais. Em vez de organizar todas as salas de uma vez, dividimos o gráfico de entrada em subgráficos menores e tentamos criar diagramas a partir deles, um por um. Os autores do algoritmo original chamam esses subgráficos de "cadeias" por causa do próprio princípio desses gráficos, em que cada nó não tem mais que dois vizinhos e, portanto, é bastante simples criar seu esquema.
O circuito de saída final é sempre um componente conectado; portanto, não faz sentido conectar os componentes individuais ao circuito e tentar combiná-los, porque o processo de combinação pode ser bastante complicado. Portanto, após a colocação da corrente, a próxima corrente conectada será sempre aquela que estiver conectada aos vértices já alinhados no circuito.
Layout GenerateLayout(inputGraph) { var emptyLayout = new Layout(); var stack = new Stack<Layout>(); stack.Push(emptyLayout); while(!stack.Empty()) { var layout = stack.Pop(); var nextChain = GetNextChain(layout, inputGraph); Layout[] partialLayouts = AddChain(layout, nextChain); if (!partialLayouts.Empty()) { if (IsFullLayout(partialLayouts[0])) { return partialLayouts[0]; } else { stack.Push(partialLayouts); } } } return null; }
Pseudo-código mostrando uma abordagem incremental para encontrar o esquema certo.O pseudo-código mostrado acima demonstra a implementação de um esquema incremental. A cada iteração do algoritmo (linhas 6-18), primeiro pegamos o último circuito da pilha (linha 7) e calculamos qual cadeia adicionar em seguida (linha 8). Isso pode ser feito simplesmente armazenando o número do último circuito adicionado a cada circuito parcial. No próximo passo, adicionamos a seguinte cadeia ao circuito (linha 9), gerando vários circuitos detalhados e os salvamos. Se a fase de expansão falhar, mas nenhum novo esquema parcial for adicionado à pilha, e o algoritmo precisará continuar com o último esquema parcial salvo. Chamamos essa situação de pesquisa de retorno porque o algoritmo não pode estender o esquema parcial atual e deve voltar e continuar com outro esquema salvo. Isso geralmente é necessário quando não há espaço suficiente para conectar circuitos adicionais aos vértices já compostos no circuito. Além disso, uma pesquisa de retorno é o motivo pelo qual sempre tentamos gerar vários esquemas avançados (linha 9). Caso contrário, não teríamos nada para retornar. O processo termina quando geramos um circuito completo ou a pilha está vazia.
a) Gráfico de entrada
b) Diagrama parcial
c) Diagrama parcial
(d) Descrição completa
(e) Descrição completa
Esquema incremental. As figuras (b) e (c) mostram dois diagramas parciais após o planejamento do primeiro circuito. A figura (d) mostra o circuito completo após a expansão (b) por um segundo circuito. A figura (e) mostra o circuito completo após a expansão (c) por um segundo circuito.
Para dividir o gráfico em partes, é necessário encontrar uma incorporação plana do gráfico de entrada, ou seja, um desenho no plano no qual as arestas se cruzam apenas nos pontos finais. Esse anexo é usado para obter todas as faces do gráfico. A idéia principal da decomposição é que é mais difícil criar um circuito a partir de ciclos, porque seus nós têm mais restrições. Portanto, estamos tentando organizar os ciclos no início da decomposição, para que sejam processados o mais cedo possível e reduza a probabilidade da necessidade de voltar nos estágios subsequentes. A primeira cadeia de decomposição é formada pela menor face do anexo e as faces subsequentes são adicionadas na ordem da primeira pesquisa de largura. Se houver outras faces que possam ser selecionadas, a menor delas será usada. Quando não há faces restantes, os componentes não cíclicos restantes são adicionados. A Figura 4 mostra um exemplo de decomposição em uma cadeia, que foi obtida de acordo com estas etapas.
a)
b)
Decomposição em cadeias. A figura (b) mostra um exemplo de como colocar a figura (a) em um circuito. Cada cor representa uma cadeia separada. Os números indicam a ordem em que as cadeias são criadas.
c) Bom design parcial
(d) Descrição completa
a) Gráfico de entrada
b) Gráfico parcial incorreto
Pesquise com retorno. A Figura (b) mostra um exemplo de um circuito parcial ruim, porque não há espaço suficiente para conectar os nós 0 e 9. Para gerar o circuito completo (d), é necessário um retorno a outro circuito parcial (c).
Recozimento simulado
O algoritmo de simulação de recozimento é uma técnica de otimização probabilística cujo objetivo é estudar o espaço de possíveis circuitos. Foi escolhido pelos autores do artigo original por se mostrar útil em situações semelhantes no passado. Ao implementar o algoritmo, decidi usar o mesmo método, porque queria começar com o que já provou sua eficácia na solução desse problema. No entanto, acho que ele pode ser substituído por outro método e minha biblioteca é escrita de tal maneira que o processo de substituição do método é bastante simples.
O algoritmo de simulação de recozimento avalia iterativamente pequenas alterações na configuração atual ou no circuito. Isso significa que criamos uma nova configuração selecionando aleatoriamente um nó e alterando sua posição ou forma. Se a nova configuração melhorar a função de energia, ela sempre será aceita. Caso contrário, há pouca chance de aceitar a configuração de qualquer maneira. A probabilidade de tomar decisões piores diminui com o tempo. A função de energia é projetada de maneira a impor grandes multas aos nós que se cruzam e aos nós adjacentes que não se tocam.
A é a área total de interseção entre todos os pares de blocos no diagrama. D é a soma dos quadrados das distâncias entre os centros dos pares de blocos no gráfico de entrada que são vizinhos, mas não se tocam. Valor
afeta a probabilidade de que o recozimento simulado possa ir para a pior configuração; esse parâmetro é calculado a partir da área média dos blocos de construção.
Depois de selecionar um nó para alterar, alteramos sua forma ou posição. Como escolhemos uma nova posição? Você pode escolhê-lo aleatoriamente, mas isso frequentemente degradará a função de energia e o algoritmo convergirá muito lentamente. Podemos escolher uma posição com maior probabilidade de aumentar a função de energia? Veja o que estou levando? Usamos espaços de configuração para selecionar uma posição que satisfaça os limites do maior número de salas vizinhas.
Em seguida, para alterar a forma, basta selecionar uma das formas de sala disponíveis. Embora o algoritmo não tente decidir qual formulário provavelmente nos levará ao esquema correto. No entanto, seria interessante tentar esse recurso e ver se ele acelera o algoritmo.
List<Layout> AddChain(chain, layout) { var currentLayout = GetInitialLayout(layout, chain); var generatedLayouts = new List<Layout>(); for (int i = 1; i <= n, i++) { if () { break; } for (int j = 1; j <= m, j++) { var newLayout = PerturbLayout(currentLayout, chain); if (IsValid(newLayout)) { if (DifferentEnough(newLayout, generatedLayouts)) { generatedLayouts.Add(newLayout); } } if () { currentLayout = newLayout; } else if () { currentLayout = newLayout; } } } return generatedLayouts; }
Este é o pseudo-código do método responsável pela criação de um circuito de circuito separado, simulando o recozimento.
Para acelerar todo o processo, tentaremos encontrar a configuração inicial de baixa energia. Para fazer isso, organizaremos os nós na cadeia atual para uma pesquisa abrangente, começando por aqueles que são adjacentes aos nós já incluídos no esquema. Em seguida, os nós ordenados são colocados um de cada vez e, para eles, a posição com a menor energia é selecionada no espaço de configuração. Aqui não estamos fazendo nenhum retorno - este é um processo simples e ganancioso.
Vídeo bônus
O vídeo abaixo mostra os diagramas gerados a partir do mesmo gráfico de entrada que no primeiro vídeo. No entanto, desta vez, uma abordagem incremental é mostrada. Você pode perceber que o algoritmo adiciona cadeias de nós, uma de cada vez. Também é visto que, às vezes, existem dois circuitos parciais consecutivos com o mesmo número de nós. Isso acontece quando o algoritmo retorna. Se a primeira tentativa de adicionar outro circuito à primeira falha parcial do circuito, o algoritmo tentará outro circuito parcial.
Materiais para download
A implementação do algoritmo no .NET pode ser encontrada no
meu github . O repositório contém a DLL .NET e o aplicativo WinForms GUI, controlado pelos arquivos de configuração YAML.