É possível obter uma estrutura semelhante a uma colméia, conectando todas as salas sem ter muitos corredores? (Muitos são 3-4 + corredores vindos de um quarto individual)
Abaixo está a saída de como meus quartos ficam, basicamente eles são colocados aleatoriamente.
O que eu espero obter no corredor.
procedural-generation
Liquidificador
fonte
fonte
Respostas:
Bem, a maneira mais simples de pensar começa por garantir que todos os quartos estejam conectados por pelo menos 1 corredor:
Agora sabemos que você pode chegar a todos os quartos, mas agora, se quiser mais do que este labirinto estritamente linear, basta percorrer os quartos e criar aleatoriamente um novo caminho para conectar os quartos, até um limite por quarto de 2 a 3, ou até que uma certa porcentagem de quartos atinja o máximo de conexões - etc.
Como etapa final, você pode adicionar regras que alterariam seus resultados para acomodar várias situações. Por exemplo, você pode observar que qualquer sala com apenas 1 corredor é, por definição, um beco sem saída; Você pode criar mais becos sem saída ou eliminá-los, garantindo que tudo tenha pelo menos 2 conexões. Você pode fazer com que becos sem saída tenham uma passagem secreta. Você pode garantir que a sala dos chefes seja um beco sem saída. Você pode garantir que sua sala inicial seja um beco sem saída, mas verifique se a segunda sala possui um mínimo de X conexões. Ao infinito.
Cada suposição e regra pode mudar radicalmente a aparência dos seus níveis, mas isso faz parte da diversão! Isso deve pelo menos levar você a uma colméia / caverna para começar.
fonte
Basta construir seus quartos já conectados. Comece com uma sala e depois construa 1 a 3 corredores para outras salas. Depois, recorra até adicionar quartos suficientes.
fonte
Como essas salas são vértices de gráfico incorporados em uma planície 2D, isso poderia, em teoria, ser resolvido resolvendo o problema do vendedor ambulante (o que seria bom com apenas algumas salas). Obviamente, uma heurística simples seria adequada e permitiria uma escalabilidade razoável.
Você calcula as arestas (comprimentos do corredor) entre todos os quartos. Você os classifica por comprimento. Você adiciona o corredor mais curto, a menos que ele crie um ciclo ou aumente o grau do vértice (sala) acima do valor máximo desejado (3-4) (Repetir). Para verificar os ciclos, você pode aplicar o UnionFind ou fazer um BFS rápido em pequenos dados.
fonte