[Unity]シックスボールパズル再現への道（判定編）

# はじめに
Unityを学んで約10か月が経過したエンジニア、シータです。


今回は私が学校の友人と共同で行った**６ボールパズル再現プロジェクト**の話をしようと思います。



成果物をゲーム投稿サイトなどで発信するのは権利的に危ういので、成果物の動画と処理解説を行います！

何卒最後までお付き合いください！

# 成果物

<iframe width="560" height="315" src="https://www.youtube.com/embed/jjaDnBVi0ag?si=JF0Wy-K6GTs3HOww" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>

# 動作環境


Unity2022.3.13f

# スクリプト
<details><summary>判定処理</summary><div> 

```cs
public int ShapeJudgement(int[] GSIArray, GameObject[] GSArray, int[] GSBArray)//物理挙動終了後のボール消しジャッジ
{
    Delete = new List<List<int>>();
    DeleteType = new List<int>();
    DeleteColorList = new List<int>();
    
    int keseta; 
    specialnumber = 0;
    
    bool[] processed = new bool[GSIArray.Length]; //マーキング配列
    List<List<int>> Data = new List<List<int>>(); //二次元リスト

    for (int i = 0; i < GSIArray.Length; i++)
    {
        List<int> sameballslist = new List<int>();
        sameballs = 1;
        if (processed[i]) continue;
        
        CountSameBallsRecursive(GSIArray, GSArray, i, processed, sameballslist);

        if(sameballs > 5)
        {
            sameballslist.Insert(0,i);//add
            Data.Add(sameballslist); //二次元リストに6つ以上連結している番号群を格納する。           
        }
    }
    
    HexagonJudgement(Data, GSIArray, GSArray, GSBArray);
    PyramidJudgement(Data, GSIArray, GSArray, GSBArray);
    StraightJudgement(Data, GSIArray, GSArray, GSBArray);
    
    StartCoroutine(BreakCoroutine(Delete, DeleteType, DeleteColorList, GSIArray, GSArray, GSBArray));

    if (specialnumber > 0)
    {
        keseta = specialnumber + 1;
    }
    else
    {
        if (Data.Count > 0)
        {
            for (int i = 0; i < Data.Count; i++)
            {
                foreach (int ballIndex in Data[i])
                {
                    effectManager.NormalBreak(ballIndex, GSIArray, GSArray, GSBArray);
                }
            }
            keseta = 1;

        }
        else
        {
            keseta = 0;
        }      
    }
    return keseta;
}
```
</div></details>

<details><summary>探索スクリプト</summary><div> 

```cs
void CountSameBallsRecursive(int[] GSIArray, GameObject[] GSArray,int index, bool[] processed, List<int> sameballslist)
{
    
    processed[index] = true; // ボールを処理済みとマーク

    foreach (var j in surrounds)
    {
        if(GSIArray[index] < 1) continue;
        int newIndex = index + j;
        if (newIndex < 0 || newIndex >= GSIArray.Length) continue;

        if(processed[newIndex]) continue;
        
        if (GSIArray[index] != GSIArray[newIndex]) continue;
        switch(index % 19){
            case 0:
                if(newIndex == index - 1 || newIndex == index - 10 || newIndex == index + 9) continue;
                break;
            case 10:
                if(newIndex == index - 1) continue;
                break;
            case 9:
                if(newIndex == index + 1 || newIndex == index + 10 || newIndex == index - 9) continue;
                break;
            case 18:
                if(newIndex == index + 1) continue;
                break;
        }
        sameballs++; // 同じボールを見つけたらカウント
        sameballslist.Add(newIndex);
        CountSameBallsRecursive(GSIArray, GSArray, newIndex, processed, sameballslist);          
    }
}
```
</div></details>

# 判定処理
6ボールパズルの判定処理は予想以上に複雑です。まずは判定処理を語る上で必要な、各スフィアに与えられた番号について確認してください。

<img width="90%" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3680216/627dbe3c-baa8-0e32-30d4-0bd21ababb5b.png">


よって、隣り合うボールの番号は以下のように表せます。

<img width="90%" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3680216/d4a35fb4-9d57-8284-9e55-02f3d8430ef9.jpeg">



また、判定は主に二つのフェーズにわかれており、

**①探索フェーズ：同色かつ隣接したボール番号を保存していく
②形判定フェーズ：特殊な形が紛れ込んでいないか調べる**

というような分け方になります。それではさっそく探索フェーズから見ていきましょう。

## [6ボールパズルのざっくり判定フロー：連結判定]

<details><summary>探索スクリプト</summary><div> 


