mcfunction距離測定の各手法紹介

この記事はMinecraft Java Editionのコマンドおよび、基礎的な数学・プログラミングが分かる人向けのものです。

はじめに

マインクラフトのコマンドのような、三次元の座標を扱うロジックでは座標間の距離を扱いたいことがよくある(?)と思います。
座標Aと座標Bの二座標間の距離Dは、以下の数式で求められます。

D=\sqrt{(A_x-B_x)^2+(A_y-B_y)^2+(A_z-B_z)^2}

しかし、コマンドでは平方根（√）の演算をサポートしていないため、この数式の計算を簡単に行うことはできません。
そのため、これまでに様々な距離測定手法が考案されてきました。
この記事では、私が把握している距離測定手法を紹介していきます。

再帰移動法

おそらく最も素朴な手法です。
座標Aから座標Bに向かって、ローカル座標¹での移動を繰り返し、座標Bに到達するまでにかかった移動回数から距離Dを求めます。
この手法の精度²は、一度に移動する距離に依存します。
一度の移動距離を細かくして精度を上げるほど、また実行時の距離Dが長いほど、コマンドの実行回数が増えてしまうという欠点があります。
精度（移動距離の逆数）をN、実行時の距離DをM、と置いた時、計算量オーダー³はO(NM)となります。
つまり、コマンドの負荷は精度と実行時の距離に比例して増加します。

二分探索法

再帰移動法に二分探索アルゴリズム⁴を適用することでコマンド実行数を減らした手法です。
まず、座標Aの位置から適当な距離X以内に座標Bがあるかを判定します。
もし範囲内であればそのままの位置を保持し、範囲外であれば座標Bの方向に距離X進んだ位置へ移動します。
そこから今度は距離X/2以内に座標Bがあるかを判定し、範囲外であれば座標Bの方向に距離X/2進んだ位置へ移動、さらに距離X/4以内に・・・という風に、どんどん距離を半分にしながら処理を一定回数繰り返します。
移動するたびにその距離に応じた値をスコアへ加算していき、最終的なスコアから距離Dを求めます。

この方法には、距離X*2以上の距離を測れないという欠点があります。
距離Xを大きく設定するほど最大距離は増えますが精度が下がり、繰り返し回数を増やすほど精度は上がりますがコマンドの実行回数が増えます。
精度をN、最大距離をM、と置いた時、計算量オーダーはO(log NM)となります。
再帰移動法と比べるとlogの分計算量オーダーは低くなりますが、その代わり最大距離を設定する必要があります。

以下のライブラリで実装されています。
https://github.com/Ai-Akaishi/AiUtil

再帰&二分探索法

再帰移動法と二分探索法を組み合わせた手法です。
再帰移動法で大雑把な距離を求め、二分探索法で正確な距離を求めます。
精度を高めほど負荷が増える再帰移動法と、最大距離の制限がある二分探索法の欠点を補った手法と言えます。



これ以降に紹介する手法の計算量オーダーはO(1)です。

単位ベクトル法

座標をスコアに代入して計算する手法です。
まず、座標Aと座標BのXYZ各軸の差（差分ベクトル）と、座標Aから座標Bへの向きで原点から1ブロック進んだ座標（単位ベクトル）を求めます。
同じ向きのベクトル同士は相似関係にあるため、次の関係式が成り立ちます差分ベクトルの(X|Y|Z)成分 / 単位ベクトルの(X|Y|Z)成分 = 距離。
この関係式通りに計算をすることで距離Dを求めます。
なるべく精度を高めるため、またゼロ除算を避けるために、XYZのうち成分の絶対値が最も大きい軸を選んで計算を行います。
この方法には、座標をスコア代入する際に適当なn倍をする都合上、座標の絶対値がintの最大値/n以上だとスコアがオーバーフローしていまい、正確な測定ができなくなるという欠点があります。

近似execute幾何学法

