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?
fonte
Respostas:
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ã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.
fonte