【Unity】要素の並びを高速にシャッフルする

トランプなどのカードの並びをシャッフルする良い方法を探してるの。

スクリプトで実装することになるけど、高速にシャッフルできる方法があるわ！

ある配列の要素の並びをシャッフルする方法の紹介です。

要素の並びのシャッフルは、フィッシャー–イェーツのシャッフルと呼ばれるアルゴリズムを使えば高速に実現できます。計算量は要素数に比例し、メモリ消費量は固定です。^[1]

本記事では、フィッシャー–イェーツのシャッフルを使って、配列の要素をシャッフルする方法を解説していきます。

動作環境

Unity2021.2.1f1

目次非表示

フィッシャー–イェーツのシャッフルとは
サンプルプログラム
- 実行結果
さいごに
参考サイト

フィッシャー–イェーツのシャッフルとは

有限個数の要素の配列をランダムな並びにシャッフルするアルゴリズムです。

本記事では、次の改良版アルゴリズムを用いてシャッフルを実現することとします。

要素数が n の配列 a をシャッフルする(添字は0からn-1):
    i を n – 1 から 1 まで減少させながら、以下を実行する
        j に 0 以上 i 以下のランダムな整数を代入する
        a[j] と a[i]を交換する
フィッシャー–イェーツのシャッフル – Wikipedia

このシャッフルアルゴリズムを視覚的に表すと次のようになります。

なお、上記のデモでは数字部分に次のアセットを使用させていただきました。

また、動きの部分には次のアセットを使用させていただきました。

サンプルプログラム

フィッシャー–イェーツのシャッフルを実装したサンプルプログラムです。

与えられた配列に対してシャッフル操作を施す拡張メソッドとして実装しました。

ShuffleExtensions.cs

using System.Collections.Generic;
using UnityEngine;

public static class ShuffleExtensions
{
    /// <summary>
    /// 指定された要素の配列をシャッフルする
    /// </summary>
    public static void Shuffle<T>(this IList<T> array)
    {
        for (var i = array.Count - 1; i > 0; --i)
        {
            // 0以上i以下のランダムな整数を取得
            // Random.Rangeの最大値は第２引数未満なので、+1することに注意
            var j = Random.Range(0, i + 1);
            
            // i番目とj番目の要素を交換する
            var tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }
}

呼び出し元では、次のようにして使います。

ShuffleExample.cs

using System.Linq;
using UnityEngine;

public class ShuffleExample : MonoBehaviour
{
    [SerializeField] private int[] _array;

    private void Update()
    {
        // Enterキーが押されたら
        if (Input.GetKeyDown(KeyCode.Return))
        {
            // 配列をシャッフル
            _array.Shuffle();
            
            // シャッフル結果を出力
            print(
                string.Join(
                    ", ",
                    _array.Select(x => x.ToString())
                )
            );
        }
    }
}