Algoritmo de caminho mais longo para geração de labirintos roguelike

10

Eu tenho um mapa simples baseado em grade composto por salas, como este (A = entrada, B = saída):

   0 1 2 3
  #########
0 # B # #####
  #########
1 # ### #
  #########
2 # # #
  # # #
3 # # #
  #########
4 # ### #
  #########
5 ### A #
  ### #
6 ### #
  #########

E estou tentando criar um algoritmo adequado para criar um caminho de portas entre as salas, de tal maneira que o jogador precise explorar a maior parte do mapa antes de encontrar a saída.

Em outras palavras, eu estou tentando encontrar o caminho mais longo possível de A para B .

(Estou ciente de que esse problema pode ser resolvido para gráficos acíclicos; no entanto, nesse caso, pode haver ciclos.)

EDIT: Outro exemplo em que as salas são conectadas usando o aterro e a saída é escolhida como a sala mais distante da entrada:

   0 1 2 3
  #########
0 # B # #
  # # - #####
1 # | # #
  ### # #
2 ### # #
  ### - # - ###
3 # | ###
  # - #######
4 #A | #
  # # #
5 # # #
  # # #
6 # # #
  #########

Observe que o caminho para a saída não é o caminho mais longo possível.

Usuário não encontrado
fonte
Se você forçar o jogador a seguir o caminho mais longo possível, estará construindo um caminho reto que finge ser complexo. Isto é mau.
o0 '.
Não é ruim (é a base do gênero de atiradores ferroviários, por exemplo), mas você precisa estar ciente de que está fazendo isso e projetar o resto do seu jogo para funcionar bem com ele.
Também é mais fácil controlar o ritmo do jogo quando os níveis são principalmente lineares. Permite adicionar, por exemplo, uma sala de recuperação após uma sala de monstros particularmente difícil. Se não houvesse um caminho principal, a distribuição de desafios e recompensas seria aleatória.
Usuário não encontrado

Respostas:

11

Eu acho que você está fazendo isso da maneira errada. O caminho máximo em um gráfico com ciclos é tecnicamente indefinido porque é infinito se o ciclo estiver entre o início e o fim. Provavelmente existem maneiras inteligentes de estender / restringir a definição de caminho máximo, mas não acho que seja a melhor abordagem aqui.

Você não está tentando modelar um caminho longo real (por exemplo, um robô tentando explorar o máximo de área possível em um mapa). Você está apenas tentando convencer o jogador a explorar muitas salas.

Portanto, aproveite a chance do jogador encontrar a saída proporcional à porcentagem do mapa explorado até agora . Digamos que há X salas em um nível, e o personagem do jogador explorou Y. Da próxima vez que o personagem entrar em uma sala, coloque a saída lá com probabilidade f (Y, X). Um exemplo trivial de f pode ser (Y * Y) / (X * X) - por exemplo, para 10 quartos, há 100% de chance de sair na última sala, 81% de chance de estar na próxima e última sala - e apenas um 1% de chance de estar no primeiro quarto.

Você pode ajustar a equação da maneira que quiser, fazendo com que o jogo pareça certo, e talvez até dar ao jogador algumas habilidades para aumentar a probabilidade de gerar. A parte principal é, não gere a saída até que o personagem realmente entre na sala. Este método também é imune ao conhecimento do jogador sobre o algoritmo de geração de masmorras; mesmo se o jogador tiver padrões de movimento estranhos, como o salto do cavaleiro no NetHack ou no teletransporte, eles terão que explorar mais salas para encontrar a saída.

Se você precisar gerar estaticamente a saída, poderá usar a mesma ideia com um caractere virtual. Imagine um preenchimento de inundação começando na posição do personagem, movendo-se uma vez na célula a cada iteração. A última sala a ser preenchida é a onde a saída pertence (na verdade, a última célula a ser preenchida é a célula em que está mais distante do jogador). No entanto, neste caso, o jogador tem mais informações sobre a saída - se estiver à esquerda, provavelmente à direita - e se puderem se teletransportar, poderão realmente chegar mais rápido do que uma caminhada aleatória normal.

Finalmente, acabei de terminar um roguelike, onde a saída surgiu do outro lado do mapa a partir do personagem do jogador e depois vaguei aleatoriamente. Alguns itens da masmorra tornaram visível no mapa, à custa de ficar com fome mais rápido. Não fiz nenhuma análise, mas definitivamente parecia que eu tinha que explorar mais o mapa para encontrá-lo, e isso dava aos níveis uma sensação única.


