パズルゲームでBFS！

はじめに

こんにちは！monoです

最近は競技プログラミングにはまっていて、11月末ICPCという大会に出てさらにモチベが爆発してしまいました。(ICPCについては昨日の記事にもあがってますね)

今回はゲーム開発をした際に競技プログラミングの知識がいい感じに役に立ったことがあったので紹介しようと思います。

状況説明

まずはどんなゲームを作ったのか。

1. 盤面があってその上にピースを並べる
2. 画像左上の部分から電気を流す。そのとき、ピース上の黒い線と家電の部分は電気が流れる
3. 家電に電気が流れているか、ゴール（右下）とつながっているかを判定したい

概要はざっくりこんな感じです

解決方法

タイトルにもあるように、今回はBFS（幅優先探索）というアルゴリズムを使いました。

BFSをどう説明しようか…と思ったらつい先日ちょうど良い動画がyoutubeにあがっているではないか!!! 詳しくはこちらをご覧下さい（投げやり）

https://www.youtube.com/watch?v=0_9heBS7Flg

結局BFSは何ができるんだ!!!と言われますと、まあいろいろありますが、距離が求まります。 判定したいのはつながっているかなので距離を求める必要はありませんが、距離が求まる場所はつながっていて、求まらない点はつながっていないといった感じで判定することができます。

さて、BFSをするのはいいんですが、BFSをするには頂点と辺の情報が必要です。（↑の動画では各マスを頂点とみてその上下左右のマスに向かって辺があるって感じです） しかし、今回の場合は各マスを頂点とみるだけでは連結判定は難しそうです。

そこで、画像でいうとの赤丸のところを頂点として（それが盤面全体に広がっている感じ） 辺は頂点をつないでる黒線の部分（あと家電の部分も）にあると考えると上手くいきそうだな～って考えました。

殴り書きの汚いコードですが、実際のBFSのコード（一部分だけ取り出した）もこんな感じに割とすっきり収まります。競プロをやっていたおかげでこの辺はサクサク書けて楽しかったですね。

int[] vx = { 0, 1, 0, -1 };
int[] vy = { 1, 0, -1, 0 };
Queue<Tuple<int, int>> tq = new Queue<Tuple<int, int>>();
tq.Enqueue(Tuple.Create(sx, sy));
while (0 < tq.Count)
{
    var q = tq.Dequeue();
    int x = q.Item1;
    int y = q.Item2;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + vx[i];
        int ny = y + vy[i];
        if ((0 <= nx && nx <= max_x * 2) && (0 <= ny && ny <= max_y * 2) && power_line[x, y, i] == 1 && distance[nx, ny] == -1)
        {
            distance[nx, ny] = distance[x, y] + 1;
            tq.Enqueue(Tuple.Create(nx, ny));
        }
    }
}

これがどのくらい時間がかかるかというと、縦 $H$ マス、横 $W$ マスとすると $O(HW)$ ぐらい。1000マス $\times$ 1000マスでも1秒以内に計算できるぐらいです。すごい！

電気を流す

余談ですが、BFSで探索しているタイミングで電気のオブジェクトを生成するとめちゃくちゃ簡単に電気を流すことができました。 電気は「Lightning Bolt Effect for Unity」というアセットが使いやすくて良かったです。https://assetstore.unity.com/packages/tools/particles-effects/lightning-bolt-effect-for-unity-59471

これを使うと以下のコードのように電気が生成できます。

//オブジェクト生成
GameObject bolt = (GameObject)Instantiate(lightning, new Vector3(0, 0, 0), Quaternion.identity);
DigitalRuby.LightningBolt.LightningBoltScript boltScript = bolt.GetComponent<DigitalRuby.LightningBolt.LightningBoltScript>();
//始点、終点座標指定
boltScript.StartPosition = new Vector3(0,0);
boltScript.EndPosition = new Vector3(1,1);

これをBFSに突っ込んで…

int[] vx = { 0, 1, 0, -1 };
int[] vy = { 1, 0, -1, 0 };
Queue<Tuple<int, int>> tq = new Queue<Tuple<int, int>>();
tq.Enqueue(Tuple.Create(sx, sy));
while (0 < tq.Count)
{
    var q = tq.Dequeue();
    int x = q.Item1;
    int y = q.Item2;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + vx[i];
        int ny = y + vy[i];
        if ((0 <= nx && nx <= max_x * 2) && (0 <= ny && ny <= max_y * 2) && power_line[x, y, i] == 1 && distance[nx, ny] == -1)
        {
						//オブジェクト生成
						GameObject bolt = (GameObject)Instantiate(lightning, new Vector3(0, 0, 0), Quaternion.identity);
						DigitalRuby.LightningBolt.LightningBoltScript boltScript = bolt.GetComponent<DigitalRuby.LightningBolt.LightningBoltScript>();
						//始点、終点座標指定
						boltScript.StartPosition = new Vector3(x / 2f, y / 2f, -2f);
            boltScript.EndPosition = new Vector3(nx / 2f, ny / 2f, -2f);
            distance[nx, ny] = distance[x, y] + 1;
            tq.Enqueue(Tuple.Create(nx, ny));
        }
    }
}

こんな感じで書けば一応電気は流れます（ゲームを動かすにはもう少しなんやかんやが必要だけと割愛）。自分でも「え？これだけ？」となっていました。

選ばれたのはBFSでした

それと、連結判定するならDFSやUnionFindなど他にも手法があったのですが今回はBFSを選びました。理由は単純にBFSが好きというのはありますが、BFSは「近いところから探索する」という特徴があります。Unityで電気のオブジェクトを生成する部分の処理が重かったらということを考えていて、BFSで探索しているタイミングで電気のオブジェクトを生成すればスタート地点から順に近いところから電気のオブジェクトが発生するので「電流が流れている」っぽい感じになるだろ！って感じの魂胆です。実際は一瞬で電気のオブジェクトが生成されたので杞憂に終わった訳ですが。Unityすごい！

感想・まとめ

開発はWebがメインでゲーム開発はあまりやってこなかった(Unityはほぼ初)のですが、やはり動きがあると開発ﾀﾉｼｲ!!!となっていました（動けば）。 開発した感想としてはゲーム（特にパズルゲーム）ではアルゴリズム力が生かせる場面が多そうだなぁと感じました。今回紹介したゲームでも「どうピースを並べるとクリアできるのか」をいい感じに判定できるようにして問題を自動生成とかできないか…とか考え始めると止まらなくなってしまいます。

以上、ゲーム開発でアルゴリズムの知識が役に立ったという話でした。これからもアルゴリズム力を日々鍛えていきたいと思います。精進精進!!!