Recherche du chemin le plus court sur une grille hexagonale

14

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.

Timothy Mayes
la source
5
Un * vous donne le chemin le plus court quelle que soit la forme de votre graphique (grille, hex, forme libre ..)
Jari Komppa

Réponses:

21

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:

entrez la description de l'image ici

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.

ZorbaTHut
la source
Merci pour le lien vers l'algorithme de recherche A *. La seule façon dont j'imagine pouvoir traverser nsew et nw / se est un hex incliné. Ce qui est bizarre dans ma tête. Pouvez-vous me lier à un exemple de cela?
Timothy Mayes,
4
Je dis que votre image rendue n'a pas à ressembler beaucoup à la structure interne. Je suggère que vous utilisez en interne NSEW et NW / SE, mais vous l'affichez à l'utilisateur comme s'il s'agissait d'une grille. Joindre un schéma explicatif à la réponse originale :)
ZorbaTHut
2
Représentation intéressante pour une grille hexagonale. Je crée généralement un motif irrégulier, donc l'adjacence est différente pour les lignes paires et impaires. Cela introduit une complexité minimale supplémentaire dans la recherche de chemin, mais utilise un tableau bidimensionnel plus efficacement (en supposant que toute la zone de jeu est un rectangle.
Panda Pyjama
2
@PandaPajama: jagged fonctionne mieux pour stocker efficacement des cartes rectangulaires; vous pouvez faire fonctionner les coordonnées non dentelées avec cette astuce
amitp
2
@PandaPajama, il y a une autre astuce intéressante que vous pouvez utiliser - vous pouvez utiliser la représentation non dentelée pour les coordonnées, puis abstraire le support pour votre stockage de données derrière quelque chose qui utilise la méthode "dentelée". J'ai trouvé que le système de coordonnées de non-dentelé est beaucoup plus facile à gérer, mais bien sûr, une fois qu'il est abstrait, le backend peut faire tout ce qu'il veut pour rendre les choses efficaces :)
ZorbaTHut
5

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.

Pieter Geerkens
la source
Hou la la! Un vote négatif pour publier une bibliothèque de code de travail, avec des exemples et de la documentation, qui répond à la question / problème posé par le PO.
Pieter Geerkens
5
Bien que je n'étais pas le downvoter (et l'étiquette suggère généralement de laisser un commentaire expliquant un downvote), je soupçonne que le downvote était parce que (a) le post se détache de la publicité, et (b) mettre la majeure partie d'une réponse de l'autre côté d'un lien est généralement mal vu parce que les liens ont tendance à pourrir et les sites SE essaient d'être autonomes. Les informations fournies ici sont intéressantes, mais elles ne répondent pas à la question de l'utilisateur , et les seules informations pouvant répondre à la question se trouvent de l'autre côté du lien.
Steven Stadnicki
Bons points; Merci. J'ai développé le post avec des extraits qui abordent la question de savoir comment maintenir efficacement les coordonnées de la grille hexadécimale. La bibliothèque de codes publiée est un logiciel gratuit
Pieter Geerkens
Oups! La division par 2 ne fonctionne que pour les entiers positifs. (Merci encore, K&R.) Elle devrait être remplacée par un appel à la méthode Normalize () dans IntVector2D:
Pieter Geerkens
public IntVector2D Normalize() { if (Z==1) return this; else { var x = (X >= 0) ? X : X - Z; var y = (Y >= 0) ? Y : Y - Z; return new IntVector2D(x/Z, y/Z); } }
Pieter Geerkens
0

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.

david.pfx
la source