Recherche du chemin le plus court sur une grille hexagonale

J'écris un jeu au tour par tour qui a quelques éléments de simulation. Une tâche à laquelle je raccroche actuellement est la recherche de chemin. Ce que je veux faire, c'est déplacer chaque tour un aventurier IA d'une tuile plus près de sa cible en utilisant son x, y actuel et sa cible x, y.

En essayant de comprendre cela moi-même, je peux déterminer 4 directions sans problème en utilisant

dx = currentX - targetY
dy = currentY - targetY

mais je ne sais pas comment déterminer laquelle des 6 directions est en fait le "meilleur" ou le "plus court" itinéraire.

Par exemple, dans la configuration actuelle, j'utilise Est, Ouest, NE, NW, SE, SW, mais pour arriver à la tuile NE, je me déplace vers l'Est puis sur NW au lieu de simplement déplacer NW.

J'espère que tout cela n'a pas été décousu. Même juste un lien ou deux pour me lancer serait bien. La plupart des informations que j'ai trouvées concernent le dessin des grilles et le développement du système de coordonnées étrange nécessaire.

Quelques réponses!

Le système de coordonnées que j'ai vu le plus souvent pour la traversée hexadécimale est celui où le joueur peut se déplacer dans toutes les directions normales NSEW, ainsi que NW et SE. Il vous suffit ensuite de rendre chaque ligne décalée d'un demi-carré. À titre d'exemple, l'emplacement (2,7) est considéré comme adjacent à (1,7), (3,7), (2,6), (2,8) et les autres: (1,6) et (3,8). Pendant ce temps, si nous supposons que (2,7) est rendu au centre de l'écran, (2,6) sera rendu de haut en bas, (2,8) sera rendu de haut en bas -la gauche, (1,7) et (3,7) le placera respectivement à gauche et à droite, et (1,6) et (3,8) se placeront respectivement en haut à gauche et en bas à droite.

Un diagramme de ce que je veux dire:

Si vous le faites de cette façon, trouver le chemin direct le plus court n'est pas difficile - parcourez la distance maximale NW / SE que vous pouvez sans dépasser votre cible le long d'un axe cardinal, puis parcourez directement le long de cet axe jusqu'à la cible.

Mais bien sûr, cela vous fera heureusement traverser des montagnes ou d'autres terrains impraticables. Pour répondre à une question que vous n'avez pas encore posée: l' algorithme de recherche A * est une approche courante et raisonnablement bonne de la recherche de chemin. Il gérera non seulement des dispositions étranges sans grille, mais traitera avec plaisir les obstacles et même les sols obstrués / lents.

Je viens de poster une bibliothèque d'utilitaires hex-grid sur CodePlex.com ici: https://hexgridutilities.codeplex.com/ La bibliothèque comprend la recherche de chemin (en utilisant A- * a la Eric Lippert) et inclut des utilitaires pour la conversion automatisée entre coordonnées irrégulières (appelées utilisateur) et coordonnées non dentelées (appelées canoniques). L'algorithme de recherche de chemin permet au coût de l'étape pour chaque nœud de varier à la fois avec l'hex d'entrée et le côté hex parcouru (bien que l'exemple fourni soit plus simple). En outre, un champ de vision élevé utilisant la projection d'ombres est fourni, [modifier: mots supprimés].

Voici un exemple de code qui se convertit facilement entre trois systèmes de coordonnées à grille hexadécimale:

static readonly IntMatrix2D MatrixUserToCanon = new IntMatrix2D(2,1, 0,2, 0,0, 2);
IntVector2D VectorCanon {
  get { return !isCanonNull ? vectorCanon : VectorUser * MatrixUserToCanon / 2; }
  set { vectorCanon = value;  isUserNull = isCustomNull = true; }
} IntVector2D vectorCanon;
bool isCanonNull;

static readonly IntMatrix2D MatrixCanonToUser  = new IntMatrix2D(2,-1, 0,2, 0,1, 2);    
IntVector2D VectorUser {
  get { return !isUserNull  ? vectorUser 
             : !isCanonNull ? VectorCanon  * MatrixCanonToUser / 2
                            : VectorCustom * MatrixCustomToUser / 2; }
  set { vectorUser  = value;  isCustomNull = isCanonNull = true; }
} IntVector2D vectorUser;
bool isUserNull;

static IntMatrix2D MatrixCustomToUser = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
static IntMatrix2D MatrixUserToCustom = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
IntVector2D VectorCustom {
  get { return !isCustomNull ? vectorCustom : VectorUser * MatrixUserToCustom / 2; }
  set { vectorCustom  = value;  isCanonNull = isUserNull = true; }
} IntVector2D vectorCustom;
bool isCustomNull;

IntMatrix2D et IntVector2D sont des implémentations entières [modifier: homogènes] du vecteur graphique et de la matrice affine2D. La division finale par 2 sur les applications vectorielles consiste à re-normaliser les vecteurs; cela pourrait être enterré dans l'implémentation IntMatrix2D, mais alors la raison du 7ème argument aux constructeurs IntMatrix2D est moins évidente. Notez la mise en cache et l'évaluation paresseuse combinées des formulations non actuelles.

Ces matrices sont pour le cas:

• Grain hexagonal vertical;
• Origine en haut à gauche pour les coordonnées canoniques et utilisateur, en bas à gauche pour les coordonnées personnalisées;
• Axe Y verticalement vers le bas;
• Axe X rectangulaire horizontalement à travers; et
• Axe X canonique au nord-est (c'est-à-dire vers le haut et vers la droite, à 120 degrés CCW de l'axe Y).

La bibliothèque de codes mentionnée ci-dessus fournit un mécanisme tout aussi élégant pour la sélection d'hex (c.-à-d. Identifier l'hex sélectionné avec un clic de souris).

En coordonnées canoniques, les 6 vecteurs directeurs cardinaux sont (1,0), (0,1), (1,1) et leurs inverses pour tous les hexagones, sans l'assymétrie des coordonnées déchiquetées.

C'est un problème résolu, avec beaucoup de littérature pour le sauvegarder. La meilleure ressource que je connaisse est sur Red Blob Games: https://www.redblobgames.com/grids/hexagons/ .

En bref, la raison la plus probable est que vous avez commencé avec le mauvais système de coordonnées. L'utilisation d'un système de coordonnées Cube implémentant l'algorithme A * est assez simple. Voir la démo en direct sur le lien ci-dessus.

Si vous voulez vraiment utiliser un autre système, convertissez-le vers et depuis quand vous en avez besoin.