```cs
void CountSameBallsRecursive(int[] GSIArray, GameObject[] GSArray,int index, bool[] processed, List<int> sameballslist)
{
    
    processed[index] = true; // ボールを処理済みとマーク

    foreach (var j in surrounds)
    {
        if(GSIArray[index] < 1) continue;
        int newIndex = index + j;
        if (newIndex < 0 || newIndex >= GSIArray.Length) continue;

        if(processed[newIndex]) continue;
        
        if (GSIArray[index] != GSIArray[newIndex]) continue;
        switch(index % 19){
            case 0:
                if(newIndex == index - 1 || newIndex == index - 10 || newIndex == index + 9) continue;
                break;
            case 10:
                if(newIndex == index - 1) continue;
                break;
            case 9:
                if(newIndex == index + 1 || newIndex == index + 10 || newIndex == index - 9) continue;
                break;
            case 18:
                if(newIndex == index + 1) continue;
                break;
        }
        sameballs++; // 同じボールを見つけたらカウント
        sameballslist.Add(newIndex);
        CountSameBallsRecursive(GSIArray, GSArray, newIndex, processed, sameballslist); //再帰処理          
    }
}
```
</div></details>

上のスクリプトを開いていただくと、再帰的な構造になっていることがわかります。
いわゆる、**深さ優先探索**というやつです。

![Depth-first-tree.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3680216/679e3d97-07a8-a4fb-bfca-27d11d2e2dee.png)

#### 深さ優先探索に関する説明（Wikipedia参照）
>"形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。"
 
 https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

 　
深さ優先探索の説明は少し割愛するとして、基本的な探索のフローを以下に示します。

　
<font color="red">**1**</font>：0番から132番まで番号順に<font color="red">**2**</font>、<font color="red">**3**</font>の処理を行う。


<font color="red">**2**</font>：<font color="orange">**「同色かつ隣り合わせのボール」**</font>の番号があれば連結リストに格納。
```cs
sameballslist.Add(newIndex); //連結リスト
```

<font color="red">**3**</font>：起点を<font color="red">**2**</font>で選んだ<font color="orange">**「同色かつ隣り合わせのボール」**</font>に移し、<font color="red">**2**</font>の処理を実行。

<font color="red">**4**</font>：処理が完結するまで<font color="red">**2**</font>と<font color="red">**3**</font>を繰り返し、リストの要素数が5つに満たない場合は連結リストを空にして<font color="red">**1**</font>を進める。

<font color="red">**5**</font>：5つを超えた場合は6つ以上のボールが連結しているため、二次元リストにそのリストごと格納する。
　


**「なんのこっちゃ・・・・。」**

　
って感じでも大丈夫です！
要は下の画像のように、

<img  width ="80%" src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3680216/d0aa76b5-9f8d-be73-f909-99a46f472ca6.jpeg">

<font color="orange">**同色かつ隣り合わせのボール i + 10 と
同色かつ隣り合わせのボール i + 11 と
同色かつ隣り合わせのボール i + 21 と
同色かつ隣り合わせのボール i + 30 と
・・・・・
同色かつ隣り合わせのボール i + 14**　　みたいな感じで</font>

#### 枝分かれを繰り返して探索を行い、最終的に同色で連結した番号を全部保存しとこうぜ！！！！

ってことです。


ただここで重要なのが、**一度探索したボールは二度と探索しない**こと。
これがないと、連結した2つの同色同士で探索を永遠と繰り返してしまうからです。

今回はとりあえず、探索したかどうかをマーキングするための配列を用意し、マーキング配列の10番目がtrueなら10番目のボールは探索しない、といったような処理を挟んでいます。

```cs:HexagonalJudgement
    processed[index] = true; // ボールを処理済みとマーク
    
    //・・・・//
    
    if(processed[newIndex]) continue; //マーキング配列processed[]がtrueなら探索対象からはじく
```
これで、6つ以上同色で隣り合わせの番号群が格納された、二次元データが得られました。

## [6ボールパズルのざっくり判定フロー：形判定]

あとは正直簡単です。先ほど得られた隣接同色群のデータすべてにおいて、

<font color="red">**1**</font>：ヘキサゴンが作れるかどうかの判定


<font color="red">**2**</font>：ピラミッドが作れるかどうかの判定

<font color="red">**3**</font>：ストレートが作れるかどうかの判定

を行います。
参考に、ヘキサゴンかどうかを判定するコードだけ添付しておきます。

