ゴリラが派手に破壊するためのアルゴリズム 〜よく知られたアルゴリズムをゲーム開発へ応用する時の考え方〜

AdventCalendar2025 unity

本記事は面白法人グループ Advent Calendar 2025の16日目の記事です。

こんにちは

どうも、ゴリラです。もとい@commojunです。今回はUnityを使って、こちらのゴリラさんが活躍するゲームを作ってみました。動画を御覧ください。

ゲーム動画

ゲームの特徴

これは、ゴリラさんが画面奥方向へ疾走するタイプのランゲームです。このゲームの特徴には、以下のようなものがあります。

  • 自動的に走行するゴリラさんを左右に操作しながら、道中にあるブロックでできた建物を破壊する
  • 破壊したブロックの破片は、ゴール上空に飛んでいき、大きな塊になる
  • ゴールに到着したゴリラさんは大きくジャンプし、大きな塊に最後の一撃！を加える
  • 最後の一撃！ですべての破片が吹っ飛び、スコアボードに着地し、その位置によってスコアが集計される

特にこだわったのは、やはり最後の一撃！ですね。道中の建物を壊せば壊すほど、最後の塊がより大きくなり、ゴリラさんの破壊演出がより派手になるという仕組みになっています。

派手な破壊

フレームレート落ち問題

ゴリラ界ではなかなか好評な演出でしたが、一つ問題がありました。それは、破片が増えすぎると処理が重くなり、フレームレートが落ちてしまう問題です。

破片が増えれば増えるほど、物理運動を計算しなければいけないオブジェクトの数が増えるのはもちろんのこと、破片同士の衝突判定を計算しなければならない数もn2オーダーで増えてしまいます（私の調査不足の可能性もありますが、レイヤーの設定を調整して破片同士の衝突を無効にしても衝突判定の計算自体は減らすことができませんでした）。

このゲームはスマートフォンでプレイすることを想定したものであるため、ミドル〜ロースペックのスマートフォンでもある程度サクサクと動作する必要があります。ですが、何も考えずに実装するとこの通り、実機の映像では、フレームレートが落ちて画面がカクカクになってしまいます。

スマートフォン実機での映像

これでは、せっかくこだわった破壊演出の気持ちよさが台無しです。何か軽量化のための対策をする必要があります。

クラスタリングする

そこで今回取った作戦は、近くにある破片同士をある程度グループにまとめるクラスタリングを行い、物理エンジンの計算をさせるオブジェクトの個数を削減させるという方法です。例えば、オブジェクトの数が500個の場合と200個の場合で比較するとこうなります。

  • 500個の場合
    • 物理演算: 500個/フレーム
    • 衝突判定: 250,000ペア/フレーム
  • 200個の場合
    • 物理演算: 200個/フレーム (60%削減)
    • 衝突判定: 40,000ペア/フレーム (84%削減)

このように、計算対象とするオブジェクト数を削減することによる効果は大きく、一定の上限を設定可能な方法でクラスタリングできれば、ある程度の性能が担保できると言えます。

k-meansアルゴリズム

バラバラのオブジェクト同士を近隣の者同士でまとめるクラスタリング手法といえば…k-meansというアルゴリズムを思い浮かべる方も多いかと思います。アルゴリズムの概要をざっくり説明すると以下のような感じです。

  1. k個の初期centroid（クラスタ中心）をランダムに選択
  2. 各データ点を最も近いcentroidに割り当て
  3. 各クラスタのcentroidを、そのクラスタに属する点の平均位置として再計算
  4. centroidの変化が閾値以下になるまで2-3を繰り返す（収束まで）

k-meansアルゴリズム

このアルゴリズムを利用すれば、多数の破片を効率的にまとめ上げ、物理シミュレーションさせるオブジェクトの個数を最大k個に抑えることができそうです。

それでは実際に実装してみようと思ったのですが、私の直感が「待てよ」と訴えかけてきました。

内なるゴリラの声を聴く

ここでいったん立ち止まり、私の内なるゴリラが訴えかけてくる直感に耳を傾けることにしました。

アルゴリズムのステップを教科書通りにすべて実装する必要はないのではないか？

私は、このゲーム特有の前提事項や、演出上「これで十分」とできる品質のラインを鑑みると、k-meansアルゴリズムのステップのうち、かなりの部分が必要ないことに気が付きました。

centroid（クラスタ中心）をランダムに選択する必要がない

