15

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

これが私のマップシステムの仕組みです。

(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,2）（1,0）（1,2）（2,1）（2,2））です。タイルに隣接していますが（配列の構造上）、実際には選択したいものではありません。ブルートフォース攻撃を行うことはできますが、それは美しくはなく、半径の選択のすべての側面をカバーしているとは限りません。 '。

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

4

2 に答える 2

16

六角形および直交グリッド

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

上に表示されているのは2つのグリッドです。それはすべて、タイルに番号を付ける方法と、六角形のグリッドが何であるかを理解する方法にあります。私の見方では、六角形のグリッドは変形した直交グリッドにすぎません。

私が紫色で囲んだ2つの六角形のタイルは、理論的にはまだに隣接してい0,0ます。ただし、直交するグリッドから16タイルグリッドを取得するために行った変形により、2つは視覚的に隣接しなくなりました。

変形

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

選択

私が示す画像は、半径1を示しています。半径2の場合、選択に含めるべきではないタイルに(2, -2)気付くでしょう。(-2, 2)等々。したがって、半径rを選択する場合は、ポイント(r, -r)と(-r, r)を選択しないでください。それ以外は、選択アルゴリズムは正方形のタイルグリッドと同じである必要があります。

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

実装

これについて少し詳しく見ていきましょう。グリッド内の任意の方向に沿った移動には1.コストがかかり、引き伸ばされた方向に沿った移動には2.コストがかかることがわかりました。たとえば、を参照(0, 0)してください。(-1, 1)

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

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

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

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

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

ここで、対角線が変形軸に沿っているかどうかを確認します。これは、が正または負の整数である (n, -n)任意の点です。は確かにその条件を満たすので、この対角ベクトルは変形に沿っています。これは、このベクトルの長さ（またはコスト）が、ではなく2倍になることを意味します。つまり、です。n(3, -3)36

要約すると。(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）を選択ループに直接含めることができるため、範囲外のタイルを完全に回避する方法でグリッドを反復できます。

于 2013-03-20T13:07:46.897 に答える
7

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

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 */
    /* should ignore coordinates that are out of bounds */
}

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);
        }
    }  
}
于 2011-01-03T14:36:00.483 に答える