六角形のタイルと隣接する隣人を見つける

Question

私は六角形のタイルマップを使用してシンプルな2Dボードゲームを開発しています。画面に六角形を描く方法と管理方法について、いくつかの記事（六角形のタイルに質問があるときにリンクされているGamedev Oneを含む）をいくつか読みました動き（私が以前にすでにやったことがありますが）。私の主な問題は、特定の半径に基づいて隣接するタイルを見つけることです。

これが私のマップシステムの動作です。

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

等...

私が苦労しているのは、使用することで隣接するタイルを「選択」することができないという事実です for(x-range;x+range;x++); for(y-range;y+range;y++); それは不要なタイルを選択しているため（私が与えた例では、（1,1）タイルを選択し、1の範囲を与えると、（3,0）タイル（私が実際に必要なもの（0,1）（）（（0,1））（ 0,2）（1,0）（1,2）（2,1）（2,2））、これはタイルに隣接しています（配列の構造のため）が、実際には私が望むものではありません選択する。私はそれを強制的に強制的にすることができたが、それは美しくなく、おそらく「半径のものを選択する」のあらゆる側面をカバーするものではないだろう。

誰かがここで私を正しい方向に向けることができますか？

Answer 1

六角形のグリッドとは何ですか？

上で見ることができるのは、2つのグリッドです。それはすべて、タイルを数え、六角形のグリッドとは何かを理解する方法です。私がそれを見る方法では、六角形のグリッドは変形した直交のグリッドにすぎません。

私が紫色で旋回した2つのヘックスタイルは、理論的にはまだ隣接しています 0,0. 。ただし、直交のグリッドからヘックスタイルグリッドを取得するために行った変形のために、2つはもはやありません 視覚的に 隣接。

変形

私たちが理解する必要があるのは、変形が特定の方向に起こったことです。 [(-1,1) (1,-1)] 私の例の想像上の線。より正確には、まるでグリッドがその線に沿って伸びているかのように、そして 押しつぶされた それに垂直な線に沿って。そのため、当然、そのラインの2つのタイルが広がり、視覚的に隣接しなくなりました。逆に、タイル (1, 1) と (-1, -1) 対角線でした (0, 0) 今では異常に近づいています (0, 0), 、実際に彼らが今いるということです 視覚的に隣接しています に (0, 0). 。しかし、数学的には、それらはまだ対角線であり、コードでそれらをそのように扱うのに役立ちます。

選択

私が示す画像は、半径1の半径を示しています。 (2, -2) と (-2, 2) 選択に含めるべきではないタイルです。等々。したがって、半径の選択のために r, 、ポイント (r, -r) と (-r, r) 選択しないでください。それ以外に、選択アルゴリズムは四角いタイル張りのグリッドと同じでなければなりません。

六角形のグリッドに軸を適切にセットアップし、それに応じてタイルに番号を付けていることを確認してください。

実装

これを少し拡張しましょう。グリッド内のあらゆる方向に沿った動きが私たちに費用がかかり、沿った動きがコストがかかることがわかりました。 伸びた 方向に費用がかかります。2。参照してください (0, 0) に (-1, 1) 例えば。

これを知って、距離を2つのコンポーネントに分解することにより、このようなグリッド上の任意の2つのタイル間の最短距離を計算できます。軸の1つに沿った斜めの動きとまっすぐな動きです。たとえば、間の距離の場合 (1, 1) と (-2, 5) 通常のグリッドには：

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

それは、2つのタイル間の距離ベクトルになります。ただし、グリッドの変形を補う必要があるので、次のように分解します。

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

ご覧のとおり、ベクトルを1つの対角線に分解しました (3, -3) 軸に沿ってまっすぐに (0, -1).

次に、斜めのものが変形軸に沿っているかどうかを確認します。 (n, -n) どこ n 正または負の整数です。(3, -3) 確かにその状態を満たしているので、この斜めのベクトルは変形に沿っています。これは、このベクトルの長さ（またはコスト）が 3, 、それは2倍になります 6.

要約する。間の距離 (1, 1) と (-2, 5) の長さです (3, -3) プラスの長さ (0, -1). 。あれは distance = 3 * 2 + 1 = 7.

C ++での実装

以下は、上記で説明したアルゴリズムのC ++の実装です。

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

ここで、上記が実装されていることが与えられます ComputeDistanceHexGrid 関数、指定された選択範囲よりもさらにタイルを無視する選択アルゴリズムの素朴で最適化されていない実装を持つことができます。

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

選択点について (1, 1) そしての範囲 1, 、上記のコードには、予想される結果が表示されます。

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

可能な最適化

これを最適化するには、タイルが選択点からどれだけ離れているかを知るロジックを含めることができます（で見つかったロジック ComputeDistanceHexGrid）選択ループに直接入ると、範囲外のタイルを完全に回避する方法でグリッドを反復させることができます。

Answer 2

私が考えることができる最も単純な方法...

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)

少し離れているかもしれません。私はちょうど私の頭の中でそれを通り抜けました。しかし、少なくとも、それはあなたが何をする必要があるかのアイデアです。

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