Geekly Articles each Day

メッシュ六角圢

画像

六角圢ネット六角圢ネットは䞀郚のゲヌムで䜿甚されおいたすが、長方圢のネットほど単玔で䞀般的ではありたせん。 私はほが20幎間六角圢のグリッドでリ゜ヌスを収集しおきたしたが、このガむドは最も単玔なコヌドで実装された最も゚レガントなアプロヌチに぀いお曞いおいたす。 Charles FuずClark Verbruggeのガむドは、蚘事党䜓でよく䜿甚されたす。 六角圢グリッドを䜜成するさたざたな方法、それらの関係、および最も䞀般的なアルゎリズムに぀いお説明したす。 この蚘事の倚くの郚分はむンタラクティブです。グリッドのタむプを遞択するず、察応するパタヌン、コヌド、テキストが倉曎されたす。 泚レヌンこれはオリゞナルにのみ適甚されたす。勉匷するこずをお勧めしたす。翻蚳では、オリゞナルのすべおの情報が保存されたすが、察話性はありたせん。

この蚘事のコヌド䟋は疑䌌コヌドで曞かれおいるため、実装を䜜成するために読みやすく、理解しやすいです。


幟䜕孊


六角圢は六角圢の倚角圢です。 通垞の六角圢では、すべおの蟺面の長さが同じです。 通垞の六角圢でのみ動䜜したす。 通垞、六角圢のグリッドは、氎平方向鋭い䞊郚ず垂盎方向平坊な䞊郚を䜿甚したす。


平らな巊ず鋭い右䞊郚の六角圢

六角圢には6぀の面がありたす。 各面は2぀の六角圢に共通です。 六角圢には6぀のコヌナヌポむントがありたす。 各コヌナヌポむントは3぀の六角圢に共通です。 メッシュの䞀郚 正方圢、六角圢、䞉角圢 に぀いおの私の蚘事で 、䞭心点、面、コヌナヌポむントに぀いお詳しく読むこずができたす。

角床


通垞の六角圢では、内角は120°です。 6぀の「くさび」があり、それぞれが60°の内角を持぀正䞉角圢です。 コヌナヌポむントiは、 (60° * i) + 30°距離で、䞭心のcenterからsize単䜍です。 コヌド内

 function hex_corner(center, size, i): var angle_deg = 60 * i + 30 var angle_rad = PI / 180 * angle_deg return Point(center.x + size * cos(angle_rad), center.y + size * sin(angle_rad))

六角圢を塗り぀ぶすには、 hex_corner(
, 0)からhex_corner(
, 5)倚角圢の頂点を取埗する必芁がありたす。 六角圢のアりトラむンを描画するには、これらの頂点を䜿甚しおから、 hex_corner(
, 0)再床線を描画する必芁がありたす。

2぀の方向の違いは、xずyが堎所を倉えるこずで、角床が倉化するこずです平らな䞊郚の六角圢の角床は0°、60°、120°、180°、240°、300°、および鋭い䞊郚-30 °、90°、150°、210°、270°、330°。


平らで尖った六角圢の角床

サむズず堎所


ここで、いく぀かの六角圢を䞀緒に配眮したいず思いたす。 氎平方向では、六角圢のheight = size * 2はheight = size * 2です。 隣接する六角圢間の垂盎距離vert = height * 3/4 。

六角圢のwidth = sqrt(3)/2 * height 。 隣接する六角圢間の氎平距離horiz = width 。

䞀郚の六角圢ゲヌムは、通垞の六角圢ず正確に䞀臎しないピクセルアヌトを䜿甚したす。 このセクションで説明する角床ず䜍眮の匏は、このような六角圢の寞法ず䞀臎したせん。 六角圢のメッシュアルゎリズムに぀いお説明しおいる残りの蚘事は、六角圢がわずかに䌞瞮しおいる堎合でも適甚できたす。




座暙系


六角圢をグリッドに組み立お始めたしょう。 正方圢グリッドの堎合、構築する明らかな方法は1぀だけです。 六角圢には、倚くのアプロヌチがありたす。 䞀次衚珟ずしお立方座暙を䜿甚するこずをお勧めしたす。 軞座暙たたはオフセット座暙を䜿甚しお、マップを保存し、ナヌザヌに座暙を衚瀺する必芁がありたす。

オフセット座暙


最も䞀般的なアプロヌチは、埌続の各列たたは行をオフセットするこずです。 列はcolたたはq瀺されたす。 行はrowたたはr瀺されたす。 奇数たたは偶数の列/行をオフセットできるため、氎平および垂盎の六角圢には2぀のオプションがありたす。


氎平配眮「odd-r」


氎平配眮「偶数-r」


瞊配眮「odd-q」


瞊配眮「偶数-q」

立方座暙


六角圢のグリッドを芋るもう1぀の方法は、正方圢のグリッドのように2぀ではなく3぀の䞻軞を芋るこずです。 それらぱレガントな察称性を瀺しおいたす。

立方䜓のグリッドを取り、 x + y + z = 0で察角平面を切り取り x + y + z = 0 。 これは奇劙な考えですが、六角圢グリッドのアルゎリズムを簡玠化するのに圹立ちたす。 特に、デカルト座暙の暙準操䜜を䜿甚できたす。座暙の加算ず枛算、スカラヌ倀による乗算ず陀算、および距離。

立方䜓のグリッド䞊の3぀の䞻軞ず、六角圢のグリッドの6぀の察角線方向ずの関係に泚目しおください。 グリッドの察角軞は、六角圢のグリッドの䞻方向に察応しおいたす。


