Algoritmo para mapa 2D procedural com caminhos conectados

Problema a resolver: Gere um mapa aleatório de masmorra 2D para um jogo baseado em peças em que todas as salas estão conectadas.

Estou procurando soluções melhores do que as que tenho atualmente.

Minha solução atual é que eu corro dois algoritmos. O primeiro gera a masmorra com seus quartos. O segundo garante que todos os quartos estejam conectados. Estou curioso para saber que outras soluções podem existir. Mais rápido e / ou mais fácil etc. A velocidade não é realmente uma preocupação, mas se a velocidade puder ser obtida sem nenhum custo real, isso é uma coisa boa. Mais importante é que eu, e outros que lêmos, aprendamos maneiras diferentes de abordar e resolver o problema.

Abaixo estão minha implementação atual. Atualmente, os quartos não têm saídas ou saídas em 2, 3 ou 4 direções.

Gerando as salas de masmorra

Configuração: defina a sala atual para a sala superior esquerda.

1. Obtenha um tipo de quarto válido para o quarto (onde o tipo de quarto válido é um tipo sem saídas para fora da masmorra e com saídas que correspondem às saídas da sala acima e da sala à esquerda. Só é necessário verificar acima e esquerda devido ao passo 2 abaixo).
2. Abaixe a sala e avance a coordenada x uma etapa. Se a coordenada x exceder a largura da masmorra, defina a coordenada x como 0 e avance a coordenada y um passo. Se a coordenada y exceder a altura da masmorra, estamos prontos.
3. Repita do item 1.

Em seguida, verifico se todas as salas estão conectadas. Se elas não estiverem todas conectadas, corro um segundo algoritmo que, de uma maneira não-sexy, mas definitivamente boa o suficiente em termos de layout da masmorra, percorre as salas e as altera para que tudo acabe. estar conectado.

Verificando se todos os quartos estão conectados

Instalação: Crie um mapa 2D de números inteiros representando caminhos e inicialize as entradas para um valor "não processado" (ainda não percorrido), -1. Defina um número inteiro do índice do caminho inicial que monitora o caminho atual como 1. Defina a sala atual para a sala superior esquerda, adicionando-a a uma pilha de salas para verificar.

1. Se a pilha contiver salas a serem verificadas, coloque-a no índice de caminho da sala com o índice de caminho atual. Se a pilha não contiver nenhuma sala, aumente o índice do caminho e tente obter uma sala avançando coluna por coluna, linha por linha, até obtermos uma sala que ainda não foi processada. Se não for possível encontrar espaço, estamos prontos.
2. Verifique se a sala tem uma saída para a esquerda. Se houver, adicione o espaço esquerdo à pilha, se ainda não estiver lá.
3. Repita a etapa 2 para as direções inferior, direita e superior (pois estamos usando uma pilha que significa que as salas são atravessadas no sentido horário, começando pela direção superior).
4. Repita da etapa 1.
5. Se a contagem dos índices de caminho for maior que um, haverá salas desconectadas.

Se houver salas desconectadas, agrupo as salas pelo índice de caminho, obtenha o índice do caminho maior e conecte todas as outras salas a essas salas. Este é um trabalho em andamento, mas meu plano (atual, "brutal") é percorrer cada sala de um grupo de salas (exceto a primeira) para verificar se há um caminho horizontal ou vertical para o grupo de salas biggeset e Nesse caso, crie um caminho horizontal / vertical injetando / atualizando os quartos entre eles. Enxague e repita. Feio, sim, mas é algo que não será perceptível em termos de padrão visual, por isso funciona nesse sentido.

Um dos melhores e mais usados ​​algoritmos que eu já vi por aí é gerar masmorras usando o Particionamento de espaço binário.

A melhor explicação geral que li é a encontrada em The Chronicles of Doryen (anexada ao final para fins de backup) porque explica o procedimento sem entrar no código, deixando a implementação para o leitor.

Dois outros tutoriais sobre o mesmo assunto, com código, podem ser encontrados em

• Como usar árvores BSP para gerar mapas de jogos
• Geração de masmorras usando árvores BSP

Construindo a árvore do BSP

Começamos com uma masmorra retangular cheia de células da parede. Vamos dividir esta masmorra recursivamente até que cada sub-masmorra tenha aproximadamente o tamanho de uma sala. A divisão da masmorra usa esta operação:

• Escolha uma direção aleatória: divisão horizontal ou vertical
• Escolha uma posição aleatória (x para vertical, y para horizontal)
• Dividir a masmorra em duas sub-masmorras

Agora temos duas sub-masmorras A e B. Podemos aplicar a mesma operação a ambas.

Ao escolher a posição de divisão, temos que tomar cuidado para não ficar muito perto da borda da masmorra. Devemos ser capazes de colocar uma sala dentro de cada sub-masmorra gerada. Repetimos até que as sub-masmorras mais baixas tenham aproximadamente o tamanho das salas que queremos gerar.

Construindo a masmorra

Agora criamos uma sala com tamanho aleatório em cada folha da árvore. Obviamente, a sala deve estar contida dentro da sub-masmorra correspondente. Graças à árvore BSP, não podemos ter duas salas sobrepostas.

Para construir corredores, passamos por todas as folhas da árvore, conectando cada folha à sua irmã. Se os dois quartos tiverem paredes cara a cara, podemos usar um corredor reto. Caso contrário, temos que usar um corredor em forma de Z.

Agora subimos um nível na árvore e repetimos o processo para as sub-regiões pai. Agora, podemos conectar duas sub-regiões com um link entre duas salas ou um corredor e uma sala ou dois corredores.

Repetimos o processo até conectar as duas primeiras sub-masmorras A e B

O método BSP é aparentemente o método mais popular para gerar masmorras, mas não é o único.

Para completar, explicarei o gerador que funcionou para mim . Tenho que admitir que não me lembro de onde li sobre isso, então vou apenas dizer que não é minha invenção (um artigo antigo de Jamis Buck parece muito familiar).

Um labirinto com quartos

A idéia básica é que uma masmorra é um labirinto com salas, mais ou menos. Portanto, o primeiro passo para esse algoritmo é gerar um labirinto :

O próximo passo é torná-lo escasso (remova os becos sem saída):

O passo número 3 é adicionar alguns loops (torná-lo não perfeito ), mas vou pular a imagem porque é quase imperceptível (não precisava de um labirinto perfeito, por isso tomei alguns atalhos no algoritmo de geração de labirinto, então já tinha loops neste ponto).

Em seguida, na etapa 4, precisamos remover células isoladas:

Neste ponto, terminamos os corredores e estamos prontos para adicionar salas. Para isso, fazemos o seguinte:

1. Gere um conjunto de salas (largura e altura)
2. Para cada sala, iteramos em todos os locais possíveis e decidimos o melhor local.
   • A melhor localização é calculada adicionando um peso às condições (como adjacência a um corredor).
3. Colocamos os quartos.

Até agora, nossa masmorra ficará assim:

O passo final é adicionar decorações.

Algumas considerações finais

• Eu usei uma versão simplificada do algoritmo de Eller .
• Algoritmos diferentes de labirinto podem resultar em diferentes texturas. Você pode preferir outro algoritmo. Por exemplo, a imagem a seguir mostra diferentes texturas resultantes de "Árvore binária" (diagonal diagonal) e uma variação dos algoritmos "Divisão recursiva" (corredores longos):