mcfunction距離測定の各手法紹介

:::note info
この記事はMinecraft Java Editionのコマンドおよび、基礎的な数学・プログラミングが分かる人向けのものです。
:::
# はじめに
マインクラフトのコマンドのような、三次元の座標を扱うロジックでは座標間の距離を扱いたいことがよくある(?)と思います。
`座標A`と`座標B`の二座標間の距離`D`は、以下の数式で求められます。
```math
D=\sqrt{(A_x-B_x)^2+(A_y-B_y)^2+(A_z-B_z)^2}
```
しかし、コマンドでは平方根（√）の演算をサポートしていないため、この数式の計算を簡単に行うことはできません。
そのため、これまでに様々な距離測定手法が考案されてきました。
この記事では、私が把握している距離測定手法を紹介していきます。

## 再帰移動法
おそらく最も素朴な手法です。
座標Aから座標Bに向かって、ローカル座標[^1]での移動を繰り返し、座標Bに到達するまでにかかった移動回数から距離Dを求めます。
この手法の精度[^2]は、一度に移動する距離に依存します。
一度の移動距離を細かくして精度を上げるほど、また実行時の距離Dが長いほど、コマンドの実行回数が増えてしまうという欠点があります。
精度（移動距離の逆数）をN、実行時の距離DをM、と置いた時、計算量オーダー[^3]は`O(NM)`となります。
つまり、コマンドの負荷は精度と実行時の距離に比例して増加します。
[^1]: ローカル座標とは、`^1 ^2 ^3`のような表記の、所謂`向き相対`のことです。
[^2]: ここで`精度`とは「実際の距離と測定値の誤差の小ささ」という意味とします。
[^3]: 計算量オーダーとは、アルゴリズムの効率を測る指標であり、アルゴリズムに入力されるデータの変化に対する、大まかな計算回数の変化を表す数式です。

## 二分探索法
再帰移動法に二分探索アルゴリズム[^4]を適用することでコマンド実行数を減らした手法です。
まず、座標Aの位置から適当な`距離X`以内に座標Bがあるかを判定します。
もし範囲内であればそのままの位置を保持し、範囲外であれば座標Bの方向に距離X進んだ位置へ移動します。
そこから今度は`距離X/2`以内に座標Bがあるかを判定し、範囲外であれば座標Bの方向に距離X/2進んだ位置へ移動、さらに`距離X/4`以内に・・・という風に、どんどん距離を半分にしながら処理を一定回数繰り返します。
移動するたびにその距離に応じた値をスコアへ加算していき、最終的なスコアから距離Dを求めます。
[^4]: 二分探索アルゴリズムとは、求めたい値と適当な値の大小が比較できる場合に、探索する範囲を半分ずつに絞っていくことで、なるべく少ない比較回数で値を特定するアルゴリズムです。
（例）「お前テストの点数50点以上だった？」「うん」「75点以上だった？」「いいや」「63点以上？」「うん」「69点以上？」「うん」「72点以上？」「いいや」「70点以上？」「いいや」「じゃあ69点だろ」

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

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

[^5]: execute幾何学とは、executeのサブコマンドを組み合わせて、複雑な幾何学的操作を行う技術群の俗称です。
[^6]: 鏡像変換操作とは、ある平面を鏡のように見立て、点などを面対象の位置に移動させる操作です。
[参考] https://wiki3.jp/minecraft_technology/page/11

## ディスプレイtransformation法
ディスプレイ系エンティティの変形を司る`transformation`NBTの性質を利用して、序盤で紹介した平方根を含む数式を計算する手法です。
`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

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

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