Obtenez un anneau de tuiles dans la grille hexagonale

Grâce à ce post: tuiles hexagonales et trouver leurs voisins adjacents , je suis en mesure de collecter des tuiles adjacentes à une tuile donnée. Mais je suis plutôt coincé sur un algorithme qui ne me donne qu'un "anneau" de tuiles spécifié par un décalage. L'algorithme donné dans ce post Stack Overflow ne se soucie pas exactement de l'ordre dans lequel il collecte les tuiles.

Je sais qu'à chaque décalage 6 tuiles sont ajoutées.

• Le décalage 1 vous donne 6 tuiles (les premières tuiles adjacentes).
• Le décalage 2 vous donne 12.
• Le décalage 3 vous donne 18, etc.

Il y a une croissance constante de 6 à chaque décalage. Je suppose donc qu'il devrait y avoir une règle qui s'adapte à ces décalages. Je ne peux pas vraiment comprendre celui-ci. N'importe qui?

Un anneau hexagonal avec le rayon de N se compose de 6 lignes droites, chacune avec une longueur N - voir mon exemple extrêmement grossier ci-dessous :) Pour N = 2:

Les flèches couvrent chacune 2 hexagones.

Je suppose que vous avez certaines fonctions qui vous donnent la tuile voisine dans une direction spécifique, comme le nord (), le sud-est () etc. Donc, votre algorithme, en pseudocode, devrait être quelque chose comme ceci:

var point = startingPoint.north(N)
for i = 0..N-1:
    result.add(point)
    point = point.southeast(1);
for i = 0..N-1:
    result.add(point)
    point = point.south(1);
for i = 0..N-1:
    result.add(point)
    point = point.southwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.northwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.north(1);
for i = 0..N-1:
    result.add(point)
    point = point.northeast(1);

Notez que cela devrait également fonctionner pour les cas de bord N = 1, renvoyant 6 tuiles et N = 0 renvoyant un ensemble vide.

Je sais que le code n'est pas parfait :) Il y a une redondance ici. Dans mes projets utilisant des cartes régulièrement carrelées (hexagonales ou autres), j'ai généralement une énumération "Direction", ce qui me permet de le faire plus facilement:

var point = startingPoint.inDir(N, Direction.North)
var dir = Direction.SouthEast.
for d = 0..Direction.count():
    for i = 0..N-1:
        result.add(point)
        point = point.inDir(1, dir);
    dir = nextDirection(dir);

J'ai trouvé cet article comme une très bonne référence pour les algorithmes de grille hexagonale, et sa section sur "Distances" fournit une méthode pour déterminer le nombre d'étapes entre deux tuiles. Si vous convertissez vos coordonnées axiales (xy) en coordonnées de cube (xyz), la distance est toujours égale au plus grand des décalages de coordonnées entre les deux tuiles, ou max (| dx |, | dy |, | dz |).

Une recherche exhaustive de la grille entière pour les tuiles à la distance souhaitée est $O(n^2)$ avec les dimensions de la grille, mais c'est une implémentation simple qui fonctionne bien pour les petites grilles.