Geração processual de masmorras 3D de vários andares

Recentemente, joguei vários roguelike, então decidi tentar escrever meu próprio gerador de masmorras procedurais. Existem muitas maneiras de resolver esse problema, e eu escolhi o algoritmo do autor TinyKeep descrito aqui . Eu expandi esse algoritmo para que ele funcione em 3D e possa criar masmorras de vários andares.

Código de amostra publicado no repositório do Github . Para demonstração, eu uso o Unity3D, mas é claro que esses conceitos se aplicam a qualquer outro mecanismo.

Duas dimensões

Primeiro, preciso escrever um algoritmo para duas dimensões. Em geral, funciona da mesma forma que o algoritmo TinyKeep, mas possui diferenças para criar níveis mais interessantes.

A cena para este exemplo é chamada Dungeon2D. O código para ele está na pasta Scripts2D.

Algoritmo

O mundo está dividido em uma grade retangular. Suponho que 1 unidade será suficiente para indicar o corredor. Em um jogo completo, 1 unidade do Unity pode corresponder, por exemplo, a 5 metros. Para a grade, escolhi um tamanho de 30 × 30.

1. Organizamos os quartos arbitrariamente, mas para que eles não se sobreponham. A localização não importa, portanto, neste exemplo, eu apenas dou a eles uma localização e tamanho aleatórios. Além disso, em cada lado, adicionei um buffer de 1 unidade de largura (para que as salas não se tomassem), mas isso não é necessário para o algoritmo funcionar.


Retângulos vermelhos são quartos

2. Crie um gráfico de triangulação de Delaunay para salas. Eu usei o algoritmo de Bower-Watson para isso. Existem muitas implementações desse algoritmo em várias linguagens. Eu escolhi uma que será fácil de portar para C #.


Triangulação de Delaunay

3. Crie uma árvore de abrangência mínima (MST) a partir da triangulação. Eu usei o algoritmo Prim para isso.


Corredores do MST

4. Criamos uma lista de corredores, começando com cada borda da árvore do estágio 3. A árvore contém todas as salas, de modo que o caminho para cada sala é garantido que existe. Adicione aleatoriamente as arestas da triangulação à lista. Então, criaremos vários loops nos corredores. No meu código, usei a probabilidade de adicionar cada borda a 12,5%.


Corredores após adicionar várias arestas ao MST. Observe que os loops apareceram.

5. Para cada corredor da lista, use o algoritmo A * para encontrar os caminhos do início ao fim. Depois de encontrar um caminho, ele muda o estado do mundo para que os corredores futuros sempre possam ignorar os existentes.

A função de custo que usei torna menos oneroso mover-se ao longo de um corte de corredor em uma iteração diferente do que criar um novo corredor. Isso estimula um algoritmo de localização de caminhos para combinar corredores que passam por um espaço. O movimento pela sala é possível, mas caro. Portanto, na maioria dos casos, o algoritmo de localização de caminho prefere evitar salas.


Retângulos azuis são corredores

Aqui estão alguns exemplos de um algoritmo que usa recursos gráficos reais (os recursos e o código para sua colocação não estão no repositório):

Três dimensões

Depois de criar um gerador de masmorra em 2D, comecei a transferi-lo para 3D. Todos os algoritmos usados ​​têm versões 3D, então deve ser simples, certo?

Algoritmo

A grade agora tem um tamanho de 30x5x30.

1. A primeira mudança foi a geração de salas em 3D. Essa mudança é trivial.


Por favor, note que os quartos podem ter vários andares.

2. Em seguida, encontramos a triangulação 3D de Delaunay dessas salas, ou melhor, o tetraédrico de Delaunay. Depois de pesquisar informações sobre as consultas "triangulação 3D em Delaunay" ou "tetraédrica em Delaunay", encontrei muitos artigos de pesquisa, mas não um único exemplo de código.

O mais próximo do que eu precisava era da implementação da triangulação CGAL 3D, mas havia dois problemas com ela. Primeiro, este módulo estava disponível apenas sob a licença GPL. O segundo - o código era tão modelado e obscuro que não consegui descobrir onde o algoritmo foi implementado.

No final, eu tive que estudar o princípio do algoritmo de Bower-Watson para mudar sozinho. Ainda não entendo por que os círculos circunscritos são tão importantes, mas pelo menos consegui reescrever o algoritmo com as esferas descritas usando esta página no Wolfram MathWorld. Como essas são principalmente operações com matrizes 4x4, Matrix4x4 todo o trabalho complexo ao tipo Matrix4x4 do Unity3D.

Esta nova versão está localizada em Scripts3D/Delaunay3D.cs , caso alguém precise de um código facilmente compreendido com uma licença MIT.


É difícil perceber, mas em vez de um triângulo com três vértices, o algoritmo agora cria um tetraedro com 4 vértices. Pelo menos um desses picos estará localizado em outro andar, porque, caso contrário, o tetraedro será degenerado. Isso oferece ao estágio de pesquisa muitas oportunidades de movimentação entre andares.

3 e 4. As arestas do estágio 2 com alterações completamente triviais podem ser passadas para o algoritmo Prim.


Corredores 3D-MST


Corredores com várias costelas adicionados novamente

