続・ UnityEngine.Random の実装と性質 ～ rotation(Uniform) の謎

はじめに

前回の記事 から調査が進んだので、 UnityEngine.Random の実装と性質についての追加情報をまとめました。

調査環境は Unity 2022.2.0b14 (Windows) です。

なお、調査は入出力の観測にて行っているため、実際の計算式や手順と異なる場合があります。数学的には等価だと思いますが、浮動小数点数の計算誤差や環境などによって結果がわずかに異なる場合があります。ご了承ください。

前回までのおさらい

前回の記事では、 InitState() ・ value ・ Range(int, int) ・ Range(float, float) について調査しました。

public class UnityRandom  
{  
    private uint x, y, z, w;  
  
    private uint Next()  
    {  
        uint t = x ^ x << 11;  
        x = y;  
        y = z;  
        z = w;  
        return w = w ^ w >> 19 ^ t ^ t >> 8;  
    }  
  
  
    public void InitState(int seed)  
    {  
        x = (uint)seed;  
        y = x * 1812433253 + 1;  
        z = y * 1812433253 + 1;  
        w = z * 1812433253 + 1;  
    }  
  
    public float value  
        => (Next() & 0x7fffffu) / 8388607.0f;  
  
    public int Range(int min, int max)   
        => min + (int)(Next() % (uint)(max - min));  
  
    public float Range(float min, float max)  
    {  
        float t = value;  
        return t * min + (1 - t) * max;  
    }  
}

InitState() についての補足

前回の記事で InitState() の調査を行った際、どうやって線形合同法のパラメータを求めたかを紹介します。

最初の内部状態を x_0 、次に遷移したときの内部状態を x_1 、さらにその次を x_2 とします。
このとき、遷移関数から以下の関係式が得られます。

\begin{aligned} x_1 &= m x_0 + a \\ x_2 &= m x_1 + a \end{aligned}

ここで、 m と a は線形合同法のパラメータであり、 m は乗算の定数、 a は加算の定数です。

この 2 式を組み合わせて、

\begin{aligned} x_2 - x_1 &= m(x_1 - x_0) \\ m &= (x_2 - x_1) (x_1 - x_0)^{-1} \end{aligned}

とすることで m を得ることができます。
なお、 (x_1 - x_0)^{-1} は通常の割り算ではなく 2^{n} を法とする 逆数を掛ける ことで計算します。今回は 32 bit なので n = 32 です。
プログラム的には以下のコードで求めることができます。

public static uint MultiplicativeInverse(uint x)  
{  
    if ((x & 1) == 0)  
        throw new ArgumentException("x must be odd");  
  
    uint y = x;  
    y = y * (2 - y * x);  
    y = y * (2 - y * x);  
    y = y * (2 - y * x);  
    y = y * (2 - y * x);  
  
    return y;  
}

m がわかればあとは簡単で、最初の式から、

a = x_1 - m x_0

とすれば a が求まります。

というわけで、連続する 3 つの値が観測できれば、線形合同法のパラメータそのものを復元できるといえます。

ところで、ビルドしたアプリやエディタの初期状態についてはよく分からない、としましたが、現在のスクリプトリファレンスを確認すると、

It is statically initialized with a high-entropy seed from the operating system, and stored in native memory where it will survive domain reloads.

とあるため、 /dev/random 的なもの (何らかの CSPRNG) で初期化されているようです。

以前の記事を書いたときには何も記載がなかったような気がします… こういった情報が増えていくのはありがたいことです。

今回の進捗

今回はそれ以外の応用的なメソッドについて調べてみました。

insideUnitCircle

単位円内のランダムな点を取る insideUnitCircle は、以下のように計算できます。

public Vector2 insideUnitCircle  
{  
    get  
    {  
        var angle = Range(0f, MathF.PI * 2);  
        var radius = MathF.Sqrt(Range(0f, 1f));  
        return new Vector2(  
            radius * MathF.Cos(angle),   
            radius * MathF.Sin(angle));  
    }  
}

念のためですが、 MathF は System 名前空間に生えている標準搭載のほうで、 Unity の Mathf とは異なります。
計算自体はほとんど変わりませんが、非 Unity 環境との互換性を考えて今回は MathF にしています。

insideUnitSphere

単位球内のランダムな点を取る insideUnitSphere は、以下のように計算できます。

public Vector3 insideUnitSphere  
{  
    get  
    {  
        var p = MathF.Asin(Range(-1f, 1f));  
        var t = Range(0, MathF.PI * 2);  
        var r = MathF.Cbrt(value);  
  
        return new Vector3(  
            r * MathF.Cos(p) * MathF.Cos(t),   
            r * MathF.Cos(p) * MathF.Sin(t),   
            r * MathF.Sin(p));  
    }  
}

p が xz 平面上の回転、 t が xy 平面上の回転、 r が中心からの距離です。
MathF.Cbrt は立方根を求める関数です。

onUnitSphere

単位球上のランダムな点を取る onUnitSphere は、以下のように計算できます。

public Vector3 onUnitSphere  
{  
    get  
    {  
        var p = MathF.Asin(Range(-1f, 1f));  
        var t = Range(0f, MathF.PI * 2f);  
  
        return new Vector3(  
            MathF.Cos(p) * MathF.Cos(t),   
            MathF.Cos(p) * MathF.Sin(t),   
            MathF.Sin(p));  
    }  
}

rotation

ランダムな Quaternion を取得する rotation は、以下のように計算できます。

public Quaternion rotation  
{  
    get  
    {  
        float x = Range(-1f, 1f);  
        float y = Range(-1f, 1f);  
        float z = Range(-1f, 1f);  
        float w = Range(-1f, 1f);  
  
        float reciprocalLength = 1 / MathF.Sqrt(x * x + y * y + z * z + w * w);  
        reciprocalLength *= w < 0 ? -1 : 1;  
  
        return new Quaternion(  
            x * reciprocalLength,  
            y * reciprocalLength,  
            z * reciprocalLength,  
            w * reciprocalLength);  
    }  
}

これの計算方法はスクリプトリファレンスに書いてあったので調査が簡単でした。
なお、 w は常に正の値をとるようです。

rotationUniform

よりランダムな (?) Quaternion を取得する rotationUniform は、以下のように計算できます。

public Quaternion rotationUniform  
{  
    get  
    {  
        float a = Range(0f, 1f);  
        float b = Range(0f, MathF.PI * 2);  
        float c = Range(0f, MathF.PI * 2);  
  
        float x = MathF.Sin(b) * MathF.Sqrt(1 - a);  
        float y = MathF.Cos(b) * MathF.Sqrt(1 - a);  
        float z = MathF.Sin(c) * MathF.Sqrt(a);  
        float w = MathF.Cos(c) * MathF.Sqrt(a));  
  
        float signOfW = w < 0 ? -1f : 1f;  
  
        return new Quaternion(  
            x * signOfW,  
            y * signOfW,  
            z * signOfW,  
            w * signOfW);  
    }  
}

これも計算手法がスクリプトリファレンスに書いてあったのですが、

Employs Hopf fibration to return a random Quaternion within a uniformly distributed selection space.

Hopf fibration とは……? こういう数学はさっぱりで Wikipedia を見ても全く分からなかったので、観察と直感で調べました。理論について詳しい方がいらっしゃればぜひご教授ください…

rotation と rotationUniform の違いについて

スクリプトリファレンス曰く、

(rotationUniform) Gives higher quality results compared to the more naive approach employed by rotation, though at a 40% performance cost.

とのことで、 rotationUniform は品質が良く、 rotation は高速な代わりに相対的に品質が良くない、とされています。
これは実際のところ、どの程度違うのでしょうか?

実際に点を描画してみる

rotation はぱっと見た感じ、一辺の長さが 2 の 4 次元超立方体内のベクトルを生成 → 正規化(4 次元超球上のベクトルに変換) → クォータニオンに、としている気がします。
となると、超立方体の角に相当する部分が濃くなりそうな雰囲気があります (これは 3 次元立方体 → 球の変換を考えれば理解しやすそうです) が、これが実際どのように影響するかというと……?

まずは、普通に見るとどうなるか見てみましょう。

これは、 Vector3.forward のベクトルをランダムに回転させた位置に点を打つ作業を行ったものです。左の赤いのが rotation, 右の緑が rotationUniform です。
まったく違いが判りません……。

それでは、 Quaternion.w < 0.01 のものだけ抽出するとどうなるでしょうか。

斜めから見た画像はこちらで、

上から見た画像はこちらです。

rotation のほうには赤い X のような偏りが見えています。これがもしかすると 4 次元超立方体の辺や角の部分かもしれません。
対して rotationUniform のほうにも濃い点ができていますが、これはおそらく正しいはずです。
理由を説明しましょう。 こちらの文献 曰く、 \lambda 軸周りに \theta だけ回転させるクォータニオンはこのような値を持っています。

\begin{split} x &= \lambda_x \mathrm{sin}(\theta / 2) \\ y &= \lambda_y \mathrm{sin}(\theta / 2) \\ z &= \lambda_z \mathrm{sin}(\theta / 2) \\ w &= \mathrm{cos}(\theta / 2) \\ \end{split}

ということは w \approx 0 の場合には \theta \approx 180 ° であるはずなので、 Vector3.forward を 180° 回転させた位置に (上から見た画像の画面下方向に) 集中するはず…です。

ヒストグラムにしてみる

ところで、直感的な映像による確認もよいですが、簡単な統計データとしても見てみましょう。

クォータニオンは一辺 -1 <= x <= 1 の範囲の 4 次元超立方体内に収まるので、一辺を 16 等分して 65536 個の領域に分割し、どの領域に何個クォータニオンが入ったかのヒストグラムをつくりました。
簡単のため Unity の AnimationCurve を悪用してグラフを作りました。

まず、以下が rotation のほうのヒストグラムです。 Unity が途中で線の描画を諦めてしまっている点にご留意ください…

次に、以下が rotationUniform のほうのヒストグラムです。

これを見ると、特に両端のエリア (Quaternion.x が -1 や +1 に近いエリア) において rotationUniform のほうが均等に分布していそうな印象を受けます。
また、 rotation では部分的に突出したデータが見られます。グラフの縦軸にも注目してみてください。

標準偏差を取ると、 rotation では 62.2241 ・ rotationUniform では 54.0865 となりました。 (なお、平均値は 16 です。)
数値的にも rotationUniform のほうがばらつきが少ないことが示唆されます。

次に、 eulerAngles を使って 3 次元にした場合のヒストグラムを見てみましょう。
同様に一辺 16 等分して 4096 個の領域に分割してヒストグラムを作成しました。

まず、 rotation のほうのヒストグラムです。

次に、 rotationUniform のほうのヒストグラムです。

こちらも、やはり rotationUniform のほうが突出した部分が少なく、円形の理想的な形に近い分布になっていそうです。

標準偏差を取ると、 rotation では 21.9124 ・ rotationUniform では 19.6578 となりました。 (同じく、平均値は 16 です。)

パフォーマンス

最後に、パフォーマンスの差について調べてみましょう。
私の環境 (12th Gen Intel(R) Core(TM) i7-12700F) で 2^{20} 個の Quaternion を生成するのにかかった時間は、 rotation は 61.167 ms ・ rotationUniform は 83.261 ms でした。
rotation のほうが 36 % ほど速く、スクリプトリファレンスに載っていた数値と概ね合致しました。

まとめ

以上を私見を交えてまとめると、

  • 正味の違いはほぼ分からないが、詳しく見ると rotation で偏りがわずかに見られる
  • 基本的には rotationUniform を使うべき
    • 何万オーダーで生成するような、パフォーマンス第一の場合は rotation を検討する

といった感じでしょうか。

ColorHSV()

ランダムな色を取得する ColorHSV() は、以下のように計算できます。

public Color ColorHSV(  
    float hueMin, float hueMax,  
    float saturationMin, float saturationMax,   
    float valueMin, float valueMax,   
    float alphaMin, float alphaMax)  
{  
    // note: (max, min) の順。実際は Lerp(value, min, max) のように実装されています  
    float h = Range(hueMax, hueMin);  
    float s = Range(saturationMax, saturationMin);  
    float v = Range(valueMax, valueMin);  
    float a = Range(alphaMax, alphaMin);  
  
    Color HsvToRgb(float h, float s, float v, float a)  
    {  
        float hStar = h * 6;  
  
        float c = v * s;  
        float x = c * (1 - Math.Abs(hStar % 2f - 1f));  
  
        return hStar switch  
        {  
            >= 0 and  
            < 1 => new Color((v - c) + c, (v - c) + x, (v - c) + 0, a),  
            < 2 => new Color((v - c) + x, (v - c) + c, (v - c) + 0, a),  
            < 3 => new Color((v - c) + 0, (v - c) + c, (v - c) + x, a),  
            < 4 => new Color((v - c) + 0, (v - c) + x, (v - c) + c, a),  
            < 5 => new Color((v - c) + x, (v - c) + 0, (v - c) + c, a),  
            < 6 => new Color((v - c) + c, (v - c) + 0, (v - c) + x, a),  
            _ => throw new ArgumentException()  
        };  
    }  
  
    return HsvToRgb(h, s, v, a);  
}

ほぼ Wikipedia に載っているものと同じです。

ちなみに、これは UnityCsReference で 実際のコードを確認する こともできます。

補足・雑記など

その他、気付いたことや雑記などです。

浮動小数点数の計算について

今回実験をしていて気が付いたのですが、実行環境が Unity 上 (mono) か Visual Studio 上 (dotnet) かで出力される浮動小数点数の値が微妙に異なる場合があるようです。
Unity 上では絶対に合わなかったテストケースが dotnet に移植したプロジェクトでは合った場合があったためです。

全く根拠のない推測ですが、 mono のほうはいわゆる -ffast-math のようなアグレッシブな最適化をしているのではないかと思います。

UnityEngine.Random に値を仕込む方法

調査にあたっては、まず UnityEngine.Random から任意の値を出力できるようにする必要があります。いわゆる「乱数調整」みたいなものです。これをどうやって行ったのかを記載しておきます。

Random の内部構造は Xorshift であることは本記事の冒頭や前回の記事でお伝えした通りです。
Xorshift は内部状態をそのまま吐き出すタイプなので、かなり楽に調整ができます。

具体的には、

  1. 4 個の内部状態に欲しい値をそれぞれセットする
  2. 乱数を 4 回巻き戻す

という手順を通すだけです。

Xorshift を巻き戻す処理は具体的には以下で行えます。どうやって求めたかは こちらの記事 を参照してください。

public void Prev()  
{  
    w ^= z ^ z >> 19;       // t ^ t >> 8  
    w ^= w >> 8; w ^= w >> 16;  
    w ^= w << 11; w ^= w << 22;     // w = x  
    uint tx = w;  
    w = z;  
    z = y;  
    y = x;  
    x = tx;  
}

そして、こういう感じで内部状態をセット + 巻き戻し処理を行います。
HackState() は欲しい値を 4 つセットすると、それに対応する内部状態を返してくれます。

public static uint[] HackState(Span<uint> values)  
{  
    var emu = new UnityRandom() { 
        x = values[0], 
        y = values[1], 
        z = values[2], 
        w = values[3] };  
    emu.Prev();  
    emu.Prev();  
    emu.Prev();  
    emu.Prev();  
    return new uint[] { emu.x, emu.y, emu.z, emu.w };  
}

あとは、リフレクションで内部状態を書き込むメソッドを作成して Random.state = state; で書き込めば、 UnityEngine.Random の出力値を 4 つぶんまではコントロールできます。

public static UnityEngine.Random.State SetState(uint[] values)  
{  
    // ボックス化が必要なので object で受ける  
    object state = new UnityEngine.Random.State();  
  
    var flags = BindingFlags.NonPublic | BindingFlags.Instance | BindingFlags.SetField;  
  
    state.GetType().GetField("s0", flags).SetValue(state, (int)values[0]);  
    state.GetType().GetField("s1", flags).SetValue(state, (int)values[1]);  
    state.GetType().GetField("s2", flags).SetValue(state, (int)values[2]);  
    state.GetType().GetField("s3", flags).SetValue(state, (int)values[3]);  
  
    return (UnityEngine.Random.State)state;  
}

おわりに

というわけで、現状存在するすべてのメソッド・プロパティの挙動を調べることができました。満足です。
(浮動小数点数の下位桁が微妙にずれる問題はありますが、めちゃくちゃ面倒なので見なかったことに……)

付録として、上記のソースをまとめたものを添付しておきます。

UnityRandom.cs

JDK 17 における擬似乱数生成と LXM ファミリについて

はじめに

2021/09/14 に GA となった JDK 17 では、 擬似乱数生成まわりの強化 が行われました。

更新点を見ると、 LXM という新しい擬似乱数生成器が実装されているようです。
しかし、このアルゴリズムについて聞いたことがなかったため (実装当時) 、調べてみました。

ついでに、このアルゴリズムが導入されるきっかけとなった JEP 356: Enhanced Pseudo-Random Number Generators についてもある程度解説しようと思います。

本記事では、特に注釈がなければ下記環境を使用して検証しています。

openjdk 17.0.6 2023-01-17
OpenJDK Runtime Environment Temurin-17.0.6+10 (build 17.0.6+10)
OpenJDK 64-Bit Server VM Temurin-17.0.6+10 (build 17.0.6+10, mixed mode, sharing)

JEP 356 の要約

そもそもどういった提案で何が追加されたのか、のざっくりとしたお話です。
原文は JEP 356 を参照してください。

旧 API では、擬似乱数生成器ごとの互換性が微妙だったり (SplittableRandom は Random を継承していないので代入できないなど) 、各生成器で nextDouble() などをそれぞれが独自に (コピペで) 実装していてよろしくなかったり、といった問題がありました。

また、 SplittableRandom には "弱点" が見つかっており、新しい別のアルゴリズムを導入して問題を回避したいニーズがありました。
JEP 内ではこの弱点について具体的に触れられていませんが、おそらく こちらの文献 *1 を指しているものと思います。
問題点の説明の部分を要約します。 SplittableRandom は内部に gamma という定数を持っており、 split() で新しいインスタンスを生成した際に自身と異なる gamma を設定することで別々の乱数列を得る仕組みになっています。この gamma は乱数の品質に深くかかわっており、 "弱い" gamma を設定すると品質が下がってしまいます。 Java では弱い gamma を弾くアルゴリズムが入っているのですが、それでも処理しきれない値 ( 2 ^ {64} / k や 2 ^ {s} m + 1 など) が存在しており、それが選ばれた場合に乱数の品質が下がってしまう、という問題がありました。

問題への対応だけではなく、ポジティブな面もあります。
擬似乱数生成器によっては split() や jump() といった異なる乱数列を得る仕組みを持つものがあり、並列実行において便利に扱うことができます。前者は SplittableRandom 、後者は xoroshiro128+ アルゴリズムなどが該当します。
この機能を統一的に扱うことができる API を用意したい、というニーズがありました。

インタフェースの追加

以下のインタフェースが提供されます。箇条書きは実装関係を示しています。

これらについて、ざっくりと解説をしていきます。 (網羅しているわけではないので、詳細はそれぞれリンク先の API ドキュメントから確認してください。)

RandomGenerator

擬似乱数生成器としての基底のインタフェースです。基本的に nextLong() を実装すれば nextDouble() などはデフォルト実装で生やしてくれます。

これのおかげで、擬似乱数生成器を独自実装する際に Random を継承する必要がなくなりました。不要な内部状態などがついてこなくなります。

StreamableGenerator

異なる乱数列を出力するインスタンスを無限に生成する rngs() をサポートします。

rngs() は Stream<RandomGenerator> 、つまり擬似乱数生成器のインスタンスが得られるストリームを返します。何に使うのかというと、 (特にマルチスレッドにおける) 並列実行です。

本質的に乱数生成は内部状態の変更を伴います。したがって、スレッド間でインスタンスを共有してしまうと、内部状態が正しく更新されず出力が崩壊したり、ロックで時間と手間がかかったりと良いことがありません。
(ちなみに Random はロックをかけるほうの手法を採用しており、代償としてオーバーヘッドがかなり大きかったのです。)
そこで、各スレッドで別々のインスタンスを利用することによって、速度と品質を同時に得ることができる、というわけです。従来の ThreadLocalRandom に近い雰囲気です。

ただ、各スレッド用の個別インスタンスを作る際、単純にクローンを作ったり適当なシードを与えて初期化したりした場合、運が悪いと出力される乱数列が重複してしまい、ランダムではなくなってしまう (相関が生まれる) 可能性があります。
これを回避するアプローチは 2 つあり、それらが SplittableGenerator, JumpableGenerator にあたります。

SplittableGenerator

従来 SplittableRandom で使えた機能の一般化である split() をサポートします。
(実際に SplittableRandom もこのインタフェースを実装するようになりました。)