まず、クラスタの中心であるcentroidをランダムに選択する必要がないことに気が付きました。なぜなら、ステージの道中に破壊した建物の破片はランダムに飛び散り、ゴール上空で塊を形成します。破片が塊のどの位置に付着するかは完全にランダムです。つまり、塊に到着した先着k個の破片をそのままcentroidとするだけで、centroidをランダム選択することとほぼ同義の手続きを達成できるのです。これでk-meansアルゴリズムのステップ1が不要となりました。

centroidの位置を再計算する必要がない

本来のk-meansアルゴリズムでは、centroidの位置を何回も再計算する手続きがありますが、これも不要であると気が付きました。そもそもこのアルゴリズムは、データマイニングや機械学習などの分野で用いられているものであり、各ノードを意味のあるクラスタに分類することと、centroidがそのクラスタの特性を代表する正確な重心点であることへの関心が高い場合に有用なものです。翻ってこのゲームにおいては、クラスタ分類にもcentroidにも意味は求められておらず、なんとなく近所で固まってれば十分であるため、ステップ3、ステップ4のcentroid再計算の手続きは不要となります。

シンプルなクラスタリングアルゴリズム

すると、本ゲームにおける、破片のクラスタリングアルゴリズムはかなりシンプルになります。

  1. 先着k個の破片をcentroidとする
  2. k+1番目以降に到着した破片は、最も距離が近いcentroidの子要素にする

これだけで、必要なクラスタリングが完了します。

コライダーの統合

無事にクラスタを形成し、物理計算するオブジェクトの個数を削減できたのですが、これだけでは性能の改善には至りませんでした。原因は、クラスタリングしてもなお、そのクラスタに属する破片一つ一つが個別にコライダー（当たり判定を行う箱）を持っていたためでした。そのため、衝突判定を行うペア数の削減には至っていなかったのです。この問題を解決するためには、おのおのが持つコライダーを、クラスタを内包する大きなコライダーへと統合する必要がありました。

コライダーの統合自体は、UnityのBoundsクラスに用意されたEncapsulate()関数を応用すれば比較的簡単に実装できます。

private void Integrate(Crust parent, Crust child)
{
    BoxCollider parentCollider = parent.rb.GetComponent<BoxCollider>();
    Collider childCollider = child.rb.GetComponent<Collider>();

    // バウンディングボックスを統合
    Bounds parentBounds = parentCollider.bounds;
    Bounds childBounds = childCollider.bounds;
    parentBounds.Encapsulate(childBounds);

    // 親のコライダーを拡張
    parentCollider.size =
        parentCollider.transform.InverseTransformVector(parentBounds.size);
    parentCollider.center =
        parentCollider.transform.InverseTransformPoint(parentBounds.center);

    // 子のコライダーを無効化
    childCollider.enabled = false;
}

しかしこの時、親要素となるオブジェクトが中途半端な向きに回転していると、期待した結果が得られないことがわかりました。問題を特定して、親要素が回転していても期待した結果を得るためにはかなり深い理解と複雑な実装が必要になりそうであったため、親要素の回転をリセットしてからこのロジックを適用することにしました。割り切りも重要です。

親となるブロックの向きがリセットされている

これらの工夫を組み合わせることで、破片同士を効率的にクラスタリングし、パフォーマンスの向上に寄与することができました。

クラスタリングされている様子

比較

クラスタリングの適用前と後の比較動画を見てみましょう。

before ← → after

ウホッ！これは全然違いますね！物理エンジンの計算対象とするオブジェクト数の削減により、目に見えて爽快感が向上していることが感じ取れます。

さいごに

いかがでしたか？ゴリラさんもこの通り、ニッコリですね。

本記事では、ゴリラさんが疾走するランゲームで、多くのオブジェクトを効率的に破壊するためのクラスタリング手法について解説しました。k-meansアルゴリズムのように、教科書に載っているような様々なアルゴリズムの知識を引き出しに多く持っておくことは、エンジニアとして問題解決の手札を増やすことができて有用だと思います。その一方で、世の中で知られているアルゴリズムを今取り組んでいる問題にそのまま適用するのではなく、その問題のバックグラウンドや、どこまでの水準で問題を解決すれば十分なのかを同時に鑑みることも重要だと思います。その上で、必要に応じて必要な分だけアルゴリラズムのエッセンスを取り入れ、応用できるエンジニアが実務上で信頼されるのではないかと思います。ゴリラさんが教えてくれました。

カヤックではゲームのパフォーマンスチューニングを楽しみながら実装できるエンジニアを募集しています。