5. As dificuldades começam quando implementadas no algoritmo 3D A *. A versão 2D é incrivelmente simples, é uma implementação padrão do A *. Para transferi-lo para 3D, preciso adicionar a capacidade de procurar o caminho para subir e descer e conectar salas em diferentes andares. Decidi conectar os pisos não com escadas verticais, mas com lances de escadas.

Esse é o problema. Um lance de escada é mais complicado do que apenas subir. Para se mover verticalmente, as escadas precisam se mover horizontalmente. Ou seja, ela tem uma subida e uma extensão . Dê uma olhada na imagem abaixo. A célula atual é um quadrado azul sólido. Os vizinhos possíveis são quadrados vazios. O algoritmo de pesquisa de caminho não pode se mover para uma célula diretamente acima da célula atual. Em vez disso, ele terá que se mover horizontal e verticalmente.


Vista lateral Você pode criar nós nas laterais, mas não na parte superior.

Para criar um algoritmo de busca de caminho para uma escada, eu precisava selecionar sua forma. Uma proporção de altura para comprimento de 1: 1 seria muito íngreme, por isso escolhi uma proporção de 1: 2. Para cada unidade de medida vertical, a escada move duas unidades horizontais. Além disso, para que o personagem seja colocado, deve haver espaço acima da escada, ou seja, duas células acima da escada também devem estar abertas. Em geral, uma escada ocupa quatro células:


Escadaria e espaço livre acima dela

Também deve haver um corredor na parte superior e inferior da escada. O algoritmo de busca de caminho não deve chegar às escadas pelo lado ou pela direção oposta. Será impraticável e estranho se a escada colidir com o corredor, como mostrado abaixo.



Ou seja, no final, o formato das escadas deve se parecer com a imagem abaixo. O algoritmo de localização de caminho deve garantir a existência de corredores em dois quadrados azuis.


A escada começa com um quadrado azul sólido e sobe um andar.

O algoritmo de busca de caminho deve passar do ponto inicial para o ponto final em uma etapa. Isso significa que ele deve ser deslocado 3 unidades na horizontal e 1 unidade para cima ou para baixo. O algoritmo A * foi projetado para mover a cada etapa de um nó para o próximo. Para criar as escadas, eu tenho que "pular" quatro células da escada.

A dificuldade é que, de alguma forma, preciso que o algoritmo contorne as escadas que ele cria. Não posso adicioná-los ao conjunto fechado A *, porque, nessas células, outro caminho de outra direção não poderá seguir. Mas também não posso deixá-los, porque o algoritmo de pesquisa de caminhos poderá se mover pela escada recém-criada, criando as situações indesejáveis ​​mostradas acima.

A solução foi que cada nó acompanhe todos os nós anteriores em seu caminho. Então, ao considerar um nó vizinho, ele será rejeitado se se referir ao caminho do nó atual. O corredor no final da escada conterá todas as células ocupadas pela escada, o nó no início da escada e todos os nós no caminho até ela, e assim por diante até o início. O algoritmo de busca de caminho pode criar outro caminho atravessando as escadas, porque o segundo caminho não saberá sobre as escadas.

O comportamento descrito acima é necessário apenas para alguns caminhos em potencial na mesma chamada de função de caminho. Para gerar todos os corredores, ainda existem muitos desafios para encontrar o caminho. As iterações subsequentes simplesmente ignoram as escadas existentes como antes.

O algoritmo neste estágio não é mais completamente A *. Existem muitos casos especiais apenas para escadas de contabilidade. A necessidade de verificar todo o caminho anterior em cada estágio é um processo caro. Uma implementação ingênua seguiu todos os nós antes do início, lendo-os como uma lista vinculada. Em seguida, levaria tempo O (N) para verificar o caminho para cada nó vizinho.

Eu escolhi esta implementação: armazenando uma tabela de hash em cada nó, cujas chaves são os nós anteriores. Devido a isso, a verificação do caminho é realizada em O (1), no entanto, ao adicionar um nó ao caminho, a tabela de hash precisa ser copiada, e esse é O (N). Eu escolhi esse método porque percebi que o algoritmo lê caminhos com mais frequência do que alterá-los.

Seja como for, a complexidade geral será de aproximadamente O (N ^ 2), embora eu não saiba como analisar isso corretamente. Essa modificação é o principal "gargalo" do algoritmo de geração de masmorras.

Depois de fazer todas essas alterações, o resultado foi o seguinte:


Retângulos verdes são escadas


Os caminhos do gerador podem ser simples ...


... ou complicado

Aqui está a aparência de uma masmorra 3D com recursos gráficos reais:


Calabouço com vários andares


O algoritmo de geração de masmorras é capaz de criar comportamentos emergentes interessantes.


Duas escadas formam uma escada dupla


Difícil de explicar a escada de largura tripla


Um caminho descendo dois andares pode criar duas escadas com uma plataforma no meio


Quando vários caminhos passam próximos um do outro, os corredores podem ser bastante grandes


Duas escadas descem para um andar

Conclusão

A parte mais difícil do projeto foi a criação dos algoritmos necessários para a versão 3D. Não consegui encontrar uma única implementação da triangulação 3D de Delaunay, então tive que fazer isso sozinha. Os requisitos para o algoritmo de busca de caminhos eram muito específicos, então eu também fiz isso.

Mas o trabalho valeu a pena. As masmorras criadas por esse algoritmo são interessantes e podem se tornar a base para um bom jogo.