Unityの接触判定管理を隣接行列を用いて表現してみる試み

前置き

大量の接触判定管理を同時にいい感じに管理して参照する方法はないかなと この質問 を見てて思ったところ高専時代に離散数学の授業をしてた某教員の顔が思い浮かびグラフ理論で見られる無向グラフで接触状態を表現できるのではないかと思いこの記事を書きました

サンプルコード

以下の解説で使用される実装は上記のリポジトリにおいて公開されています。
Unity2Dで実装されていますがわかっている人なら3Dでも容易に書き換えられると思います。

前提条件

以下のようなボールがいくつもあるなかでボールをClickすると隣接してるボールが消えてClickしたボールも消えるような実装を書きたい。

説明っぽいやつ

※参考文献の最初の6ページ位を事前に読んでもらえると理解が進みます。素晴らしい資料ですね・・・

頂点の集合Vと枝の集合Eとして表現できるデーター構造は以下のようにあらわすことができます。

G=(V,E)

今回やりたいのはボール同士の当たり判定を管理したいので頂点をボール、枝を「当たってる状態」として表現します
枝に方向が定義されてない場合は無向グラフ、ある場合は有向グラフとして扱われますが今回は只の当たり判定なので無向グラフとして考えます

(イメージ図: 雑で申し訳ない・・・）

グラフの数値的表現

※参考文献の6pに丁寧な説明があるためスキップしてそちらを読んでも差し支えない
隣接している頂点の関係はリスト、行列を用いて表現可能でこれらを隣接行列、隣接リストと言います。
頂点$(v,u)$ に隣接関係があるとき行列成分$a(v,u)=1$、ないときは$a(v,u)=0$になるデータ表現。
今回は表現と実装が容易な隣接行列を用いて頂点同士の隣接関係（ボールの接触関係）を表現します。
以下のようなグラフがあるときは

次のような行列で表すことができます

a=
\begin{pmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{pmatrix}

n行目m列が1なら頂点nと頂点mが隣接関係にある、0ならないといった感じで表現されます。
そのような表現方法を使うため対称行列になります。

行列と行ってもなんかガリガリ数値計算をするわけでもないので只の隣接一覧表みたいな感じですね

実装

基本的な考え方

隣接行列はあくまでも当たり判定がどうなっているかを記録する為の表現方法に過ぎないのでBallクラスを作ってballのPrefabにアタッチしそこでOnCollisionEnter2D OnCollisionExit2Dをイベントを呼べるようにして当たり判定がとられる&外れる度にBallPlayManagerクラスの隣接行列を更新するような実装にします。

BallManager

当たり判定の状態管理とボールの生成からDestroy()まではこのクラスにやってもらいます

using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// ボールを生成したり管理したりするクラス
/// </summary>
public class BallPlayManager : MonoBehaviour
{
    [SerializeField]
    private int _maxBall = 900;

    [SerializeField]
    private Transform _ballGenratePos; //ballの生成位置をtransformで定義

    //ballの数×ballの数のサイズになる隣接行列を定義
    private bool[,] _adjacencyMatrix; //隣接行列でBallの接続関係を表現する無向グラフを表現する
    private List<Ball> _balls;//各ballPrefabにアタッチされてるballクラスを格納するリスト
    private string _ballPrefabPath = "TestBall"; // 動的生成するPrefab名を指定（Resourcesにある）

    private void Start()
    {
        _balls = new List<Ball>(_maxBall);
        _adjacencyMatrix = new bool[_maxBall, _maxBall];//
        BallGenerate();
    }

    /// <summary>
    /// ボール生成クラス、Eventの追加
    /// </summary>
    private void BallGenerate()
    {
        GameObject obj = (GameObject)Resources.Load(_ballPrefabPath);

        for (int i = 0; i < _maxBall; i++)
        {
            _balls.Add(Instantiate(obj, _ballGenratePos).GetComponent<Ball>());
            _balls[i].BallNumber = i;//ballの要素番号をballのIDとして使うよ
            _balls[i].ColliderEnter.AddListener(AdjacencyMatrixEnterUpdateEvent);//当たった時のイベントを購読
            _balls[i].ColliderExit.AddListener(AdjacencyMatrixExitUpdateEvent);//当たり判定が外れたときのイベントを購読
            _balls[i].OnClick.AddListener(BallClickd);//Clickした時のイベントを購読
        }
    }

    /// <summary>
    /// 接触状態になったときに反映されるメソッド
    /// </summary>
    /// <param name="mynumber"></param>
    /// <param name="ballnumber"></param>
    private void AdjacencyMatrixEnterUpdateEvent(int mynumber, int ballnumber)
    {
        _adjacencyMatrix[mynumber, ballnumber] = true;//頂点(v,u)を1にする処理
    }

    /// <summary>
    /// 接触状態が解除になったときに反映されるメソッド
    /// </summary>
    /// <param name="mynumber"></param>
    /// <param name="ballnumber"></param>
    private void AdjacencyMatrixExitUpdateEvent(int mynumber, int ballnumber)
    {
        _adjacencyMatrix[mynumber, ballnumber] = false;//頂点(v,u)を0にする処理
    }

    /// <summary>
    /// 生成したballがClickされときに呼ばれるメソッド
    /// </summary>
    private void BallClickd(int ballnumber)
    {
        for (int i = 0; i < _maxBall; i++)
        {
            if (_adjacencyMatrix[ballnumber, i] && i != ballnumber)
            {
                Destroy(_balls[i].gameObject); //隣接行列で接触状態にあるボールを破壊
            }
        }
        Destroy(_balls[ballnumber].gameObject); //最後にClickされたボールを破壊
    }
}

Ballクラス

当たり判定系のイベント関数やClickEventはこっちに持ってもらいボールごとに発火するように実装しています。

using UnityEngine;
using UnityEngine.Events;

/// <summary>
/// ボール本体にアタッチされるクラス
/// </summary>
public class Ball : MonoBehaviour
{
    public int BallNumber = -1;

    //ボールの当たり判定が発火した時に呼ばれるEvent型を定義
    [System.Serializable]
    public class BallColliderEventType : UnityEvent<int, int>
    { }

    // ボールがClickされたときに発火するEvent型を定義
    [System.Serializable]
    public class BallClickEvent : UnityEvent<int> { }

    public BallColliderEventType ColliderEnter = new BallColliderEventType();
    public BallColliderEventType ColliderExit = new BallColliderEventType();
    public BallClickEvent OnClick = new BallClickEvent();

    /// <summary>
    /// 当たったら隣接行列の要素を1(bool型なのでtrue)
    /// </summary>
    /// <param name="other"></param>
    private void OnCollisionEnter2D(Collision2D other)
    {
        //壁とか関係ないObjectに接触した時の為にTrygetComponentでBallかどうか判定
        if (other.gameObject.TryGetComponent(out Ball ball))
        {
            ColliderEnter.Invoke(BallNumber, ball.BallNumber);
        }
    }

    /// <summary>
    /// 接触状態が外れたら隣接行列の要素0(bool型なのでfalse)
    /// </summary>
    /// <param name="other"></param>
    private void OnCollisionExit2D(Collision2D other)
    {
        if (other.gameObject.TryGetComponent(out Ball ball))
        {
            ColliderExit.Invoke(BallNumber, ball.BallNumber);
        }
    }

    /// <summary>
    /// Clickされたときに呼ばれるEvent(serializefieldでアタッチ)
    /// </summary>
    public void ClickEvent()
    {
        OnClick.Invoke(BallNumber);
        //Debug.Log(BallNumber);
    }
}

出来上がった実装

特に実用する気はなく思いつきが実装になったらどんな感じかなみたいな気持ちで書きました。

参考文献

東北大学塩浦准教授 講義資料　アルゴリズムとデータ構造
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad09/ad09-09.pdf

余談

グラフ（離散数学的）をサクッと書くときはGraphvizOnlineが便利だということがわかった。

graph {
  1 -- 2
  1 -- 3
  2 -- 3
  3 -- 4
}

簡単な無向グラフぐらいならこれで書けます。
あと更に余談なんですが
ffmpeg -i {任意のmp4} {任意の名前}.gifで .gifが出力されるの便利ですね・・・世界は便利にあふれている・・・