execute幾何学⁵による鏡像変換操作⁶を利用して、座標Aから座標Bまでの距離Dを保ちつつ座標Bを座標Aの真上に移動させた座標βを求めます。
座標βの位置と座標Aの差がY軸だけになるので、引き算で距離Dを求めることができます。
このexecute幾何学による鏡像変換操作は近似であり誤差があります。
そのためかなり大雑把な精度になってしまう手法ではありますが、この座標変換の考え方は後述するexecute幾何学＆マクロ式でも使われています。

以下のリポジトリに実装例があります。
https://github.com/TUSB/TheUnusualSkyBlock/tree/1-17-1/data/calc/functions/geometry/distance

ディスプレイtransformation法

ディスプレイ系エンティティの変形を司るtransformationNBTの性質を利用して、序盤で紹介した平方根を含む数式を計算する手法です。
transformationの変形には、right_rotation, scale, left_rotation, translationをそれぞれ指定する分解形式と、16個の数値からなる変換行列で指定する行列形式の二種類の表現形式があります。
また、行列形式で指定しても分解形式に変換されて保存されるという仕様があります。
この変換処理の過程に距離の計算が含まれており、これを利用することで距離を求めます。

かなり高い精度で距離Dを求めることができます。
あまり軽量ではないディスプレイ系エンティティのNBT処理を利用していることや、ハッキーな動作を利用していることが一応の懸念点です。

以下のライブラリで実装されています。
https://github.com/Ai-Akaishi/AiMath/

[参考動画] https://www.youtube.com/watch?v=xHN4dmMP0EY

execute幾何学＆マクロ法

手前味噌ですが、自分としては一番汎用的だと考えている手法です。
近似execute幾何学式と同じ様に、距離を保ったまま位置関係を回転させて軸に揃え、その軸の値から距離を求めます。
近似を使わないため、ほぼ誤差なく座標変換操作をすることができ、高精度の距離を求めることができます。
マクロやNBTアクセスを利用していますが負荷もそこまで高くなく、高精度で最大距離制限もないため、使いやすいのではないかと考えています。

以下のライブラリで実装されています。
https://github.com/komaramune/km-distance

終わりに

各手法には様々な特性があるため、使われる場面によって最適な手法は変わってきます。
予想される最大距離や、必要な精度や、負荷の許容度などによって最適な手法を選択してください。

距離測定のような、通常のプログラムであれば数行で実装できる簡単な処理も、コマンドだと一筋縄ではいきません。
しかし、だからこそ試行錯誤の末に様々な手法が編み出されてきました。
そして、こうした手法を手軽に活用できるようにしたライブラリには、大きな需要があるはずです。
この記事を読んで、少しでもライブラリ開発に興味を持っていただけたら幸いです。

1. ローカル座標とは、^1 ^2 ^3のような表記の、所謂向き相対のことです。 ↩

2. ここで精度とは「実際の距離と測定値の誤差の小ささ」という意味とします。 ↩

3. 計算量オーダーとは、アルゴリズムの効率を測る指標であり、アルゴリズムに入力されるデータの変化に対する、大まかな計算回数の変化を表す数式です。 ↩

4. 二分探索アルゴリズムとは、求めたい値と適当な値の大小が比較できる場合に、探索する範囲を半分ずつに絞っていくことで、なるべく少ない比較回数で値を特定するアルゴリズムです。
   （例）「お前テストの点数50点以上だった？」「うん」「75点以上だった？」「いいや」「63点以上？」「うん」「69点以上？」「うん」「72点以上？」「いいや」「70点以上？」「いいや」「じゃあ69点だろ」 ↩

5. execute幾何学とは、executeのサブコマンドを組み合わせて、複雑な幾何学的操作を行う技術群の俗称です。 ↩

6. 鏡像変換操作とは、ある平面を鏡のように見立て、点などを面対象の位置に移動させる操作です。
   [参考] https://wiki3.jp/minecraft_technology/page/11 ↩