六角圢


キュヌバ

正方圢ず立方䜓のグリッドのアルゎリズムはすでにあるため、立方座暙を䜿甚するず、これらのアルゎリズムを六角圢のグリッドに適合させるこずができたす。 ほずんどの蚘事のアルゎリズムにこのシステムを䜿甚したす。 異なる座暙系のアルゎリズムを䜿甚するには、3次座暙を倉換し、アルゎリズムを実行しおから元に戻したす。

六角圢のグリッドに察しお立方座暙がどのように機胜するかを孊びたす。 六角圢を遞択するず、3぀の軞に察応する立方䜓座暙が遞択されたす。




  1. 立方䜓のグリッドの各方向は、六角圢のグリッド䞊の線に察応しおいたす。 zが0、1、2、3に等しい六角圢を遞択しお、接続を確認しおください。 線は青でマヌクされおいたす。 x 緑ずy ラむラックに぀いおも同じこずを詊しおください。

  2. 六角圢グリッドの各方向は、立方䜓のグリッドの2぀の方向の組み合わせです。 たずえば、六角圢グリッドの「北」は+yず-z間にあるため、「北」ぞの各ステップはyを1増加させ、 zを1枛少させたす。

立方䜓座暙は、六角圢のグリッド座暙系の賢い遞択です。 条件はx + y + z = 0ため、アルゎリズムで保存する必芁がありたす。 たた、この条件により、各六角圢に垞に暙準座暙が存圚するこずが保蚌されたす。

立方䜓ず六角圢には倚くの異なる座暙系がありたす。 それらのいく぀かでは、条件はx + y + z = 0ずは異なりx + y + z = 0 。 倚くのシステムの1぀だけを瀺したした。 たた、 xy 、 yz 、 zxを䜿甚しお3次座暙を䜜成するこずもできたすが、これらには独自の興味深いプロパティのセットがありたすが、ここでは考慮したせん。

ただし、この圢匏で地図を保存する方法がわからないため、座暙に3぀の数字を保存したくないず考えるこずができたす。

軞座暙


「台圢」ずも呌ばれる軞座暙系は、3次座暙系の2぀たたは3぀の座暙に基づいお構築されたす。 条件x + y + z = 0ため、3番目の座暙は必芁ありたせん。 軞座暙は、マップを保存し、ナヌザヌに座暙を衚瀺するのに圹立ちたす。 3次座暙の堎合ず同様に、デカルト座暙での加算、枛算、乗算、陀算の暙準操䜜を䜿甚できたす。

倚くの立方座暙系ず倚くの軞がありたす。 このガむドでは、すべおの組み合わせを扱いたせん。 2぀の倉数、 q 列ずr 行を遞択したす。 この蚘事のスキヌムでは、 qはxに察応し、 rはzに察応したすが、さたざたな察応を取埗しお回路を回転および回転させるこずができるため、このような察応は任意です。

倉䜍グリッドを超えるこのシステムの利点は、アルゎリズムの理解床が高いこずです。 このシステムの欠点は、長方圢のカヌドを保管するのが少しおかしいこずです。 マップの保存に関するセクションを参照しおください。 䞀郚のアルゎリズムは3次座暙ではさらに明確ですが、条件x + y + z = 0があるため、3番目の暗黙の座暙を蚈算し、これらのアルゎリズムで䜿甚できたす。 私のプロゞェクトでは、 q 、 r 、 s軞を呌び出すため、条件はq + r + s = 0になり、必芁に応じおs = -q - r蚈算できたす。

軞


倉䜍座暙は、正方圢グリッドに䜿甚される暙準のデカルト座暙ず䞀臎するため、ほずんどの人が最初に考えるものです。 残念ながら、2぀の軞のうちの1぀が「コヌトに逆らう」必芁があり、結果ずしおすべおが耇雑になりたす。 キュヌビックおよびアキシャルシステムは「りヌルに沿っお」移動し、アルゎリズムは単玔ですが、カヌドの保管はもう少し耇雑です。 「亀互」たたは「二重」ず呌ばれる別のシステムがありたすが、ここではそれを考慮したせん。 キュヌビックやアキシャルよりも䜜業しやすい人もいたす。


倉䜍座暙、立方および軞

軞は、察応する座暙が増加する方向です。 軞に垂盎なのは、座暙が䞀定のたたである線です。 䞊蚘のグリッド図は、垂線を瀺しおいたす。


座暙倉換


プロゞェクトで軞座暙たたは倉䜍座暙を䜿甚する可胜性がありたすが、倚くのアルゎリズムは立方座暙でより簡単に衚珟できたす。 したがっお、システム間で座暙を倉換できる必芁がありたす。

軞座暙は立方䜓ず密接に関連しおいるため、倉換は簡単です。

 #      q = x r = z #      x = q z = r y = -xz

コヌドでは、これらの2぀の関数は次のように蚘述できたす。

 function cube_to_hex(h): #  var q = hx var r = hz return Hex(q, r) function hex_to_cube(h): #  var x = hq var z = hr var y = -xz return Cube(x, y, z)

オフセット座暙はかなり耇雑です

 #     -q col = x row = z + (x + (x&1)) / 2 #   -q   x = col z = row - (col + (col&1)) / 2 y = -xz #     -q col = x row = z + (x - (x&1)) / 2 #   -q   x = col z = row - (col - (col&1)) / 2 y = -xz #     -r col = x + (z + (z&1)) / 2 row = z #  -r   x = col - (row + (row&1)) / 2 z = row y = -xz #    -r col = x + (z - (z&1)) / 2 row = z #  -r   x = col - (row - (row&1)) / 2 z = row y = -xz

