こんにちは、あすらと（＠__asurato__）です。
モダンなゲームではあまり見かけなくなりましたが、大戦略やCivilizationのような戦略シミュレーションではヘクス座標系が採用されています。ヘクス座標系では1つのマスが正六角形になっており、正六角形の各マスは隙間なくマップに敷き詰められます。本日はヘクス座標系のマスの管理方法について考察しましたのでご覧ください。
ヘクスマップの例
前提
本記事では以下を前提としています。これらの前提が容易・高速に達成できるアルゴリズムが良い手法であるとここでは定義します。
- Tileクラスが各マスの情報を表す
- Tile型のインスタンスは配列や二次元配列に格納される
- マスが指定されたらそのマスに関するTile型のインスタンスを取得したい
- あるマスに隣接しているマスも取得したい
例えば tiles[id] 等でそのidに関するTile型のインスタンスを取得することができれば前の3つについて達成されます。言い方を変えると、関数f: id→Tile となる関数が作れるならOKです。
またマスXに隣接したマスYを取得できれば最後の項目は達成されます。前3つの項目によりidからTileへの変換は前提とするため、XのidからYのidが取得できれば達成されます。
以下からマスの管理方法について章立てで説明します。
並んでる方向にIDを振る手法（一次元）
このような場合はIDを振る方向を横に変えるとなんと解決します。
- 特徴
- 隣接マスのIDの取得が簡単
- 自然な発想
- メモリの無駄がない
- マップが長方形の場合のみ使用可能
二次元直交座標に変換する手法
一次元的にIDを与えるのではなく、二次元座標を用いて各マスを二次元配列に格納することもできます。座標[a, b]のマスはtiles[a][b]として取得します。
問題点として、tiles[0][0]とは異なりtiles[0][1]には値が存在しません。tiles[a][b]が存在するかを常にチェックする必要があります。
- 特徴
- 隣接マスのIDの取得が簡単
- 例）a→a+1、b→b+1で右下のマスを取得できる
- 全てのマップ系で使用可能
- 座標にマイナスの値が含まれるときは別途対処の必要あり
- 配列の戻り値がTileとNullの2種類があり、Nullチェックが必要
- 二次元配列のうち半分が死にマスとなり、メモリの無駄遣い♠️
二次元直交座標＋Map法
上の手法の派生系で、二次元座標を文字列に変換してMapに格納する手法です。ちなみにPythonのようにタプルをキーにできる言語や、座標を示す構造体をMapのキーに自前で設定する場合は文字列への変換は不要です。メリットはメモリの無駄がないこと、デメリットは座標とMapのキーとの相互変換が面倒な点でしょう。
- 特徴
- 隣接マスのIDの取得には座標とMapのキーとの相互変換が必要
- メモリの無駄がない
- 座標がマイナスを含む場合も対応できる
- 全てのマップ系で使用可能
二次元座標＋配列法
私が考えたイケイケアルゴリズムです。
まず上図のように軸を設定し座標を計算します。B軸の位置について、Aの要素が0以上になるように設定しましょう。
次に2つの配列を用意します。1つ目の配列には全てのマスが格納され、もう1つの配列には前者の配列のキー(ID)が入ります。
まず要素Aが小さい順に、要素Aが同値の場合は要素Bが小さい順にマスを配列１へ格納します。その格納の際に、要素B=0となるマスの（配列１における）IDを配列２に格納します。2つの配列を用いて、座標(a, b)のマスは arr1[arr2[a] + b] として取得できます。
- 特徴
- 隣接マスのIDの取得が簡単
- 例）a→a-1、b→b+1で右下のマスを取得できる
- ほとんどのマップ系で使用可能
- ただし間が空くマップ系だと「二次元直交座標に変換する手法」と同様にNullチェックが必要になる
- メモリの無駄がない
- 軸が斜めになっているので直感的ではない
- でも頑張れば直交座標でも使えそう
まとめ
- マップが長方形ならIDを縦or横方向に振る方法でよい
- 縦か横かはその時のマップの性質によって見極める必要がある
- 二次元直交座標＋Map法は任意のマップで使えるので、最終手段として検討しよう
- 二次元座標＋配列法はコードが少し難しくなるが色々効率的
参考サイト
http://higesusk.blog.fc2.com/blog-entry-146.html
https://ninagreen.hatenablog.com/entry/2015/11/14/193417
https://sinsei.space/blog/11747
https://www.redblobgames.com/grids/hexagons/