内部状態とは別にある種の定数を持ち、この定数をインスタンスごとに変えることで乱数列自体を別々にするしくみを持ちます。
定数が異なれば、初期の内部状態 (≒シード) が完全一致していてもそれぞれ異なる乱数列が出力されるため、乱数の重複を回避できます。

ちなみに、現在 SplittableGenerator を実装している擬似乱数生成器が split() で定数をどうやって決めているのかというと、 nextLong() ベースでランダムに決定しているようです。
つまり奇跡が起こって親子で定数が一致する可能性も 0 ではありませんが、そこは楽観的に決定しているようです。
もっとも、そうなる確率は天文学的に低く、もしそうなっても内部状態が離れていれば実用上重複しないので、心配する必要はありません。
具体例を挙げると、 L64X128MixRandom で同じ乱数列に入る確率は 2 ^ {-63} 、かつ親との距離が \pm 2 ^ {64} 以内になる確率は約 2 ^ {-190} ですので、 GUID の衝突よりもはるかに低確率です。

JumpableGenerator

固定長ジャンプを高速に行う jump() をサポートします。

jump() は、 nextLong() を大量に ( 2 ^ {64} や 2 ^ {128} といったオーダーで) 呼び出したのと同じ状態遷移を高速に得られる機能です。
これによって、そのジャンプ距離と同じ回数 nextLong() などを呼び出さない限りは乱数列が重複しない保証を得る (そんな回数は現実的に呼び出せないので事実上独立した乱数列を得る) ことができます。

通常の乱数列を 1 本の長いテープに例えると、 SplittableGenerator は「異なるテープを何本も用意する」、 JumpableGenerator は「1 本のテープを等間隔に分割して使う」といったイメージです。
こう書くと JumpableGenerator のほうは 1 本あたりの長さ (≒周期; 使える量) が減ってしまって良くないように思えるかもしれませんが、切ったとしてもそれぞれ 2 ^ {64} 個分の長さはあって現実的に使いきれる量ではないので、心配は無用です。
また SplittableGenerator に比べると品質のばらつきが比較的少ない利点もあります。前述した「 SplittableRandom で gamma 値によっては品質が下がってしまう問題」のようなことが起こりにくいです。

LeapableGenerator / ArbitrarilyJumpableGenerator

JumpableGenerator の拡張として、 LeapableGenerator と ArbitrarilyJumpableGenerator も存在します。

LeapableGenerator は、 jump() よりも長距離の固定長ジャンプを行う leap() もサポートします。
ArbitrarilyJumpableGenerator は、さらに任意長のジャンプを行える jump(distance) もサポートします。

これらの見分けが難しいかもしれませんが、基本的にはジャンプ距離の違いと、距離を指定できるかどうかです。

  • JumpableGenerator : 中距離の固定長ジャンプ (例: 2 ^ {64})
  • LeapableGenerator : ＋長距離の固定長ジャンプ (例: 2 ^ {128})
  • ArbitrarilyJumpableGenerator : ＋任意長ジャンプ

LeapableGenerator の存在意義は、擬似乱数生成器の分割自体を並列化することにあります。
jumps() で n 個のインスタンスを生成するとき、 jump() を n 回連続で呼ぶ必要があり、 O(n) で時間がかかることになります。この時、最初に leap() でいくつかの子インスタンスを作り、そこから jump() で孫インスタンスを切り出すようにすれば処理時間が (n / leap() で作ったインスタンスの数) となり、最善を尽くせば O(\sqrt{n}) に短縮することができます。先のテープのたとえで言えば、最初にテープを何本かに切り分けて、それらを重ねてまとめて切っていくイメージです。

ちなみに、固定長のジャンプ距離については厳密な指定はなく、周期を p として jump() が 2 ^ {64} または \sqrt{p} ぐらい、 leap() が 2 ^ {128} ぐらい、といった目安が参考として記載されています。実用上は特に気にする必要はありませんが、もし擬似乱数生成器を実装する側になった場合は参考にしてください。

なお、 2023/03/17 時点では ArbitrarilyJumpableGenerator を実装している擬似乱数生成器はありません。

JumpableGenerator シリーズの注意点

注意点として、 JumpableGenerator において rngs() や jumps() で作成したインスタンスからさらに rngs() などで孫を作ってはいけないことが挙げられます。
jumps() は、内部的には

  1. 自身のコピーを作る
  2. 自身を jump() させる
  3. コピーを返す

といったことを繰り返しています。
ここで、子でも rngs() してしまうと最初の親と子の jump() 呼び出し回数 (距離) が一致し、擬似乱数生成器の内部状態がかなり近い (最悪一致する) 状態となり、結果として親子でほぼ同一の乱数列を永遠に出力し続けるようになってしまいます。
jumps() の戻り値が Stream<JumpableGenerator> ではなく Stream<RandomGenerator> になっているのはそのためで、孫の作成を自然と防止するようにできています。

孫が欲しい場合 (例えば、単一スレッドで複数の乱数列が必要なものをさらにマルチスレッド処理する場合など) は LeapableGenerator の leaps() を使いましょう。大本 → leaps() → 子供 → jumps() → 孫 、といった感じで生成できます。もちろん、 leaps() を繰り返して子孫を作ると同じ問題が発生します。 leaps() と jumps() を使い分けるのがポイントです。

なお、 SplittableGenerator の splits() では子孫で衝突する問題は事実上発生しません。一つの乱数列を共有している JumpableGenerator とは異なり、乱数列自体がインスタンスごとに異なるためです。

実装例

インタフェースが分かったところで、自分でアルゴリズムを実装する際の例を紹介します。
今回は Seiran128 アルゴリズムを実装してみました。
このアルゴリズムは LeapableGenerator の要件を満たしているので、それでざっくり実装してみます。

package Java17Test.src;  

import java.nio.ByteBuffer;  
import java.security.SecureRandom;  
import java.util.concurrent.atomic.AtomicLong;  
import java.util.random.RandomGenerator.LeapableGenerator;  

public class Seiran128 implements LeapableGenerator {  

    private long state0, state1;  

    private static final AtomicLong SEEDER = new AtomicLong(ByteBuffer.wrap(SecureRandom.getSeed(8)).getLong());  

    public Seiran128() {  
        this(SEEDER.getAndAdd(0x9e3779b97f4a7c15L));  
    }  

    public Seiran128(long seed) {  
        state0 = seed = seed * 6364136223846793005L + 1442695040888963407L;  
        state1 = seed = seed * 6364136223846793005L + 1442695040888963407L;  
    }  

    public Seiran128(long s0, long s1) {  
        if (s0 == 0 && s1 == 0) {  
            long seed = SEEDER.getAndAdd(0x9e3779b97f4a7c15L);  
            s0 = seed = seed * 6364136223846793005L + 1442695040888963407L;  
            s1 = seed = seed * 6364136223846793005L + 1442695040888963407L;  
        }  

        state0 = s0;  
        state1 = s1;  
    }  

    @Override  
    public void jump() {  
        internalJump(new long[] { 0xF4DF34E424CA5C56L, 0x2FE2DE5C2E12F601L });  
    }  

    @Override  
    public double jumpDistance() {  
        return 0x1p64;  
    }  

    @Override  
    public long nextLong() {  
        long s0 = state0, s1 = state1;  
        long result = Long.rotateLeft((s0 + s1) * 9, 29) + s0;  

        state0 = s0 ^ Long.rotateLeft(s1, 29);  
        state1 = s0 ^ s1 << 9;  

        return result;  
    }  

    @Override  
    public LeapableGenerator copy() {  
        return new Seiran128(state0, state1);  
    }  

    @Override  
    public void leap() {  
        internalJump(new long[] { 0x185F4DF8B7634607L, 0x95A98C7025F908B2L });  
    }  

    @Override  
    public double leapDistance() {  
        return 0x1p96;  
    }  

    private void internalJump(long[] jumpTable) {  
        long t0 = 0, t1 = 0;  

        for (int i = 0; i < 2; i++) {  
            for (int b = 0; b < 64; b++) {  
                if ((jumpTable[i] & (1L << b)) != 0) {  
                    t0 ^= state0;  
                    t1 ^= state1;  
                }  
                nextLong();  
            }  
        }  

        state0 = t0;  
        state1 = t1;  
    }  
}

nextDouble() などは RandomGenerator のデフォルト実装としてついてくるので基本的には nextLong() だけ、 LeapableGenerator を実装する場合は対応する jump() ・ leap() などを実装すればよいです。

ただ、 RandomGenerator.of("Seiran128") でインスタンス化できるか試してみましたが、どうもうまくいきませんでした。
内部実装を見た限りでは internal なアノテーションを設定する必要がありそうで、今のところ外部からの追加は難しそうです。
(もしうまくやる方法をご存じの方がいらっしゃればぜひ…)

LXM アルゴリズムについて

さて、いよいよ本題に入ります。
JDK 17 では以下の擬似乱数生成器 (アルゴリズム) が追加されています。 ソースコードはこちらを参照してください。

  • Xoroshiro128PlusPlus
  • Xoshiro256PlusPlus
  • L32X64MixRandom
  • L64X128MixRandom
  • L64X128StarStarRandom
  • L64X256MixRandom
  • L64X1024MixRandom
  • L128X128MixRandom
  • L128X256MixRandom
  • L128X1024MixRandom

RandomGenerator.of("Xoshiro256PlusPlus") といった形でアルゴリズム名を指定することでインスタンスを生成することができます。

xoroshiro128++ と xoshiro256++ については 作者のサイトでの説明 や論文 *2 が存在しますが、 LXM ファミリは初出当時は jdk リポジトリや API ドキュメント以外では記述のないアルゴリズムでした。 2023 年現在は論文 *3 が発表されており、詳細を知ることができます。

以降は、 java.util.random パッケージの "The LXM Family of Random Number Generator Algorithms" の項 をベースに紹介していきます。

LXM は、

  • L : LCG → Linear Congruential Generator; 線形合同法
  • X : XBG → Xor-Based Generator; xoshiro/xoroshiro アルゴリズム
  • M : Mixer → 上の 2 つを混ぜること (いわゆる出力関数)

という略語です。
名前の通り、内部に線形合同法と xo(ro)shiro の 2 つのアルゴリズムを独立して持ち、出力の際にそれらを "mix" することによって高品質な乱数出力を実現する設計となっています。

「あの悪名高い線形合同法？怪しい…」と思われた方もいらっしゃるかもしれませんが、線形合同法も使い方を工夫したりこのように他の擬似乱数生成器と組み合わせたりすることで高品質な乱数を生成することができます。使い方を工夫した例でいえば PCG が有名です。

L64X128MixRandom という暗号めいた名前は、それぞれどんなアルゴリズムを組み合わせているかを示しています。

name LCG (bits) XBG (algorithm) Mixer (algorithm)
L32X64MixRandom 32 xoroshiro64 (32-bit) mixLea32(s+x0)
L64X128MixRandom 64 xoroshiro128 mixLea64(s+x0)
L64X128StarStarRandom 64 xoroshiro128 starstar(s+x0)
L64X256MixRandom 64 xoshiro256 mixLea64(s+x0)
L64X1024MixRandom 64 xoroshiro1024 mixLea64(s+x0)
L128X128MixRandom 128 xoroshiro128 mixLea64(sh+x0)
L128X256MixRandom 128 xoshiro256 mixLea64(sh+x0)
L128X1024MixRandom 128 xoroshiro1024 mixLea64(sh+x0)

2021/09/12 当時は Package Summary の表 "LXM Multipliers" には概ね mixLea32 が使われていると書かれていますが、 これは誤りでした。 32 bit ベースの L32X64MixRandom だけが本当に mixLea32 で、それ以外の mixLea32 の行は実際は mixLea64 を使用しています。 2023/03/17 現在のドキュメントでは修正されています。

ちなみに、 LXM の xoroshiro128 のパラメータ (遷移関数のシフト/ローテート定数) は (24, 16, 37) であり、 Xoroshiro128PlusPlus の (49, 21, 28) とは異なります。
LXM のパラメータは公式実装における xoroshiro128** 、 Xoroshiro128PlusPlus のは xoroshiro128++ に基づいているようです。 (ちなみに xoroshiro128++ のほうが新型です。)
解析を行う場合に混同するとおかしくなるので注意が必要です。

L64X128MixRandom の必要最小限の実装は以下のようになります。なお、異常系や付加機能 (split() など) は省いています。

package Java17Test.src;  

import java.util.random.RandomGenerator;  

public class L64X128MixRandomClone implements RandomGenerator {  

    private final long lcgAdditive;  
    private long lcgState, xbgState0, xbgState1;  

    public L64X128MixRandomClone(  
        long lcgAdditive, long lcgState, long xbgState0, long xbgState1) {  
        this.lcgAdditive = lcgAdditive | 1;  
        this.lcgState = lcgState;  
        this.xbgState0 = xbgState0;  
        this.xbgState1 = xbgState1;  
    }  

    @Override  
    public long nextLong() {  

        // Mix  
        long r = lcgState + xbgState0;  
        r = (r ^ r >>> 32) * 0xdaba0b6eb09322e3L;  
        r = (r ^ r >>> 32) * 0xdaba0b6eb09322e3L;  
        r = (r ^ r >>> 32);  

        // LCG  
        lcgState = lcgState * 0xd1342543de82ef95L + lcgAdditive;  

        // XBG (xoroshiro)  
        long s0 = xbgState0, s1 = xbgState1;  
        s1 ^= s0;  
        s0 = Long.rotateLeft(s0, 24) ^ s1 ^ s1 << 16;  
        s1 = Long.rotateLeft(s1, 37);  
        xbgState0 = s0;  
        xbgState1 = s1;  

        return r;  
    }  
}

LCG パートでは、加算する定数 (lcgAdditive) をインスタンスごとに可変にすることで、 PCG と同様に異なる乱数列の生成 (split()) を可能にしています。
この部分での周期は 2 ^ {l} ( l は lcgState のビット数) です。

ちなみに、 L128 のバリアントでは 128 bit 乗算を行っている…　わけではなく、工夫によって 64 bit 乗算と 64 bit x 64 bit → 128 bit の乗算のみで計算できるようになっています。
まず、乗算する定数 0x1d605bbb58c8abbfd は 65 bit 、つまり上位 64 bit が 0x1 になっています。これによって、乗算結果の下位 64 ビット (lo) は lo * 0xd605bbb58c8abbfdL 、上位 64 bit (hi) は Math.unsignedMultiplyHigh(lo, 0xd605bbb58c8abbfdL) + hi * 0xd605bbb58c8abbfdL + lo として計算することができます。 64 bit ごとに区切った筆算をイメージすると分かりやすいです。

XBG パートは、既存の xo(ro)shiro 系アルゴリズムから出力関数 (+, **, ++) を除いた状態になっています。この部分での周期は 2 ^ {x} - 1 ( x は xbgState の合計ビット数) です。
-1 されているのは、 xbgState がすべて 0 の場合は何回遷移しても 0 のままになるので除外しているためです。実際のコンストラクタではすべて 0 で初期化されないように補正処理が行われています。

そして、全体としての周期は 2 ^ {l} \cdot (2 ^ {x} - 1) = 2 ^ {l + x} - 2 ^ {l} となります。具体的には、 L64X128MixRandom では 2 ^ {192} - 2 ^ {64} です。各パートの周期が互いに素なため、単に掛け合わせたぶんだけ周期になります。

Mix パートが出力関数です。これを状態更新前にやっているのは、内部状態の更新と並列に計算できるようにして高速化を狙っているためです。
この mixLea64 実装は SplittableRandom の出力関数に似ていますが、定数が異なっています。
シフトを 32 bit 単位に揃えたり乗算の定数を同じにすることでより高速化を図っているようです。
定数設定は ソースコードのコメント を見た限りでは Doug Lea 氏 (SplitMix の論文の共著者) によるものらしいです。詳しくは LXM の論文を参照して下さい。

ところで、現状の JDK 17 では LXM ファミリは SplittableGenerator だけ実装してありますが、 LeapableGenerator も実装することもできます。
例えば、 L64X128MixRandom における jump() と leap() はこのように実装できます。

    @Override  
    public void jump() {  
        internalJump(new long[] { 0x2bd7a6a6e99c2ddcL, 0x0992ccaf6a6fca05L });  
    }  

    @Override  
    public double jumpDistance() {  
        return 0x1p64;  
    }  

    @Override  
    public LeapableGenerator copy() {  
        return new L64X128MixRandomClone(lcgAdditive, lcgState, xbgState0, xbgState1);  
    }  

    @Override  
    public void leap() {  
        internalJump(new long[] { 0x360fd5f2cf8d5d99L, 0x9c6e6877736c46e3L });  
    }  

    @Override  
    public double leapDistance() {  
        return 0x1p96;  
    }  

    private void internalJump(long[] jumpTable) {  
        long x0 = 0, x1 = 0, s = lcgState;  

        for (int i = 0; i < 2; i++) {  
            for (long b = 1; b != 0; b <<= 1) {  
                if ((jumpTable[i] & b) != 0) {  
                    x0 ^= xbgState0;  
                    x1 ^= xbgState1;  
                }  
                nextLong();  
            }  
        }  

        lcgState = s;  
        xbgState0 = x0;  
        xbgState1 = x1;  
    }

基本的には xo(ro)shiro の ジャンプ関数実装 を使うだけです。
LCG パートに変更がないのは、ジャンプ距離が 2 ^ {64} や 2 ^ {96} と LCG の周期 ( 2 ^ {64}) の倍数になっており、 n 周して元の位置に戻ってきているためです。
理論上は任意長ジャンプの ArbitrarilyJumpableGenerator を実装することも可能ですが、そこそこ手間がかかるので割愛します。

これは完全に余談ですが、 L128X1024MixRandom のコンストラクタがあまりにもいかついので笑ってしまいました。

LXM ファミリの品質について

JEP 356 によれば、 LXM ファミリは TestU01 や PractRand といった著名な乱数性テストに合格するとのことです。
ただ、具体的にどう合格しているのか (TestU01 なら p-value の許容範囲はどこまでか・何個のシード値で試したか、 PractRand ならどのモードで何 TB まで確認したか) は書かれていませんでした。

そこで論文を見ると、TestU01 は BigCrush (最も多くのテストを行うモード) において、現行の L64X128MixRandom 相当の実装では複数の初期化方法について各 84 回ものテストを行い問題ないことを確認した、とあるようです。
また、 PractRand では 4 TB までテストにパスすることを確認した、ともありました。

ただ、確認したとされている PractRand のバージョンは 0.90 とのことで、現行の最新版 (0.94 及び pre-0.95) より前のものになっています。 v0.94 でいくつかのテストが追加されており、それで FAIL した擬似乱数生成器もそこそこあったので、懸念材料となります。

最も、単体でもほとんどの (線形性テストを除く) テストを突破しうる xo(ro)shiro に LCG を組み合わせたうえで mix までかけているので、大丈夫ではあるだろう、とは推測できます。
参考までに、 SplittableRandom は雑に言えば state += gamma; という足し算だけのシーケンスを mix を通して出力するだけのものです。それでも PractRand にパスしている ので、それより内部が複雑な LXM でも通るだろう、というのが理由です。

実際に確認してみましょう。 LXM ファミリの中で最も内部状態が小さい (つまり、問題が顕在化しやすいと思われる) L32X64MixRandom について、 PractRand v0.94 でテストを行いました。引数は -multithreaded -te 1 -tf 2 -tlmaxonly と、最も多くのテストをかけられるモードを指定しています。

RNG_test using PractRand version 0.94
RNG = L32X64MixRandomJava64, seed = 0x19aa8a23
test set = expanded, folding = extra

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 megabytes (2^29 bytes), time= 2.9 seconds
  no anomalies in 1220 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 gigabyte (2^30 bytes), time= 7.7 seconds
  no anomalies in 1293 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 gigabytes (2^31 bytes), time= 15.4 seconds
  no anomalies in 1368 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 gigabytes (2^32 bytes), time= 29.2 seconds
  no anomalies in 1448 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 gigabytes (2^33 bytes), time= 60.3 seconds
  no anomalies in 1542 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 gigabytes (2^34 bytes), time= 117 seconds
  no anomalies in 1636 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 32 gigabytes (2^35 bytes), time= 213 seconds
  no anomalies in 1716 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 64 gigabytes (2^36 bytes), time= 455 seconds
  no anomalies in 1807 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 128 gigabytes (2^37 bytes), time= 914 seconds
  no anomalies in 1902 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 256 gigabytes (2^38 bytes), time= 1667 seconds
  no anomalies in 1983 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 gigabytes (2^39 bytes), time= 3541 seconds
  no anomalies in 2058 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 terabyte (2^40 bytes), time= 7137 seconds
  no anomalies in 2132 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 terabytes (2^41 bytes), time= 14111 seconds
  no anomalies in 2194 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 terabytes (2^42 bytes), time= 29294 seconds
  no anomalies in 2255 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 terabytes (2^43 bytes), time= 59262 seconds
  no anomalies in 2313 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 terabytes (2^44 bytes), time= 119867 seconds
  no anomalies in 2366 test result(s)