実装䞊の泚意数倀が偶数0か奇数1かを刀断するために、a2 剰䜙による陀算 の代わりに1 ビット単䜍の「AND」 を䜿甚したす。 詳现な説明に぀いおは、実装のメモペヌゞを参照しおください 。


隣接する六角圢


1぀の六角圢が指定されおいたすが、次の6぀の六角圢はどれですか ご想像のずおり、答える最も簡単な方法は、3次座暙で、軞座暙でかなり単玔で、倉䜍座暙で少し難しいです。 6぀の「察角」六角圢を蚈算する必芁がある堎合もありたす。

立方座暙


六角圢の座暙で1぀のスペヌスを移動するず、3぀の立方䜓座暙の1぀が+1倉化し、もう1぀が-1倉化したす合蚈は0のたたでなければなりたせん。 3぀の可胜な座暙は+1倉化し、残りの2぀の座暙は-1倉化したす。 これにより、6぀の倉曎が可胜になりたす。 それぞれが六角圢の方向の1぀に察応したす。 最も簡単で最速の方法は、コンパむル時に倉曎を事前に蚈算し、 Cube(dx, dy, dz) 3次座暙テヌブルCube(dx, dy, dz)に配眮するこずです。

 var directions = [ Cube(+1, -1, 0), Cube(+1, 0, -1), Cube( 0, +1, -1), Cube(-1, +1, 0), Cube(-1, 0, +1), Cube( 0, -1, +1) ] function cube_direction(direction): return directions[direction] function cube_neighbor(hex, direction): return cube_add(hex, cube_direction(direction))


軞座暙


前ず同様に、最初にキュヌビックシステムを䜿甚したす。 Cube(dx, dy, dz)テヌブルCube(dx, dy, dz)をCube(dx, dy, dz)し、 Hex(dq, dr)テヌブルHex(dq, dr)倉換したす。

 var directions = [ Hex(+1, 0), Hex(+1, -1), Hex( 0, -1), Hex(-1, 0), Hex(-1, +1), Hex( 0, +1) ] function hex_direction(direction): return directions[direction] function hex_neighbor(hex, direction): var dir = hex_direction(direction) return Hex(hex.q + dir.q, hex.r + dir.r)


オフセット座暙


軞座暙では、グリッドのどこにいるかに応じお倉曎を加えたす。 列/行のオフセットにいる堎合、ルヌルはオフセットのない列/行の堎合ずは異なりたす。

前ず同様に、 colおよびrow远加する数倀のテヌブルを䜜成したす。 ただし、今回は2぀の配列がありたす。1぀は奇数列/行甚で、もう1぀は偶数列/行甚です。 䞊蚘のグリッドマップで(1,1)芋お、6぀の各方向に移動するずきにcolずrowどのように倉化するかを確認しおください。 ここで(2,2)プロセスを繰り返したす。 テヌブルずコヌドは、4皮類のオフセットグリッドごずに異なりたす。それぞれの皮類のグリッドに察応するコヌドを瀺したす。

奇数
 var directions = [ [ Hex(+1, 0), Hex( 0, -1), Hex(-1, -1), Hex(-1, 0), Hex(-1, +1), Hex( 0, +1) ], [ Hex(+1, 0), Hex(+1, -1), Hex( 0, -1), Hex(-1, 0), Hex( 0, +1), Hex(+1, +1) ] ] function offset_neighbor(hex, direction): var parity = hex.row & 1 var dir = directions[parity][direction] return Hex(hex.col + dir.col, hex.row + dir.row)


偶数EVENおよび奇数ODD行のグリッド

でもr
 var directions = [ [ Hex(+1, 0), Hex(+1, -1), Hex( 0, -1), Hex(-1, 0), Hex( 0, +1), Hex(+1, +1) ], [ Hex(+1, 0), Hex( 0, -1), Hex(-1, -1), Hex(-1, 0), Hex(-1, +1), Hex( 0, +1) ] ] function offset_neighbor(hex, direction): var parity = hex.row & 1 var dir = directions[parity][direction] return Hex(hex.col + dir.col, hex.row + dir.row)


偶数EVENおよび奇数ODD行のグリッド

奇数
 var directions = [ [ Hex(+1, 0), Hex(+1, -1), Hex( 0, -1), Hex(-1, -1), Hex(-1, 0), Hex( 0, +1) ], [ Hex(+1, +1), Hex(+1, 0), Hex( 0, -1), Hex(-1, 0), Hex(-1, +1), Hex( 0, +1) ] ] function offset_neighbor(hex, direction): var parity = hex.col & 1 var dir = directions[parity][direction] return Hex(hex.col + dir.col, hex.row + dir.row)


偶数EVENおよび奇数ODD列のグリッド

でもq
 var directions = [ [ Hex(+1, +1), Hex(+1, 0), Hex( 0, -1), Hex(-1, 0), Hex(-1, +1), Hex( 0, +1) ], [ Hex(+1, 0), Hex(+1, -1), Hex( 0, -1), Hex(-1, -1), Hex(-1, 0), Hex( 0, +1) ] ] function offset_neighbor(hex, direction): var parity = hex.col & 1 var dir = directions[parity][direction] return Hex(hex.col + dir.col, hex.row + dir.row)


偶数EVENおよび奇数ODD列のグリッド

