distance

で、こんなもんかな…と思いつつ abagames.util.vector とか見てると、

  public float dist(Vector v) {
    float ax = fabs(x - v.x);
    float ay = fabs(y - v.y);
    if (ax > ay) {
      return ax + ay / 2;
    } else {
      return ay + ax / 2;
    }
  }

なんていうのを見つけた。へえ。確かに比較時の距離としての要件は満たすしゲームではこれで十分なのかな。そういえば他でも見たこともあるような気もするのでよく知られたテクニックなんだろう、私が知らなかっただけで。

直感的に思ったのが 2 で割っているのはどうかということ。片方が 0 の時はこの関数は正しい値を返す。それ以外の場合は常に大きい値を返す。ていうことは当り判定なんかで雑な評価をこの関数でしてから詳細な比較をすることもできるわけか。

それはそうと、 ax, ay の一次結合でできる限り実際の値に近い値を返す関数も考えてみたくなるのが人の常。この関数を呼ぶ際の二者の角度は、全ての角度が同程度にありえると仮定する。角度 \theta0<\theta<\pi/4 を考えて、常に X が Y より大きく、 X の値が 1 であるとしても一般性を損わない。一般化された dist 関数は 0 から 1 の実数 r を用いて、 ax + r * ay を返す。これらを用いて実際の距離 D と dist の返す距離 E は、

D=\frac{1}{\cos\theta}\\E=1+r\tan\theta

D と E の平均的な差を最小にするため最小二乗法を用いる。連続関数なので積分になることに注意。

\int^{\pi/4}_0(D-E)^2d\theta\\{}=[\tan\theta+\theta+r^2(\tan\theta-\theta)-\log(\frac{1+\sin\theta}{1-\sin\theta})-2r\log\cos\theta-\frac{2r}{\cos\theta}]^{\pi/4}_{0}\\{}=(1-\frac{\pi}{4})r^2-2(\sqrt{2}-\log\sqrt{2}-1)r+C

省略しすぎの感もあるけどめんどいので。難しい三角関数の不定積分は計算力皆無の私にゃムリなので (というか sin, cos とその自乗しかできない気がする) 岩波公式集の I より。最後の C は r に依存しない定数項、どうせ微分で消える。で、これを r で微分して 0 になる点を探すと、

r=\frac{\sqrt{2}-\log\sqrt{2}-1}{1-\pi/4}=0.31518825

最後のはもちろん近似。mimetex には approx だの sim は無い、みたい。で、得られた dist 関数をプロットしてみましょう。

plot [0:pi/4] f(x)=1/cos(x), g(x)=1+0.315*tan(x), h(x)=1+0.5*tan(x), g(x), h(x), f(x)

http://shinh.skr.jp/tmp/vect_dist.jpg

一番上の緑がオリジナルの r=0.5 の時、赤が r=0.315 、青が実際の距離の値です。まあこんなもんかというところ。

以下追記:

1/\cos(\theta) を Taylor 展開して二次まで持ってくると、 1+\theta^2/2 となる。\theta は割と小さい値域なので、 ay の自乗の項も用いた方が近似として良くなりそうだ。というか自乗の項だけあれば悪くない近似になりそう。と思って積分…はめんどいので maxima …も計算めんどそうな式をどばーと吐きやがったので、 gnuplot に数値的に fit させてみた。というわけで出てきた係数は 0.436521 。 ax+0.436521*ay*ay が距離の近似に良いという結論。

plot [0:pi/4] f(x)=1/cos(x), g(x)=1+0.315*tan(x), h(x)=1+0.5*tan(x), i(x)=1+0.5*tan(x)*tan(x), j(x)=1+0.436521*tan(x)*tan(x), f(x) t "sqrt(ax^2+ay^2)", i(x) t "ax+0.5*ay^2", j(x) t "ax+0.436521*ay^2"

http://shinh.skr.jp/tmp/vect_dist2.jpg

うん、非常に良い。ていうかゲームではこれで十分な気がする。ってこのへんまで書いてやっぱりどこかで見たことがある話題な気がするのでした…

あと、 0.5 もそんなに悪くないと思う。常に実際の値より少し高いという特性はそれなりに便利なはず。(あたり判定とかだとあたってるのにあたらなくて文句を言う人はあたっていなくてあたって文句を言う人より少ないだろうし)

もいっこ追記: ちなみに一次の項は fit した段階で限りなく 0 に近い値だったので(まああたりまえか) 捨ててます。

追記: OK やはり wo さんだった。自分の記憶力が怖い(あまりの腐りっぷりに)

http://morihyphen.hp.infoseek.co.jp/log/03_05.html (03_05_09)

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h