Geração de masmorras sem corredores e dependências de sala

Estou fazendo um jogo com um mundo processualmente gerado, criado no início do jogo, composto por várias áreas representadas por grades (por exemplo, 8x8, 9x6, os tamanhos seriam idealmente arbitrários). Essas áreas devem estar conectadas entre si por meio de uma lista de dependências.

Existe uma conexão quando pelo menos três espaços dessa grade são expostos entre essas duas áreas. Na célula do meio dessa área de conexão de 3 espaços, está a porta entre as áreas:

Eu tenho tentado descobrir uma maneira de conectá-los, mas torna-se cada vez mais complexo quanto mais áreas você precisar considerar ao mesmo tempo.

Eu tentei fazer prototipagem de papel e, embora seja um processo muito simples ao visualizá-lo, não encontrei um bom conjunto de expressões matemáticas que me permitam colocar salas com a mesma eficiência por código.

Aqui está um exemplo "simples" com o qual estou lutando agora:

• A área 'a' precisa estar conectada a 'b' e 'c'
• A área 'b' precisa estar conectada a 'a' e 'd'
• A área 'c' precisa estar conectada a 'a' e 'd'
• A área 'd' precisa estar conectada a 'b' e 'c'

Considere, por simplicidade, que estamos colocando os quartos por ordem de aparência na lista (tentei outros). Então, estou abordando isso como seu algoritmo de geração de calabouço processual padrão.

Colocamos 'a' em qualquer lugar do quadro, pois é a primeira área. Em seguida, escolhemos uma parede aleatoriamente e, como nada está conectado a essa parede, podemos colocar 'b' lá:

Agora precisamos colocar 'c', mas 'a' já está no quadro e tem uma parede ocupada, por isso decidimos colocá-lo em outra parede. Mas nem todo canal serve, porque 'd' está chegando e precisa estar conectado a 'b' e 'c' também:

Tentei uma possível limitação de que 2 salas com o mesmo conjunto de dependências não podem estar em paredes opostas, mas mesmo isso não garante sucesso:

E em outros casos, onde as áreas têm tamanhos diferentes, estar em paredes opostas pode funcionar:

Além disso, não considerar uma parede usada é uma suposição falha, pois exclui soluções válidas:

Tentei pesquisar pesquisas sobre outros algoritmos de Geração de Procedimentos ou similares, como os algoritmos Optimal Rectangle Packing e Layout de gráfico, mas geralmente esses algoritmos não levam em conta todas as restrições desse problema e são difíceis de misturar.

Pensei em várias abordagens, incluindo colocar uma área e voltar até encontrar um local adequado, mas elas parecem muito dependentes de tentativa e erro e custam caro em termos de computação. Mas, dada a extensa pesquisa sobre os dois últimos problemas que mencionei, pode ser a única / melhor solução?

Eu só queria ver se alguém teve problemas semelhantes no passado ou está disposto a me ajudar a descobrir isso e me dar algumas dicas sobre onde eu deveria começar com o algoritmo. Ou, na sua falta, terei que afrouxar as restrições que estabeleci.

Este é um problema interessante. Acredito que possa ser resolvido usando o planejamento de ações no espaço das colocações dos quartos.

Defina o estado do mundo da seguinte maneira:

//State:
//    A list of room states.
//    Room state:
//      - Does room exist?
//      - Where is room's location?
//      - What is the room's size?

Defina uma restrição como:

 // Constraint(<1>, <2>):
 //  - If room <1> and <2> exist, Room <1> is adjacent to Room <2>

Onde "adjacente" é como você descreveu (compartilhando pelo menos três vizinhos)

Diz-se que uma restrição é invalidada sempre que os dois quartos não são adjacentes e ambos existem.

Defina um Estado como válido quando:

// foreach Constraint:
//        The Constraint is "not invalidated".
// foreach Room:
//       The room does not intersect another room.

Defina uma ação como uma colocação de uma sala, considerando um estado atual. A ação é válida sempre que o estado resultante da ação é válido. Portanto, podemos gerar uma lista de ações para cada estado:

// Returns a list of valid actions from the current state
function List<Action> GetValidActions(State current, List<Constraint> constraints):
    List<Action> actions = new List<Action>();
    // For each non-existent room..
    foreach Room room in current.Rooms:
        if(!room.Exists)
            // Try to put it at every possible location
            foreach Position position in Dungeon:
                 State next = current.PlaceRoom(room, position)
                 // If the next state is valid, we add that action to the list.
                 if(next.IsValid(constraints))
                     actions.Add(new Action(room, position));

Agora, o que resta é um gráfico , onde Estados são nós e Ações são links. O objetivo é encontrar um Estado que é tanto válida, e todos os quartos foram colocados. Podemos encontrar um posicionamento válido pesquisando o gráfico de maneira arbitrária, talvez usando uma pesquisa aprofundada. A pesquisa será mais ou menos assim:

// Given a start state (with all rooms set to *not exist*), and a set of
// constraints, finds a valid end state where all the constraints are met,
// using a depth-first search.
// Notice that this gives you the power to pre-define the starting conditions
// of the search, to for instance define some key areas of your dungeon by hand.
function State GetFinalState(State start, List<Constraint> constraints)
    Stack<State> stateStack = new Stack<State>();
    State current = start;
    stateStack.push(start);
    while not stateStack.IsEmpty():
        current = stateStack.pop();
        // Consider a new state to expand from.
        if not current.checked:
            current.checked = true;
            // If the state meets all the constraints, we found a solution!
            if(current.IsValid(constraints) and current.AllRoomsExist()):
                return current;

            // Otherwise, get all the valid actions
            List<Action> actions = GetValidActions(current, constraints);

            // Add the resulting state to the stack.
            foreach Action action in actions:
                State next = current.PlaceRoom(action.room, action.position);
                stateStack.push(next);

    // If the stack is completely empty, there is no solution!
    return NO_SOLUTION;

Agora o qualidade da masmorra gerada dependerá da ordem em que salas e ações são consideradas. Você pode obter resultados interessantes e diferentes provavelmente permutando aleatoriamente as ações que você executa em cada estágio, fazendo uma caminhada aleatória no gráfico de ação do estado. A eficiência da pesquisa dependerá muito da rapidez com que você pode rejeitar estados inválidos. Pode ser útil gerar estados válidos a partir das restrições sempre que você desejar encontrar ações válidas.

Suas prioridades de geração estão em conflito. Ao gerar níveis, seu primeiro objetivo deve ser uma rede de pontos conectados planos (sem sobreposição) , independentemente da escala. Em seguida, prossiga para criar salas a partir dos pontos nessa web. Criar formas de sala primeiro é um erro, de um modo geral. Crie a conectividade primeiro e depois veja quais formulários de sala podem ser acomodados nela.

Algoritmo Geral

1. Crie uma grade de piso quantizada de tamanho suficiente para suportar seu nível, usando uma matriz ou imagem 2D.

2. Pontos de dispersão aleatoriamente através deste espaço vazio. Você pode usar uma verificação aleatória simples em cada bloco para ver se recebe um ponto ou usar a distribuição padrão / Gaussiana para dispersar os pontos. Atribua um valor numérico / cor único a cada ponto. Estes são os IDs. (PS: Se, após essa etapa, você achar que precisa aumentar seu espaço, faça-o).

3. Para cada um desses pontos gerados, em sequência, aumente gradualmente um círculo de limites ou retângulo de limites em uma única etapa (geralmente uma taxa de 0,5-1,0 células / pixels por etapa) em xey . Você pode aumentar todos os limites em paralelo, todos começando no tamanho zero na mesma etapa, ou pode começar a cultivá-los em momentos e taxas diferentes, influenciando o tamanho daqueles que começam mais cedo (imagine mudas crescendo, onde algumas comece tarde). Por "crescer", quero dizer preencher os limites recém-incrementados com a cor / ID exclusiva do ponto de partida para esses limites. Uma metáfora para isso seria segurar canetas contra as costas de um pedaço de papel e assistir a manchas de cores diferentes crescerem até que se encontrassem.

4. Em algum momento, os limites de um ponto e outro vão colidir durante a etapa de crescimento. Este é o ponto em que você deve parar de aumentar os limites para esses dois pontos - pelo menos no sentido uniforme descrito na etapa 3.

5. Depois de aumentar todos os limites de pontos o máximo possível e interromper todos os processos de crescimento, você terá um mapa que deve ser amplamente, mas não totalmente preenchido. Agora você pode arrumar esses espaços vazios, que eu assumo serem brancos, como se estivessem colorindo uma folha de papel.

Preenchimento de espaço pós-processo

Uma variedade de técnicas pode ser usada para preencher os espaços vazios / em branco que permanecem, na etapa 5:

• Faça com que uma única área vizinha já colorida reivindique o espaço, enchendo-o dessa cor para que tudo se junte.
• Inunde com novas cores / números / IDs ainda não utilizados, de forma que eles formem áreas totalmente novas.
• A abordagem round robin é tal que cada área vizinha já preenchida "cresce" um pouco no espaço vazio. Pense nos animais que bebem em volta de um bebedouro: todos eles bebem um pouco da água.
• Não preencha totalmente o espaço vazio, basta atravessá-lo para ligar as áreas existentes usando passagens retas.

Perturbação

Como passo final para tornar as coisas mais orgânicas, você pode fazer perturbações nas bordas em graus variados, nas células das bordas das áreas. Apenas certifique-se de não bloquear rotas de movimento cruciais.

Teoria, pelo interesse

Isso é semelhante à abordagem adotada nos Diagramas de Voronoi / Triangulação de Delaunay , exceto que, acima, você não está explicitamente criando arestas - em vez disso, quando áreas delimitadoras colidem, o crescimento cessa. Você notará que os diagramas de Voronoi são preenchedores de espaço; isso ocorre porque eles não cessam o crescimento apenas com o toque, mas com algum grau nominal de sobreposição. Você pode tentar semelhante.