なでしこでHEXマップの2点間距離計算をする - 日曜プログラマーの個人的覚書

HEXマップとは

六角形のチップが隙間無く配置されたマップ形式。
マップ上の距離感覚が直観的で分かりやすいため、シミュレーションゲーム等で使われる。
短所は、データをX,Y座標系で扱う場合の管理が難しい事と距離計算が複雑になる事。

距離計算式を作る

今回は、1000×1000のチップが配置されたHEXマップの距離計算を行う。
なお、チップの配置と座標の関係は次のようにする。

[0,0]		[1,0]		[2,0]		[3,0]
	[0,1]		[1,1]		[2,1]		[3,1]
[0,2]		[1,2]		[2,2]		[3,2]
	[0,3]		[1,3]		[2,3]		[3,3]

Y座標が偶数のマスと奇数のマスで半マス分ずらして表示する形となる。

この場合、それぞれ[x,y]に隣接するマスは次のようになる。

（y：偶数の場合）
	[x-1,y-1]		[x,y-1]
[x-1,y]		[x,y]		[x+1,y]
	[x-1,y+1]		[x,y+1]

（y：奇数の場合）
	[x,y-1]		[x+1,y-1]
[x-1,y]		[x,y]		[x+1,y]
	[x,y+1]		[x+1,y+1]

[x,y]のマスを中心に見た場合、Y方向に線対称、X方向に非対称となる事が分かる。
隣接するマス同士の距離を1とすると、2点間の距離は隣接するマスへの移動の繰り返しとなるので、例えば[2,0]から移動する場合、[0,3]から[3,3]までの同じY座標の範囲のどこに移動しても距離は同じ3となる。（この範囲からX方向に外れると、外れた分だけ距離が加算される。）

[0,0]		[1,0]		[2,0]		[3,0]
	[0,1]		[1,1]		[2,1]		[3,1]
[0,2]		[1,2]		[2,2]		[3,2]
	[0,3]		[1,3]		[2,3]		[3,3]

これらを合わせて考えると、距離の計算式は以下のようになる。
$\left[ x_{a}, y_{a} \right]$ から $\left[ x_{b}, y_{b} \right]$ までの距離

$y_a$ , $y_b$ ：ともに偶数, または奇数の場合

$dist =$
$\left\{ \begin{matrix} \left| x_b - x_a \right| \leq \frac{\left| y_b - y_a \right| }{2} & \rightarrow & \left| y_b - y_a \right| \\ \left| x_b - x_a \right| \gt \frac{\left| y_b - y_a \right| }{2} & \rightarrow & \left| y_b - y_a \right| + \left( \left| x_b - x_a \right| - \frac{ \left| y_b - y_a \right| }{2} \right) \end{matrix} \right\}$
（偶数同士・奇数同士の移動では同じX座標で半マス分ずれる事を考える必要が無いため、数式は単純となる）

：偶数, ：奇数の場合
- $x_a < x_a$ の場合

$dist =$
$\left\{ \begin{matrix} \left| x_b - x_a \right| \leq \lceil \frac{ \left| y_b - y_a \right| }{2} \rceil & \rightarrow & \left| y_b - y_a \right| \\ \left| x_b - x_a \right| \gt \lceil \frac{ \left| y_b - y_a \right| }{2} \rceil & \rightarrow & \left| y_b - y_a \right| + \left( \left| x_b - x_a \right| - \lceil \frac{ \left| y_b - y_a \right| }{2} \rceil \right) \end{matrix} \right\}$

- $x_a \geq x_a$ の場合

$dist =$
$\left\{ \begin{matrix} \left| x_b + 1 - x_a \right| \leq \lceil \frac{ \left| y_b - y_a \right| }{2} \rceil & \rightarrow & \left| y_b - y_a \right| \\ \left| x_b + 1 - x_a \right| \gt \lceil \frac{ \left| y_b - y_a \right| }{2} \rceil & \rightarrow & \left| y_b - y_a \right| + \left( \left| x_b + 1 - x_a \right| - \lceil \frac{ \left| y_b - y_a \right| }{2} \rceil \right) \end{matrix} \right\}$

：奇数, ：偶数の場合
- $x_a \lt x_a$ の場合

$dist =$
$\left\{ \begin{matrix} \left| x_b - 1 - x_a \right| \leq \lceil \frac{ \left| y_b - y_a \right| }{2} \rceil & \rightarrow & \left| y_b - y_a \right| \\ \left| x_b - 1 - x_a \right| \gt \lceil \frac{ \left| y_b - y_a \right| }{2} \rceil & \rightarrow & \left| y_b - y_a \right| + \left( \left| x_b - 1 - x_a \right| - \lceil \frac{ \left| y_b - y_a \right| }{2} \rceil \right) \end{matrix} \right\}$

- $x_a \geq x_a$ の場合