fonte
A geração dinâmica parece uma boa ideia, desde que o jogador não perceba. Caso contrário, acho que eles se sentiriam enganados. Eu amo a idéia de aterro, no entanto.
Usuário não encontrado
2
Bem, toda a sua proposta está enganando o jogador. Não me culpe por refinar a matemática para não exigir um modelo mundial. ;) Mas você pode usar truques de design para torná-lo mais agradável - por exemplo, a saída é colocada a priori, mas uma chave necessária para usá-la é gerada no método que descrevi, ou colocada em um monstro que só aparece depois de explorar o X quartos / matar monstros X, ou abrindo a porta requer lançando interruptores X, um em cada quarto, etc ...
Eu tentei uma abordagem de aterro. Ele faz um bom trabalho de conectar todas as salas e produz ramificações curtas, mas na verdade não produz o caminho mais longo possível para a saída, mesmo que a saída seja o último nó visitado (ou, na minha implementação, o mais distante). (exemplo adicionado à minha pergunta)
Usuário não encontrado
Sou a favor de labirintos baseados em chaves / comutadores. Parece mais fácil implementar esse tipo de coisa com árvores, porque, se você tiver dois ramos, poderá detectar qual ramo leva à saída, bloqueá-lo e colocar a chave no outro ramo.
Usuário não encontrado
Mas admito que errei ao pensar que era um problema de busca de caminhos "A a B". Sei que faz mais sentido encontrar a saída como resultado do algoritmo do que como objetivo.
Usuário não encontrado
6

Uma alternativa possível seria criar uma árvore de expansão (máxima?) Usando Prim / Kruskal (para eliminar ciclos) e aplicar um algoritmo tradicional de caminho mais longo na árvore de expansão.

No entanto, estou preocupado que o algoritmo de spanning tree tenda a criar ramificações sem saída, forçando o jogador a voltar constantemente.

EDIT: resultado do uso de um algoritmo baseado em Kruskal e da colocação da saída no final do ramo mais longo:

   0 1 2 3
  #########
0 #A | #
  # ##### - #
1 # # #
  ### #
2 ### #
  ### #
3 ### #
  ### - #####
4 # | #
  # - ##### - #
5 # ### #
  # - #######
6 # # B #
  # # - #
7 # | #
  #########
Usuário não encontrado
fonte
1
Eu ia sugerir Primm também :-), +1, acho BackTrack é uma parte importante de um monte de jogos também ... verifique diablo 2.
Mr.Gando
2

Aqui está algo para se mexer:

Connect each room with a door to another room.
N = 0.75*TotalNumberOfRooms
Until (pathSize > N) {
  Use A* pathing to get a path from A to B. (G being size of room, or # of monsters)
  if (pathSize < N) remove a connection/door
  if (noPath) choose a different door/connection
  if (room.doors < 1) choose a different door/connection
}

Eu removia portas aleatoriamente ao longo do caminho, caso contrário, você acaba com uma porta na saída e toneladas de portas no início.

Eu acho que O(n^2)isso não é ótimo para mapas grandes.

Stephen Furlani
fonte
Uma solução muito elegante em princípio. Da próxima vez, devo tentar pensar em algo assim antes de procurar técnicas complicadas.
Usuário não encontrado
Bem, talvez elegante, mas vai ser um porco do processador. O (n ^ 2) não será dimensionado bem com mapas grandes.
Stephen Furlani
1

Acredito que você já tenha ótimas respostas, mas aqui estão os meus US $ 0,02 em solução teórica para o problema.

O que você deseja NÃO é o caminho mais longo, mas o caminho mais curto. Você quer a sala mais distante, considerando que está considerando o caminho mais curto para a sala. Isso provavelmente parece confuso, mas é muito fácil de calcular.

  1. Comece na sua sala inicial. Marque cada um de seus vizinhos 1. Eles estão a uma distância da sala de partida.
  2. Para cada quarto marcado como 1, visite cada um dos vizinhos NÃO MARCADOS e marque-os como 2. Eles estão a 2 distância do início.
  3. Continue até ter coberto todos os quartos. A sala com o número máximo está mais distante desde o início.

A computação de um caminho mais longo real (não demorará muito para, digamos, 10 salas) não funcionará porque você não pode fazer o jogador seguir esse caminho mais longo. Portanto, colocar a entrada e a saída em duas salas mais afastadas uma da outra é a sua melhor aposta. Para encontrar isso, calcule a sala mais distante de uma sala aleatória. Então, a partir dessa sala, encontre a sala mais distante. Isso é chamado de encontrar o diâmetro de um gráfico, por favor, pesquise no Google.

Sid Datta
fonte