䞊蚘のルックアップテヌブルを䜿甚するこずが、ネむバヌを蚈算する最も簡単な方法です。 興味がある堎合は、 これらの数倀の抜出に぀いおも読むこずができたす 。

察角線


六角圢の座暙の「察角」空間を移動するず、3぀の立方䜓座暙の1぀が±2倉化し、他の2぀が∓1倉化したす合蚈は0のたたでなければなりたせん。

 var diagonals = [ Cube(+2, -1, -1), Cube(+1, +1, -2), Cube(-1, +2, -1), Cube(-2, +1, +1), Cube(-1, -1, +2), Cube(+1, -2, +1) ] function cube_diagonal_neighbor(hex, direction): return cube_add(hex, diagonals[direction])

前ず同様に、結果を蚈算した埌、3぀の座暙のいずれかを折り畳むこずにより、これらの座暙を軞に倉換するか、オフセット座暙に倉換できたす。



距離


立方座暙


立方䜓座暙系では、各六角圢は3次元空間の立方䜓です。 隣接する六角圢は、互いに1の距離にある六角圢のグリッドにありたすが、立方䜓のグリッドには2の距離にありたす。 これにより、距離の蚈算が簡単になりたす。 正方圢のグリッドでは、 マンハッタン距離はabs(dx) + abs(dy)です。 立方䜓のグリッドでは、マンハッタン距離はabs(dx) + abs(dy) + abs(dz)です。 六角圢のグリッドの距離は、その半分に等しくなりたす。

 function cube_distance(a, b): return (abs(ax - bx) + abs(ay - by) + abs(az - bz)) / 2

この゚ントリに盞圓するのは、3぀の座暙の1぀が他の2぀の座暙の合蚈でなければならず、それを距離ずしお取埗するずいう匏です。 以䞋の半分の圢匏たたは最倧倀の圢匏を遞択できたすが、同じ結果が埗られたす。

 function cube_distance(a, b): return max(abs(ax - bx), abs(ay - by), abs(az - bz))

図では、最倧倀が色で匷調衚瀺されおいたす。 たた、各色は6぀の「察角線」方向の1぀を衚しおいるこずに泚意しおください。

GIF


軞座暙


アキシャルシステムでは、3番目の座暙は暗黙的に衚珟されたす。 距離を蚈算するためにアキシャルからキュヌビックシステムに倉換したしょう

 function hex_distance(a, b): var ac = hex_to_cube(a) var bc = hex_to_cube(b) return cube_distance(ac, bc)

あなたのケヌスのコンパむラがhex_to_cubeずcube_distance むンラむンで埋め蟌む堎合、次のコヌドを生成したす

 function hex_distance(a, b): return (abs(aq - bq) + abs(aq + ar - bq - br) + abs(ar - br)) / 2

軞座暙の六角圢間の距離を蚘録する倚くの異なる方法がありたすが、蚘録方法に関係なく、軞システムの六角圢間の距離は立方システムのマンハッタン距離から抜出されたす 。 たずえば、 ここで説明する 「差分の差」は、 aq + ar - bq - brずいう衚蚘からaq - bq + ar - brずしお取埗され、 cube_distance二分cube_distanceではなく最倧倀圢匏を䜿甚したす。 3次座暙ずの関係を芋るず、それらはすべお類䌌しおいたす。

オフセット座暙


軞座暙ず同様に、倉䜍の座暙を3次座暙に倉換し、3次システムの距離を䜿甚したす。

 function offset_distance(a, b): var ac = offset_to_cube(a) var bc = offset_to_cube(b) return cube_distance(ac, bc)

倚くのアルゎリズムで同じテンプレヌトを䜿甚したす。六角圢から立方䜓ぞの倉換、アルゎリズムの立方䜓バヌゞョンの実行、立方䜓の結果の六角圢の座暙軞座暙たたはオフセット座暙ぞの倉換。


線画


ある六角圢から別の六角圢に線を匕く方法は 線圢補間を䜿甚しお線を描画したす 。 ラむンはN+1ポむントで均等にサンプリングされ、これらのサンプルがどの六角圢であるかが蚈算されたす。

GIF


  1. 最初に、端点間の六角圢の距離であるNを蚈算したす。
  2. 次に、ポむントAずBの間でN+1ポむントを均等にサンプリングしたす。線圢補間を䜿甚しお、 0からNたでの倀iそれらを含むに぀いお、各ポむントがA + (B - A) * 1.0/N * iたす。 図では、これらの制埡点は青で瀺されおいたす。 結果は浮動小数点座暙です。
  3. 各制埡点浮動を六角圢intに倉換したす。 このアルゎリズムはcube_roundず呌ばれcube_round 以䞋を参照。

すべおをたずめおAからBに線を匕きたす。

 function lerp(a, b, t): //  float return a + (b - a) * t function cube_lerp(a, b, t): //   return Cube(lerp(ax, bx, t), lerp(ay, by, t), lerp(az, bz, t)) function cube_linedraw(a, b): var N = cube_distance(a, b) var results = [] for each 0 ≀ i ≀ N: results.append(cube_round(cube_lerp(a, b, 1.0/N * i))) return results

泚



可動範囲


座暙範囲


特定の六角圢の䞭心ず範囲Nどの六角圢がそのNステップ以内にありたすか

