Nesta semana, comecei a trabalhar em um novo tópico: a geração de masmorras e cavernas. Usei o particionamento de espaço para gerar salas, algoritmos de geração de labirinto para gerar corredores e autômatos celulares para dar às cavernas uma aparência mais natural.

Divisão de espaço

Existem várias maneiras de gerar salas de masmorra ( posicionamento aleatório , geração baseada em agente , usando o comportamento da direção de separação ou um mecanismo físico , etc.). Mas meu método favorito é dividir o espaço, porque é facilmente controlado e expandido.

Também existem várias maneiras de dividir o espaço: divisão em grades, divisão binária do espaço, divisão do espaço por uma árvore de quadrantes, diagramas de Voronoi, etc. Decidi usar uma partição binária de espaço, porque é adequada para gerar salas retangulares. Este método ganhou popularidade graças a um artigo no RogueBasin.

A única complexidade desse algoritmo é a escolha da posição de separação. Se não impusermos uma restrição à posição de separação, obteremos partições estranhas de espaço:


Existem várias maneiras de evitar esse comportamento. Uma delas é limitar a posição de separação a duas proporções, por exemplo, na faixa de 30% a 70% ou de 40% a 60%. Outra maneira é usar a distribuição normal ou binomial em vez da distribuição uniforme, aumentando assim a probabilidade de separação no centro do lado, e não nas bordas. Esses métodos corrigem o problema, mas é difícil entender como exatamente os parâmetros afetam o resultado final.

Portanto, usei outro método, cuja vantagem é que ele possui um parâmetro e é facilmente entendido: a proporção máxima permitida entre o comprimento e a largura das células. Ao amostrar uma nova separação, primeiro calculo os valores mínimo e máximo que ela pode ter para que a razão para duas novas células seja menor que o limite e, em seguida, realizo uma amostragem uniforme entre esses dois limites. Aqui está o resultado ao variar a taxa máxima permitida:


Bons resultados são obtidos com uma proporção máxima de 2,0 a 3,0:

Geração de quartos

O próximo estágio é a geração em cada célula da sala. Não há problemas especiais aqui, apenas estabeleci limites para que os quartos não sejam muito pequenos e não fiquem muito próximos das paredes das células.

Aqui estão os resultados:

Seleção de costela

Nos geradores de masmorra de divisão binária, a árvore binária usada na etapa de divisão é normalmente reutilizada para gerar corredores. Eu não fiz isso, porque essa abordagem parece me limitar.

Em vez disso, na fase de dividir o espaço, construo a estrutura de uma lista de arestas duplamente conectada , o que nos permite saber quais células estão localizadas próximas umas das outras. Dessa forma, recebo os seguintes gráficos:


Existem três vantagens nessa abordagem. Primeiro: se, no futuro, eu quiser mudar a maneira de dividir o espaço, o restante do gerador permanecerá válido, porque ele recebe apenas uma estrutura de dados semi-edge na entrada. Segundo: agora, para selecionar as arestas que se tornarão corredores, posso usar qualquer algoritmo para gerar labirintos . Terceiro: se eu quiser adicionar loops à masmorra, eu posso facilmente implementar isso.

Por enquanto, apenas uso o algoritmo de Kruskal e a distância dos blocos da cidade para selecionar arestas. Aqui estão os resultados:

Geração de Corredores

O próximo passo é gerar corredores a partir das arestas selecionadas. Esta é provavelmente a parte mais complicada do gerador, porque preciso tomar cuidado para que nenhum corredor se cruze com o outro.

Aqui estão os resultados:

Geração de cavernas

Os resultados anteriores foram adequados para criar masmorras, criptas e outras estruturas artificiais, mas eu queria dar às cavernas e minas uma aparência mais natural. A maneira clássica de gerar cavernas é usar um autômato celular, conforme descrito neste artigo do RogueBasin. O grande problema dos autômatos celulares é que seus resultados não são completamente controlados.

Enfim, decidi usar autômatos celulares para criar uma aparência natural, mas impor restrições a eles para obter um resultado controlado. Em vez de apenas dois estados: vivo e morto, eu uso quatro: absolutamente morto, morto, vivo, definitivamente vivo. Os estados “perfeitamente precisos” não podem mudar no processo; são usados ​​para limitar os resultados.

As salas e corredores gerados nas etapas anteriores são preenchidos com células "exatamente vivas". Ou seja, ainda temos salas de apoio e garantimos que elas serão conectadas uma à outra. As arestas que não foram selecionadas são preenchidas com células "exatamente mortas" para que nenhum novo caminho apareça entre as salas. Por fim, ao redor de salas e corredores, aleatoriamente tornamos algumas células vivas. Aqui está a configuração inicial:


Então começamos o autômato celular:



Aqui estão mais alguns resultados de amostra:


Mais tarde adicionarei um preenchimento para remover partes inacessíveis.

Este é o primeiro passo em uma longa jornada para criar um gerador de masmorra interessante. Estou satisfeito com os resultados. Estou especialmente orgulhoso do método restrito de autômatos celulares de criar cavernas naturais e controladas. Também gosto do fato de que cada estágio de geração é separado dos outros e pode ser modificado individualmente.

Excluir células isoladas

Em seguida, implementei um preenchimento para remover células inacessíveis:

Vários corredores entre salas

Experimentando os parâmetros do gerador, descobri que se você adicionar um pouco de ruído entre as salas conectadas, obtém resultados interessantes.

Aqui está a diferença nos resultados antes de aplicar ruído às salas conectadas e imediatamente depois, o parâmetro muda em apenas uma unidade:



Se você aumentar as salas um pouco, o resultado será ainda mais interessante:


É ótimo que tenhamos um acidente e que surjam estruturas bonitas, mas, ao mesmo tempo, a estrutura do gráfico e as designações das salas são preservadas, o que será útil:

Geração de Azulejos para Cavernas

Passei a maior parte do tempo gerando ladrilhos. Não é muito difícil, mas para a implementação correta são necessários alguns truques.

Aqui estão os resultados da amostra:


O melhor é que você pode facilmente mudar de uma caverna de pedra para uma areia ou gelo:


Os próximos passos na geração da masmorra serão a adição de cenários e monstros.