概要
戦略ゲーム等でよく見る、六角形のタイルで敷き詰められた座標系に関するあれこれ。以下のページが self-contained でかつ内容的にも実用上十分であると世界的に認知されている:
- 理論: https://www.redblobgames.com/grids/hexagons/
- 実践: https://www.redblobgames.com/grids/hexagons/implementation.html
言語別のライブラリ一覧
以下は、忘れっぽい将来の自分に向けたメモ
２つのオプション
六角形の頂点が 12時方向に向くように敷き詰める方法を pointy なレイアウトという。六角形の辺が 12時方向を向くように敷き詰める方法を flat なレイアウトという。
３つの座標系
大まかにいって我々は３つの座標系を行き来する。(X, Y)-座標系, (x, y)-座標系, (q, r)-座標系。
(X, Y)-座標系は横軸右が X軸正の方向、縦軸下が Y軸正の方向の座標系であり、SVG や pixi.js など世の中のかなり多くの 2D ライブラリで採用している座標系である。単位はピクセル。
(x, y)-座標系は、同じく直交座標系であるが、スケールが異なる。この座標系では六角形の外接円の半径を 1 とする。原点は六角形の中心点とする。
(q, r)-座標系は、斜交座標系であり、(x, y)-座標系と同じく六角形の外接円の半径を1とし、原点として六角形の中心点をとる。pointy の場合、q 軸正方向は 3時方向、 r 軸の正方向は 5時方向。flat の場合は q軸は4時方向、r軸は6時方向。基底ベクトルの長さは各六角形の中心間の距離、すなわち√3 とする。
座標系を一意に指定するもの
前述のように、レイアウトの任意性と、(X, Y)-座標系の任意性がある。これを特徴づけるパラメータさえ決めてしまえば、各座標系の相互変換が一意に決まる。以下がパラメータ
-
layout: 2値。すなわち pointy か flat のいずれか。 -
originX: 単位はピクセル。(X, Y)-座標系の原点位置の X座標 -
originY: 同上。 Y座標。 -
radius: 単位はピクセル。(X, Y)-座標系における六角形の外接円の半径
上記の４つの数値が与えられれば、任意の点 P の各座標系における座標を相互変換できる。多くの場合、(q, r)-座標系で各種作業をして、(X, Y)-座標系に変換してUIライブラリに渡すという処理パターンになる。
主要トピック
rounding / binning
点の座標 (X, Y) が与えられた時、その点がどの六角形に所属するか？というのがよくあるユースケースで、round とか bin と言われる。座標を、(q, r)-座標系に変換して、四捨五入相当のことをするのだが、すこしややこしいアルゴリズムが必要になる。
distance
「移動力 3 の戦車が移動できるタイルは？」というようなユースケースで重要になる。マンハッタン距離に似たような、ちょっと違うような距離関数を定義できる。
path finding
任意の二点を指定した際にどの六角形を通るのかを探すアルゴリズム。A*-アルゴリズムが使えるので固有の難しさは存在しない。
map creation
指定された形（長方形・三角形・六角形などなど）のタイル一覧を生成する機能。世界地図の作成に使われる
wraping
作成した世界地図をつなげる。右の境界をすぎると左端から出て、、、などなど
rotation
回転。ユースケースは少ないが、アルゴリズム的に美しい。座標の符号を反転させるだけ！