tomettes trouver leurs voisins adjacents

Question

Je développe un jeu simple carte 2D en utilisant des cartes de tuiles hexagonales, j'ai lu plusieurs articles (y compris le gamedev ses, qui sont liés chaque fois qu'il ya une question sur les tuiles hexagonales) sur la façon de tirer hexagones sur l'écran et comment gérer le mouvement (même si une grande partie de ce que je l'avais déjà fait avant). Mon principal problème est de trouver les tuiles adjacentes en fonction d'un rayon donné.

Voilà comment fonctionne mon système de carte:

(0,0) (0,1) (0,2) (0,3) (0,4)
   (1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
   (3,0) (3,1) (3,2) (3,3) (3,4)

etc ...

Ce que je suis aux prises avec le fait que je ne peux pas simplement « select » les tuiles adjacentes en utilisant for(x-range;x+range;x++); for(y-range;y+range;y++); car il sélectionne les tuiles indésirables (dans l'exemple que j'ai donné, sélectionner le (1,1) tuile et donnant une gamme de 1 serait aussi me donner le (3,0) tuile (ceux que je réellement besoin d'être (0,1) (0,2) (1,0) (1,2) (2,1) (2,2)) , qui est un peu à côté de la tuile (à cause de la façon dont le tableau est structuré) mais ce n'est pas vraiment ce que je veux choisir. Je pourrais simplement la force brute, mais ce ne serait pas beau et couvrirait probablement pas tous les aspects de 'sélection chose rayon'.

point que quelqu'un peut me dans le sens ici?

Answer 1

Qu'est-ce qu'une grille hexagonale?

Ce que vous pouvez voir ci-dessus sont les deux grilles. Il est dans la façon dont vous numérotez vos tuiles et la façon dont vous comprenez ce qu'est une grille hexagonale est. La façon dont je vois, une grille hexagonale est rien de plus qu'un quelconque orthogonal déformé.

Les deux tuiles hexagonales je suis entouré d'un cercle en violet sont théoriquement toujours à côté de 0,0. Cependant, en raison de la déformation, nous sommes passés à travers pour obtenir la grille de tuiles hexagonale de celui orthogonale, les deux ne sont plus visuellement adjacents.

Deformation

Ce que nous devons comprendre est la déformation est arrivé dans une certaine direction, le long d'une ligne imaginaire [(-1,1) (1,-1)] dans mon exemple. Pour être plus précis, il est comme si la grille a été allongée le long de cette ligne, et squashed le long d'une perpendiculaire de la ligne à cela. Alors, naturellement, les deux tuiles sur cette ligne se sont dispersés et ne sont plus visuellement adjacentes. A l'inverse, les tuiles (1, 1) et (-1, -1) qui étaient en diagonale à (0, 0) sont maintenant particulièrement près de (0, 0), si proche en fait qu'ils sont maintenant visuellement adjacent à (0, 0). Mathématiquement cependant, ils sont encore et il aide les diagonales de les traiter de cette façon dans votre code.

Sélection

L'image que je montre illustre un rayon de 1. Pour un rayon de deux, vous remarquerez (2, -2) et (-2, 2) sont les tuiles qui ne devraient pas être inclus dans la sélection. Etc. Ainsi, pour toute sélection de rayon r , les points (r, -r) et (-r, r) ne doit pas être sélectionné. A part cela, votre algorithme de sélection devrait être la même que celle d'une grille carrée en mosaïque.

Assurez-vous que vous avez votre axe correctement configuré sur la grille hexagonale, et que vous numérotez vos tuiles en conséquence.

Mise en œuvre

Développons sur ce point pour un peu. Nous savons maintenant que le mouvement le long d'une direction dans les coûts de la grille nous 1. Et le mouvement le long de la étiré direction nous coûte 2. Voir (0, 0) à (-1, 1) par exemple.

Sachant cela, on peut calculer la distance la plus courte entre deux tuiles sur une telle grille, en décomposant la distance en deux composantes: un mouvement diagonale et un mouvement rectiligne le long d'un des axes. Par exemple, la distance entre (1, 1) et (-2, 5) sur une grille normale, nous avons:

Normal distance = (1, 1) - (-2, 5) = (3, -4)

Ce serait le vecteur de distance entre les deux tuiles ils étaient sur une grille carrée. Cependant, nous devons compenser la déformation de la grille de sorte que nous décomposons comme ceci:

(3, -4) = (3, -3) + (0, -1)

Comme vous pouvez le voir, nous avons décomposé le vecteur dans une diagonale d'un (3, -3) et une ligne droite le long d'un axe (0, -1).

On vérifie maintenant pour voir si l'une diagonale est le long de l'axe de déformation qui est un point quelconque où (n, -n) n est un nombre entier qui peut être positif ou négatif. (3, -3) ne satisfait en effet cette condition, donc ce vecteur diagonale est le long de la déformation. Cela signifie que la longueur (ou coût) de ce vecteur au lieu d'être 3, il sera double, qui est 6.

Donc, pour récapituler. La distance entre (1, 1) et (-2, 5) est la longueur de (3, -3) plus la longueur de (0, -1). C'est distance = 3 * 2 + 1 = 7.

Mise en œuvre en C ++

Voici la mise en œuvre en C ++ de l'algorithme que je l'ai expliqué ci-dessus:

int ComputeDistanceHexGrid(const Point & A, const Point & B)
{
  // compute distance as we would on a normal grid
  Point distance;
  distance.x = A.x - B.x;
  distance.y = A.y - B.y;

  // compensate for grid deformation
  // grid is stretched along (-n, n) line so points along that line have
  // a distance of 2 between them instead of 1

  // to calculate the shortest path, we decompose it into one diagonal movement(shortcut)
  // and one straight movement along an axis
  Point diagonalMovement;
  int lesserCoord = abs(distance.x) < abs(distance.y) ? abs(distance.x) : abs(distance.y);
  diagonalMovement.x = (distance.x < 0) ? -lesserCoord : lesserCoord; // keep the sign 
  diagonalMovement.y = (distance.y < 0) ? -lesserCoord : lesserCoord; // keep the sign

  Point straightMovement;

  // one of x or y should always be 0 because we are calculating a straight
  // line along one of the axis
  straightMovement.x = distance.x - diagonalMovement.x;
  straightMovement.y = distance.y - diagonalMovement.y;

  // calculate distance
  size_t straightDistance = abs(straightMovement.x) + abs(straightMovement.y);
  size_t diagonalDistance = abs(diagonalMovement.x);

  // if we are traveling diagonally along the stretch deformation we double
  // the diagonal distance
  if ( (diagonalMovement.x < 0 && diagonalMovement.y > 0) || 
       (diagonalMovement.x > 0 && diagonalMovement.y < 0) )
  {
    diagonalDistance *= 2;
  }

  return straightDistance + diagonalDistance;
}

, compte tenu de la fonction ci-dessus de ComputeDistanceHexGrid mis en œuvre, vous pouvez maintenant avoir un naïf, unoptimized implémentation d'un algorithme de sélection qui ne tiendra pas compte des tuiles plus loin que la plage de sélection spécifiée:

int _tmain(int argc, _TCHAR* argv[])
{
  // your radius selection now becomes your usual orthogonal algorithm
  // except you eliminate hex tiles too far away from your selection center
  // for(x-range;x+range;x++); for(y-range;y+range;y++);
  Point selectionCenter = {1, 1};
  int range = 1;

  for ( int x = selectionCenter.x - range;
            x <= selectionCenter.x + range;
            ++x )
  {
    for ( int y = selectionCenter.y - range;
              y <= selectionCenter.y + range;
              ++y )
    {
      Point p = {x, y};
      if ( ComputeDistanceHexGrid(selectionCenter, p) <= range )
        cout << "(" << x << ", " << y << ")" << endl;
      else
      {
        // do nothing, skip this tile since it is out of selection range
      }
    }
  }

    return 0;
}

Pour un poi de sélectionnt (1, 1) et une gamme de 1, le code ci-dessus affiche le résultat attendu:

(0, 0)
(0, 1)
(1, 0)
(1, 1)
(1, 2)
(2, 1)
(2, 2)

Optimisation possible

Pour optimiser cela, vous pouvez inclure la logique de savoir dans quelle mesure une tuile est du point de sélection (logique trouvée dans ComputeDistanceHexGrid) directement dans votre boucle de sélection, de sorte que vous pouvez parcourir la grille d'une manière qui évite de tuiles de gamme tout à fait.

Answer 2

méthode plus simple que je peux penser à ...

minX = x-range; maxX = x+range
select (minX,y) to (maxX, y), excluding (x,y) if that's what you want to do
for each i from 1 to range:
    if y+i is odd then maxX -= 1, otherwise minX += 1
    select (minX, y+i) to (maxX, y+i)
    select (minX, y-i) to (maxX, y-i)

Il peut être un peu hors; Je viens travaillé à travers dans ma tête. Mais, il est à tout le moins une idée de ce que vous devez faire.

En C'ish:

void select(int x, int y) { /* todo: implement this */ }

void selectRange(int x, int y, int range)
{
    int minX = x - range, maxX = x + range;
    for (int i = minX; i <= maxX; ++i)
        if (i != x) select(i, y);
    for (int yOff = 1; yOff <= range; ++yOff)
    {
        if (y+yOff % 2 == 1) --maxX; else ++minX;
        for (int i=minX; i<=maxX; ++i)
        {
            select(i, y+yOff);  select(i, y-yOff);
        }
    }  
}