時間の都合上 16 TB までの範囲ではありますが、異常は検出されませんでした。
(本来は 32 TB まで検定します。)
私の実験は完全ではありませんが、この範囲では少なくとも大丈夫だと言えそうです。

他の L64X128MixRandom などについては L32X64MixRandom よりも内部状態が大きくなっているので、それ以上の品質を確保できていると推測できます。

要約すれば、現時点では問題は検出されない、高品質な擬似乱数生成器である、ということです。

速度について

LCG と xo(ro)shiro を組み合わせて mix している関係上、それぞれ単体の xo(ro)shiro や SplittableRandom より遅くなっているのではないか、と推測できます。

実際に測ってみましょう。 1 GB (nextLong() 2 ^ {27} 回分) の乱数を生成するのにかかった時間 (実測値, ms) と、そこから計算した速度 (GB/s) を速い順に示します。環境は以下の通りです。

12th Gen Intel(R) Core(TM) i7-12700F

openjdk 17.0.6 2023-01-17
OpenJDK Runtime Environment Temurin-17.0.6+10 (build 17.0.6+10)
OpenJDK 64-Bit Server VM Temurin-17.0.6+10 (build 17.0.6+10, mixed mode, sharing)
Algorithm ms GB/s
SplittableRandom 226.00 4.42
Xoroshiro128PlusPlus 240.75 4.15
Xoshiro256PlusPlus 260.68 3.84
L64X128StarStarRandom 291.99 3.42
L64X128MixRandom 313.23 3.19
L64X256MixRandom 340.49 2.94
L64X1024MixRandom 362.83 2.76
L32X64MixRandom 386.71 2.59
L128X256MixRandom 575.84 1.74
L128X128MixRandom 578.84 1.73
L128X1024MixRandom 922.06 1.08
Random 2189.57 0.46
SecureRandom 75161.27 0.01

実測値のため環境や試行によってぶれる可能性がありますが、この結果を見ると、

  • ざっくりした傾向としては SplittableRandom > Xo(ro)shiro > LXM (L64 > L32 > L128) >> Random >>(越えられない壁)>> SecureRandom といった感じです。
    • 品質を犠牲にしてでも速度第一にする場合は SplittableRandom 、品質も大事な場合は Xoroshiro128PlusPlus がよさそうです。
  • LXM シリーズは、 L が小さい > X が小さい順に速い傾向がみられます。
    • 長い乗算が必要になるとさすがに遅くなるようです。
  • L32X64MixRandom は 32 bit ベースのため nextLong() 1 回あたり 2 回の遷移が必要になって結果として遅くなりそう、と予想していましたが、思っていたよりも速いようです。
  • 新しいアルゴリズムは、遅いものでも Random の 2.3 倍、速いものでは 9.0 倍ほど速くなっています。
    • Random が遅いのは、マルチスレッド対応のため都度ロックをかけているせいと推測しています。
  • (当然ながら) SecureRandom は非常に低速なため、必要な用途にだけ使用すべきでしょう。

といった感じです。

余談ですが、 C# に移植したバージョンで BenchmarkDotNet を使って nextLong() を測定してみると、以下のようになりました。

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22000.1574/21H2)
12th Gen Intel Core i7-12700F, 1 CPU, 20 logical and 12 physical cores
.NET SDK=7.0.200
  [Host]     : .NET 7.0.3 (7.0.323.6910), X64 RyuJIT AVX2
  DefaultJob : .NET 7.0.3 (7.0.323.6910), X64 RyuJIT AVX2
Method Mean Error StdDev Ratio RatioSD
Xoroshiro128PlusPlus 0.5713 ns 0.0114 ns 0.0107 ns 0.22 0.01
Shioi 0.5972 ns 0.0127 ns 0.0113 ns 0.23 0.00
L64X128StarStar 0.6012 ns 0.0145 ns 0.0136 ns 0.23 0.01
SplitMix 0.6013 ns 0.0168 ns 0.0157 ns 0.23 0.01
Seiran 0.6019 ns 0.0206 ns 0.0183 ns 0.23 0.01
Xoshiro256PlusPlus 0.7908 ns 0.0123 ns 0.0103 ns 0.30 0.00
L64X256Mix 0.8066 ns 0.0126 ns 0.0118 ns 0.31 0.00
L64X128Mix 0.8069 ns 0.0160 ns 0.0150 ns 0.31 0.01
L64X1024Mix 1.3266 ns 0.0239 ns 0.0212 ns 0.51 0.01
L128X128Mix 1.9699 ns 0.0253 ns 0.0225 ns 0.76 0.01
L128X256Mix 2.0528 ns 0.0215 ns 0.0202 ns 0.79 0.01
SystemRandomUnseeded 2.5940 ns 0.0259 ns 0.0242 ns 1.00 0.00
L32X64Mix 2.7956 ns 0.0280 ns 0.0262 ns 1.08 0.02
L128X1024Mix 4.5566 ns 0.0337 ns 0.0299 ns 1.76 0.03
SystemRandomSeeded 50.8033 ns 0.2700 ns 0.2525 ns 19.59 0.19

補足すると、 SplitMix は SplittableRandom 相当、 SystemRandom(Un)Seeded は .NET の System.Random にシードを与えた/与えなかったもの (それぞれ内部アルゴリズムが変化します) 、 Shioi と Seiran はいつもの私の自作アルゴリズムです。

微妙に結果は異なりますが、全体の印象としては同じ雰囲気です。

内部状態復元攻撃

これだけで記事 1 本文の分量になりそうだったので、後日別の記事に…できれば…いいな…。
L32 ・ L64 シリーズについては攻撃の目処が立っています。

その他の改善点

全体の話に戻します。

乱数を加工して使いやすくするメソッドもいくつか追加・改善されています。

nextDouble(double bound) / nextDouble(double origin, double bound)

nextDouble(double bound) と nextDouble(double origin, double bound) が追加され、一定範囲への変換が楽になりました。 nextFloat() も同様です。
今まではストリームを返すほう doubles() でだけ使えていたのが nextDouble() でも使えるようになった形になります。
「そんなの nextDouble() * (bound - origin) + origin すればいいだけなのでは？」と思われた方もいると思いますが、この方法には落とし穴があります。このメソッドの戻り値は origin <= value < bound を意図していますが、前述の式では浮動小数点数の丸め誤差によってごくまれに value == bound となってしまう場合があります。今回追加されたメソッドでは、それをよしなに制御して範囲内になるように保証してくれます。

nextExponential()

指数分布 に従う乱数を生成する nextExponential() が追加されています。

nextGaussian(double mean, double stddev)

また、 正規分布 に従う乱数を生成する nextGaussian() に nextGaussian(double mean, double stddev) が追加され、平均と標準偏差を自分で計算する必要がなくなりました。
さらに、内部実装が変わってパフォーマンスも改善しています。以前は Polar Method で実装されていましたが、 改良 Ziggurat アルゴリズム に変更されてより高速化しています。
2 ^ {24} 回の呼び出しを実測してみたところ、 OpenJDK 64-bit 16.0.2 では 918 ms, 17 では 932 ms となっており、手元の環境ではなぜかあまり変化がなかったようです。あれ……？
(ちなみに、 nextExponential() も同じアルゴリズムで実装されています。)

RandomGeneratorFactory

RandomGeneratorFactory というファクトリも追加されています。これを使うと、アルゴリズム名からインスタンスを生成したり、性質に応じて (例えば内部状態が 256 bit 以下のものを) 抽出したりすることができます。
また、 RandomGeneratorFactory.getDefault().create() でアルゴリズムを明示せずにインスタンスを生成することもできます。現行実装では L32X64MixRandom が選ばれるようです。

なぜ L32X64MixRandom がデフォルトになったのかは正直よくわかりません……
L32X64MixRandom は 32 bit 環境に特化したものであり周期が短めで、一度に 64 bit 必要な乱数生成 (nextDouble() や nextLong() など) や大規模な並列実行には向いていません。
L64X128MixRandom が無難でよかったのでは、と思ってしまいます。

余談・リリース以降の更新点について

L32X64MixRandom#nextLong() の不思議な実装については、前回の記事をご覧ください。

コミットログを見ると、一時期 L32X64MixRandom と L128X256MixRandom の初期化周りで問題があったらしいですが、現在は解消されています。

また、 nextGaussian() と nextExponential() の分布が正しくなかった 問題もあったようですが、こちらも解消されています。

アルゴリズムの選び方

LXM アルゴリズムが大量に追加されていてどれをどう使えばいいか分からなくなりそうだったので、 API ドキュメントの内容をざっくり私見も含めつつまとめると、優先度順に

  1. セキュリティ関連・シード値など 予測不可能性が必須 → SecureRandom
  2. 32 bit 環境 → L32X64MixRandom
  3. 高速性 が重要 → Xoroshiro128PlusPlus
  4. 小～中規模の並列処理 がしたい → L64X256MixRandom
  5. 超大規模の並列処理 がしたい → L128X256MixRandom
  6. 多次元均等分布性 が重要 → L64X1024MixRandom
  7. とくに要件がない、 とりあえず動けばいい → L64X128MixRandom
    (または RandomGenerator.getDefault())

といった感じです。

「多次元均等分布性が重要」というのは、身近な例ではトランプなどのシャッフルです。
n 要素のシャッフルは n! 通りの結果を持ちますが、小さな擬似乱数生成器だとこれだけのパターンを生成することができない場合があり、そうなると「絶対に出現しない盤面」が出てしまいます。
例えば、トランプ (ジョーカー 2 枚) なら 54! \approx 2 ^ {237} 通り、麻雀牌なら 136! \approx 2 ^ {773} 通り *4 になるので、最低でも (2冪の指数) ビット分の均等分布性を持つ擬似乱数生成器を選ぶ必要があります。
今回のアルゴリズムでいえば、トランプなら最低でも L64X256MixRandom を、麻雀牌なら L64X1024MixRandom を、ということになります。

ただこれは理想的な処理を行った場合の話で、例えば安直に nextLong(54) などとして乱数を生成してしまうとそれだけで 64 bit 分の情報量を消費してしまうので、トランプの例では 64 \times 54 = 3456 ビット必要になってしまいます。それだと L64X1024MixRandom でも足りないのでビット数を節約するよう工夫しなければなりません。 (byte 単位に分割して自分で nextLong(max) 相当のコードを書く、など。)
さらに言えば、現時点で LXM ファミリを引数なしの RandomGenerator.of(algorithm).create() から生成した場合、内部的には long のシード値を用いて初期化されるため、初期状態は 2 ^ {64} パターンに限定されてしまいます。もし全パターンを均等に得たい場合は create(byte[] seed) に十分な情報量を持つソース (SecureRandom の出力など) を渡して初期化する必要があります。

均等分布性について

ちょうど均等分布性の話が出たので、 Package Summary の "The LXM Family of Random Number Generator Algorithms" の均等分布性に関連する部分の解説をしたいと思います。

exactly equidistributed とは

"exactly equidistributed" (勝手訳: 厳密に均等分布する) とは、 nextLong() で得られる値について、すべての値が厳密に等確率で出現させられる、ということです。

L32X64MixRandom 以外の LXM ファミリについては、この性質を満たします。
L32X64MixRandom は、 32 bit 精度 (nextInt()) では厳密に均等分布しますが、 64 bit 精度 (nextLong()) では厳密に均等分布しません。
詳しく説明すると、 L32X64MixRandom#nextLong() は ((long)nextInt() << 32) ^ (long)nextInt() として実装されているため、 nextLong() で厳密に均等分布させるためには nextInt() 2 回分 (= 2 次元に) 厳密に均等分布させる必要がありますが、 L32X64MixRandom#nextInt() は 1 次元までしか厳密に均等分布しません。そのため、 nextLong() では厳密に均等分布しないことになります。

また、 Xoroshiro128PlusPlus と Xoshiro256PlusPlus については記載がありませんが、厳密に均等分布しないと思われます。内部状態がすべて 0 にはならないので、その時に出力されるはずだった 0 の出現個数が他の値より 1 少なくなるためです。
具体例としては、 Xoroshiro128PlusPlus では 0 が出る確率が \frac{2 ^ {64} - 1}{2 ^ {128} - 1} 、それ以外の値はそれぞれ \frac{2 ^ {64}}{2 ^ {128} - 1} となります。

ちなみに、 LCG (線形合同法) は基本的に厳密に 1 次元均等分布します。
具体例で説明します。 64 bit の線形合同法 (L64) は周期が 2 ^ {64} であるので、その周期中に long がとりうる全ての値を各 1 回だけ、すなわち厳密に等確率 2 ^ {-64} で出力します。したがって厳密に均等分布するといえます。

k-equidistributed とは

"k-equidistributed" (勝手訳: k 次元均等分布する) とは、要素数 k の long[] を連続する nextLong() で埋めたとき、すべての値の組み合わせが「ほぼ」等確率で出現させられる、ということです。
こちらは "exactly equidistributed" よりは緩めで、「厳密に」等確率でなくてもよいようです。上に挙げた Xoroshiro128PlusPlus のように 2 ^ {-128} オーダーでの違いは許容しよう、といった雰囲気です。

この性質は、従来のアルゴリズムでは Mersenne Twister の「623 次元均等分布」が有名でしょう。 (ただしこれは 32 bit 精度 (int[]) での値です。)

具体例として、 2 次元均等分布する L64X128MixRandom で考えてみましょう。
まず、内部の xoroshiro128 は {0, 0} 以外の任意の 2 次元ベクトルを生成することができます。 (つまり、 xoroshiro128 は単体で 2 次元均等分布します。)
ここに LCG パートを合わせるので、 XBG パートで {0, 0} だった場合の (つまり発生しえない) {mix(s), mix(s * m + a)} (s, m, a は LCG の内部状態と乗算定数・加算定数を示します) のベクトルが生成されるパターンが 1 つ少なくなって全周期中にそれぞれ 2 ^ {64} - 1 個、それ以外のベクトルはそれぞれ 2 ^ {64} 個ずつ生成されることになります。分母 (全周期) は 2 ^ {192} - 2 ^ {64} なので、 2 ^ {-128} オーダーでの違いとなります。

なお、 RandomGeneratorFactory.of(algorithm).equidistribution() で得られる値は、こちらの k 次元均等分布のほうです。

以下に 64 bit 精度での均等分布次元をまとめた表を示します。

アルゴリズム名 均等分布次元 厳密に均等分布するか
L32X64MixRandom 1 (2 @ 32bit)
L64X128MixRandom 2 ☑
L64X128StarStarRandom 2 ☑
L64X256MixRandom 4 ☑
L64X1024MixRandom 16 ☑
L128X128MixRandom 2 ? ☑
L128X256MixRandom 4 ? ☑
L128X1024MixRandom 16 ? ☑
Xoroshiro128PlusPlus 1
Xoshiro256PlusPlus 3

? をつけた箇所は API ドキュメント及び equidistribution() ではなぜか 1 となっていますが、実際はそれぞれ 2, 4, 16 が正しいのではないかと思います。
L128X128MixRandom ・ L128256MixRandom ・ L1281024MixRandom は、内部の XBG パート (xoroshiro128 ・ xoshiro256 ・ xoroshiro1024) がそれぞれ 64 bit 精度で 2 / 4 / 16 次元均等分布します。
これと LCG パートを組み合わせて最終的な出力が得られるのですが、この時 LCG パートの出力がどのようなものであれ XBG パートが均等分布する = 任意の値 (k 次元ベクトル) をとることができるのですから、組み合わせた出力も (XBG パートでよしなにすることで) 任意の値をとることができる = 均等分布する、と考えられます。

おわりに

.NET といい Java といい、最近標準ライブラリの擬似乱数生成器の改善がアツいです。(2021年当時の感想)

全体の所感としては、高速性をとった .NET と拡張性をとった Java という印象を受けました。
また両者とも xo(ro)shiro 系アルゴリズムを採用しており、浸透してきたようで勝手に嬉しく思っています。

ただ、他に採用実績がない初出のアルゴリズムを標準ライブラリにぶち込んでいくのはなかなか挑戦的だな、という気持ちがあります。
もちろん内部構造はどれもよく研究されたものですので無謀というわけではないですが、公開されてから欠点が見つかることはよくあるので…

*1:Anonymous Author(s). 2017. Better Splittable Pseudorandom Number Generators (and Almost As Fast). PACM Progr. Lang. 1, 1, Article 1 (January 2017), 41 pages.

*2:David Blackman and Sebastiano Vigna. Scrambled linear pseudorandom number generators, 2019. To appear in ACM Trans. Math. Softw..

*3:Guy L. Steele Jr. and Sebastiano Vigna. 2021. LXM: better splittable pseudorandom number generators (and almost as fast). Proc. ACM Program. Lang. 5, OOPSLA, Article 148 (October 2021), 31 pages. https://doi.org/10.1145/3485525

*4:同種の牌も区別しているものとします。区別しなければ約 2 ^ {617} 通りになります。

JDK にバグ報告してみたおはなしと、 Java における LXM の不思議な実装について

はじめに

どの擬似乱数生成器が速いのかを BenchmarkDotNet で調べるために、いろいろな擬似乱数生成器を C# に移植して遊んでいたのが発端です。

Java では、JDK 17 から LXM ファミリという擬似乱数生成器が追加されています。
簡単に説明すると、線形合同法 (LCG) と xoroshiro/xoshiro を組み合わせて (Mix して) 出力する擬似乱数生成器です。組み合わせは 8 種類あり、内部状態 96 bit の小規模なものから 1152 bit の大規模なものまで取り揃えています。

実例として、 L32X64MixRandom の C# 移植例はこのようになります。

public sealed partial class L32X64Mix
{
    private uint _increment;
    private uint _lcgState;
    private uint _xbgState0, _xbgState1;

    public L32X64Mix(uint increment, uint lcgState, uint xbgState0, uint xbgState1)
    {
        if (xbgState0 == 0 && xbgState1 == 0)
            throw new ArgumentException("xbgState must not be all zero");

        _increment = increment | 1;
        _lcgState = lcgState;
        _xbgState0 = xbgState0;
        _xbgState1 = xbgState1;
    }

    public uint NextUInt()
    {
        // Mix
        uint result = _lcgState + _xbgState0;
        result = (result ^ result >> 16) * 0xd36d884b;
        result = (result ^ result >> 16) * 0xd36d884b;
        result = (result ^ result >> 16);

        // LCG
        _lcgState = _lcgState * 0xadb4a92d + _increment;

        // xoroshiro64
        (uint s0, uint s1) = (_xbgState0, _xbgState1);
        s1 ^= s0;
        s0 = BitOperations.RotateLeft(s0, 26) ^ s1 ^ s1 << 9;
        s1 = BitOperations.RotateLeft(s1, 13);
        (_xbgState0, _xbgState1) = (s0, s1);

        return result;
    }
}

これは 32 bit LCG + xoroshiro64 の組み合わせの最も小規模な LXM で、主に 32 bit 環境を主眼とした実装です。ちなみに RandomGenerator#getDefault() でもこれが生成されます。
デフォルトは L64X128 とかのほうが良かったのでは、と思わなくもない

テスト結果が合わない

擬似乱数生成器の実装において、テストはとてつもなく重要です。
うっかり間違った実装をしたとしても結果はランダムなので、全く気づけなくなります。

今回は Java の実装から乱数を出力させてテストケースを作成しました。特定のシードで初期化してから 20 個の nextLong() の結果があっていればおそらく大丈夫でしょう、ということで…

import java.util.random.*;

class javaprng {
    public static void main(String[] args) {

        RandomGenerator rng = RandomGeneratorFactory.of("L32X64MixRandom").create(42);
        for (int i = 0; i < 20; i++) {
            System.out.printf("%016x%n", rng.nextLong());
        }
    }
}

C# 移植側の nextLong() 互換実装はこんな感じです。

public sealed partial class L32X64Mix
{
    public ulong Next()
    {
        return (ulong)NextUInt() << 32 ^ (ulong)NextUInt();
    }
}

というわけでテストにかけてみたのですが、これが何度直しても通りません。
Java 側と C# 移植側の出力を比べるとどうにも合わないのです…。

この diff を見ると、半々程度の割合で上位 32 bit が合っていない場合があるようです。
そこで、改めて Java 側の nextLong() の実装を確認することにしました。

public long nextLong() {
    return ((long)nextInt() << 32) ^ (long)nextInt();
}

L32X64MixRandom は 32 bit ベースなので、 nextInt() がメインの遷移・出力関数です。これを 2 個つなげて long つまり 64 bit にしている、ように見えます。
ところが、その認識が誤っていたことに気づきました。

