洞窟生成アルゴリズムの補足

今までの記事でマニアックなので省略したことを補足しておきます。

一つ目は、各接続口の座標をどこで定めるかという話です。

マップの座標軸は次のようになっており、接続口の座標は、X(またはZ)座標の小さい側の端の点で定めます。

そのため、一見同じような位置関係でも向きが違うために、通路の生成のされ方が異なることがあります。

例としてスナイパールームを見てみます。

f:id:fuji_luck:20201114182005p:plain — 生成途中のスナイパールーム

簡単のために図の右上以外の接続口はすべて通路を作らないようにマークされているとします。すると、右上の接続口から左上の接続口に向かって伸びていた通路は、元の場所から4区画分伸ばしたところで左上の接続口より先まで行ったことになり、どの接続口に向かうこともできなくなってしまうのでここで通路の生成は終了し袋小路を作ることになります。

しかし、同じ位置関係で座標軸だけが $90^\circ$ 回転している次の場合を考えると、この時点では伸びた通路が左上の接続口より先まで行っていないので、まだ通路の生成が止まらないことがわかります。

f:id:fuji_luck:20201114182734p:plain — 座標軸だけが先ほどと異なる

実際には左の部屋が邪魔するため、1区画だけ通路を伸ばしたらやはり袋小路になってしまうのですが、全く同じ位置関係でも向きが異なるために通路の生成のされ方が異なることがあると確認できました。

さて、ゲーム中ではX軸やZ軸を直接見ることはできませんが、実はその向きを間接的に知る方法があります。次の4枚の画像はすべて辺境の洞窟6階のもので、広場の位置関係は全く同じですが、これを見て気づくことはないでしょうか。

f:id:fuji_luck:20201114185359j:plain — 北

f:id:fuji_luck:20201114185437j:plain — 東

f:id:fuji_luck:20201114185927j:plain — 南

f:id:fuji_luck:20201114185942j:plain — 西

本編ではマップを開いたときに方角が表示されますが、西に行くほどX座標が小さく、北に行くほどZ座標が小さくなるという対応関係があります。確かに先ほどの4枚を見ると、画像の上側が北もしくは西になっているもののみ通路が生成されています。

なお、このフロアではキャップ最大数(CapVsHallProb)が $0$ ではないので、実際には次のように通路が生成されないこともあります。

また、チャレンジモードでは本編と違いマップを開くことができませんが、開始時のカメラの向きで方角を知ることができます。開始時の画面は、操作しなければおおよそ西南西の方角から撮ったものになっているのでそれで判別できます。

二つ目は、ゲーム内での平方根の計算の方法の話です。

このゲームでは $\sqrt{0} = 0$ というように $0$ については正確なのですが、正の数の平方根を計算するときに誤差が生じます。その原因を理解するために具体的な計算のアルゴリズムを記述します。

$a$ を正の数とします。初めに、このゲームでは $\sqrt{a} = a\times \frac{1}{\sqrt{a}}$ として計算していることを注意しておきます。したがって、 $\frac{1}{\sqrt{a}}$ の計算方法が大切です。

$\frac{1}{\sqrt{a}}$ を計算するために、まず、 $a=2^m \times (1+b)$ を満たす $m$ (整数)と $b$ ( $0\le b\lt 1$ )を求めます。これを用いると $\frac{1}{\sqrt{a}}$ は

$m$ が奇数のとき $2^{-\frac{m}{2}-\frac{1}{2}} \times \frac{\sqrt{2}}{\sqrt{1+b}}$

$m$ が偶数のとき $2^{-\frac{m}{2}-1} \times \frac{2}{\sqrt{1+b}}$

という式で表すことができ、ゲーム内ではこの式を用いて値を求めています。そのためには $\frac{\sqrt{2}}{\sqrt{1+b}}$ や $\frac{2}{\sqrt{1+b}}$ の値が必要となるのですが、このときにおそらく次のような近似がなされています。説明のためにグラフを描きます。

まず、横軸を $16$ 個の区間に分割します。

f:id:fuji_luck:20201114210154p:plain — 各区間は右端の点を含まない

次に各区間の真ん中における接線と、左端での値を用いて、曲線を直線で近似します。

f:id:fuji_luck:20201114210246p:plain — 赤い直線で近似

$\frac{\sqrt{2}}{\sqrt{1+b}}$ と $\frac{2}{\sqrt{1+b}}$ のそれぞれに対して、上のように近似してできる関数の式をあらかじめ用意しておくことで、与えられた $b$ の値に対して、 $\frac{\sqrt{2}}{\sqrt{1+b}}$ や $\frac{2}{\sqrt{1+b}}$ の近似値を容易に得られます。

この値がわかれば、上で書いたようにして $\frac{1}{\sqrt{a}}$ と $\sqrt{a}$ の値を順々に求めていくことができます。

以上が $\frac{1}{\sqrt{a}}$ 及び $\sqrt{a}$ の計算方法なのですが、見てわかるように、 $b$ の値が $\frac{1}{16}$ の整数倍やそれより少し大きいところでは値が小さくなってしまいます。逆に $\frac{1}{32}$ の奇数倍の近くでは値が大きくなってしまいます。そのため $\sqrt{1} \lt 1$ などといったことが起きてしまうのです。