```cs:HexagonalJudgement
void HexagonJudgement(List<List<int>> Data, int[] GSIArray,GameObject[] GSArray, int[] GSBArray)
{
    int color = 0;
    for (int i = 0; i < Data.Count; i++)
    {
        for (int j = 0; j < Data[i].Count; j++)
        {
            List<int> hexagon = new List<int> {Data[i][j], Data[i][j] + 1, Data[i][j] + 9, Data[i][j] + 19, Data[i][j] + 20, Data[i][j] + 11};
            bool result = hexagon.All(item => Data[i].Contains(item));

            if(!result) continue;

            color = GSIArray[Data[i][j]];
            if (DeleteColorList != null && DeleteColorList.Contains(color)) break;
            
            Delete.Add(hexagon); //エフェクトを発生させるときに使う
            DeleteType.Add(0); //エフェクトを発生させるときに使う
            DeleteColorList.Add(color); //エフェクトを発生させるときに使う

            specialnumber++;
            break;
        }
    }
    
}
```

これは同色群のなかに、**ヘキサゴンが紛れてないか**を判定するコードです。

下図のように、いびつな形をしているけどヘキサゴンが隠れているケースは往々にして存在するので、

![ゲーム案0510-6 (1).jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3680216/3cc7aa39-ab3c-b463-9f74-58446f84a0ac.jpeg)

格納されたすべての番号を起点として、

**ヘキサゴンを作れると仮定したときの番号の組み合わせ**

を考え、実際のデータの要素にすべて含まれているかどうかを調べます。

```cs
List<int> hexagon = new List<int> {Data[i][j], Data[i][j] + 1, Data[i][j] + 9, Data[i][j] + 19, Data[i][j] + 20, Data[i][j] + 11};
bool result = hexagon.All(item => Data[i].Contains(item));
```


これで、なんとか紛れ込んだヘキサゴンの判定はできそうです。

また、６ボールパズルでヘキサゴンなどの特殊な形が生まれた際は、同じ色のボールを全消しする。というシステムがあります。

つまり、同色群データの中に特殊な形を作れる同じ色の群が2つ以上あっても、実際に判定されるのは１つだけで良いわけです。そのために以下のコードを挟んでいます。

```cs
if (DeleteColorList != null && DeleteColorList.Contains(color)) break;
```

DeleteColorListというのは全消しできる色を格納させたリストです。同時並行でDeleteやDeleteTypeといったリストで<font color="red">**色**</font>と<font color="red">**形**</font>と<font color="red">**形の中で最も若い番号**</font>を控えてあるので、3つのリストに形判定の最終的な情報が保存されていることになります。


もしすでに同じ色の全消し予約が入っているなら形判定はこれ以上行わず、死にリストとして処理を中断（break）します。

そして次の同色群の判定に移る、といった感じですね。


  　


<font color="red">
※（2024/2/20追記）
おそらく上のコードだと、ヘキサゴンの優先度が守られていません。
例えば上の方に青いヘキサゴン、下の方に青いピラミッドがあってお互い連結はしてないとなると、普通にピラミッドから全消しを行ってしまうプログラムになっています。

同色をはじくのではなく、実際にオブジェクトを破壊する際にDeleteTypeに格納された形データを参照してヘキサゴンを優先的に破壊する処理を加えておく必要がありそうです。</font>


## [このあとの処理]

おそらく以下の三通り

**１、もし特殊な形があれば、全消しして落下処理に移行する。**

**２、特殊な形ではないが6つ以上連結したボールがあれば、それらを消して落下処理に移行する。**

**３、消せるものがなければ、落下処理を飛ばして新しいボールを追加する処理に移行する。**

落下処理については共同開発者が記事にしてくれているので、こちらをご覧ください。↓↓↓

https://qiita.com/Jun_Ishikawa/items/fe6a533c0531a9071d99

## おわりに

ここまで読んでくださった方ありがとうございました。理解に苦しむ箇所もあったでしょう。（私の説明力が原因）

今回は特に割愛のオンパレードだったので、いくつか解説が抜けてたりします。また初学者なので変数名が適当だったりいらない処理を挟んでいたりします。

しかし、現状シックスボールパズルの処理を解説しているブログは1つか2つしかなく、これらの処理はほとんど自分の力で作り上げました。かなり大変でしたがなんとか正常な動作を再現することができました。

そこで、私は今回学んだ内容を活かしてゲームを作ってみました。それがこちらになります。

https://unityroom.com/games/8squarepuzzle

<img width = "500" src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3680216/f00b6c11-1289-76a0-9322-42e70411d805.png">

その名も**エイトスクエアパズル**です。

学んだことを速攻活かしたくなるタイプでして、2日ほどで仕上げました。是非遊んでみてください。

それでは、次回の**シックスボールパズル再現への道：エフェクト編**でお会いしましょう！

### **ツァイチェン！！**