piastrelle esagonali e trovare i loro vicini adiacenti

Question

sto sviluppando un semplice 2D gioco da tavolo con le mappe di piastrelle esagonali, ho letto diversi articoli (tra cui il gamedev propri, che sono collegati ogni volta che c'è una domanda su piastrelle esagonali) su come disegnare esagoni sullo schermo e come gestire il movimento (anche se gran parte di essa avevo già fatto prima). Il mio problema principale è trovare le tessere adiacenti sulla base di un determinato raggio.

Questo è come funziona il mio sistema:

(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)

ecc ...

Quello che sto lottando con è il fatto che non posso solo 'selezionare' le tessere adiacenti utilizzando for(x-range;x+range;x++); for(y-range;y+range;y++); perché seleziona le piastrelle indesiderate (nell'esempio ho dato, selezionando il 1,1) piastrella (e dando una serie di 1 sarebbe anche darmi il (3,0) di piastrelle (quelli che ho effettivamente bisogno di essere (0,1) (0,2) (1,0) (1,2) (2,1) (2,2)) , che è un pò adiacente alla tessera (a causa del modo in cui la matrice è strutturato), ma non è proprio quello che voglio per selezionare. potevo solo forza bruta, ma che non sarebbe bello e probabilmente non coprono tutti gli aspetti della 'selezionando il raggio cosa'.

Qualcuno può punto me nella giusta direzione qui?

Answer 1

Che cosa è una griglia esagonale?

quello che potete vedere sopra sono le due griglie. E 'tutto nel modo in cui il vostro numero di piastrelle e il modo di capire che cosa una griglia esagonale è. Il modo di vedere, una griglia esagonale è altro che un ortogonale deformata.

I due tessere esagonali che ho cerchiato in viola sono teoricamente ancora adiacenti 0,0. Tuttavia, a causa della deformazione che abbiamo passato avere la griglia esagonale piastrella da quella ortogonale, i due non sono più visivamente adiacente.

Deformazione

Quello che dobbiamo capire è la deformazione è accaduto in una certa direzione, lungo una linea immaginaria [(-1,1) (1,-1)] nel mio esempio. Per essere più precisi, è come se la griglia è stata allungata lungo quella linea, e schiacciata lungo una linea perpendicolare a quella. Così, naturalmente, le due tessere su quella linea ha sparsi e non sono più visivamente adiacente. Viceversa, il piastrelle (1, 1) e (-1, -1) che erano diagonale (0, 0) sono ora insolitamente vicino a (0, 0), così vicino nel fatto che ora sono visivamente adiacente per (0, 0). Matematicamente tuttavia, sono ancora diagonali e aiuta a trattare in quel modo nel codice.

Selezione

L'immagine mostro illustra un raggio di 1. Per un raggio di due, si noterà (2, -2) e (-2, 2) sono le piastrelle che non dovrebbero essere inclusi nella selezione. E così via. Così, per qualsiasi selezione di raggio r , i punti (r, -r) e (-r, r) non dovrebbe essere selezionato. Oltre a questo, il vostro algoritmo di selezione dovrebbe essere la stessa di una griglia quadrata con piastrelle.

Basta fare in modo che avete il vostro asse impostato correttamente sulla griglia esagonale, e che si sta numerazione vostro piastrelle di conseguenza.

Attuazione

Diamo espandere su questo per un po '. Ora sappiamo che il movimento lungo una qualsiasi direzione nei costi di rete ci 1. E il movimento lungo la allungata direzione ci costa 2. Vedere (0, 0) per (-1, 1) per esempio.

Sapendo questo, si può calcolare la distanza più breve tra due piastrelle su una griglia, scomponendo la distanza in due componenti: un movimento diagonale ed un movimento rettilineo lungo uno degli assi. Ad esempio, per la distanza tra (1, 1) e (-2, 5) su una griglia normale abbiamo:

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

Questo sarebbe il vettore distanza tra le due tessere erano su una griglia quadrata. Tuttavia occorre compensare la deformazione griglia in modo decomponiamo così:

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

Come si può vedere, abbiamo scomposto il vettore in una diagonale uno (3, -3) e una retta lungo un (0, -1) asse.

Ora controlliamo per vedere se quella diagonale è lungo l'asse deformazione che è un qualsiasi (n, -n) punto n è un numero intero che può essere positivo o negativo. (3, -3) effettivamente soddisfare tale condizione, quindi questo vettore diagonale è lungo la deformazione. Ciò significa che la lunghezza (o costo) di questo vettore invece di essere 3, sarà doppio, pari 6.

Quindi, per ricapitolare. La distanza tra (1, 1) e (-2, 5) è la lunghezza (3, -3) più la lunghezza di (0, -1). Questo è distance = 3 * 2 + 1 = 7.

Implementazione in C ++

Di seguito è riportato l'implementazione in C ++ dell'algoritmo ho spiegato sopra:

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;
}

Ora, per quanto precede funzione di ComputeDistanceHexGrid implementata, ora è possibile avere un ingenuo, non ottimizzata implementazione di un algoritmo di selezione che ignorerà le tessere oltre l'intervallo di selezione specificata:

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;
}

Per un POI selezionent (1, 1) e una serie di 1, il codice sopra visualizzerà il risultato previsto:

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

Possibile ottimizzazione

Per ottimizzare questo, è possibile includere la logica di sapere fino a che punto una piastrella è dal punto di selezione (logica trovata in ComputeDistanceHexGrid) direttamente nella vostra selezione ciclo, in modo da poter scorrere la griglia in modo da evitare di piastrelle gamma del tutto.

Answer 2

Il metodo più semplice che posso pensare ...

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)

Può essere un po 'fuori; ho appena lavorato attraverso nella mia testa. Ma per lo meno, si tratta di un'idea di ciò che è necessario fare.

In 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);
        }
    }  
}