Garantir que o labirinto do mapa da casa com elevadores possa ser resolvido?

13

No meu jogo, vemos o chão de uma casa de lado, e o herói pode subir; um elevador sobe (para o próximo elevador para cima) ou desce (para o próximo elevador para baixo), dependendo da seta como mostrado e sempre há exatamente um par de dois elevadores conectados. Essa é a única maneira que o herói pode se mover verticalmente, embora ele possa se mover livremente na horizontal. O mapa da casa é uma grade 11x5 aleatória com itens diferentes e paredes intransponíveis à extrema esquerda, extrema direita e, às vezes, em uma das duas posições do meio:

elevadores exemplo

Minha pergunta: como garantir que o mapa seja sempre aleatório e sempre solucionável e que o herói, começando no lado esquerdo do piso inferior, possa sempre deixá-lo através de qualquer elevação apontando para cima no piso superior?

Para o que vale a pena, estou usando a linguagem Lua para desenvolvimento. Muito obrigado!

2d maze Philipp Lenssen
fonte

Respostas:

14

O que você deseja fazer é criar um gráfico, de modo que cada nó seja uma posição de elevador, e as bordas entre eles significam que você pode caminhar / levantar por lá. Depois de criar o gráfico, você pode usar dfs / bfs para verificar se é possível ir do nó inicial ao nó final.

Usando o exemplo acima, fiz uma imagem de como seria o gráfico. Círculos verdes significam que existe um elevador e as linhas verdes significam que você pode viajar de um nó para outro.

nós

Luis Estrada
fonte
Obrigado, isso é muito útil! Eu deveria ter enfatizado mais na minha pergunta que o mapa também precisa ser gerado em primeiro lugar. O que estou pensando agora é que, se não for mais fácil - em vez de gerar combinações totalmente aleatórias de elevação / parede e verificar sua solvabilidade - ter o algoritmo percorrendo a casa, como o herói faria, e assim gerar elevadores e portas aleatórios (tomando distâncias aleatórias de elevação e curvas esquerda-direita, além de adicionar paredes, por exemplo). Como em "Ande à direita em 0, 4 ou 8 voltas; crie uma elevação para cima, suba de 1 a 4 andares ..."
Philipp Lenssen
@PhilippLenssen Essa é essencialmente a abordagem de "pesquisa aleatória em profundidade da primeira pesquisa" para geração de labirinto em um gráfico.
Kevin Reid
5

A diferença entre o que você tem e um labirinto normal é simplesmente que ele tem conexões não adjacentes verticalmente. Eu acho que o que você deve observar são algoritmos de geração de labirinto baseados em gráficos . Você simplesmente precisa ter um conjunto maior de "salas adjacentes" ou "paredes possíveis" do que um labirinto 2D comum, pois todo par verticalmente alinhado de células da grade do piso que ainda não possui um elevador intermediário é adjacente. Você pode modelar isso como um gráfico em que a adição de arestas de elevação definidas exclui acidentalmente outras arestas de elevação possíveis; alguns algoritmos podem ficar confusos com isso, mas outros não.

Kevin Reid
fonte