六角圢間の距離の匏の逆の䜜業を行うこずができたすdistance = max(abs(dx), abs(dy), abs(dz)) 。 N内のすべおの六角圢を芋぀けるには、 max(abs(dx), abs(dy), abs(dz)) ≀ N これは、 abs(dx) ≀ Nおよびabs(dy) ≀ Nおよびabs(dz) ≀ N 3぀の倀がすべお必芁であるこずを意味したすabs(dz) ≀ N 絶察倀を削陀するず、 -N ≀ dy ≀ Nおよび-N ≀ dy ≀ Nおよび-N ≀ dy ≀ N埗られたす-N ≀ dz ≀ N コヌドでは、これはネストされたルヌプになりたす。

 var results = [] for each -N ≀ dx ≀ N: for each -N ≀ dy ≀ N: for each -N ≀ dz ≀ N: if dx + dy + dz = 0: results.append(cube_add(center, Cube(dx, dy, dz)))

このルヌプは機胜したすが、非垞に非効率的です。 ルヌプで反埩凊理するすべおのdz倀のうち、実際にキュヌブ条件dx + dy + dz = 0満たすのは1぀だけです。代わりに、dz条件を満足する倀を盎接蚈算したす。

 var results = [] for each -N ≀ dx ≀ N: for each max(-N, -dx-N) ≀ dy ≀ min(N, -dx+N): var dz = -dx-dy results.append(cube_add(center, Cube(dx, dy, dz)))

このサむクルは、必芁な座暙にのみ沿っおいたす。図では、各範囲は行のペアです。各行は䞍等匏です。6぀の䞍等匏を満たすすべおの六角圢を取りたす。

GIF


亀差する範囲


耇数の範囲にある六角圢を芋぀ける必芁がある堎合は、六角圢のリストを生成する前に範囲を暪断できたす。

代数たたは幟䜕孊の芳点からこの問題にアプロヌチできたす。代数的には、各領域はの圢匏で䞍等匏の条件ずしお衚され-N ≀ dx ≀ N、これらの条件の共通郚分を芋぀ける必芁がありたす。幟䜕孊的には、各領域は3次元空間の立方䜓であり、3次元空間で2぀の立方䜓を亀差させお、3次元空間で盎方䜓を取埗したす。次に、平面x + y + z = 0に投圱しお六角圢を取埗したす。この問題を代数的に解決したす。

第䞀に、我々は条件を曞き換え-N ≀ dx ≀ N、より䞀般的な圢で、か぀取るず。同じこずをしたしょうx min ≀ x ≀ x maxx min = center.x - Nx max = center.x + Nyそしおz、その結果、前のセクションからコヌドの䞀般的なビュヌを取埗したす

 var results = [] for each xmin ≀ x ≀ xmax: for each max(ymin, -x-zmax) ≀ y ≀ min(ymax, -x-zmin): var z = -xy results.append(Cube(x, y, z))

2の亀点が範囲a ≀ x ≀ bずc ≀ x ≀ dされたすmax(a, c) ≀ x ≀ min(b, d)。六角圢の領域はの範囲ずしお衚珟するのでx、y、z我々は、個々のバンドのそれぞれを暪断するこずができx、y、z、その埌亀差点における六角圢のリストを生成するために、ネストされたルヌプを䜿甚したす。䞀方の領域のために我々は六角圢を取るず、に類䌌するず。六角圢の二぀の領域の亀点に、我々は受け入れるず最倧=分H1.x + N、 H2.x + Nは、 同様であるず。同じパタヌンは、3぀以䞊の領域を亀差させるために機胜したす。x min = Hx - Nx max = Hx + Nyzx min = max(H1.x - N, H2.x - N)xyz

GIF


障害物


障害物がある堎合は、距離制限を埋めるのが最も簡単ですワむド怜玢。次の図では、4぀の動きに制限されおいたす。コヌドではfringes[k]、これはkステップで達成できるすべおの六角圢の配列です。メむンサむクルを通過するたびに、レベルk-1をlevelに拡匵したすk。

 function cube_reachable(start, movement): var visited = set() add start to visited var fringes = [] fringes.append([start]) for each 1 < k ≀ movement: fringes.append([]) for each cube in fringes[k-1]: for each 0 ≀ dir < 6: var neighbor = cube_neighbor(cube, dir) if neighbor not in visited, not blocked: add neighbor to visited fringes[k].append(neighbor) return visited




タヌン


特定の六角圢ベクトル2぀の六角圢の差に察しお、別の六角圢を指すように回転する必芁がある堎合がありたす。これは、1/6サヌクルタヌンに固執する堎合、3次座暙で簡単に実行できたす。

右に60°回転するず、各座暙が右に1ポゞション移動したす。

  [ x, y, z] to [-z, -x, -y]

巊に60°回転するず、各座暙が巊に1ポゞション移動したす。

  [ x, y, z] to [-y, -z, -x]



[元の蚘事で]スキヌムを「再生」するず、60°回転するごずに笊号が倉化し、座暙が物理的に「回転」するこずがわかりたす。120°回転するず、蚘号は再び同じになりたす。180床回転するず笊号が倉わりたすが、座暙は元の䜍眮に回転したす。

䜍眮Pが䞭心䜍眮Cを䞭心に回転し、新しい䜍眮Rに至る完党なシヌケンスを次に瀺したす。

  1. PおよびCの䜍眮を3次座暙に倉換したす。
  2. 枛算するこずにより、センタヌベクトル算出P_from_C = P - C = Cube(Px - Cx, Py - Cy, Pz - Cz)。
  3. P_from_C䞊蚘のようにベクトルを回転し、最終的なベクトルに指定を割り圓おR_from_Cたす。
  4. 圢質転換ベクタヌは、远加の䞭心䜍眮に戻りたすR = R_from_C + C = Cube(R_from_C.x + Cx, R_from_C.y + Cy, R_from_C.z + Cz)。
  5. Rの3次䜍眮を目的の座暙系に倉換したす。

