Como posso ajustar esse algoritmo de busca de caminhos A * para lidar com diferentes valores de movimento do terreno?

8

Estou criando um jogo de ação 2D baseado em mapas com design de interação semelhante ao Diablo II. Em outras palavras, o jogador clica em torno de um mapa para movê-lo. Acabei de terminar o movimento do jogador e estou indo para o caminho.

No jogo, os inimigos devem cobrar o personagem do jogador. Existem também cinco tipos diferentes de terreno que oferecem bônus de movimento diferentes. Eu quero que a IA aproveite esses bônus de terreno enquanto eles tentam alcançar o jogador.

Disseram-me para verificar o algoritmo de pesquisa A * (http://en.wikipedia.org/wiki/A*_search_algorithm). Estou fazendo este jogo em HTML5 e JavaScript e encontrei uma versão em JavaScript: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript Estou tentando descobrir como ajustá-lo Apesar.

Abaixo estão minhas idéias sobre o que preciso mudar. Com o que mais eu preciso me preocupar?

  • Ao criar um gráfico, precisarei inicializar a matriz 2D que passo adiante com uma travessia de um mapa que corresponde aos diferentes tipos de terreno.
  • in graph.js: a definição "GraphNodeType" precisa ser modificada para lidar com os 5 tipos de terreno. Não haverá paredes.
  • em astar.js: O g e h pontuação terá de ser modificado. Como devo fazer isso?
  • em astar.js: isWall () provavelmente deve ser removido. Meu jogo não tem paredes.
  • no astar.js: Não tenho certeza do que é isso. Eu acho que indica um nó que não é válido para ser processado. Quando isso aconteceria?
  • Em um nível alto, como altero esse algoritmo de "oh, existe uma parede aí?" para "esse terreno me levará ao jogador mais rápido que o terreno ao meu redor?"

Por causa do tempo, também estou debatendo a reutilização do meu algoritmo de Bresenham para os inimigos. Infelizmente, os diferentes bônus de movimento do terreno não serão usados ​​pela IA, o que fará com que o jogo seja péssimo. : / Eu realmente gostaria de ter isso para o protótipo, mas não sou desenvolvedor de profissão nem cientista da computação. : D

Se você souber de algum código que faça o que estou procurando, compartilhe!

Dicas de verificação de sanidade para isso também são apreciadas.

javascript ai html5 user422318
fonte
Ei, autor da biblioteca aqui. Você está usando a versão mais recente do github? github.com/bgrins/javascript-astar/blob/master/astar.js . É muito mais rápido que a antiga implementação baseada em lista.
18712 Brian Grinstead

Respostas:

7

Você precisa prestar atenção a uma linha muito específica no algoritmo:

// g score is the shortest distance from start to current node, we need to check if
//   the path we have arrived at this neighbor is the shortest one we have seen yet
var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor

Esse é o custo desse nó específico. Você gostaria de modificá-lo para algo como

var gScore = currentNode.g + currentNode.cost

Isso fará com que o caminho evite terrenos caros e prefira terrenos baratos; é sua responsabilidade fazer com que 'currentNode.cost' retorne algo apropriado para o seu terreno. É que nem todo terreno tem um custo de 1 que você está prestando atenção ... alguns terrenos são mais baratos que outros. Há outras considerações, mas esse ponto específico no código deve ser o foco de sua atenção.

Myrddin Emrys
fonte
Obrigado por isso. Modifiquei meu código para que cada nó pesquise o pixel em suas coordenadas e o armazene como um custo. Infelizmente, fiz um caminho de teste entre dois pontos na minha grade de 800x500 e meu navegador travou. : / Existem vários fatores nisso: o código astar pode precisar de otimização; meu tamanho de tela é enorme; talvez minha inicialização do gráfico esteja incorreta; e talvez as cores nos avatares dos personagens estejam bagunçando as coisas. O que devo fazer? :(
user422318
Quando você diz "armazena o pixel", você quer dizer que ele armazena o custo do terreno, sim? Como é improvável que algum valor de RGB corresponda ao custo real desse terreno. Provavelmente você deve armazenar algo entre 1 e 10 (1 sendo uma estrada, 10 sendo um pântano), embora os valores exatos, é claro, dependam do seu jogo preciso.
Myrddin Emrys
11
Ei, autor da biblioteca aqui. Você está usando a versão mais recente do github? github.com/bgrins/javascript-astar/blob/master/astar.js . É muito mais rápido que a antiga implementação baseada em lista.
18712 Brian Grinstead
2
@ Brian Você deve colocar esse comentário na pergunta, e não na minha resposta, para que a pessoa que realmente usa a biblioteca receba a notificação no e-mail e não em mim.
Myrddin Emrys
2

Esse é exatamente o tipo de coisa para a qual A * é. Tudo o que você precisa fazer é atribuir os vértices entre os custos dos nós com base nos tipos de terreno. (Parece que seus exemplos usam um gráfico em que todos os vértices têm um custo de 1.)

caos
fonte
0

Esta implementação é um pouco específica para o ligar / desligar no momento. Como diz Myrddin Emrys, você precisará modificar a pontuação g com base no custo (em vez de apenas 1). Houve uma discussão sobre isso aqui: https://github.com/bgrins/javascript-astar/issues/3 .

Eu adoraria ter essa solução transportada de volta para a biblioteca principal, se você a trabalhar!

Brian Grinstead
fonte