Existem algoritmos de busca de caminhos que lidariam com diferentes tipos de movimento?

12

Estou desenvolvendo um bot para um simulador de jogo de tabuleiro BattleTech http://en.wikipedia.org/wiki/BattleTech , baseado em turnos.

O tabuleiro é dividido em hexágonos, cada um com um tipo e elevação de terreno diferentes. Você dirige um robô que se move sobre eles, para destruir outros robôs.

Conheço apenas os algoritmos de busca de caminhos Dijkstra e A *, mas o problema é que existem 3 tipos de movimentos: andar, correr e pular vários hexágonos (cada um deles tem suas próprias regras). Caminhar e correr são quase os mesmos.

O melhor caminho pode ser uma combinação ou cada tipo de movimento. Aqui está um exemplo de mapa http://megamek.info/sites/default/files/isometric_view.png

Você conhece um bom algoritmo para essa busca complexa de caminhos ou uma maneira de combinar resultados A * para cada tipo de movimento?

alexvisio
fonte
Eu acho que isso geralmente é tratado por alguma manipulação inteligente de um caminho ponderado com A * (o peso é o custo desse caminho / quadrado). Por exemplo, se é preferível pular, o peso é menor (por exemplo, 5) do que caminhar (por exemplo, 10).
precisa saber é o seguinte
Como exatamente os três tipos de movimento diferem? Eles podem ser combinados (caminhe para o ladrilho A, depois corra para B e depois pule para C no mesmo turno)? Quando sim, quais são as regras que impedem o jogador de se formar sempre usando o método mais barato para passar do bloco A ao bloco B?
26513 Philipp
@ Philipp Sim, podem ser, ao usar A *. Você pode adicionar todos os blocos para os quais pode mover-se com todos os tipos de movimento à lista aberta e, com base no preço de cada um + uma boa heurística, pode determinar qual deles progredir mais adiante.
Akaltar
@ Philipp Não, você pode usar apenas um tipo de movimento a cada turno.
alexvisio
Andar: percorrer os hexágonos com pouca diferença de altitude. Execute: o mesmo, mas você pode ir longe, embora gere calor e perca a precisão do disparo (por isso nem sempre é o melhor). Pular: você pode pular obstáculos (uma parede ou rio) em vez de caminhar ao redor deles.
alexvisio

Respostas:

10

Dijkstra e A * podem adicionar custos diferentes às arestas (= conexões) de um bloco para outro. Eles também permitem conectar dois nós (= blocos) com mais de uma aresta, cada um com um custo diferente.

O modo alternativo de salto significaria que existe uma aresta direta alternativa de cada bloco para cada bloco na distância do salto. Mas como um mecânico pode andar ou pular em um turno, o custo para usar essa aresta seria os pontos de movimento de um turno inteiro, mais os pontos restantes do turno atual quando já havia um movimento nesse turno.

De acordo com sua descrição, a decisão de caminhar versus correr não faz muita diferença em relação à escolha do caminho, mas parece ser uma decisão estratégica a ser tomada. O ator definitivamente pode andar quando o destino pode ser alcançado na curva atual sem recorrer à corrida. Mas, caso contrário, existem muitos fatores a serem considerados, como:

  • nível de calor atual e probabilidade de estar envolvido em combate antes de ser capaz de esfriar
  • dificuldade de qualquer tiro que precise ser disparado nesta rodada
  • quão estrategicamente importante é chegar ao destino rapidamente

Não existe uma regra rígida para tomar essa decisão. O melhor que você pode fazer é usar uma abordagem heurística. Atribua valores de pontos positivos ou negativos a todas as circunstâncias, some-os e veja se o resultado é positivo ou negativo.

Há também outro fator em encontrar o caminho: em algumas condições, pode fazer sentido para um mecânico evitar terminar sua vez em determinados locais. Quando estiver em uma área de perigo, usar três turnos para ir de A a B, mas terminar cada um na cobertura, pode ser melhor do que usar apenas dois, mas ficar exposto no final de cada um. Ou talvez não. Depende das circunstâncias e da mecânica exata do jogo. Esta, novamente, é uma decisão estratégica que você deve tomar com base em heurísticas. Você pode representar isso adicionando um custo adicional às arestas que encerram o turno em um bloco perigoso para desencorajar a IA de fazer essa jogada.

Philipp
fonte