método para pathfinding especializado?

Question

Eu estou trabalhando em um roguelike no meu (muito pouco) tempo livre. Cada nível vai ser basicamente algumas salas retangulares ligados entre si por caminhos. Quero que os caminhos entre salas de estar com aparência natural e ventoso, no entanto. Por exemplo, eu não iria considerar o seguinte aparência natural:

       B       
       X       
       X       
       X       
      XX       
     XX        
    XX         
  AXX          

Eu realmente quero algo mais parecido com isto:

       B       
       X       
       XXXX    
          X    
          X    
          X    
          X    
  AXXXXXXXX    

Esses caminhos devem satisfazer algumas propriedades:

1. I deve ser capaz de especificar uma área dentro da qual eles são delimitadas,
2. I deve ser capaz de parametrizar como ventoso e longas estão,
3. As linhas não deve olhar como eles começaram em um caminho e terminou na outra. Por exemplo, o primeiro exemplo acima parece que começou em A e terminou no B, porque, basicamente, mudou de direção várias vezes até que ele alinhado com B e, em seguida, só fui direto para lá.

Eu estava esperando para usar A *, mas honestamente não tenho idéia o que o meu heurística seria. Eu também considerou o uso de um algoritmo genético, mas eu não sei como prático que o método pode acabar.

A minha pergunta é, o que é uma boa maneira de obter os resultados que eu quero? Por favor, não apenas especificar um método como "A *" ou "o algoritmo de Dijkstra," porque eu também precisam de ajuda com uma boa heurística.

Answer 1

Antes de descobrir como produzir caminhos, você tem que descobrir uma maneira mais precisa para o estado que você quer. Uma maneira de fazer isso é atribuir cada caminho de uma pontuação, em seguida, procurar caminhos de alta pontuação. Aqui estão algumas questões a considerar:

1. Você prefere corridas de longa retas para as curtas? Como você vai quantificar essa preferência? (Para obter um algoritmo de busca para convergir, será mais fácil se a sua função de pontuação é não-linear.)

2. Se você não quiser ir direto para o seu destino, você pode querer recompensar passos que estão fora da linha principal. Por exemplo, no caminho de A para B, considerar cada ponto, em seguida, tomar três passos e calcular a direcção entre pontos. Agora pegue o cosseno da diferença de que direção e direção reta de A para B. negá-lo. Passos sobre a contagem de linha -1 contra você, passos perpendicular são neutras, e passos de distância da linha de +1 para você.

Aqui estão alguns bons passos seguintes:

• Pense em várias idéias mais pontuação.
• Desenhe uma dúzia de caminhos de mão e ordem de classificação-los por quanto você como eles.
• Para cada caminho, criar um par de pequenas variações com a mão.
• Execute sua função de pontuação em todos os caminhos. Mantenha mexendo até obter uma função de pontuação que gosta do que você como.

Em seguida, você estará pronto para pensar sobre algoritmos de busca.

Answer 2

Eu diria pathfinding é o termo errado aqui: o que normalmente envolve encontrar uma rota válida de A para B, e o problema não é a constatação de que a rota, mas na criação de rotas para atender sua finalidade. Você está deliberadamente a criação de caminhos sub-óptima e sua qualidade vai ser difícil de quantificar. Então eu não acho que um algoritmo de busca com qualquer heurística seria a melhor solução para o problema. Quando você tem um critério obrigatório (a caminho de trabalho) e algumas, critérios indefinidos difusos (com aparência natural e sinuosas), é melhor começar por cumprir os requisitos obrigatórios e tentar transformar isso para os outros requisitos. Dessa forma, você sempre tem algo que funciona.

Eu sugiro, dado que parecem preferir caminhos horizontais e verticais transformando em ângulos retos, para começar com um, 2 caminho segmento reto de A para B. (A * com Manhattan heurística distância pode encontrar este para você, mas é tão fácil para o passo-lo sozinho). Em seguida, tomar um ponto aleatório ao longo de um dos dois segmentos e um dos dois pontos finais para esse segmento, e mover-se que subsecção da linha paralela a si própria por uma certa distância aleatória. Em seguida, adicione as 2 segmentos de linha adicionais para se juntar à nova posição da linha para os antigos pontos de conexão. Seu segundo exemplo mostra uma iteração deste algoritmo: se A é (0,0) e B é (5, 7), então você ter escolhido o segmento de 2ª linha (o vertical) ao acaso, escolheu o ponto final na (0,5 ) e um ponto médio em (5,5), e empurrou essa seção para a direita por 3 unidades, antes de juntar-lo de volta.

Answer 3

Aqui está uma idéia ---

Iniciar em um e fazer um movimento em uma direção aleatória - esquerda, para cima ou para baixo. Após cada jogada, rola um número aleatório para ver se você ligar. Vamos dizer que 75% do tempo que você continuar viajando na mesma direção, e 25% do tempo você vai virar. Quando você liga, sempre girar em uma direção que leva mais estreitos com B. Isso significa que, se você está se movendo para a esquerda ou direita, você vai ter que virar-se, e se você está se movendo para cima, fazer um / escolha esquerda para a direita com base em quão longe você está atualmente à direita ou à esquerda da meta. Além disso, se você bater uma das fronteiras mundiais, por sua vez!

Isso não deve ser muito difícil de código. Tenho a sensação de que você está apenas tentando tornar isso mais complicado do que precisa ser ...