倉換にはいく぀かの段階がありたすが、それぞれが非垞に単玔です。軞座暙で盎接回転を定矩するこずでこれらのステップの䞀郚を短瞮できたすが、六角圢ベクトルはオフセット座暙では機胜せず、オフセット座暙のステップを短瞮する方法がわかりたせん。stackexchangeでロヌテヌションを蚈算する他の方法の説明も参照しおください。


指茪


シンプルなリング


特定の六角圢が特定の半埄のリングに属しおいるかどうかを調べるには、radiusこの六角圢から䞭心たでの距離を蚈算し、等しいかどうかを調べる必芁がありたすradius。このようなすべおの六角圢のリストを取埗するにradiusは、䞭心からステップを螏み、リングに沿ったパスに沿っお回転したベクトルに埓う必芁がありたす。

 function cube_ring(center, radius): var results = [] #      radius == 0;  , ? var cube = cube_add(center, cube_scale(cube_direction(4), radius)) for each 0 ≀ i < 6: for each 0 ≀ j < radius: results.append(cube) cube = cube_neighbor(cube, i) return results

このコヌドcubeは、図の䞭心から角に向かう倧きな矢印で瀺されるリングから始たりたす。たず、角床4を遞択したした。これは、方向番号が移動するパスに察応しおいるためです。別の開始角床が必芁な堎合がありたす。内偎のサむクルの各段階でcube、リングに沿っお1぀の六角圢を移動したす。スルヌ6 * radius始めた堎所の手順は完了したす。



スパむラルリング


らせんパタヌンに沿っおリングに沿っお通過するず、リングの内偎の郚分を埋めるこずができたす。

 function cube_spiral(center, radius): var results = [center] for each 1 ≀ k ≀ radius: results = results + cube_ring(center, k) return results



倧きな六角圢の面積は、すべおの円の合蚈に䞭心の1を加えたものです。面積を蚈算するには、次の匏を䜿甚したす。

この方法で六角圢をバむパスするこずは、移動範囲の蚈算にも䜿甚できたす䞊蚘を参照。



範囲


䞎えられた距離で䞎えられた䜍眮から芋えるものは䜕で、障害物によっおブロックされおいたせんかこれを刀断する最も簡単な方法は、特定の範囲内の各六角圢に線を匕くこずです。線が壁に合わない堎合は、六角圢が衚瀺されたす。[元の蚘事の図]の六角圢に沿っおマりスを移動するず、これらの六角圢ぞの線の描画ず、線が亀わる壁が衚瀺されたす。

このアルゎリズムは広い範囲で䜎速になる可胜性がありたすが、実装は簡単なので、最初から始めるこずをお勧めしたす。

GIF


可芖性にはさたざたな定矩がありたす。むニシャルの䞭心から別の六角圢の䞭心を芋たいですかスタヌトの䞭心から別の六角圢の䞀郚を芋たいですかたぶん、開始点のどこからでも別の六角圢の䞀郚ですか完党な六角圢よりも少ないビュヌぞの障害スコヌプは、䞀芋思われるよりもunningで倚様な抂念です。最も単玔なアルゎリズムから始めたしょう。ただし、プロゞェクトの答えが正しく蚈算されるこずを期埅しおください。単玔なアルゎリズムで非論理的な結果が埗られる堎合もありたす。

でクラヌクVerbruggeマニュアル範囲を蚈算するためのアルゎリズムを説明し、「䞭倮から開始しお倖偎に移動したす。」GithubにあるDueloプロゞェクトも参照しおください。道順を含む範囲のオンラむンデモ。たた、2D可芖性の蚈算に関する私の蚘事を読むこずができたす。これには、六角圢を含む倚角圢で動䜜するアルゎリズムがありたす。ロヌグラむクファンコミュニティには、正方圢グリッド甚の優れたアルゎリズムセットがありたすこちら、こちら、こちらをご芧ください。それらのいく぀かは、六角圢のグリッドに適応させるこずができたす。


六角圢からピクセル


六角圢からピクセルに倉換するには、「ゞオメトリ」セクションに瀺されおいるサむズず堎所のスキヌムを調べるず䟿利です。軞座暙の堎合、六角圢からピクセルぞの倉換は、基底ベクトルを考慮しおアプロヌチする必芁がありたす。図では、矢印A→Qは基底ベクトルqであり、A→Rは基底ベクトルrです。ピクセル座暙はq_basis * q + r_basis * rです。たずえば、1、1のBは基底ベクトルqずrの合蚈です。


行列ラむブラリを䜿甚するず、操䜜は単玔な行列乗算です。ただし、ここではマトリックスなしでコヌドを蚘述したす。軞グリッドのためx = q、z = r次のように私は、このガむドで䜿甚するこずは、倉換は次のようになりたす

平らな䞊面を有する六角圢のため
 function hex_to_pixel(hex): x = size * 3/2 * hex.q y = size * sqrt(3) * (hex.r + hex.q/2) return Point(x, y)

先のずがったトップ甚
 function hex_to_pixel(hex): x = size * sqrt(3) * (hex.q + hex.r/2) y = size * 3/2 * hex.r return Point(x, y)

マトリックスアプロヌチは、埌でピクセルの座暙を六角圢の座暙に倉換する必芁があるずきに䟿利です。マトリックスを逆にするだけです。3次座暙の堎合、3次基底ベクトルx、y、zを䜿甚するか、最初にそれらを軞に倉換しおから軞基底ベクトルq、rを䜿甚できたす。

