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.
path-finding
roguelikes
Usuário não encontrado
fonte
fonte
Respostas:
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
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:
fonte
Aqui está algo para se mexer:
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.fonte
2 Estouro de pilha publica postagens semelhantes a esta: traçado mais longo do gráfico , referência da mesma publicação .
fonte
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.
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.
fonte