念のため説明しておくと、 Java には組み込みの符号なし整数型 (C# でいう ulong) がありません。
そのため long にキャストして拡張しているわけなのですが、これは符号付き整数型のため、符号拡張が行われます。
ということはつまり、 nextInt() が負の (最上位ビットが 1 の) 数を返した場合に、符号拡張のため上位 32 bit にも情報がはみ出します。具体例を挙げると、nextInt() が 0xfedcba98 を返した場合、 (long)nextInt() は 0x00000000fedcba98 ではなく 0xfffffffffedcba98 になります。

これを上位ビットと xor でつなげているため、下から 32 ビット目 (2 個めの nextInt() の最上位ビット) が 1 のときに上位 32 bit が反転するという現象が起きているわけです。
この情報をもとに diff をよく見ていただけると分かるかと思います。

そうなると、果たしてそれは妥当なのか、という疑問が浮かびました。乱数の出力が変わってしまっているわけですから、本来の性質を保てているか分からなくなってしまうのでは？と思いました。

なので、バグ報告をしてみることにしました。

JDK に報告してみる

バグレポートは https://bugreport.java.com/bugreport/ から投げることができます。アカウントなどは不要のようです。

ここにバグの概要や環境情報、再現用コードや回避手段などを記入して投げます。

1 日程度待つと、中の人が確認してくれた上で、チケットが発行された旨のメールが届きます。

これで チケット が web 上で確認できるようになりました。私が記入した内容が載っているので、知りたい方はご参照ください。英語に不安がある……

また、あとから何かに気づいたなど追加情報がある場合は、このメールにあるリンクから送信することができます。

あとは中の人たちがよしなにしてくれるのを待ちます。

バグじゃなかった？

チケット公開から 1 日ほど経ったころ、チケットが resolved になりました。 "Not an Issue" とのこと…

中の人曰く (意訳)、

報告者は、ランダムな 32 bit をつなげて 64 bit にするのが正しいと仮定しているが、これはドキュメント化されていない挙動である (ので、それが正解とは限らない) 。
現在の実装は驚くべきものに見えるかもしれないが、均等分布性は損なわれていない。

(現行実装の) nextLong() から 2 つの nextInt() の結果を復元することは可能であり、情報の損失や生成はない。
nextInt() 2 個と nextLong() の間には全単射の関係があり、前者が一様分布なら、後者も一様分布になる。

もし接続が xor ^ ではなく or | だったら、それは不具合だっただろう。

ということで、これで問題ないとのことです。なんと……

ただ実際、仮に直したとしても再現性が維持できなくなる問題が出てくるので、これはこれで良かったのではないか、とも思います。

なので、 C# における nextLong() の正しい互換実装はこのようになります:

public sealed partial class L32X64Mix
{
    public ulong Next()
    {
        // see https://bugs.openjdk.org/projects/JDK/issues/JDK-8304120
        return (ulong)NextUInt() << 32 ^ (ulong)(long)(int)NextUInt();
    }
}

せっかくなので、本当に問題ないかどうか、擬似乱数生成器のテストフレームワークである PractRand に nextLong() の出力を与えてテストしてみました。

RNG_test using PractRand version 0.94
RNG = L32X64MixRandomJava64, seed = 0x19aa8a23
test set = expanded, folding = extra

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 megabytes (2^29 bytes), time= 2.9 seconds
  no anomalies in 1220 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 gigabyte (2^30 bytes), time= 7.7 seconds
  no anomalies in 1293 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 gigabytes (2^31 bytes), time= 15.4 seconds
  no anomalies in 1368 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 gigabytes (2^32 bytes), time= 29.2 seconds
  no anomalies in 1448 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 gigabytes (2^33 bytes), time= 60.3 seconds
  no anomalies in 1542 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 gigabytes (2^34 bytes), time= 117 seconds
  no anomalies in 1636 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 32 gigabytes (2^35 bytes), time= 213 seconds
  no anomalies in 1716 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 64 gigabytes (2^36 bytes), time= 455 seconds
  no anomalies in 1807 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 128 gigabytes (2^37 bytes), time= 914 seconds
  no anomalies in 1902 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 256 gigabytes (2^38 bytes), time= 1667 seconds
  no anomalies in 1983 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 gigabytes (2^39 bytes), time= 3541 seconds
  no anomalies in 2058 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 terabyte (2^40 bytes), time= 7137 seconds
  no anomalies in 2132 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 terabytes (2^41 bytes), time= 14111 seconds
  no anomalies in 2194 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 terabytes (2^42 bytes), time= 29294 seconds
  no anomalies in 2255 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 terabytes (2^43 bytes), time= 59262 seconds
  no anomalies in 2313 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 terabytes (2^44 bytes), time= 119867 seconds
  no anomalies in 2366 test result(s)

時間の都合で 16 TB までですが、問題は検出されませんでした。
実際のところも問題なさそうです。

おわりに

想像していたより簡単にバグ報告ができることがわかりました。

また、ご対応いただいた中の人 (?) には大変ご迷惑をおかけしました…
思っていたより対応が速くて助かりました。

せっかくなので、今回作成した LXM のテストベクトルを付録として公開します。
シード値 42 で初期化してから連続する 20 個の nextLong() 出力を観測したものです。別言語への移植をされる方がもしいらっしゃいましたらご利用ください。

LXM PRNG test vectors

Unicode の入力・表示テストに使える文字(列)

はじめに

アプリやゲームにおいて、「自由入力」のテキストボックスやそれを表示するラベル (ユーザ名・コメント欄・etc.) などを安易に設置すると、想定の斜め上を行く妙な文字(列)を入力され、意図しない表示・処理になることが多々あります。
本稿では、そのテストに使えるような文字(列)を記載していきます。なるべくコードポイント (U+xxxx) も併記するようにしました。

想定環境は主に PC ・スマートフォンで動作するクライアント (もっと具体的には Unity の TextMeshPro InputField) です。
Web やデータベース周りでは、例えば古典的な XSS や 寿司ビール問題 など別種の気を付けるべきポイントがあるかもしれませんが、あまり詳しくないのでここには記載しません。

なお、特に注記がない場合は Unicode / UTF-8 であるものとします。
環境によっては正しく表示されない可能性がありますがご了承ください。逆に考えると、その環境ではこれらのテストが有効であったことを意味します…
執筆環境は Windows 10 (游明朝が利用可能) / Firefox です。

省エネのため箇条書きスタイルでお送りしますが、ご了承ください。

テストに使える文字(列)

空文字列

  • それはそう

空白文字

  • U+0020 " " (半角スペース)
  • U+3000 "　" (全角スペース)
  • U+0009 " " (Tab)
    • 環境によってサイズが大きく異なる
  • U+200B "​" (ゼロ幅スペース)
  • その他 → スペース / 幅の比較
  • U+2800 "⠀" (点字カテゴリの点がない文字)
    • 見た目上空白だが So (Symbol, Other) カテゴリのため、 Zs (Separator, Space) カテゴリを禁止してもすり抜ける
  • 空白文字のみで構成された文字列を許容するか？

改行文字

  • U+000D U+000A (CR LF), U+000A (LF) のどちらか？
  • 連打された場合にレイアウトが破綻しないか
    • あるいは、そもそも入力できるのが適切かどうか
  • 末尾の空行を行数にカウントするか

RTL (Right-to-Left)

  • 右から左へ描画するシステム (アラビア文字など)
    • العربية
      • U+0627 U+0644 U+0639 U+0631 U+0628 U+064A U+0629
      • データ上の並び順としては ‭ ا ـل ـعـ رـ ـب ـيـ ةـ となっている
  • U+202E (Right-to-Left Override)
    • 後続文字の描画順を強制的に「右から左」にする
    • ABCD と ‮DCBA
    • 上記 2 つは同じに見えるが、後者はデータ上 U+202E に続けて DCBA と並んでいる
    • 禁止ワードフィルタをすり抜ける、正しいファイル名に見せかけるなど大問題になりうる
      • "正規ファイルだよ‮xcod.exe‬" はデータ上 "正規ファイルだよ U+202E xcod.exe" であるので、実行ファイルとして開けてしまう
  • RTL と LTR の混在
    • 例: アラビア文字 (RTL) の文章中でも、数字は LTR (Left-to-Right) として描画されるべき
      • لدي 100 تفاحة.
        • == I have 100 apples.

その他の制御文字・特殊な文字

  • U+0000 "�" (␀)
    • ヌル文字 \0
    • これが文字列終端になる環境 (C など) の場合、挿入することで後続の文字列を事実上消せる
  • U+0007 "" (␇)
    • ベル \a
    • ターミナルで出力すると音が鳴るなどする
  • U+FFFD � (REPLACEMENT CHARACTER)
    • UTF-8 として不正なバイト列を読んだ場合などで出現
    • コピペなどで正規に(?)入力することもできるが、一般のユーザにはバグ・文字化けに見えそう

その環境における制御文字(列)

  • データベース (?) が csv の場合における , や "
  • Unity (TextMeshPro) における <b> や <s> , <color=red> など

長い文字列

  • テスト例
  • KB ～ MB オーダーの文字列を突然コピペされたときに動作するか
  • IME の変換前状態で、一時的にテキストボックスの文字数制限を突破できる場合がある
    • 毎フレーム処理したり、文字変更イベントを都度受け取ったりするタイプの環境では注意
  • 文字の正規化処理で長くなる可能性 → 正規化
    • U+FDFA ﷺ は NFKD ・ NFKC 正規化 で 18 文字に分解されうる
      • U+0635 U+0644 U+0649 U+0020 U+0627 U+0644 U+0644 U+0647 U+0020 U+0639 U+0644 U+064A U+0647 U+0020 U+0648 U+0633 U+0644 U+0645
      • صلى الله عليه وسلم
      • C# では "\ufdfa".Normalize(System.Text.NormalizationForm.FormKD) で確認可能
    • 正規化が必要な場合、正規化→長さチェックの順に行う (逆だと限界突破しうる)

大きなスペースをとる文字

  • 以下原寸大。特に最初の 2 つは入力・表示できてしまう環境が多いため注意
  • U+A9C5 ꧅
  • U+FDFD ﷽
  • U+A9C1 U+A9C2 ꧁꧂
  • U+12031 𒀱
  • U+1242B 𒐫

大きなスペースをとる文字列

  • U+0E14 U+0E47 (x10) ด็็็็็็็็็็
  • U+05D1 U+059F (x10)
    • ב֟֟֟֟֟֟֟֟֟֟

スペースをとらない・不可視の文字

  • U+200B "​" (ゼロ幅スペース)
  • U+200C "‌" (Zero width non-joiner; ZWNJ)
  • U+2063 "⁣" (Invisible Separator) やほかにもたくさん
  • U+180E "᠎" (Mongolian Vowel Separator)
    • 上記と異なり General Punctuation ブロックではないので注意
  • なりすましや文字数稼ぎに利用されうる
    • アカウント名の末尾に追加して重複判定を回避する、4 文字以上必須のユーザ名を (見た目上) 空文字列にする、など
  • U+05D1 U+05BC (x10) בּּּּּּּּּּ
    • U+05BC を大量に重ねても幅をとらない

複数の表現がある文字 (正規化)

  • 同一の文字に複数の表現方法がある場合
  • これらが混在していると、検索・ソートなどを愚直に (バイト一致判定で) 行った場合に問題になる
    • 正規化 によってこれらを直感的に正しく行える
    • ただし、非可逆な操作なので保存する場合は注意

UTF-16 において 2 バイトで表現できない (U+10000 以降の) 文字

  • U+29E3D 𩸽 (ほっけ)
  • U+1F97A 🥺 など多くの絵文字が該当する
  • UTF-16 ベースで、サロゲートペアを正しく扱えないシステムにおいて問題になる
    • 例: C# において文字列長を string.Length でとっているとズレが生じる

フォントに含まれない文字

  • 明らかに文化の異なる文字は自明
    • U+1740 ᝀ ブヒッド文字や U+10000 𐀀 線文字 B など
  • Unicode の比較的小さな部分にある漢字は機械的に弾きにくいかもしれない
    • U+34C7 㓇 など
    • JIS X 0213 の第 4 水準 あたりは対応していないものが多そう
      • 上の字は Adobe-Japan1-4 に対応している クレー に含まれないことを確認。ただ、当然一般的なものはほぼ含まれているので特殊な人名用漢字や異体字でない限り実用上問題になることは少なさそう
  • もし対応文字数が少ないフォントを利用している場合は、デザインのずれが許容できるフォールバックフォントを用意するか、厳しめの (ホワイトリストのような) 文字制限をかける

異体字セレクタ

  • U+FE00 ～ U+FE0F, U+E0100 ～ U+E01EF を後ろにつけると文字の細かなバリエーションが変わる
  • 漢字
    • 葛󠄀 (U+845B U+E0100; 下部が "ヒ")
    • 葛󠄁 (U+845B U+E0101; 下部が "L + 人")
    • 邉 邉󠄀 邉󠄁 邉󠄂 邉󠄃 邉󠄄 邉󠄅 邉󠄆 邉󠄇 邉󠄈 邉󠄉 邉󠄊 邉󠄋 邉󠄌 邉󠄍 邉󠄎 邉󠄏 邉󠄐 邉󠄑 邉󠄒 邉󠄓 邉󠄔 邉󠄕 邉󠄖 邉󠄗 邉󠄘 邉󠄙 邉󠄚 邉󠄛 邉󠄜 邉󠄝 邉󠄞 邉󠄟
      • 最初の一文字 U+9089 がオリジナル (単体) で、それ以降は U+E0100 ～ U+E011F の異体字セレクタを後続させている (フォントの関係上すべて別の字形になっているとは限らないが)
      • → 参照
  • 絵文字のスタイル選択
    • U+2615 ☕ に異体字セレクタをつけて
      • U+2615 U+FE0E ☕︎ (テキストスタイル)
      • U+2615 U+FE0F ☕️ (絵文字スタイル)

国と地域の旗の絵文字

  • U+1F1EF U+1F1F5 🇯🇵 (日本の国旗)
    • 2 文字で表すタイプ → Regional indicator symbol
      • 🇯 と 🇵 (JP) からなる
    • 仕様上、検索などで問題になりうる
      • 🇰🇷🇺🇸 (韓国とアメリカ; KR US) のテキスト上で 🇷🇺 (ロシア; RU) を検索するとマッチしてしまう
      • → 参考
  • U+1F3F4 U+E0067 U+E0062 U+E0065 U+E006E U+E0067 U+E007F 🏴󠁧󠁢󠁥󠁮󠁧󠁿 (イングランドの旗)
    • 旗 + 地域コード(ここでは gbeng) + 終了 で表すタイプ → Emoji tag sequences

外字

  • U+E000 ～ U+F8FF, U+F0000 ～ U+FFFFD, U+100000 ～ U+10FFFD
  • そもそも入力できて良いのか？を検討すべき
  • 有名どころでは Apple の U+F8FF (林檎のロゴ) や Twitter の U+EA00 (例の鳥) など
  • それ以外の用例は → Private use areas
  • 特殊なところでは Ninja cat 🐱‍👤 → ニンジャキャット
    • U+1F431 U+200D U+1F464 🐱 + ZWJ + 👤
    • Windows 10 では 1 文字の Ninja cat 絵文字が描画される
      • 構成文字自体は一般的な (Unicode に存在する) ものだが、組み合わせたとき独自の描画になる

最近追加された文字

  • 2022/06/01 現在最新の Unicode 14.0 (2021/09) で追加された文字
    • U+1FAE0 🫠 (溶ける顔) など
  • 超マイナーな文字ならともかく、絵文字は比較的入力しやすいので危ない
  • 文字が追加される前提で設計しなければならない

複数のコードポイントで表現される文字

  • 👨🏻‍👩🏿‍👦🏽‍👦🏼 → ソース (図6)
    • 分割すると 👨 + 🏻 + ZWJ + 👩 + 🏿 + ZWJ + 👦 + 🏽 + ZWJ + 👦 + 🏼
    • U+1F468 U+1F3FB U+200D U+1F469 U+1F3FF U+200D U+1F466 U+1F3FD U+200D U+1F466 U+1F3FC
    • 1 書式素に 11 コードポイント、 UTF-8 では 41 バイト
      • 書式素 (Grapheme) : 人間が見て "1 文字" と思える単位 (要約)
    • これを正しく "1 文字" として判定するには、書式素単位でカウントできる StringInfo.GetTextElementEnumerator() や GraphemeSplitter ライブラリなどを利用する
  • 👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩
    • U+1F469 U+200D を繰り返している。 35 コードポイント、 UTF-8 で 122 バイト
    • カーソルを動かす / 選択すると分かるように、これでも 1 文字扱いされる
  • 👩‍⚕️ (Woman health worker)
  • 👨🏿‍🦳
    • U+1F468 U+1F3FF U+200D U+1F9B3
    • 👨 + 🏿 (dark skin tone) + ZWJ + 🦳 (white hair)
      • skin tone の範囲は U+1F3FB ～ U+1F3FF
      • hair の範囲は U+1F9B0 ～ U+1F9B3
  • #️⃣
  • ஙொ
    • U+0B99 U+0BCA
    • U+0BCA ொ は直前の文字を挟み込む形で作用する

色がある前提の絵文字・色を付ける絵文字

  • モノクロ描画の場合、識別が難しくなる可能性はある
  • 例 (上が通常、下は異体字セレクタ U+FE0E を後続させてテキストスタイルにしたもの)
    • U+26AA U+26AB U+1F534 U+1F535 U+1F7E0 U+1F7E1 U+1F7E2 U+1F7E3 U+1F7E4
      • ⚪⚫🔴🔵🟠🟡🟢🟣🟤
      • ⚪︎⚫︎🔴︎🔵︎🟠︎🟡︎🟢︎🟣︎🟤︎
    • U+2B1B U+2B1C U+1F7E5 U+1F7E6 U+1F7E7 U+1F7E8 U+1F7E9 U+1F7EA U+1F7EB
      • ⬛⬜🟥🟦🟧🟨🟩🟪🟫
      • ⬛︎⬜︎🟥︎🟦︎🟧︎🟨︎🟩︎🟪︎🟫︎
    • Unicode の字形例 ではハッチで描き分けている
  • 複数のコードポイントを利用する場合
    • U+1F408 U+200D U+2B1B 🐈‍⬛ (黒猫)
    • U+1F44F U+1F3FB 👏🏻 (skin tone)

合字 (リガチャ)

  • 連続すると見た目が変わる文字
  • コードポイント的には ae と æ (U+00E6) など
  • フォント(描画システム)側で解決する場合もあり
    • ffi / ffi
    • 前者がリガチャ無効、後者がリガチャ有効。コードポイントとしては同じ ffi
  • 文字体系がリガチャ前提な デーヴァナーガリー など
    • द्ध्र्य は、 द ् ध ् र ् य で構成されている
      • U+0926 U+094D U+0927 U+094D U+0930 U+094D U+092F
      • → 参照

非常に似ている文字

環境に依存して見た目が変わる文字

  • ロケール
    • 骨 骨 骨 骨 骨 骨
    • コードポイントはすべて U+9AA8
    • lang にそれぞれ zh-CN, zh-TW, zh-HK, ja-JP, ko-KR, vi-VN (中国, 台湾, 香港, 日本, 韓国, ベトナム) を指定している
  • OS
    • 絵文字は環境によって大幅に字形 (イラスト?) が異なる場合がある
    • U+1F3AB 🎫 (チケット)
      • → 様々な環境での見え方
      • 確かに「チケット」だが、色合い・向きなどは多種多様
        • 色や向きなどに意味を持たせた表現をすると、別の表示になる受け手の解釈が変わってくる
        • どうしても統一したい場合は画像埋め込みか？ (それでも IME とは表示が異なる)

1 文字あたりのバイト数が大きい文字

  • コードポイント単位
    • U+10000 以降の 4 バイトが最大 (UTF-8, UTF-16)
  • 書式素単位
    • イングランドの旗 🏴󠁧󠁢󠁥󠁮󠁧󠁿 は UTF-8 において 28 バイト
    • 家族の絵文字の無限連結 👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩‍👩 (制限なし)
  • 文字数制限がバイト・ワード単位でしか設定できない環境 (C# の string.Length に依存している場合など) では、上記の文字を入力した場合に「見た目上の文字数」が著しく少なくなってしまう
    • 逆に、書式素単位で設定すると非常に大きいバイト数の文字を入力される可能性がある
  • 厳密に判定するなら書式素の数を数える。また、十分余裕を持ったバッファを用意しておく
  • 正規化で大きくなる文字 (前述)
    • U+FDFA ﷺ は 1 文字から 18 文字に (UTF-8 では 3 バイトから 33 バイトに) 膨らむ

不正な文字列・バイト列

  • 解釈できないバイト列
    • UTF-8 における C0 AF
      • U+002F / を 2 バイトで表現した…ともとれるが、 / は 2F の 1 バイトで表現しなければならないため不正
      • これを / と解釈するとディレクトリトラバーサル対策の回避などに利用できてしまうため → セキュリティ
    • UTF-16 における D8 D8 (サロゲートペアの片割れ)
      • サロゲートペアを用いる文字を入力した際、一時的に現れる場合がある
        • char 単位でしか検証できない環境 (Unity の InputField.OnValidateInput) など
      • 文字数制限でペアの片割れだけ弾いてしまう、片割れのままログ出力してしまうなどでエラーになりうる
    • ただ、一般的な IME から直接入力・コピペする手段はないはず
    • 不正な部分は U+FFFD � に置き換えられうる (VSCode で確認)
      • 環境によってはより深刻なエラーにもなりうるため、存在させない
  • 非文字
    • 文字ではないコードポイント (未定義とは異なり、将来的にも文字になりえない)
    • U+FFFE
      • (UTF-16 において) U+FEFF (BOM) のバイト順を逆に解釈するとこれになる。したがって、これを認識した場合はバイト順を逆にして読むべきであると分かる
      • 補足: BOM → Byte Order Mark
        • UTF-8 において EF BB BF
        • ただし、 UTF-8 においては推奨はされない (あってもいいが、 UTF-8 はそもそもエンディアンに依存しないため入れる必要がない)
    • 「存在してはいけない」わけではなく、内部的に使用されることはある (最も、外部とのやりとりに使うべきではない)
  • 未定義の文字

余談

上記に載せるほどではない、文字関連の余談です。

幽霊文字

  • 実際の利用例がない文字 → Wikipedia
  • プログラム的には気にしなくてよい。しいて言えばフォントが対応しているかぐらい
    • その定義からして使われることはまずないが…
  • マシュマロでは U+5F41 彁 を伏せ字に利用している
    • 利用例がないことを逆手に取っている → 参照

点字

  • U+2800 ～ U+28FF → Wikipedia
  • ドットアートが可能 ⠠⠵
  • U+2800 "⠀" は見た目上空白だがカテゴリが Other Symbol のため、空白カテゴリを禁止してもすり抜ける可能性がある (上述)

Methematical Alphanumeric Symbols

  • 𝑰𝑵𝑻𝑬𝑹𝑵𝑬𝑻 𝑨𝑵𝑮𝑬𝑳
  • 文字だけで (フォントを変えることなく) 書体を変えることができる → リスト
  • A 𝐀 𝐴 𝑨 𝖠 𝗔 𝘈 𝘼 𝒜 𝓐 𝔄 𝕬 𝙰 𝔸
    • U+0041 U+1D400 U+1D434 U+1D468 U+1D5A0 U+1D5D4 U+1D608 U+1D63C U+1D49C U+1D4D0 U+1D504 U+1D56C U+1D670 U+1D538
  • 基本的にコードポイントは連続しているが、一部既に存在した文字 (U+210E ℎ など) の箇所は未割り当てになっているので注意 (前述の ℎ に対応する U+1D455 など)
    • また、既存だった文字は書体がずれがちなので注意
      • ... 𝑓 𝑔 ℎ 𝑖 𝑗 ...
      • きちんとやりたいならフォントを変えるべき

実際に問題を起こした文字列

  • Black dot bug
    • iOS で特定の文字列を表示するとアプリがクラッシュしていた → 参照
    • U+0020 U+003C U+26AB U+003E U+0020 U+1F448 U+1F3FB U+0020 (U+200E U+200F)x891 U+0020 U+200E
      • → gist
      • LTR と RTL が非常に多く含まれている
    • Apple でさえ、バグるときはバグる
  • テルグ文字 (の一部の組み合わせ)
    • 同じく iOS でクラッシュしていた → 参照
    • U+0C1C U+0C4D U+0C1E U+200C U+0C3E
      • → pastebin
      • Black dot bug とは異なり短いが、壊れるときは壊れる

ひらがなは 2 バイト文字か？

  • UTF-8 において "2 バイト文字" ではないのは自明。 2 バイトなのは U+07FF までで、平仮名ブロックは U+3040 から始まる
  • では「すべてのひらがなは 3 バイト」と言えるか?
  • U+1B001 𛀁 (や行え) はひらがなであり 4 バイト (UTF-8 で F0 9B 80 81) なので、つまり一概には言えない

おわりに

以上のように、個性豊かな文字(列)がたくさん存在します。
たかが文字、されど文字…
全部 Unicode が悪い… と思いましたが文字は実世界の映しではあるので、つまり人類が悪い
また、本稿は問題になりうる文字を網羅したものではなく、あくまでそれらの一部です。

テキストボックス実装の際は、全部対応…　するのは骨が折れるどころか複雑骨折するので、何らかのライブラリを利用するか、目立つところは処理してあとは心の隅に置いておくか、とするとよさそうです。

コピペが簡単になるように以上をまとめたテキストファイルをご用意いたしました。
上述の文字(列)たちを LF 改行で記載しています。テストにご利用ください。
※ U+0000 (ヌル文字) だけは gist に入力できなかったため省略しています。ご了承ください。

Unicode の入力・表示テストに使える文字(列) (U+0000 null を除く)

ブルアカ二次創作 STG を作った ～ 開発裏話

はじめに

「ブルーアーカイブ」のキャラを操作して戦う、縦スクロール弾幕 STG を作りました。
PC ブラウザ上で遊べるので、未プレイの方はぜひプレイしてみてください。

https://andanteyk.github.io/MillenniumAssault/

ここでは、開発の裏話等々を残していきたいと思います。

思いついたように書いているのでだいぶ読みにくいと思いますが、箇条書きぐらいの雰囲気で読んでください。
需要は考えません。書きたいので書きます…

発端

「ゲーム開発部」に関する作品を作ってタグをつけて投げると、プレゼントがもらえるかも… という公式さんのプレゼント企画です。

これを見て、「ちょっとやってみるかー」となりプロジェクトを作成したのが 04/18 です。

やろうと思えた要因としては、

  • ゲーム開発部のイベント・キャラ等々が好きだった
  • プログラミングならできるので、本当の意味で「ゲーム開発部」ができる
    • (イラストとかに比べれば、の話なので、マサカリを投げないでくださいね…！)
  • ゲーム開発部の設定が「レトロゲーム好き」であり、こちらもレトロチックにすれば
    • テーマが一致して強い
    • 私だけでもなんとかグラフィック(・サウンド)を賄うことができそう
  • 締め切り (04/16 - 05/20) まで 1 か月はある
    • イラスト中心の企画で 2 週間 とかだったら厳しかったでしょうね…
    • 逆に、締め切りがなかったらそれはそれでリリースできなかったと思います。無限に延期できてしまうので…
  • GW にまとまった休みがとれて、かつ大きな予定がなかった

という感じです。

始めるにあたり、ざっくり要件・目標を定めました。

  • 基本的にすべて自分で作ること
    • 具体的にはプログラム・グラフィック・サウンド（・プランニング）
      • ライセンス周りが面倒で、かつ二次創作になるので、ややこしくなることは避けたかった
      • (フォントとライブラリは流石に無理なので、正式な手段でお借りしました)
  • 新技術のテスト・学習をすること

ゲームのジャンルについては、とりあえず弾幕系シューティングにするか、というのは決まっていました。
ゲームシステム自体の元ネタはお察しかと思いますが、 巫女さんと魔法使いのシューティング です。
理由としては、

  • 工数がかかりにくそう (RPG とかに比べれば、ですが)
  • はるか昔 (DxLib でしたね) に作ったことがあり、雰囲気は分かっていること
  • ブルアカのテーマ (銃器を扱う) にマッチしていること

という感じです。

プラットフォームについては、今回は WebGL (ブラウザ上でプレイする形式) としました。
WebGL は試したことがなかったので、パフォーマンス上の問題や技術的制約に引っかからないか (一部の標準機能が封印されていたりします) 、といった懸念はありました。
ただ、言ってしまえば一発ネタなので、インストールの手間がかからず、すぐに遊べてすぐに終われるブラウザ上で完結する強さのほうが大きいのでは、と思い採用しました。
(実際この目論見はうまくいったような気がします。)

今回はソロ開発で「プログラム・グラフィック・サウンド・企画　私」状態だったので、「仕様はとりあえず作りながら考えるか」と見切り発車しました。

以降は各セクションの自分（？）からの所感や反省などです。

プランニング

ゲーム仕様レベルの設計思想や広報などを書きます。

自機

当初予定は「メイン双子、＋αでアリス」だったのですが、いつの間にかユズさんが増えていました。おかげで Player Select 画面を作り直すことになりましたが、よしとします。

基本的には本編に沿ったり、スキルからの連想で作っています。

  • モモイ: 広範囲型
  • ミドリ: 狙撃型 (EX スキルから)
  • アリス: 貫通型
  • ユズ: 爆発型

元ネタのほうで見たことのある挙動だな、と思った方もいらっしゃるかと思いますが、概ねその通りの想定で作っています。
(流石に銃弾がホーミングするのはおかしいのでオートエイムにするか、とかはありますが)

アリスさんがレーザーなのは… 本当はレールガンではあるのですが、本編のエフェクトもレーザーっぽい感じなのでよかったのではないでしょうか。

バランス調整はかなり難しかったですが、まぁ細かいところは置いておいて DPS を概ね同じにしておこう、程度の方針でした。

アリスさんとユズさんは対ビナー特効を持っています（貫通・爆発して複数のボディにヒットするため）。アリスさんについては火力が高すぎがちになっていましたが、下げすぎると今度は道中や通常ボスで戦いにくくなってしまうので、まぁいいか、ということにしました。

ユズさんが塩梅が難しく、かなりピーキーな性能になってしまったのがちょっと心残りです。
爆風をもうちょっと広く or 強くしてもよかったかな、とか…
（でもあまり広くしすぎると多段ヒットしたりして強くなりすぎるので…）

クリア報告ツイートを見ると（本当にありがとうございます）、ミドリさんの使用率がかなり高いようでした。やはりオートエイムはつよい…！

操作系統については、「なるべくシンプルにしよう」というのは当初からありました。
最初期はもはやショットボタンすらなく、常にオートショット状態で「移動」と「スキル」だけあるような状態でした。
というのも、一応スマートフォンでも動作させられる余地を残しておきたかったからです。
敵の攻撃も、東方のように高密度な弾幕を撃ってきて低速+細やかな移動で避ける、というスタイルよりは、高速弾をちょっとした反射神経で避ける、というバランスにしよう、と（当初は）思っていました。
スマートフォンでは細やかな操作は絶望的であるのと、そもそも画面上に弾を出しまくると動作環境的に重くなる懸念があったためです。

まぁやっぱり押せたほうがいいよね、ということで、最終的には 移動・ショット・スキル の 3 系統になりました。
低速移動はショットと兼ねています。最初は常に等速 (現在のショット中と同じ) だったのですが、もともと自機の移動が遅めで爽快感がなかった・緊急回避が難しかったので、ノーショット時に加速 (x1.5) するようにしました。

スキルストックに上限がなくて画面をはみ出していくのは…　仕様です。
最初に気づいたとき、見た目がバグっぽくて面白い (ファミコンのころにありがちな感じな) のと、ユーザー有利なバグなのでそのまま仕様にしてしまおう、となった経緯があります。

ステージ

最初は「まぁ 3 面ぐらい遊べれば十分だろう」と思っていたのですが、 カリンさんとネルさんのスプライトを描いた際に「同じメイドなら多少増やしても工数が少ないのでは？」などと思ってしまい（そんなことはなく普通に大変でした）、アスナさんとアカネさんを追加しました。

これで 5 面 (ユウカさんと C&C 4人) になったので、せっかくだしあと 1 面… となり、ビナーを追加することにしました。
採用理由としては、

  • 見た目が派手でシューティングゲームっぽい
    • 実際、告知動画でも「映え」があったと思います。たぶん…
  • ブルアカ本編で最初に戦ったボスなので思い入れがある
  • (サウンドの都合上、戦闘 BGM がビナー戦のものだった)

蛇っぽい動きを作るのはなかなか難しかったですが、苦労に見合っただけの働きはしてくれたと思います。
あの動きは、 DOTween の Sequence を少しずつインターバルを入れて再生させることで実現しています。
例えば、頭は即時、次の体パーツは 0.1s 遅れ、次のは 0.2s ... といった具合です。

ビナーの動きといえば、開発初期は若干動きが怪しくて、ボディが一か所に固まってしまうことが多かったのです。
そうすると自機の弾が多段ヒットするようになり（ヒットで消滅する前に複数のボディに当たる）、耐久弾幕 (浄化の嵐) で無敵になる前の数秒間の隙にスキルを叩きこむことによって HP を削り切り、耐久弾幕をスキップできる…　というバグがあって大変笑いました。マリス砲とか妹紅さんの使い魔とかそういったものが脳裏をよぎりました…

話を戻して…
道中の設計としては、以下に注意していました。

  • 1 面はとにかく簡単にすること
    • 操作に慣れさせるまで、しばらく弾は撃たない (撃ったとしても自機狙いではない)
    • 開幕で離脱されると悲しいので…　退屈なぐらいでも構わない、としました。
  • 工数を減らす（同じ動作・射撃設定の敵を使いまわす）
    • スポーン位置を変えるだけで、ある程度別のムーブっぽく見えるようにはしました
    • プレイヤーとしてもパターンが見えるようになるので、一応それらしくなります

ただ、コピペが続いてあまりにも単調になってしまったのと、雑魚の行動パターン作成にモチベーションがわかなかったため、開発後期に中ボスを導入しました。
これでバリエーションを増やしつつ、出来のよくない雑魚戦を削ることができました。
（実は中ボス戦の裏にも旧レイアウトの敵が配置されたままになっており、実際早く中ボスを撃破するとその敵が出てきます。中ボス出現中は雑魚の湧きをキャンセルするようにしています。）

近い理由で、6 面は道中がありません。楽をしたかったのと、即ビナーが出てくるインパクトがあって良いのでは、となったのがあります。

個人的にうまくいったかなと思っているのが 3 面の、中ボスカリン撃破後に画面外から狙撃されるところです。
シチュエーション的にそれっぽく、かつ "caution!" のインパクトがある（しかし脅威ではない）ので、楽しくなったかと思っています。

難易度想定としては、東方でいう Easy と Normal の中間ぐらいです。なぜなら私の腕前がそれぐらいだからです… (Normal で 1-2 コンティニューでクリアできるぐらい)
開発者補正で回避力が上がっている説はあるので、普通のプレイヤーにとっては Normal ぐらいになったかもしれません。
完全に別の話ですが、プレイ後の感想で「東方をやりたくなった」とあって若干嬉しくなりました。ちょうど新作 (虹龍洞) が出ているのでぜひ…！

ボス

一発ネタなので、おそらく繰り返してプレイしてくれる方は少ないでしょう。
したがって「覚えれば余裕だけど初見殺し」の戦略はなるべく回避しなければなりません。

そこで、 "caution!" 警告エフェクトを事前に焚いておくことで、驚かせつつキルはとらない程度のバランスになるようには気を付けていました。
5-6 面は警告があっても避けられない場合があるかもですが、そこは後半面なので許してもらって…

弾幕の設計にあたっては、攻撃に全く寄与しない（後ろとか左右遠くにすっ飛んでいく）弾を増やして、インパクトを確保しつつ実際そこまで難しくない、みたいなバランスにできれば…　と思ってはいたのですが、実際はなかなか難しかったです。
作っているとどうしても「こうすればプレイヤーに当てられる」という方向に意識が持っていかれがちですね… 当てられて嬉しい人間は作者しかいないのですが…（なんならプレイをやめられたら作者にも損なのに）

東方を観察していると、弾にかなり細かく加速度が設定されていて (発射瞬間の速度は遅く（どの方向に来るか分かる）、急に加速して (プレイヤーが認識する速度になる) 、プレイヤー付近に来たころに減速する（認識していた速度より避けやすくなる）、といった) 、流石だなと思ったりしました。
設計上加速度をつけるのが若干面倒な感じになってしまっていたので、もし次があれば楽に加速できるようにしておきたいです。

また、今回特有の制約として「同時に大量に弾を出すと処理落ちする」問題がありました。大量にといっても 32 個とかのレベルでも若干怪しいです。
そのため、後期に作られたキャラ (アカネ/アスナ/ビナーあたり) は、螺旋状に出したり時間差で撃ったりというのを気を付けていました。

キャラごとに弾幕の方向性みたいなものを決めていました。

  • ユウカ: バリア、数学っぽい(四角や円など)
  • アカネ: 反射、爆発 (背後ではじける巨大弾のやつです)
  • カリン: スナイパー(高速巨大弾)、曳光弾(弾から弾を出す)
  • アスナ: 高速移動(スキルからの連想)、軌道が曲がる弾(つかみどころない感)
  • ネル: 乱射、力技感

「げきこう」「コールサイン ダブルオー」あたりは調整の余地があったな、という反省があります…
激昂はもう少しプレモーションを増やしたり見た目上の綺麗さが出せれば…　と ダブルオーは轢かれる (回避した先に弾源が来る) 事故が多発していたので、うまいことできなかったな…と

ビナーの耐久弾幕 (浄化の嵐) は、「それっぽさ」を出すのにとてもいい感じになったと思います。ブルアカ本編でもかなり火力が高い攻撃で苦戦しましたし…
一応ノーダメージで抜けられることも確認してはいますが、まぁもう少しマイルドにしてもよかったのでは、と反省はあります… 最初の大縄跳びは普通に私も苦手です。

ところで、 1 面にユウカさんを置いたのは「ゲーム開発部が作ったなら多分そうするだろうな」という感じがあったからです。かにビーム先生のイラスト のアレとかの雰囲気で…
とても好きなキャラクターなので、雑に置いたわけではないです。念のため。 Extra とか作るならユウカさんにしていたかもしれません。

アイテム

いわゆる「得点アイテム」や「パワーアイテム」は最初から実装しない予定でした。というのも、元ネタよりも画面が狭く、半透明表現なども使えないので画面がごちゃごちゃしそうなため、またパワーアップの実装とバランス調整に手間がかかりそうだったためです。

ただ、いざ抜いてみると「敵や弾がまだあるのを避けながら、上に行って全回収する」とか、「ボスが落とした点符を速やかに回収してまた下に戻る」みたいな操作ができなくなってしまって少し退屈になってしまったので、よく考えられているな…　と思いました。

エクステンドとスキルアップ(ボム)は、かなり大盤振る舞い目に設定しました。
おそらく繰り返しプレイはされずに負けたらそれきりでしょうから、多少残機が減ってもすぐに補充できるようにと思って増やしていました。せっかくなので最後まで見てほしいので…
プレイ感想を見るに、なんならもうちょっと増やしてもよかったかもしれませんね…

デザインとしては、セリナさんのスキルの救急箱がモチーフです。ただ 赤十字レギュレーション に引っかかる可能性が…？との杞憂のため、ハートアイコンにしておきました。調べた感じでは色反転は大丈夫そうでしたが。

あと、アイテムではないですがスコアについて…
ステージクリアのスコアがかなり大きめ (ラスボスまで行っても撃破点がだいたい 100 万行くかどうかのところ、ステージ x 100 万) になっているのは、結果ツイートからどれぐらいまで進めたかを推測しやすくするためです。

プロモーション

せっかくなので動画を撮影してツイートにくっつけることにしました。静止画では弾幕が伝わらないので…

動画撮影・編集環境がそもそもなかったので、構築から始めました。 2 日ぐらいかかって締め切り当日に差し掛かったので割と危なかったです…

撮影は OBS , 編集は AviUtl です。編集といってもクロスフェードさせただけですが…
動画はいつもは GameBar で撮っているのですが、枠の切り取りができなかったので艦これブラウザのデバッグで入れたまま放置されていた OBS を使いました。
環境構築を含めて結構手間だったので、世の動画勢各位はすごいなと思うなどしました…

動画制作時は、出し惜しみしないことを念頭に置いていました。
今回はネタバレよりもプレイされないことのほうがデメリットなので…
その点ではビナーはいい感じのサムネイルになったのではと思います。

プログラミング

開発は Unity 2021.1.3f1 で行いました。
ソースコードはこちらで公開しています。
コミットログを眺めてもらうと開発の雰囲気が分かるかもしれません。

以下、使ってみたライブラリや機能の所感を書いていきます。

UniTask

非同期処理を簡潔に書けるようにするライブラリです。
このプログラムの中核をなしています。ほぼすべてのスクリプトで using しています。

というのも、今回の制作における重要な目的のひとつが「UniTask v2 に慣れる」だったためです。
基本的に Unity 標準のイベントは Start だけ使って、他 (OnTriggerEnter2D, Button.onClick など) は UniTask に用意された要素で実装しています。

UniTaskAsyncEnumerable がかなり使い勝手が良かったです。
雑に説明すると、普通の for 文が空間方向の繰り返し (円形のような) であるのに対して、これを使うと時間方向にも簡易に繰り返す (例としては螺旋など) ことができます。
詳しくはソースコードを参照してもらうのが早いのですが、例えば、螺旋状に弾を撃つ攻撃 (アカネの初回攻撃) は、以下のように実装できます（エフェクト等は省略しています）：

f:id:andantesoft:20210524221832g:plain 

async UniTask Phase(float direction, CancellationToken token)  
{  
    float baseRadian = Seiran.Shared.NextRadian();      // 撃ち始め角度の乱数(-pi ~ +pi)  
    int ways = 24;  
    
    // ways 回 だけ 0.05 秒ごとに ForEachAsync の中身を実行する  
    await UniTaskAsyncEnumerable.Timer(TimeSpan.Zero, TimeSpan.FromSeconds(0.05), PlayerLoopTiming.FixedUpdate)  
        .Select((_, i) => i)  
        .Take(ways)  
        .ForEachAsync(i =>  
        {  
            // 弾の生成  
            var bullet = BulletBase.Instantiate(m_NormalShotPrefab, transform.position, BallisticMath.FromPolar(32, baseRadian + i * Mathf.PI * 2 / ways * direction));  
        }, token);  
}

とても簡潔に書けます。

並列実行も簡単で、「動きながら撃つ」も await (Move(token), Shot(token)); と書くだけで実現できます。
これのおかげで移動コードと射撃コードを別々に実装することが可能です。

また、 "HP が 0 になったら、攻撃を中止して次のフェーズに移る" といった処理は、キャンセル機構を使用して実装しています。

// destroy されたとき(エディタで再生中止された or 撃破されたとき)にキャンセルされる  
var destroyToken = this.GetCancellationTokenOnDestroy();  
// HP が 0 になったときにキャンセルする (別途被ダメージ処理で hpTokenSource.Cancel() する)  
var hpTokenSource = new CancellationTokenSource();      

// どちらかがキャンセルされたときにキャンセルされる CTS を生成  
using (var combinedTokenSource = CancellationTokenSource.CreateLinkedTokenSource(destroyToken, hpTokenSource.Token))  
{  
    var combinedToken = combinedTokenSource.Token;  

    // ここの action() の実装に各フェーズの動作を記述する  
    await action(combinedToken).SuppressCancellationThrow();  
}

こうすると、(action() を適切に実装していれば) HP が 0 になった瞬間に上のブロックを抜けて、次のフェーズの処理に進むことができます。

初心者向け(?)逆引き

一番最初にあれば助かったな、と思うシリーズです。
文献としては https://qiita.com/toRisouP/items/8f66fd952eaffeaf3107 がとても詳しいですが、前提知識が割と必要な気がしたので、雑に使いたい人は下を見てみるとよい…かもです。

※ 間違っていたらマサカリを投げてください

(m 秒後から) n 秒ごとに繰り返したい
// timeSpanDelay 経過後にループが始まる。 (TimeSpan.Zero を渡せば今すぐ)  
// ループ(ラムダ式の処理)は timeSpanInterval ごとに呼ばれる  
await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.ForEachAsync(_ => { /* 同期的な処理 */ }, token);  

// timeSpanDelay == timeSpanInterval なら、  
// UniTaskAsyncEnumerable.Interval だと簡潔  

// これも等価  
await foreach(var _ in UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
    .WithCancellation(token)) {  
    /* 同期的な処理 */  
}

フレーム単位なら TimerFrame が、毎フレームなら EveryUpdate が使えます。
また、 FixedUpdate 相当のタイミングで実行したい場合は PlayerLoopTiming.FixedUpdate を引数に渡すことで実現できます。

やりたい処理が非同期なら、以下が使えます。
(2 秒動く → 1 秒待つ → ... など)

await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.ForEachAwaitWithCancellationAsync(async (_, token) => {  
    await Move(token);    // など, 非同期的な処理  
}, token);  

// これも等価  
await foreach(var _ in UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
    .WithCancellation(token)) {  
    await Move(token);    // など, 非同期的な処理  
}
一定回数の繰り返し
// x 回繰り返したら終わる  
await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.Take(x)            // ←これで回数制限できる  
.ForEachAsync(_ => { /* 同期的な処理 */ }, token);

LINQ が使えます。

何回目のループか知りたい (for 文の i が欲しい)
await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.Select((_, i) => i)        // ← これでインデックスに変換できる  
.ForEachAsync(i => { /* 同期的な処理; i がインデックスとして使える */ }, token);

別のシーケンスが使いたいときは、

// このシーケンスを処理の引数に使いたい  
static IEnumerable<float> Linear(float start, float end, int way)  
{  
    for (int i = 0; i < way; i++)  
        yield return Mathf.Lerp(start, end, i / (way - 1f));  
}  

await UniTaskAsyncEnumerable.Timer(timeSpanDelay, timeSpanInterval)  
.Zip(Linear(128, -128, density + 1).ToUniTaskAsyncEnumerable(), (a, b) => b)    // これで突っ込む  
.ForEachAsync(y => { /* 処理 (Linear で求めた y が使える)*/ }, token);
投げっぱなしにする
var bullet = BulletBase.Instantiate(...);

// 投げっぱなしの非同期処理は UniTaskVoid を戻り値にすると効率がいい (らしい)
UniTaskVoid MoveBullet(BulletBase bullet, CancellationToken token) { ... }

// .Forget() すると警告を消せる
MoveBullet(bullet, bullet.GetCancellationTokenOnDestroy()).Forget();

キャラ側で弾の特殊挙動を記述する際など、出したらそれっきりで以降放置するような場合に便利です。
(弾側に記述しろ、はまぁその通りではあるのですが…)

キャンセル周りについて

実装において、慣れが必要なのはキャンセルの部分です。
このエラーメッセージを無限に見ました。

f:id:andantesoft:20210524221835p:plain

コルーチンと違って GameObject が Destroy されても UniTask のコードは動き続けます。
例えば安直に await UniTask.Delay(5000); としてしまうと、待機中に Destroy(gameObject) された場合、後続のコードで破壊済みの this や transform を参照して落ちます。
したがって、必ずキャンセル処理を実装する必要があります。

具体的にどうするのかというと、

  • 呼び出しの大本で this.GetCancellationTokenOnDestroy() を使って Destroy 時にキャンセルされるトークンを生成する
    • もし別のキャンセル事由がある場合は (HP が 0 になったとか)、上に書いたように CancellationTokenSource.CreateLinkedTokenSource で合成できる
  • そのメソッドから呼び出す非同期メソッド すべて に CancellationToken を 必ず 渡す
    • 子孫にもそのまま渡していく
    • UniTaskAsyncEnumerable.Timer などは .WithCancellation(token) (await foreach の場合) や .ForEachAsync(..., token) (メソッド呼び出し式の場合) で渡す
  • UniTask(Void) を返す非同期メソッドを自分で実装するときは、必ず CancellationToken を引数に含める

という感じです。
すごい量の cancellationToken: token を書くことになりますが、怠ると予期しないタイミングでエラーになるので横着せずに書いていきました。

また、トークンを渡し忘れると上に書いたエラーだけでなく「撃破したのに弾を撃ち続ける」なども起こります。
必ずキャンセルを意識するようにしなければなりません。

DOTween の待機について

UniTask の機能で Tween を待機することができますが、その際の注意点です。

まず、 DOSpeed() (弾速を変更する; ≒加速度設定) が DOTween.To を使って定義されているとして、

// Speed は bullet のプロパティです
public DG.Tweening.Core.TweenerCore<Vector3, Vector3, DG.Tweening.Plugins.Options.VectorOptions> DOSpeed(Vector3 endValue, float duration)
    => DOTween.To(() => Speed, value => Speed = value, endValue, duration)
        .SetEase(Ease.Linear)
        .SetLink(gameObject);

段階的に加速させるコードを以下のように書いたとしましょう。
最初にちょっとだけ加速して予兆を見せてから、一気に加速するイメージです。

await bullet.DOSpeed(BallisticMath.FromPolar(32, radian), 1);
await bullet.DOSpeed(BallisticMath.FromPolar(192, radian), 1);

するとこれを引きます。

f:id:andantesoft:20210524221835p:plain

1 行目の実行中にスキルなどで bullet が Destroy されると、 2 行目で bullet が参照できなくなるので落ちます。
(厳密には、 DOTween.To の getter を参照されたタイミング辺りで落ちます。)
まぁ CancellationToken を渡していないせいだろうと、これに変えます。

await bullet.DOSpeed(BallisticMath.FromPolar(32, radian), 1).WithCancellation(token);
await bullet.DOSpeed(BallisticMath.FromPolar(192, radian), 1).WithCancellation(token);

するとこれを引きます。

f:id:andantesoft:20210524221835p:plain

何がいけなかったのかというと、 .WithCancellation(token) は .ToUniTask(TweenCancelBehaviour.Kill, token) と同じ意味になるのですが、 この TweenCancelBehaviour.Kill の場合、キャンセルされた際でも OperationCanceledException が飛ばないようです。
その結果、 1 行目がキャンセルされてもそのまま 2 行目に実行が継続されて落ちてしまっています。

したがって、飛ぶように KillAndCancelAwait を指定してあげればよい、というわけです。

await bullet.DOSpeed(BallisticMath.FromPolar(32, radian), 1).ToUniTask(TweenCancelBehaviour.KillAndCancelAwait, token);
await bullet.DOSpeed(BallisticMath.FromPolar(192, radian), 1).ToUniTask(TweenCancelBehaviour.KillAndCancelAwait, token);

こうすれば、 1 行目の実行中にキャンセルが走った場合、きちんとキャンセル例外が飛んで実行が中断され、 2 行目に進まなくなります。

まとめ

キャンセル周りの手間をかけたとしても、全体的にすごく楽に書けるので良かったです。なんなら公式で組み込みにしてくれてもいいのでは、と思うレベルの必要度でした。
あと Unity の非同期はほぼシングルスレッドなので、WinForms のように UI スレッドに切り替えないでコンポーネントに触ったら落ちる、みたいな地雷が少ないのも初心者にはやさしいです。
まぁ習熟は必要で、実際私が初期に書いたコードは若干怪しい感じになっており、少し慣れた今リファクタリング(バグ修正？)してもいいかもしれませんね…

Input System

Unity の新しい入力管理システムです。
導入の利点などは https://forpro.unity3d.jp/unity_pro_tips/2021/05/20/1957/ に詳しいです。
(ちょうどこの記事を書いているときに見つけました…)

ただ、何度も地雷を踏んだので、あまり印象が良くないです… プロダクトに使うにはまだ不安定なのでは、という印象がありました。（私が不慣れなだけの可能性はあるので、 Input System マスターの方がいらっしゃったらすみません）

旧 Input の使い方がわかっている方は、 移行用のドキュメント があるので見るのが早いです。

以降、私が爆発したポイントを列挙していきます。

Input.GetKeyDown|Up() 互換が (Stable 版には) ない

2021/05/21 現在の最新 Stable 版 (1.0.2) には、上記メソッド互換の機能が存在しません。…存在しません！！

近いものとしては、 input.Player.Fire.started|performed イベントと設定を駆使する方法で取れなくはなさそうです。しかし、設定が難しい（挙動がどう変わるのか分かりにくい）うえ、 event なので扱いが難しいです。
他には、 Keyboard.current.aKey.wasPressed|ReleasedThisFrame があり、こちらはプロパティなので自然に使えます。しかし、これはキーを直接指定するものであり、ゲームパッド等々との併用には使えません。せっかく手間をかけて入力を仮想化した意味が薄れてしまいます。

Preview バージョン (1.1.0-preview.3) には input.Player.Fire.WasPressed|ReleasedThisFrame() が実装されており、これが GetKeyDown|Up() 互換で使えます。したがって、 Preview 版を入れる必要があります。
(Package Manager からは指定できないようなので、 manifest.json を直接書き換えて導入します。)

あまりにも基本的なメソッドが欠けているので、旧 Input に戻したほうがいいのでは…？　という強い誘惑にかられました…

Keyboard.current は null になりうる

先の記事にはちゃんと書いてありましたが、私は知らなかったので…

キーボードが繋がっていたとしても、 Scene のロード中などに一時的に null になる場合があります。そのため、必ず null チェックを入れる必要があります。
デバッグコマンドだから Keyboard.current で直指定でもいいや、としていると引っかかりがちなので注意です。

エディタ上で再生開始時に一切の入力を受け付けなくなる

再生開始時に、ランダムにキーボード・クリックその他すべての操作が無視されるようになります。
Input Debug ビューからのキーテストは反応しますが、 Game ビューには反映されません。

これはいまだに原因がわかっていません…

ワークアラウンドは「Hierarchy ビューで InputSystemUIInputModule (EventSystem ?) がアタッチされているオブジェクトを選択する」です。なぜかは分かりませんが、以降操作できるようになります。
もし解決策をご存じの方がいらっしゃればご一報ください…

情報が薄い

一番致命的なやつです…
採用例が少ないので、公式のマニュアル(英語)を見て、分からなければフォーラム(英語)を巡回する羽目になります。

「導入してみた」記事は日本語でもよくありますが、実用してみた場合はあまりなかったりするので…

良かった点

dis るだけ dis ってもアレなので、良かった点を書きます。

まず、 キーボード/ジョイパッド 等々への対応はとても楽です。デフォルト設定も存在しており、コピペすれば概ねいい感じに対応できます。

また、スマートフォン対応用の On-Screen Button/Stick が標準で実装されており、スクリプトを貼るだけで「タップすると Z キー相当のイベントが走るボタン」「ドラッグで Left Stick 扱いされるスティック」が実装できます。
雑にスマートフォン対応するだけならあっという間です。
加えて拡張性もあります。今回はショットボタンをトグル形式 (押しっぱなし扱いになるボタン) にしましたが、以下の短いスクリプトを書いて貼り付けるだけです。

[RequireComponent(typeof(Toggle))]  
public class OnScreenToggle : OnScreenControl  
{  
    private Toggle m_Toggle;  

    [InputControl(layout = "Button")]  
    [SerializeField]  
    private string m_ControlPath;  
    protected override string controlPathInternal { get => m_ControlPath; set => m_ControlPath = value; }  

    private void Start()  
    {  
        m_Toggle = GetComponent<Toggle>();  

        m_Toggle.onValueChanged.AddListener(value =>  
        {  
            SendValueToControl(value ? 1f : 0f);  
        });  

        SendValueToControl(m_Toggle.isOn ? 1f : 0f);  
    }  
}

2D Pixel Perfect

今回のようなレトロチックなゲームを実装するにあたり必須になるコンポーネントです。
カメラにアタッチするだけで Sprite の (見た目上の) 位置を整数にそろえてドットがくっきり表示されるようになり、かつ Pixel Perfect に拡大してくれるようになります。

UI と併用するときに少しだけ注意が必要で、 Custom Canvas Scaler を Canvas にアタッチしたうえで、 Canvas を Screen Space - Camera にする必要があります。 (やらないと UI 側と Sprite 側で描画がずれます。)

Custom Canvas Scaler は同梱されていませんが、 GitHub にあります。

Tilemap

その名の通りタイルマップです。今回は背景に使用しました。
かなり直感的なエディタがついているので、ほとんど迷わずに制作できました。

強いて問題を挙げると、そのままだと半グリッドだけずれている (16x16 のタイルなら、オフセットが (8, 8) になっている) ことです。これは Tilemap コンポーネントの Tile Anchor を (0.5, 0.5) から (0, 0) にすれば直ります。が、今度はエディタで塗るときにカーソルが半グリッドずれるので、編集時は (0.5, 0.5) にして終わったら (0, 0) にするというちょっと面倒な運用をしていました。

あとはアセットが大量に生成される (スプライト単位ではなくタイル単位なので、 1 枚の画像に 16 個タイルを置いていた場合でも 16 個アセットができる) のがちょっと…　となるぐらいでしょうか。これは単に気持ちの問題ですが。

Google Sheets API

Google Spreadsheet と連携するものです。ステージの雑魚敵を設定する際、シートのデータ → ScriptableObject の設定値に変換するために使いました。（もちろんエディタ専用です。）
ScriptableObject において配列の直編集は相当な苦行なので、ステージエディタなどをする場合はほぼ必須だと思います。
(ローカルの CSV をいじれる環境があれば CSVReader 実装でいいかもしれませんが、 Office がないので…)

実装は StageDataEditor.cs にあります。導入もコメントに書いたので良ければ参考にしてください。
client_secret.json の生成 (アクセス権の獲得) が若干手間かもしれませんが、それだけの価値はあります。

シートの中身はこんな感じで、

f:id:andantesoft:20210524221840p:plain

Unity 上でこのボタンを押すと Enemies がシートに合わせて設定されます。

f:id:andantesoft:20210524221843p:plain

今回の機能は「位置を決めて Instantiate するだけ」でしたが、弾の動きとか HP とかも記述できるようにしておけばバリエーションを増やしやすかったかも、という反省があります。Prefab Variant を生産し続けてゴリ押しして終わらせてしまいました…

なお、導入にあたって Visual Studio の nuget パッケージ管理から直接突っ込むとうまく動作しませんでした。
別のプロジェクト (WinForms とか) でダウンロードしてから、バイナリ *.dll だけを Editor フォルダ下に突っ込む手法で動かしていました。
この時、 netstandard2.0 のものだけ入れるようにしましょう。同名の *.dll が複数あると Unity がエラーを吐きます。

また、毎回の注意点として、 client_secrets.json といった機密情報は git に含めないように十分注意が必要です。

Addressable Asset System

悪名高い Resources/AssetBundle の後継です。
今回は AssetBundle のように本体と分割して扱うことは考えていなかったので、いわば "Better Resources" のような運用をしていました。本来の使い方ではないかもですが…

運用としては、Inspector でチェックボックスを入れればパスが得られるので、それを

var prefab = await Addressables.LoadAssetAsync<GameObject>("some/prefab/path.prefab");

とするだけで読み込めます。 Resources と使用感はほとんど変わりません。 UniTask があるので await もできます。

注意すべき点としては、 WebGL ビルドする前に必ず Addressables もビルドする必要があることが挙げられます。何度となく忘れて古いアセットがロードされました…
一時はビルド前に自動で Addressables ビルドが走るようにエディタスクリプトに書いておいたのですが、いつからかビルドに失敗するようになってしまったので結局手動でビルドしていました。うまく自動化できるとよかったのですが…

WebGL

謎の OnJointBreak2D エラー

一番最初に直面したのがこれです。
Development Build は正常に成功するのですが、実行して InGame に入ると以下のエラーがコンソールに出て、動作が不安定になります。

Script error: OnJointBreak2D  
This message parameter has to be of type: [UNREGISTERED]  
This message will be ignored.

これは UniRx を入れており、かつ Project Settings の Strip Engine Code が有効になっていると発生します。 UniRx 側で Joint2D を参照しているにもかかわらず、ビルド時に未使用判定を受けて Joint2D のコードが削除されてしまい、実行時エラーとなります。
(UniRx は悪くないです、念のため)

これを防ぐためには、ルートの Assets フォルダ直下に link.xml というファイルを作成し、こんな感じに記述します。

<linker>  
  <assembly fullname="UnityEngine">  
    <type fullname="UnityEngine.Joint2D" preserve="all" />  
    <type fullname="UnityEngine.Collider" preserve="all" />  
    <type fullname="UnityEngine.BoxCollider2D" preserve="all" />  
    <type fullname="UnityEngine.CircleCollider2D" preserve="all" />  
  </assembly>  
  <assembly fullname="Unity.ResourceManager, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null" preserve="all">  
    <type fullname="UnityEngine.ResourceManagement.ResourceProviders.LegacyResourcesProvider" preserve="all" />  
    <type fullname="UnityEngine.ResourceManagement.ResourceProviders.AssetBundleProvider" preserve="all" />  
    <type fullname="UnityEngine.ResourceManagement.ResourceProviders.BundledAssetProvider" preserve="all" />  
    <type fullname="UnityEngine.ResourceManagement.ResourceProviders.InstanceProvider" preserve="all" />  
    <type fullname="UnityEngine.ResourceManagement.AsyncOperations" preserve="all" />  
  </assembly>  
  <assembly fullname="Unity.Addressables, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null" preserve="all">  
    <type fullname="UnityEngine.AddressableAssets.Addressables" preserve="all" />  
  </assembly>  
</linker>

これでビルドすると、 fullname で指定したクラスがビルドに確実に含まれるようになり、うまくいきます。
(Joint2D 以外でも Collider や Addressables で似た事象が起きたので追加してあります。)

Strip Engine Code を無効にする手もあり、もちろんそちらのほうが手軽ですが、副作用があるので可能なら上の手段をとったほうがよさそうです。

エディタが重い・ビルドが重くて長い

こればかりはどうしようもないですが…

スクリプトを変更するたびに 10-15 s ぐらい待たされます。リリースビルドに至っては CPU をフルに消費した状態で 10-12 分程度かかります。なかなかしんどいです…

また、エディタ実行時の重さもだいぶひどいです。なんなら 1 fps になることもしばしばありました。
この辺りは私の実装が悪い説も大いにあるのですが、だとしてもしんどいです。
(これに関しては、何かのプロファイリングを知らぬ間に有効にしてしまっていた説もあります…)

GameObject のキャッシュ機構とかを作るべきだったな、とはずっと思っていました。思っていたら期間が終わりました…
逆に言えば、最適化のしがいはありそうです。

GitHub Pages で動かない

今回は公開場所を GitHub Pages にしたのですが、そこでは Project Settings の Compression Format を Disabled にする必要があります。 Brotli や Gzip だと起動時にエラーが出ます。
(また、記憶が怪しいですが確か Brotli にすると localhost での実行時でもエラーが出ます。)

というのも、 Brotli や Gzip にした場合はサーバ側で配信する際に設定が必要らしいです。自前サーバならよしなに設定すれば OK なのですが GitHub Pages では設定しようがないので Disabled にして回避します。

ツイートボタンを置きたい

Twitter の民としては、ゲーム内にツイートボタンを置きたくなります。
リザルトをつぶやけるようにしておけば、プレイヤーがクリアしてくれたか分かってとても嬉しくなります。（ありがとうございます。）

ただ、ここで問題があります。
エディタでは Application.OpenURL(string url) を呼ぶだけで対応する URL を開くことができます。しかし、ビルド (ブラウザ上) でこれを実行すると、見事ポップアップブロックに弾かれます。スマートフォンのブラウザの場合、ブロックされたことすら通知されず握りつぶされます。

原因はというと、現代のブラウザでは邪悪なポップアップを防ぐため、ユーザ起因のアクションでのみポップアップを開くことができるようになっているためです。
（これ自体はもちろん正当な処理です。）

そして、Unity 内のボタンをクリックした際、入力から実際に反応する (uGUI の onClick イベントが呼ばれる) までには若干のラグがあります (ほんの少し非同期になっているイメージです)。すると「ユーザ起因のアクション」でないとみなされ、ブロックされてしまいます。

これを回避するためには、 js レイヤーのイベントを利用してウィンドウを開かなければなりません。そのための仕組みが用意されています。
(公式マニュアル)

まず、 Assets/Plugins/ のどこかに以下のスクリプト (TweetPopup.jslib) を用意します。

// note: keyup イベント上での発行は IE, FireFox では popup block に引っかかる  
// が、タイミングを合わせる意味でもここに書いておく  
// (クリックでもイベントが消費されるので、意図通りに操作すれば出ない…はず)  
mergeInto(LibraryManager.library, {  
    RegisterPopupEvent: function(url) {  
        var resolvedUrl = Pointer_stringify(url);  
        var open = function(event) {  
            if (!(event instanceof MouseEvent) && event.key != "z")  
                return;  
            window.open(resolvedUrl);  
            document.getElementById('unity-canvas').removeEventListener('click', open);  
            document.removeEventListener('keyup', open);  
        };  
        document.getElementById('unity-canvas').addEventListener('click', open, false);  
        document.addEventListener('keyup', open, false);  
    }  
});

そして、 C# コードからはこのように呼び出します。

#if UNITY_WEBGL && !UNITY_EDITOR  
[DllImport("__Internal")]  
private static extern void RegisterPopupEvent(string url);  
#endif  

public void RegisterTweetEvent(string url)  
{  
#if UNITY_WEBGL && !UNITY_EDITOR  
    RegisterPopupEvent(Uri.EscapeUriString(url));  
#else       // エディタ上ならやる必要はない (むしろ呼び出すと実行時エラー)  
    Application.OpenURL(Uri.EscapeUriString(url));  
#endif  
}

すると、 RegisterTweetEvent() を実行したあと、次にクリック/キー入力されたとき、指定した URL が別窓で開くようになります。Twitter 用の URL パラメータは マニュアル や "Twitter Intent" で検索してください。

ただし、 //note: に書いた通りキー入力経由でポップアップさせた場合は、環境によってはブロックされてしまいます。ブロックされないイベントは非常に限定されており、どのブラウザでも通るのは click ぐらいで、 keydown/up などのキー関連イベントでは環境依存 (少なくとも FireFox では全面的にダメ) なようです。
これは仕様なので回避策はありません。諦めましょう。

また、スマートフォン環境ではまた別の手法 (twitter:// インテントを使ってアプリを開くなど) が必要らしいです。今回はそこまでしませんでしたが…

スマートフォン対応 (スマートフォン上で動作しているか検出する)

もともと想定環境ではありませんが、そのままだと「ボタンはタップで押せるので InGame までは進めるが、以降キー入力ができずただ殴られるだけになり終了」という大変ユーザー体験の悪い状態になるので、最低限操作できるようにだけはしておきたいです。

スマートフォン上での入力エミュレーションについては Input System の項で述べたとおりです。
あと必要なのは、操作用 UI を出し分けるためにスマートフォン上で動作しているかを検出することです。これは、twitter ポップアップの項と同じように IsMobile.jslib を作って、

mergeInto(LibraryManager.library, {  
    IsMobile: function() {  
        return Module.SystemInfo.mobile;  
    }  
});

として、同じ要領で IsMobile() を C# スクリプト側から呼べばよいです。
UnityLoader.SystemInfo.mobile としている文献がよくヒットしますが、そちらは現在の Unity バージョンでは廃止済みなので実行時エラーになります。今は代わりに Module が使えます。

もっと単純に Application.isMobilePlatform でとれるかも？という話も見かけますが、うまくいかなかったような気がします（記憶があいまいなので、一度試してみるとよさそうです…）

ところでリリース後の話ですが、やはりというかスマートフォン上で起動したユーザーが少なからずいたようなので、この工夫は無駄ではありませんでした。備えあれば憂いなしです。

グラフィック

グラフィック担当の私です。画像作成の際に気を付けていたことなどを書きます。

全体的な傾向

まず、テーマはレトロチックです。ファミコンぐらい想定です。
（ぐらいというのは、厳密に色数やスプライト数を制限したりすると可視性やデザインセンスの面で厳しいので…）
ということで、以下のレギュレーションを設けました：

  • 半透明禁止
    • 代わりにディザリングやカットアウトを使います
    • 雑にフェードイン/アウトさせたり、境界をぼかしてごまかしたりできないので、一番つらかったかもしれません
  • 加算合成禁止
    • 弾幕を光らせることができない…！
  • 回転禁止
    • 2D Pixel Perfect がよしなにしてくれるとはいえ、見た目がよくならなさそうだったため
    • 自機の弾は例外です（超高速で目立たないかと…）
  • 1 スプライトの色数を 2-4 色程度に抑える
    • ディザリングで頑張る

また、目には見えないところですが、なるべくスプライト自身のサイズを削る工夫をしていました。
もともと小さいのでパフォーマンスとかファイルサイズは誤差みたいなものですが、なんというか「レトロチック」なので…

例えば、下のようなボタンの背景は 8x16 のスプライトを 9slice で引き延ばして利用しています。

f:id:andantesoft:20210524221845p:plain

ツールは GIMP を使用しています。

アニメーション

全体的に、左右非対称に描いたうえで左右反転させて差分を作り、 2 コマのアニメーションにする手法を使っていました。
手間を減らしつつ最低限アニメさせることができてよいです。
止まっているよりはだいぶ工夫感が出る…はず…

消滅していくアニメーション ("Start!" など) を描くにあたり、 GIMP の消しゴムレイヤー (塗ったところが消える) が便利でした。いちいちレイヤー結合しては削除して… といったフローが不要になります。

キャラクターグラフィック

最初は「双子ならほぼ色変えだけで済むので、双子中心で作って余力があればアリスを」といった感じだったのですが、途中でスプライトを全入れ替えするわ（後述）、ブルアカ本家の実装祝いにユズさんまで実装するわで普通に工数が重かったです。でも楽しかったです。

メイド部もコスチュームが近いので楽…かと思いきや、よく見るとバリエーションに富んでいたので輪郭ぐらいしか流用できませんでした。ドット絵の練習にはなりましたね…

あと、余裕があればクリア画面に専用ポーズの画像を出したりしたかったのですが、まぁ時間的に無理でした…

// あと、こういったテーマ企画の際は、三面図みたいなものを 3D モデルのキャプチャでいいので公開してほしい気持ちになりました。自機の背中を書きたくても資料がなく、ストーリーの出撃イベントを巡っては小さなちびキャラの背中を観察していました…

背景スプライト

以下のような画像を使っています。制約があったほうがそれっぽいかな… と思い、1 ステージ当たり 16 枚分にしました。色数も 1 枠当たり 2 色に抑えています。

f:id:andantesoft:20210524221849p:plain

工場のフックのケーブルと箱の胴体は、実は同じスプライト (上の画像の 8 番目) です。ファミコンとかでこういうのしがちなイメージがあったので勝手にテンションが上がりました。言わないと誰も気づかないと思うので書きます。

f:id:andantesoft:20210524221850p:plain

基本的に「背景」なので、弾や敵の認識の邪魔にならず、かつキャラの色にかぶらないようにするのがかなり難しかったです。特にユウカさんは #000080 と #FFFFFF を併せ持っていて、かつ #00FFFF のバリアまで撃ってくるので、明るくても暗くても目立たなくなり大変でした…

UI

可能な範囲で本家っぽくなるようにしました。ボタンの形と三角形の飾りぐらいですが…

あとは「そもそもの画面数と遷移を減らそう」が方針としてありました。画面と遷移が増えるとその分バグと工数が増えるので、本当に最低限としました。ポーズはフォーカスアウトで、タイトルに戻るは F5 でできます…！

また、こういった短時間だけ遊ぶゲームは操作分からなくなりがち問題があるので、最初に「このボタンがこれ」と表示して終わり、ではなく、常に画面下とか右に「何キーが何なのか」を書いておくようにしていました。 Apex Legends とかその辺り親切ですよね…

UI といえば、フォントは大切ですね…
最初は PixelMplus のフォントを使っており、ターミナルらしくて味が出てはいたのですが、 ＭＳ　ゴシック 感がすごかったので、ゲームらしいフォントに途中で入れ替えました。
名残が "Warning!" エフェクトなどにみられるかと思います。

ただ、変えたら変えたでフォントの横幅がだいぶ異なり (半角と全角ぐらい違います)、今まで収まっていたテキストがはみ出したりして大変でした。フォント選定は最初期に慎重に行いましょう…

フォントといえば、 TextMeshPro の RASTER モードではシャドウや囲みができないようです (SDF 限定)。
もしやりたければ最初からテクスチャに焼きこむとかでしょうか…？

サウンド

一番難しかったのがこれだったかもしれません。

BGM

"Andante" とかいうユーザー名をしておきながら音楽的素養がほぼ 0 なので、耳コピするだけでも大変でした。
なるべく耳コピしやすく、かつ使いやすくて印象的な曲を…　ということで、タイトルとビナー戦の BGM をチョイスしました。
（ビナー戦は印象的な繰り返しのフレーズが多く、それっぽくしやすかったので大変助かりました…）

本当は通常戦闘曲や勝利ジングルも入れて BGM 切り替えをしたかったのですが、私の能力では限られた時間内にとても再現しきれなかったので諦めました…

ちなみに、サウンドは「ピストンコラージュ」で作っています。洞窟物語などで使われているツールです。
最初は Domino でやろうかと思ったのですが初期音源があまりにも貧弱でそれっぽくならず (それはそう)、どうしようかと思っていたら HDD の奥底からこのツールが見つかったのでこれで行きました。10 年ものとかです…

ファミコン感を出すために 25%/12.5% 矩形波の素材を作ったりもしました。それっぽく聴こえてかなりテンションが上がったのを覚えています。

SE

SE も自作です。同じくピストンコラージュ製です。
爆発音はだいたいドラムやスネア、UI の「ピ」などは単発の矩形波音などでできています。

反射音とかボスアラートがちょっとうるさかったかな、という反省があります…

また、プログラミングセクションの話かもですが、 SE の再生優先度を設定していれば… とリリースしてから思いました。
アリスさんのスキル SE や被弾音がかき消されてしまう場合があったので…

同じくプログラミング的な話ですが、 SE には一応同時発声数制御を入れてあります。最大 8 枠で、オーバーしたら古い順に停止・上書きされる仕組みです。また、同一フレームで同じ音が鳴った場合には再生しない処理も入っています。
WebGL 環境では結構発声数の制約が厳しく、あまりたくさん鳴らすとすごいノイズが出たかエラーを吐くかしていたので (記憶があいまいです)、そもそもそうならないように制限を入れていました。

The Cutting Room Floor

いわゆる「没画像集」のコーナーです。供養のためと、私は TCRF が大好きな人種なので…

自機 (16x16)

f:id:andantesoft:20210524221822p:plain

もともとは自機が 16x16 だったのですが、ディティールがつぶれてスプライトが描きづらい・誰か判断しにくい問題があったため、現状の 32x32 に描き直しました。ユズさん実装時点では 32x32 に移行済みだったので、ユズさんの分はありません。

それにあたり、流石に当たり判定がわかりにくくなったので、当たり判定表示 (赤丸) を追加したりしました。ユズさんだと色が近いので見にくかったりしますが…

壁際に立つとめり込むのは 16x16 時代の名残です。

敵弾

f:id:andantesoft:20210524221817p:plain

これらもありましたが、それぞれ以下の理由で没になりました。

  • (緑弾) イメージに合うキャラがいなかった
  • (二重円弾) 東方っぽくなりすぎる (個人的に一番好きなデザインなので入れたい気持ちはありました)
  • (粒弾) 見えない!!

あまりカラフルにしても（デザイン上の問題 (レトロゲーム感) とか工数とか工数とか…）という気持ちがあったので、今回は色数を抑えめにしました。

NES (ファミコン) の解像度 256x224 (うち、フィールドは 176x224) にした都合上画面がだいぶ狭いので、サイズがそれぞれ小さめになっています。

弾といえば、進行方向が分かる弾（楕円形とか、鱗弾とか）を入れたい気持ちはあったのですが、 Pixel Perfect である関係上うかつに回転させると見た目がよくなさそうだったので、すべて円形弾としました。

バリケード

f:id:andantesoft:20210524221828p:plain

ユウカさんのバリアの自機が通れないバージョンです (当たると弾が消えます)。完全に動作しますが使っていません…

当初はブルアカ本編のように、遮蔽に隠れつつ射撃するようなシチュエーションがあってもいいのでは、と作っていました。

背景スクロールに合わせるとすごく移動が遅くなるので、使いどころが難しく没になりました。

ユウカ（左右移動）

f:id:andantesoft:20210524221830p:plain

上二つは使用したスプライト、下二つが左右移動用のスプライト（未使用）です。
よく見ると髪や足が動いています。
使うのを忘れていました…　最も、時間的に全員分作るのは厳しかったかとは思います。

当たり判定バグ

リリースが完全に終わって、土曜日になってから気づいたのですが…

f:id:andantesoft:20210524221853p:plain

緑の円がモモイさんと敵弾の当たり判定です。 (他のキャラ・色でもサイズは同じです)
モモイさんは二重円になっていますが、内側の当たり判定表示の白い円とほぼ同じサイズのものが被弾判定、外側の大きな円が物理判定（前述のバリケードに侵入できないようにする判定）です。…そのはずでした。

実際のところ、物理判定 (外側の円) に当たることでも被弾します。想定半径の 3 倍です……

OnTriggerEnter|Stay2D() 、isTrigger なものだけに反応すると思ったらそうではないんでしたね…　忘れていました…

それでめちゃくちゃ当たっていたようです。申し訳ないです…
試しに修正した状態で "浄化の嵐" を受けてみたところ、すんなり突破できてしまいました…

今直すのはレギュレーション的にどうなのだろうというのと、難易度がそこそこ変わりそうなので (本当に開発初期からこの状態だったので、これ前提で弾密度を組んでしまった)、一旦そのままにしておきます…

ポジティブに考えると、弾数少なめで圧迫感が出るのでまぁ良かったのではないでしょうか…

Debugging Functions

ゲーム内の Info に書いたものですが、ここにも残しておきます。

  • F8 キーを押すと高速周回モード (3 倍速) になります
  • Player Select 画面で ↑↑↓↓←→←→XZ すると、
    • デバッグモードになります
      • 被弾しても HP が減らなくなります
      • スキルを撃っても減らなくなります
      • スコアがアビドス状態になります (不正防止のため)
    • 入力に成功すると爆発音が鳴ります
    • ユズ以外を選択する場合は、Z を押す前にカーソルを動かしてください
  • Player Select 画面で 1~6 キーを押しながら開始すると、対応したステージから開始します
    • (qwerty の上のキーです)

おわりに

という感じで作っていました。久しぶりのゲーム制作でしたがとても楽しかったです。

この記事を書き終わる前に結果が出てしまいました。

「特別賞」を頂きました。
まさか本編のシナリオに合わせてくるとは思わず震えていました。ありがとうございました。

また、プレイしてくださった方々にも大きな感謝を…。少しでも楽しい時間になったら幸いです。

「ブルーアーカイブ」本編ももちろん楽しいゲームですので、もし初めて興味を持った方がいらっしゃればぜひ…！
「ゲーム開発部」のメンバーがメインストーリー Vol. 2 で活躍しています。
https://bluearchive.jp/

.NET 6 (Preview) における System.Random の実装変更

はじめに

2021 年 2 月 に、 .NET 6 Preview 1 が公開されました 。
なんとここで System.Random の仕様に大きめの追加・変更があったようなので、紹介します。

※ 本記事の内容は .NET 6 Preview 2 で確認しています。.NET 6 のリリース版では内容が変更される可能性があります。

xoshiro256** 擬似乱数生成器の採用

驚くべきことに、以前の記事 で散々文句をつけた (そして変わらないだろうと思っていた) 擬似乱数生成アルゴリズムが変更になりました。

新しく採用されたのは xoshiro256** です。このアルゴリズムは速度面・品質面でかなり優秀です。
ざっくり比較すると次のようになります。

アルゴリズム 周期 サイズ (byte) 均等分布次元 失敗するテスト Next 実行時間 (ns)
.NET 5 (Lagged-Fibonacci) ??? ( \lt 2 ^ {1705}) 280 ??? (< 55) @ 32 bit BCFN, DC6 9.351
.NET 6 (xoshiro256**) 2 ^ {256} - 1 72 4 @ 64 bit - 2.744

xoshiro256** とは

xoshiro256** は、 2018 年に Sebastiano Vigna 氏が開発した擬似乱数生成器です。
この方は Chrome などで採用されている xorshift128+ や、高速で有名な xoroshiro128+ を開発された方です。 xoshiro256** はそれらの改良版にあたります。

xoshiro256** の C# での実装例を示します。

// 内部状態 (全 0 以外なら可)
private ulong s0, s1, s2, s3;

// 64 bit 擬似乱数生成
public ulong NextUInt64()
{
    ulong result = BitOperations.RotateLeft(s1 * 5, 7) * 9;
    ulong t = s1 << 17;

    s2 ^= s0;
    s3 ^= s1;
    s1 ^= s2;
    s0 ^= s3;

    s2 ^= t;

    s3 = BitOperations.RotateLeft(s3 , 45);

    return result;
}

xoshiro256** は、 Xorshift や Mersenne Twister と同じ系列の理論を持ちます。
内部状態は 256 bit (64 bit x 4) 、 周期は 2 ^ {256} - 1 、出力は 64 bit 精度で 4 次元に均等分布します。
出力関数の工夫により、 Xorshift や Mersenne Twister でみられた線形性テストでの失敗を克服しており、 BigCrush や hwd テストに合格します。
加えて生成は非常に高速で、 作者のベンチマーク によれば 1 秒間に 9.5 GB 程度の乱数を生成することができます。

あえて欠点を述べるとすれば、内部状態復元攻撃が比較的容易に行えること (4 つの連続する 64 bit 出力が観測できれば確実に復元可能) 、 特定の (限定された) 状況下ではテストに失敗すること などが挙げられます。

既存の実装例としては Math.NET が挙げられます。標準ライブラリレベルで採用している言語は今のところ見つけられませんでした。

原典の論文は こちら を参照してください。
ちなみに、 xoshiro256++ などの出力関数を変更したバリアントも存在します。

シード指定時の互換性の維持

ところで、安直に System.Random の内部実装を変更してしまった場合、従来の乱数列の再現を期待するプログラムの動作が壊れてしまいます。

.NET 6 では、再現性が不要な new() コンストラクタではでは新しい xoshiro256** を、再現を期待する new(int seed) コンストラクタでは従来のアルゴリズムを用いる、というように切り替えることで対策をとっています。 *1
したがって、 xoshiro256** を使用したい場合はシード値を与えることができません。ちょっと残念ですが致し方ありません。

以降、本記事では new() で初期化した (xoshiro256** を使っている) ほうをベースに検証します。

出力関数

内部の状態遷移だけでなく、出力面でも強化が入っています。

NextInt64() シリーズ・ NextSingle() の追加

Next() の long を返すバージョンである NextInt64() / NextInt64(long maxValue) / NextInt64(long minValue, long maxValue) が追加されています。

なお、 NextInt64() の値域は 0 \le x \lt 2 ^ {63} - 1 であり、 long.MaxValue は返さない点に注意が必要です。 *2
Next() の仕様に合わせたものかとは思いますが、それは旧アルゴリズムの設計上 int.MaxValue が出せないことによる措置でした (以前の記事を参照) 。アルゴリズム自体が変更になったことでこの制約に縛られる必要もなくなったはずで、無意味でよろしくない制約では？と思ってしまいます…
(せめて NextUInt64() が露出していれば…)

また、 NextDouble() の float を返すバージョンである NextSingle() も追加されています。

Next(int maxValue) の内部実装変更

xoshiro256** が使用される場合、 Next(int maxValue) などの「一定範囲に変換する処理」も効率が良いものに変更されています。
ざっくり抜粋すると以下のようになっています。

// ~= (int)Math.Ceiling(Math.Log(maxValue, 2))
int bits = BitOperations.Log2Ceiling(maxValue);
while(true)
{
    ulong result = NextUInt64() >> (64 - bits);
    if (result < maxValue)
        return maxValue;
}

maxValue 以上の最小の 2 ^ {bits} を求めて 0 \le result \lt 2 ^ {bits} の範囲で乱数を生成し、 0 \le result \lt maxValue なら採用、そうでなければ再抽選する、というアルゴリズムです。
多少実行時間にブレがありますが、剰余や浮動小数点変換を使用する手法に比べて確率の偏りがなく高速です。
再抽選する確率は最悪の場合 (maxValue = 2 ^ {n} + 1 ; 特に n が大きい場合) でも 1 / 2 より小さくなるので、運が悪かったとしてもそれなりの試行回数で終了します。
(擬似乱数生成器の特性上、無限ループに陥る心配はありません。)

NextDouble() の内部実装変更

また、 NextDouble() の実装も変更になっています。

return (NextUInt64() >> 11) * (1.0 / (1ul << 53));

53 bit の乱数を生成して 2 ^ {53} で割ることで 0 \le result \lt 1 を得る、という手法です。
"53" は double 型の仮数部のビット数 (+1) から来ています。

従来のアルゴリズムでは高々 2 ^ {31} - 1 パターンしかなかったのが 2 ^ {53} パターン出るようになったので、かなり精度が向上しました。

NextBytes() の内部実装変更

さらに、 NextBytes() も変更されています。
詳細は省きますが、ざっくり説明すると 1 回の乱数生成で得られる 8 byte 分の乱数を一度に書き込むようになっています。
(C 言語で uint64_t * にキャストしてごりごり書き込んでいくイメージ、といえば伝わりやすいでしょうか…)

従来は 1 回あたり 1 byte ずつちまちま書き込んでいたので、かなりの効率化が見込めます。 (後述しますが、実際非常に高速になっています。)

パフォーマンス

メモリ

.NET 6 では、 System.Random は 1 インスタンスあたり 72 byte を消費します。 *3
内訳は以下のようになっています。 (実装はイメージです)

class Random    // クラスのヘッダ(型情報など) 16 byte
{
    class Impl  // 子クラスのヘッダ 16 byte
    {
        ulong s0, s1, s2, s3;   // 擬似乱数の内部状態 32 byte
    }
    private Impl impl;  // 子クラスへの参照 8 byte
}

クラスが入れ子になっているため若干余分に確保してしまっていますが、以前 (280 byte) に比べると 1/4 近くになっています。

速度

とりあえず実測してみましょう。 検証環境は以下の通りです。

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i7-7700HQ CPU 2.80GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores

.NET Core 5.0.4 (CoreCLR 5.0.421.11614, CoreFX 5.0.421.11614), X64 RyuJIT
.NET Core 6.0.0 (CoreCLR 6.0.21.15406, CoreFX 6.0.21.15406), X64 RyuJIT

各メソッドコール 1 回にかかった時間は以下の通りです。± は標準偏差、 Speed x は何倍速くなったかを示します。

Method .NET 5 [ns] .NET 6 [ns] Speed x
new() 　 1989.19 ± 37.66 151.631 ± 4.83 13.119
Next() 9.351 ± 0.15 2.744 ± 0.03 3.408
Next(401) 12.575 ± 0.14 6.809 ± 0.10 1.847
Next(168, 401) 12.227 ± 0.17 5.142 ± 0.11 2.378
Next(1 << 30) 12.563 ± 0.19 2.941 ± 0.09 4.272
Next((1 << 30) + 1) 12.54 ± 0.15 14.323 ± 0.20 0.876
NextDouble() 10.43 ± 0.12 2.989 ± 0.05 3.489
NextBytes(byte[256]) 2333.249 ± 19.59 41.31 ± 0.53 56.481
NextInt64() #N/A 2.612 ± 0.08 #N/A
NextInt64(401) #N/A 6.693 ± 0.15 #N/A
NextInt64(168, 401) #N/A 4.916 ± 0.12 #N/A
NextInt64(1L << 62) #N/A 3.844 ± 0.12 #N/A
NextInt64((1L << 62) + 1) #N/A 14.55 ± 0.23 #N/A
NextSingle() #N/A 3.168 ± 0.04 #N/A

速度差が特に大きかった new() と NextBytes() の処理時間の比較を以下に示します。

f:id:andantesoft:20210328221840p:plain

それ以外の Next() 系メソッドの処理時間の比較を以下に示します。

f:id:andantesoft:20210328221829p:plain

また、 .NET 6 で追加されたメソッド群と既存の似たメソッドの処理時間を比較したグラフを以下に示します。
(これだけ .NET 6 の中での比較です。)

f:id:andantesoft:20210328221834p:plain

ブレはありますが、全体的に 2 - 3 倍程度に速くなっています。 特筆すべきは new() (約 13 倍速) と NextBytes (約 56 倍速) でしょう。 new() はかなり複雑だった初期化処理が単に乱数を設定するだけになったこと、 NextBytes は乱数をまとめて配列に書き込むようになったことが影響していそうです。

ただし、注意すべきは Next((1 << 30) + 1) と NextInt64((1L << 62) + 1) です。
これらは意図的に遅くなる (再抽選率がほぼ 1 / 2 と高くなる) 値を選んだケースで、最善の場合 (再抽選率 0) の Next(1 << 30), NextInt64(1L << 62) と比べると 3 - 5 倍程度時間がかかっており、 Next では .NET 5 のものよりも遅くなっています。

以上のように maxValue に依存して速度が結構変わるので、注意…するほどではないと思いますが、覚えておくとよいかもしれません。

32 bit 環境での速度について

xoshiro256** は、64 bit 環境 (ulong 上での計算が高速に動作する環境) を想定して設計されたアルゴリズムです。
従来のアルゴリズムは 32 bit 環境メイン (int ベース) のため、 32 bit 環境においては System.Random の動作が若干遅くなる可能性はあります。
検証環境がないので実測はできていませんが…

(2021/08/31 追記:)
32 bit 環境 (厳密には x64 か arm64 以外のプラットフォーム) においては、 xoshiro256** の代わりに xoshiro128** アルゴリズムの実装が使用されます。これは xoshiro256** のワードサイズを 64 bit から 32 bit にしたようなもので、性質も概ね同様です。周期は 2 ^ {128} - 1 となっています。
したがって、上述の打ち消し部分の心配は杞憂でした。きちんと考えられていますね…!

余談: 静的インスタンスの追加 (未対応)

2021/03/28 時点ではリクエストレベルですが、 PR #50297 で静的なインスタンスを取得するプロパティが提案されています。

// ライブラリ内の定義 (イメージ) 
public class Random {
    public static Random Shared { get; }
    // ...
}

// 使用例
int randomValue = Random.Shared.Next(10);

これによって、再現性が不要なら乱数インスタンスを自分でいちいち生成・保持する必要がなくなります。
また、よく見かける誤用である「乱数が必要になるたびに new Random().Next() する」ことをある程度防げるのでは、とも思い、とても便利そうです。
正式採用されることを願って…!

(2021/08/31 追記):
.NET 6 Preview 4 で Random.Shared が実装されました。🎉

おわりに

永遠に悲しみを背負い続けるのだろうと思っていた乱数周りに手が入るとは、と大変驚いて・喜んでいます。
従来のカオティックなアルゴリズムに比べて理論的にも実用的にも優れており、かつこちらで対応する必要はほぼないのでとてもありがたいです。
メジャーリリースを楽しみにしています。

関連情報を載せておきます。

*1:厳密には、System.Random を継承したクラスから new() した場合も従来のアルゴリズムで初期化されます。

*2:内部実装では、63 bit の乱数を生成して long.MaxValue だった場合は再抽選する処理が書かれています。

*3:64 bit 環境での計測です。 32 bit 環境だとポインタの分だけ小さくなりそうです。

SCP-1214-EX ～ SCP-1214 の再現実験

補遺1214-4:

20██/██/██ に、 SCP-1214 の再現実験に成功したと主張するウェブサイトが財団の Web クローラによって発見されました。

+ 公開されていたウェブサイトの内容：

という体で始めます。 本記事では、 SCP-1214 - 特異乱数生成プログラム (オリジナルの英語版) の機能面における再現を目指します。

SCP-1214 は、要約すると以下のような性質を持っています。

  • 0-9 A-Z :;<=>?@ の 43 種類の文字をランダムに生成し、1 秒ごとに 50 文字ずつ表示しつづける C# プログラム
  • アルゴリズム的には一般的なもので、不審な点はない
  • にもかかわらず、██分経過すると特定の文字が頻繁に生成されるなど、乱数らしからぬ挙動になっていく
  • ██分～██時間経過すると、徐々に単語・文章が混じり始める
  • さらに██時間経過すると、生成される文字種が減っていく
  • [補遺1214-3 非常事態報告を参照]
f:id:andantesoft:20210223200610g:plain
SCP-1214 (フェーズ0: 起動直後)。
出力される文字は十分にランダムです。
f:id:andantesoft:20210223200614g:plain
SCP-1214 (フェーズ1: 起動後██分経過)。
"I" が連続して出力しやすくなっています。
f:id:andantesoft:20210223200619g:plain
SCP-1214 (フェーズ2: 起動後█時間経過)。
連続する文字に加え、 "PLEASE" "STOP" "HURTS" などが観察されます。
f:id:andantesoft:20210223200635g:plain
SCP-1214 (フェーズ3: 起動後██時間経過)。
"4, 8, S, O" などの文字が極端に出現しにくくなっています。

非常事態報告はともかくとして、このような挙動を擬似乱数生成器で再現することは可能でしょうか？

実装手法の検討

前提として、「"特異な" 文字列を直接プログラムで生成する手法」は、あまり面白くないのでしないものとします。 あくまで「きちんと使えば」擬似乱数生成器として機能するプログラムで実現することを目標とします。

一般的な擬似乱数生成器は、当然ながらあっという間にランダムになってしまうので、ほぼ実現不可能です。 では、敢えて壊れた生成器を設計すること (例えば以前の記事で挙げたように Xorshift を全 0 で初期化するとか、誤った遷移式で構成するとか) で実現できるかというと、それも難しい気がします。大抵の場合「どのように壊れるか」は制御できず、オリジナルの「同一の文字が並びやすいが、時々別の文字も出る」といった挙動を再現することは困難でしょう。

実現できそうな手法としては、PCG の作者が紹介している "Party Tricks" が挙げられます。これは、内部状態に「仕込み」を入れておくことで、特定のタイミングで好きな出力列が出るようにする、というものです。 リンク元の記事では、特定回数乱数を進めると ハムレットを出力する 例を紹介しています。

仕込みを入れているので、原理的に実質「安直な」手法と同じでは？　と思われるかもしれませんが、この手法は初期化を適切に行えばきちんと擬似乱数生成器として利用できること、またこの手法が適用できる擬似乱数生成器では「偶然に」同じ現象が発生する可能性は 0 ではないことから *1 、この手法を採用します。

しかしここで困難となるのが、「欲しい出力列と同じ量だけ内部状態が必要であること」です。当然ではありますが、仕込める情報量は内部状態の bit 数が上限になります。 今回の要件は、

  • 1 文字あたり 43 種類
  • 1 行 (= 1 秒) あたり 50 文字 == 43^ {50} 種類
  • オリジナルの文章から、 100 日 (= 8640000 秒) 程度は制御下で動かしたい

なので、最低でも 43^ {50 \cdot 8640000} 種類分、つまり \log _ {2} 43^ {50 \cdot 8640000} \approx 2344146375 bit の情報量 = 内部状態が必要になります。 状態空間が広いことで有名な Mersenne Twister でも 19937 bit 分、今回の要件で言えば最大でも 19937 / \log _ {2} {43} \approx 3674 文字分 (約 73 秒分) しかありません。 当然ですが、これほど巨大な内部状態を持つ既存の擬似乱数生成器は存在しない（はず）なので、自分で作らなくてはなりません。

設計

今回は、設計が比較的容易である Lagged Fibonacci 法 を採用することにしました。

Lagged Fibonacci 法の遷移式は、以下のように表されます。　*2

\begin{aligned} x_{n} = x_{n-j} + x_{n-k} \pmod{m} \end{aligned}

プログラム的に書けば、以下のようになります。遷移式から分かるようにとてもシンプルになります。

const int j = ..., k = ...;
// m = 2^64 とするため、 mod m は不要になります

ulong state[j];
int stateIndex = 0;

public ulong Next()
{
    // インデックスを [0, j) の範囲に変換するメソッド
    int mod(int index) => (index + j) % j;

    stateIndex = mod(stateIndex + 1);

    return state[stateIndex] = state[stateIndex] + state[mod(stateIndex - k)];
}

f(t) = t^ {j} + t^ {k} + 1 が原始三項式となるならば、最大周期 2^ {63} (2^ {j} - 1) が実現できます。 *3

それでは、なるべく大きい j を持つ原始三項式を調べてみましょう。 2021/01/18 時点で知られている最大の j を持つ原始三項式の一つが以下になります。 *4

\begin{aligned} x^ {74207281} + x^ {9999621} + 1 \end{aligned}

この多項式を利用して j = 74207281, k = 9999621 とすることで、最大周期 2^ {63} (2^ {74207281} - 1) を実現する擬似乱数生成器を作ることができます。10 進にするとだいたい 1407332901 桁、10^ {1.4 \times 10^ {9}} ぐらいです。 内部状態は 4749265984 bit ~= 566 MiB という暴力的な数値を誇ります。これを「一般的アルゴリズム」と呼称するのは無理がある気がしてきましたが、見なかったことにして進めます。

余談ですが、大きいほうの定数 74207281 はメルセンヌ素数 2^ {74207281} - 1 の指数から来ています。構造が単純なメルセンヌ素数をベースにすると、諸々の計算を効率的に行えるのです。
また、この原始三項式が発見されたのは 2016 年ですが、本家の SCP 記事が書かれたのは 2012 年のようです。「当時は未知だったはずの定数をどうやって知りえたのかは不明です」と言えば SCP らしくなるでしょうか…？

話を戻しましょう。 566 MiB もあれば、さきほど計算した 100 日分の情報量 (2344146375 bit ~= 279 MiB) ですら余裕でクリアできます。

内部状態設定

設計は出来ました。あとは所定の出力を得るために、内部状態を設定する必要があります。 希望する出力列は "特異な" プログラムから得るとして、内部状態をどう逆算すればよいでしょうか。 といっても、遷移関数がシンプルであることから、逆算は非常に簡単です：

// この時点で ulong[] output には希望する出力列が入っているものとする
// StateLength = output.Length = 74207281, Lag = 9999621

for (int index = StateLength - 1, lagged = index - Lag; index >= Lag; index--, lagged--)
    output[index] -= output[lagged];
for (int index = Lag - 1, lagged = StateLength - 1; index >= 0; index--, lagged--)
    output[index] -= output[lagged];

// この時点で output は対応する内部状態になっている

実装

以上で理論面での準備が整ったので、実装を行いました。 リポジトリはこちらです。理論は明らかですので "Explained" としています。

https://github.com/andanteyk/SCP-1214-EX

実装にあたって、本体(GUI) random_number_test と特異シード生成器 seed_generator は別のプロジェクトにしており、 seed_generator で内部状態をファイルに保存したのち random_number_test で読み込んで表示するようになっています。ちょっと面倒ですが、これによって本体側のプログラムに "特異性" (仕込み用コードともいいます) を持たせないようにしています。

一応「約 60 行のソースコード」という制約にしたがってファイルごとのサイズは 60 行ぐらいにしました。全体のサイズを 60 行にするとコードゴルフめいて不自然になりそうだったので許してください…

また、 .NET 5 での実装です。オリジナルは Visual Studio 2012 で開発されていたようなので .NET Framework 4 ぐらいで書くべきなのかもですが、書いていてつらくなってきたので最新のにしてしまいました。
余談ですが、当初 .NET Framework 4.8 で書いていたのを .NET 5 に書き換えた際、 I/O が ██ % 速くなってちょっと感動しました。 MemoryMarshal.Cast で ulong[] を直接入出力できるようになったのが大きそうです。

余談：ある範囲の一様分布乱数を大量に生成する手法について

SCP-1214 の実装では、 ASCII 48 ～ 90 (43種類) の範囲の乱数を大量に生成する必要があります。 しかし、安直に Next() % 43 + 48 としてしまうと、 Next() 1 回に対して 1 個の出力しか得られないのでもったいないです。ここで Next() は ulong 、つまり 64 bit 分の情報量を持つのですから、 \lfloor \log _ {43} 2 ^ {64} \rfloor = 11 文字まで一度に生成することができます。

今回は以下のように実装しました。

public IEnumerable<char> NextChars()
{
    while (true)
    {
        ulong r = Next();
        for (int i = 0; i < 11; i++)
            yield return (char)('0' + Math.BigMul(r, 43, out r));
    }
}

整数64bit . 小数点以下64bit の固定小数点数をイメージすると分かりやすそうです。 r が小数点以下 64 bit にあたります。 r を 0 ~ 1 の乱数とみなして 43 ^ {11} を掛けて、整数部を 43 進数にして各桁を取り出す、というイメージです。

なお、今回は確率の偏りを除去するコードは含めていません。どのみち仕込みを入れるので…
もし実用目的で転用する場合は入れるとよいでしょう。

起動実験記録 ██ (20██/██/██ 実施):

SCP-1214-EX の起動実験 ██ において、今まで観測されていなかった "KETER" の単語が出現しました。

f:id:andantesoft:20210223200603g:plain
SCP-1214 (起動後█時間経過)。
中央付近、Y が連続している行に "KETER" の語がみられます。

何らかの SCP に関連する情報を含んでいる可能性があるため、 ██████ 研究員によって調査が続けられています。 *5

- (公開されていたウェブサイトの内容 を閉じる)

財団はウェブサイトを無害なものに置換し、投稿者および閲覧者に対しクラス A 記憶処理を施しました。

f:id:andantesoft:20210223200626g:plain

ライセンス

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

This article is based on "SCP-1214 - Anomalous Random Number Generator" by "DrCarnage".

*1:もちろん天文学的に低い確率にはなりますが、不可能ではない点が重要です。逆に、例えば内部状態が 128 bit しかない Xorshift からハムレットが出力される可能性は 0 であると断言できます。Xorshift から確実に生成できる出力列の最大長は 128 bit == 16 byte 分しかありません。

*2:実際には + 以外の演算子を使用することもできます。例えば、以前記事にした System.Random では - を使用しています。

*3: Brent, R. P. (1994). On the periods of generalized Fibonacci recurrences. Mathematics of Computation, 63(207), 389-401.

*4:出典: https://maths-people.anu.edu.au/~brent/trinom.html 。先の論文を書かれた Brent 氏が調べています。

*5:これについては仕込みとかではなく、本当に偶然に発見されたものです。出現確率は雑に計算すると 1/pow(43, 5) ~= 1.5 億分の 1 です。とはいえシーケンスが十分に長いため、こういったことも起こりえます。