オフセット座暙の堎合、列番号たたは行番号をシフトする必芁がありたす敎数ではなくなりたす。その埌、x軞ずy軞に関連付けられたベヌスベクトルqずrを䜿甚できたす

Odd-r
 function offset_to_pixel(hex): x = size * sqrt(3) * (hex.col + 0.5 * (hex.row&1)) y = size * 3/2 * hex.row return Point(x, y)

でもr
 function offset_to_pixel(hex): x = size * sqrt(3) * (hex.col - 0.5 * (hex.row&1)) y = size * 3/2 * hex.row return Point(x, y)

奇数
 function offset_to_pixel(hex): x = size * 3/2 * hex.col y = size * sqrt(3) * (hex.row + 0.5 * (hex.col&1)) return Point(x, y)

でもq
 function offset_to_pixel(hex): x = size * 3/2 * hex.col y = size * sqrt(3) * (hex.row - 0.5 * (hex.col&1)) return Point(x, y)

残念ながら、倉䜍座暙には、マトリックスで䜿甚できる基底ベクトルがありたせん。これが、オフセット座暙でピクセルから六角圢ぞの倉換がより難しい理由の1぀です。

別のアプロヌチオフセット座暙を3次/軞座暙に倉換しおから、3次/軞座暙のピクセルぞの倉換を䜿甚したす。最適化䞭に倉換コヌドを埋め蟌むこずにより、䞊蚘ず同じ結果になりたす。


ピクセルから六角圢ぞ


最も䞀般的な質問の1぀は、ピクセルの䜍眮たずえば、マりスクリックを取埗し、六角圢のグリッド座暙に倉換する方法ですかこれが軞座暙たたは3次座暙でどのように行われるかを瀺したす。オフセット座暙の堎合、最も簡単な方法は、3次座暙を最埌にオフセット座暙に倉換するこずです。

GIF


  1. たず、六角圢からピクセルぞの倉換を逆にしたす。これにより、図に小さな青い円で瀺されおいる六角圢の小数座暙が埗られたす。
  2. 次に、六角圢の小数座暙を含む六角圢を定矩したす。図では、六角圢が匷調衚瀺されおいたす。

我々が掛けた六角圢のピクセル座暙に座暙倉換するためにq、r基底ベクトルが埗られx、y。これは行列乗算ず芋なすこずができたす。尖ったトップのマトリックスは次のずおりです。


ピクセルの座暙を六角圢の座暙に戻すこずは、かなり簡単です。行列を反転できたす


これらの蚈算により、qおよびの分数軞座暙浮動が埗られrたす。この関数hex_round()は、分数軞座暙を六角圢の敎数軞座暙に倉換したす。

軞方向の尖ったトップのコヌドは次のずおりです。

 function pixel_to_hex(x, y): q = (x * sqrt(3)/3 - y / 3) / size r = y * 2/3 / size return hex_round(Hex(q, r))

そしお、ここに軞方向のフラットトップ六角圢のコヌドがありたす

 function pixel_to_hex(x, y): q = x * 2/3 / size r = (-x / 3 + sqrt(3)/3 * y) / size return hex_round(Hex(q, r))

これらの3行のコヌドは、ピクセルの䜍眮を六角圢の軞座暙に倉換したす。オフセット座暙を䜿甚する堎合は、を䜿甚したすreturn cube_to_hex(cube_round(Cube(q, -qr, r)))。

ピクセルを六角圢に倉換する方法は他にもたくさんありたす。で、このペヌゞは私にはよく知られおいたす。


最も近い六角圢に䞞めたす。


浮動小数点を䜿甚しお3次座暙x、y、zを取埗する堎合があり、どの六角圢にあるかを調べる必芁がありたす。これは、線を描画し、ピクセルから六角圢に倉換するこずで明確になりたす。浮動小数点倀を敎数倀に倉換するこずは䞞めず呌ばれるため、このアルゎリズムを呌び出したしたcube_round。3次浮動小数点

座暙でx + y + z = 0も、3次座暙で。したがっお、各コンポヌネントを最も近い敎数に䞞めたしょう(rx, ry, rz)。ただし、x + y + z = 0䞞めた埌、ずいう保蚌はありたせんrx + ry + rz = 0。したがっお、条件がrx + ry + rz = 0真になるように、最倧​​の倉曎でコンポヌネントを倉曎したす。たずえば、倉化がy abs(ry-y)倧きい堎合abs(rx-x)そしお、abs(rz-z)それをに倉曎しry = -rx-rzたす。これは私たちにそれを保蚌しrx + ry + rz = 0たす。アルゎリズムは次のずおりです。

 function cube_round(h): var rx = round(hx) var ry = round(hy) var rz = round(hz) var x_diff = abs(rx - hx) var y_diff = abs(ry - hy) var z_diff = abs(rz - hz) if x_diff > y_diff and x_diff > z_diff: rx = -ry-rz else if y_diff > z_diff: ry = -rx-rz else: rz = -rx-ry return Cube(rx, ry, rz)

非キュヌビック座暙の堎合、キュヌビック座暙に倉換し、䞞めアルゎリズムを䜿甚しおから元に戻すのが最も簡単です。

 function hex_round(h): return cube_to_hex(cube_round(hex_to_cube(h)))

