Existe-t-il des algorithmes de recherche de chemin qui pourraient gérer différents types de mouvement?

Je développe un bot pour un simulateur de jeux de société BattleTech http://en.wikipedia.org/wiki/BattleTech , il est au tour par tour.

Le plateau est divisé en hexagones, chacun ayant un type de terrain et une élévation différents. Vous conduisez un robot qui se déplace sur eux, pour détruire d'autres robots.

Je ne connais que les algorithmes de guidage de Dijkstra et A *, mais le problème est qu'il existe 3 types de mouvements: marcher, courir et sauter plusieurs hexagones (chacun d'eux a ses propres règles). Marcher et courir sont presque les mêmes.

Le meilleur chemin pourrait être une combinaison ou chaque type de mouvement. Voici un exemple de carte http://megamek.info/sites/default/files/isometric_view.png

Connaissez-vous un bon algorithme pour cette recherche de chemin complexe ou un moyen de combiner les résultats A * pour chaque type de mouvement?

ai movement path-finding alexvisio
la source

Je pense que cela est souvent géré par une manipulation intelligente d'un chemin pondéré avec A * (le poids étant le coût de ce chemin / carré). Par exemple, si le saut est préférable, il obtient un poids plus faible (par exemple 5) que la marche (par exemple 10).

ashes999

En quoi les trois types de mouvement diffèrent-ils exactement? Peuvent-ils être combinés (marcher jusqu'à la tuile A, puis courir vers B et ensuite sauter vers C dans le même tour)? Si oui, quelles sont les règles qui empêchent le joueur de toujours utiliser la méthode la moins chère pour passer de la tuile A à la tuile B?

Philipp

@Philipp Oui, ils peuvent l'être, lorsque vous utilisez A *. Vous pouvez ajouter toutes les tuiles vers lesquelles vous pouvez vous déplacer avec chaque type de mouvement à la liste ouverte, puis en fonction du prix de chacune + une bonne heuristique, vous pouvez déterminer celle à laquelle continuer.

akaltar

@Philipp Non, vous ne pouvez utiliser qu'un seul type de mouvement à chaque tour.

alexvisio

Marcher: se déplacer dans les hexagones avec peu de différence d'altitude. Courir: pareil mais vous pouvez aller loin, même si vous générez de la chaleur et perdez de la précision de tir (ce n'est donc pas toujours le meilleur). Saut: vous pouvez sauter des obstacles (un mur ou une rivière) au lieu de les contourner en marchant.

alexvisio

Réponses:

Dijkstra et A * peuvent ajouter des coûts différents aux bords (= connexions) d'une tuile à l'autre. Ils permettent également de connecter deux nœuds (= tuiles) avec plus d'un bord, chacun avec un coût différent.

Le mode de saut alternatif signifierait qu'il existe un bord direct alternatif de chaque tuile à chaque tuile dans la distance de saut. Mais comme un robot peut marcher ou sauter dans un tour, le coût d'utilisation de cette arête serait les points de mouvement d'un tour entier, plus les points restants du tour en cours lorsqu'il y avait déjà un mouvement ce tour.

Selon votre description, la décision de marcher ou de courir ne fait pas beaucoup de différence en ce qui concerne le choix du chemin, mais cela semble plutôt être une décision stratégique à prendre. L'acteur peut certainement marcher quand la destination peut être atteinte dans le virage en cours sans recourir à la course. Mais sinon, il y a de nombreux facteurs à prendre en compte, comme:

niveau de chaleur actuel et probabilité de participer au combat avant de pouvoir se refroidir
difficulté de tous les coups qui doivent être tirés ce tour
l'importance stratégique d'atteindre la destination rapidement

Il n'y a pas de règle stricte pour prendre cette décision. Le mieux que vous puissiez faire est d'utiliser une approche heuristique. Attribuez des valeurs de points positives ou négatives à toutes les circonstances, additionnez-les et voyez si le résultat est positif ou négatif.

Il y a aussi un autre facteur dans la recherche de chemin que vous devez prendre en compte: dans certaines conditions, il peut être logique qu'un mécène évite de terminer son tour à certains endroits. Lorsque vous êtes dans une zone dangereuse, utiliser trois tours pour aller de A à B mais terminer chacun à l'abri peut être mieux que d'en utiliser seulement deux, mais être exposé à la fin de chacun. Ou peut être pas. Cela dépend des circonstances et des mécanismes de jeu exacts. Encore une fois, c'est une décision stratégique que vous devez prendre sur la base de l'heuristique. Vous pouvez le représenter en ajoutant un coût supplémentaire aux bords qui terminent le tour sur une tuile dangereuse pour décourager l'IA de faire ce mouvement.

Philipp
la source