プログラムの条件分岐として記述する場合、これだけ複雑になると分かりづらくなるため、もっと単純化してみる。
Y方向の距離：
${\Delta}_y = \left| y_b - y_a \right|$
移動先Y座標における等距離マス群の幅の半分（遊び幅）：
${\beta}_{x} = \lceil \frac{ {\Delta}_{y} }{2} \rceil$
X方向の距離：
${\Delta}_x = \left\{ \begin{matrix} {\Delta}_y mod 2 = 0 & & & & & \rightarrow & \left| x_b - x_a \right| \\ {\Delta}_y mod 2 \not= 0 & , & y_a mod 2 = 0 & , & x_b \lt x_a & \rightarrow & \left| x_b - x_a \right| \\ {\Delta}_y mod 2 \not= 0 & , & y_a mod 2 = 0 & , & x_b \geq x_a & \rightarrow & \left| x_b + 1 - x_a \right| \\ {\Delta}_y mod 2 \not= 0 & , & y_a mod 2 \not= 0 & , & x_b \lt x_a & \rightarrow & \left| x_b - 1 - x_a \right| \\ {\Delta}_y mod 2 \not= 0 & , & y_a mod 2 \not= 0 & , & x_b \geq x_a & \rightarrow & \left| x_b - x_a \right| \end{matrix} \right\}$
距離：
$dist = \left\{ \begin{matrix} {\Delta}_x \leq {\beta}_x & \rightarrow & {\Delta}_y \\ {\Delta}_x \gt {\beta}_x & \rightarrow & {\Delta}_y + \left( {\Delta}_x - {\beta}_x \right) \end{matrix} \right\}$

さらに、HEXマップの端と端が隣接するトーラス状の非ユークリッド平面と考えた場合、X方向とY方向の距離計算をそれぞれ変える必要が出てくる。

[998,996]		[999,996]		[0,996]		[1,996]
	[998,997]		[999,997]		[0,997]		[1,997]
[998,998]		[999,998]		[0,998]		[1,998]
	[998,999]		[999,999]		[0,999]		[1,999]
[998,0]		[999,0]		[0,0]		[1,0]
	[998,1]		[999,1]		[0,1]		[1,1]
[998,2]		[999,2]		[0,2]		[1,2]
	[998,3]		[999,3]		[0,3]		[1,3]

その場合、以下の計算式を加える。
画面サイズ（X,Yともに2の倍数にする）：
$W_x = 1000, W_y = 1000$
Y方向のトーラス距離：
${\Delta }_{yT} = \frac{W_y}{2} - \left| \left( {\Delta}_y mod W_y \right) - \frac{W_y}{2} \right|$
X方向のトーラス距離：
${\Delta }_{xT} = \frac{W_x}{2} - \left| \left( {\Delta}_x mod W_x \right) - \frac{W_x}{2} \right|$
移動先Y座標における（トーラス平面上の）等距離マス群の幅の半分（遊び幅）：
${\beta}_{xT} = \lceil \frac{ {\Delta}_{yT} }{2} \rceil$
トーラス距離：
$distT = \left\{ \begin{matrix} {\Delta}_{xT} \leq {\beta}_{xT} & \rightarrow & {\Delta}_{yT} \\ {\Delta}_{xT} \gt {\beta}_{xT} & \rightarrow & {\Delta}_{yT} + \left( {\Delta}_{xT} - {\beta}_{xT} \right) \end{matrix} \right\}$

なでしこで実装

上記の計算式を元に、なでしこで距離計算プログラムを作成する。
動作の流れは、移動元と移動先の座標（X,Y）を入力後、計算結果が表示されるというものである。
なお、できるだけ簡素にするため範囲内の整数か否かの入力チェックは行わない。

画面サイズXとは数値
画面サイズYとは数値
移動元Xとは数値
移動元Yとは数値
移動先Xとは数値
移動先Yとは数値
ユークリッド距離Xとは数値
ユークリッド距離Yとは数値
トーラス距離Xとは数値
トーラス距離Yとは数値
遊び幅Xとは数値
ヘキサ距離とは数値
計算結果とは文字列

画面サイズXは1000
画面サイズYは1000

▲開始地点

「移動元のX座標を入力してください。」で尋ねる
移動元Xはそれ
「移動元のY座標を入力してください。」で尋ねる
移動元Yはそれ
「移動先のX座標を入力してください。」で尋ねる
移動先Xはそれ
「移動先のY座標を入力してください。」で尋ねる
移動先Yはそれ

ユークリッド距離Yは（移動先Y−移動元Y）の絶対値
トーラス距離Yは（画面サイズY÷2−（（ユークリッド距離Yを画面サイズYで割った余り−画面サイズY÷2）の絶対値））

もしトーラス距離Yを2で割った余りが0ならば
	ユークリッド距離Xは（移動先X−移動元X）の絶対値
	遊び幅Xはトーラス距離Y÷2
違えば
	もし移動元Yを2で割った余りが0ならば
		もし移動先Xが移動元X未満ならば　ユークリッド距離Xは（移動先X−移動元X）の絶対値
		違えば　ユークリッド距離Xは（移動先X＋1−移動元X）の絶対値
	違えば
		もし移動先Xが移動元X未満ならば　ユークリッド距離Xは（移動先X−1−移動元X）の絶対値
		違えば　ユークリッド距離Xは（移動先X−移動元X）の絶対値
	遊び幅Xは（トーラス距離Y÷2）を切り上げ

トーラス距離Xは（画面サイズX÷2−（（ユークリッド距離Xを画面サイズXで割った余り−画面サイズX÷2）の絶対値））

もしトーラス距離Xが遊び幅X以下ならば　ヘキサ距離はトーラス距離Y
違えば　ヘキサ距離はトーラス距離Y＋（トーラス距離X−遊び幅X）

計算結果は「」
計算結果に「移動元（」を追加
計算結果に移動元Xを追加
計算結果に「,」を追加
計算結果に移動元Yを追加
計算結果に「）→移動先（」を追加
計算結果に移動先Xを追加
計算結果に「,」を追加
計算結果に移動先Yを追加
計算結果に「）の距離＝」を追加
計算結果にヘキサ距離を追加
計算結果を表示

「続けますか？」で二択
もし　それがいいえならば　終了

「開始地点」に飛ぶ

HEXマップとは

距離計算式を作る

なでしこで実装

実行結果