実装に関する泚意cube_roundおよびhex_roundintではなくfloatで座暙を取埗したす。Cubeずclassesを䜜成した堎合Hex、敎数の代わりに浮動小数点数を枡すこずができる動的型付けの蚀語、および統䞀型の型を持぀静的型付けの蚀語で正垞に動䜜したす。ただし、静的型付けを䜿甚するほずんどの蚀語では、float座暙甚に別のクラス/構造䜓型が必芁でありcube_round、typeがありFloatCube → Cubeたす。必芁な堎合はhex_round、代わりにFloatHex → Hexヘルパヌ関数をfloatcube_to_floathex䜿甚しcube_to_hexたす。パラメヌタヌ化された型C ++、Haskellなどを持぀蚀語では、TがintたたはfloatであるCubeを定矩できたす。たたは曞くこずができたすcube_round この関数のみに新しい型を定矩する代わりに、入力ずしお3぀の浮動小数点数を取埗したす。


地図を軞座暙で保存する


ほずんどの堎合、軞座暙系は、長方圢のマップを䜿甚するずきにスペヌスを無駄に消費するため、苊情を匕き起こしたす。これが倉䜍座暙系の理由の1぀です。ただし、䞉角圢たたは六角圢のマップを䜿甚するず、六角圢のすべおの座暙系でスペヌスが消費されたす。 1぀の戊略を䜿甚しお、これらすべおのタむプのカヌドを保存できたす。


長方圢の地図


䞉角圢の地図


六角圢の地図


菱圢の地図

図では、未䜿甚のスペヌスは各線の巊右にあるこずに泚意しおください菱圢の地図を陀く。これにより、カヌドストレヌゞ戊略の3぀のオプションが提䟛されたす。

  1. . . . , .
  2. - . , . q,r hash_table(hash(q,r)) . / , .
  3. . . . . , 0, .

    , « ». q,r , array[r][q - first_column[r]] . / , . first_column .

    , « » « », .

    • first_column[r] == -floor(r/2) . array[r][q + r/2] , .
    • , , first_column[r] == 0 , access array[r][q] — ! , - ( ), array[r][q+r] .
    • N , N = max(abs(x), abs(y), abs(z) , first_column[r] == -N - min(0, r) . array[r][q + N + min(0, r)] . - r < 0 , array[r + N][q + N + min(0, r)] .
    • , array[r][q] .



䞀郚のゲヌムでは、カヌドの端を「くっ぀ける」必芁がありたす。正方圢マップは、x軞球䜓にほが察応たたはx軞ずy軞トヌラスにほが察応に沿っおのみラップできたす。最小化は、芁玠の圢状ではなく、マップの圢状に䟝存したす。正方圢座暙マップの最小化は、オフセット座暙で簡単に実行できたす。六角圢のマップを3次座暙で折り畳む方法を瀺したす。

マップの䞭心に関しおは、6぀の「ミラヌ」センタヌがありたす。マップを離れるずき、メむンマップに再び戻るたで、最も近いミラヌ䞭心を匕きたす。 [元の蚘事]の図で、䞭倮の地図から離れお、鏡の䞭心の1぀が反察偎から地図に入る様子を芳察したす。

最も簡単な実装は、回答を事前に蚈算するこずです。マップから出る各六角圢、反察偎の察応するキュヌブを栌玍するルックアップテヌブルを䜜成したす。6぀のミラヌセンタヌのMそれぞれず、マップ䞊の各䜍眮に぀いお、L保存しmirror_table[cube_add(M, L)] = Lたす。ミラヌのテヌブルにある六角圢を蚈算するたびに、ミラヌリングされおいないバヌゞョンに眮き換えたす。

半埄のある六角圢のマップでは、Nミラヌの䞭心Cube(2*N+1, -N, -N-1)も6タヌンになりたす。

GIF



道を探す


A *怜玢アルゎリズム、DijkstraたたはFloyd-Warshallアルゎリズムなど、グラフでパス怜玢を䜿甚する堎合、六角圢グリッドでのパス怜玢は、正方圢グリッドでのパス怜玢ず倉わりたせん。パス怜玢ガむドの説明ずコヌドは、六角圢のグリッドに適甚されたす。


[元の蚘事では、この䟋はむンタラクティブで、マりスクリックで壁を远加および削陀できたす]

  1. 隣人。パス怜玢ガむドに瀺されおいるコヌド䟋は、芁玠に隣接する䜍眮を取埗するために呌び出しおいたすgraph.neighbors。これには、「近くの六角圢」セクションの機胜を䜿甚したす。貫通できない隣接する六角圢を陀去したす。
  2. ヒュヌリスティック。アルゎリズムA *のコヌド䟋ではheuristic、2぀の䜍眮間の距離を取埗する関数が䜿甚されおいたす。距離の匏に移動コストを掛けお䜿甚したす。たずえば、移動に六角圢あたり5ナニットのコストがかかる堎合、距離に5を掛けたす。


远加の読曞


C ++、Java、C、Javascript、Haxe、Pythonのコヌド䟋を䜿甚しお、六角圢グリッドの独自のラむブラリを実装するためのガむドがありたす。


この蚘事の[元の]コヌドは、HaxeずJavascriptの混合で蚘述されおいたすCube.hx、Hex.hx、Grid.hx、ScreenCoordinate.hx、ui.jsおよびcubegrid.jsキュヌブ/六角圢のアニメヌション甚。ただし、六角圢グリッドの独自のラむブラリを䜜成する堎合は、代わりに実装ガむドを怜蚎するこずをお勧めしたす。

このガむドをさらに拡匵したいず思いたす。Trelloにリストがありたす。

Source: https://habr.com/ru/post/J319644/

More articles:


All Articles