ぷよぷよみたいなゲームのチェックアルゴリズム

[ちゅるん]

ぷよぷよみたいなパズルゲームを作りたいと思っているのですが、連続した色がy軸かx軸にあるかどうかというチェックのアルゴリズムが思いつきません。

ブロックが落下した際にそのブロックの配列からx--とx++、y--とy++方向に同じ色があるか

もし限界領域内であり、y--方向にあった場合は探索位置をy方向に一つずらし、同じ方法で探索。

繰り返して探索結果が同じ色が4つ以上存在した場合、ブロックを削除し、-y軸にあるブロックを消去分だけ下げる

という方法が私の思いつきの限界なのですが、それでは上と下や上と右、各上下左右に同じ色が存在した場合に正しい結果が得られない気がします。

何か良いアルゴリズムなどございますでしょうか

[やっくん]

オセロを作ったときに似たようなことを考えたので、私の手法を書きます。

①グローバル変数で繋がっているものをカウントする変数を用意しておく
②ブロック落下→そのブロックの周りを縦横、再起的に調べていく
③色が同じならカウント、その際にブロックの位置を覚えさせておく
③全て見終わったらカウンター値から評価し、位置を覚えておいたブロックを消したり消さなかったり。

スマートな手法ではないかもしれません（＾＾；
参考程度にどうぞ。

[dic]

全部チェックする方法なので速度的に問題あるかもしれませんが

配列 int a[10][10][10] とする
最初に中身があったらその中身の色を記憶
隣をチェック、最初の色と同じかどうかチェック
同じ色だったらカウント
違う色だったらカウントやり直し
カウントが４になってたら消すフラグを立てておく
次に縦方向で同じチェックをする
消すフラグがたっているのを消す処理をする

とまぁ、総当たりで解けます

[へろりくしょん]

要は塗りつぶし処理と同じだと考えればいいと思いますよ。
ＭＳペイントにありますよね。　起点と同じ色のピクセルを塗りつぶす機能。　アレです。

[Dixq (管理人)]

ちゅるんさん

ただ玉を数えるだけでも結構難しいですよね。
やっくんさんも書かれている通り、再帰関数で計算すると計算しやすいと思います。
といっても再帰関数って使った事が無いと良く解らないと思うので、
隣接ブロックの同じ色の数を数える関数を作ってみました。

void CheckBlock(
    bl_t bl[Y][X],    //ブロックの情報
    int x,        //座標
    int y,
    int *cnt    //数えた個数
){
    int col;

    (*cnt)++;    // カウントをインクリメントする

    col = bl[y][x].col;    // 色情報を一時的に保存する

    bl[y][x].Checked = 1;    // 検査済みの箇所に印を付ける

    // 上下左右方向で隣接している同色ぷよの数をカウントする
    if (一番上ではない && 未検査 && bl[y-1][x].col == col) CheckBlock(bl, x, y-1, cnt);
    if (一番下ではない && 未検査 && bl[y+1][x].col == col) CheckBlock(bl, x, y+1, cnt);
    if (一番左ではない && 未検査 && bl[y][x-1].col == col) CheckBlock(bl, x-1, y, cnt);
    if (一番右ではない && 未検査 && bl[y][x+1].col == col) CheckBlock(bl, x+1, y, cnt);
}

　


コンパイルも何もしてないので、間違いがあるかもしれませんが・・。

左、上、右、下に隣接したブロックが無いか調べ、
あれば、その座標を自分の関数に渡します。
そうすると同じ処理を順次位置を変えながら行うことが出来ます。

再帰関数が良く解らなければ、こちらで
http://dixq.net/sort.html
再帰関数を使ったクイックソートをアニメーションで説明しているアプリがあるのでよろしければお使いください。

[へろりくしょん]

以前ぷよぷよを作ったときのソースがありますので、載せておきます。

実際にはちょっと違いますが、概ねこんな感じです。

第一引数のfdはフィールドを表す２次元配列です。
FIELD_X、FIELD_Y はそれぞれフィールドの幅と高さです。　６と１３ですね。

第２引数ｘ、第３引数ｙを基点とし上下左右を調べて同じ色なら再帰します。
戻り値は消されるぷよの数です。

addErasePuyo() 関数は一時的な消去バッファへ消す予定のぷよを放り込みます。

途中で現れる５という数値は、おじゃまぷよを表すぷよの番号です。


参考までに。

int eraseLoop(unsigned char fd[FIELD_X][FIELD_Y], int x, int y, int cnt)
{
    unsigned char puyo = fd[x][y];

    addErasePuyo(x, y, puyo);

    cnt++;
    if(x > 0){
        if(fdd[x - 1][y] == puyo) cnt = eraseLoop(fd, x - 1, y, cnt);
        else if(fd[x - 1][y] == 5) addErasePuyo(x - 1, y, 5);
    }
    if(x < FIELD_X - 1){
        if(fd[x + 1][y] == puyo) cnt = eraseLoop(fd, x + 1, y, cnt);
        else if(fd[x + 1][y] == 5) addErasePuyo(x + 1, y, 5);
    }
    if(y > 0){
        if(fd[x][y - 1] == puyo) cnt = eraseLoop(fd, x, y - 1, cnt);
        else if(fd[x][y - 1] == 5) addErasePuyo(x, y - 1, 5);
    }
    if(y < FIELD_Y - 1){
        if(fd[x][y + 1] == puyo) cnt = eraseLoop(fd, x, y + 1, cnt);
        else if(fd[x][y + 1] == 5) addErasePuyo(x, y + 1, 5);
    }

    return cnt;
}

[バグ]

１つ確認したいのですが、知りたいのは…

ぷよぷよルール(ブロックが一定個数以上隣接している個数を数える)なの？

コラムスルール(ブロックが一定個数以上並んでいるのを数える)なの？

タイトルはぷよぷよだけど、質問を読む限りではコラムスルールのように思えたので(^_^;)

[バグ]

とりあえず、ぷよぷよルールだった場合のサンプルを作ってみました。
コンソールアプリです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define WIDTH    6        // フィールド幅
#define HEIGHT    16        // フィールド高
#define VANISH    4        // 消去に必要な個数
#define COLOR    3        // 色数

// ブロック管理用構造体
struct BLOCK
{
    int nColor;        // 色
    int nVanish;    // 消去フラグ
};

// フィールド管理用構造体
struct FIELD
{
    struct BLOCK stBlock[WIDTH][HEIGHT];    // ブロック構造体配列
};

// 関数のプロトタイプ宣言
void ShowField(struct FIELD* pField);
int Check(struct FIELD* pField);
void Vanish(struct FIELD* pField);
int Slide(struct FIELD* pField);
void Count(struct FIELD* pField, int nX, int nY, int* pCount);

// メイン関数
int main(void)
{
    int nX = 0;
    int nY = 0;
    int nChain = 0;
    struct FIELD stField;

    // 乱数の種を仕込む
    srand((unsigned)time(NULL));

    // フィールドへ適当な色のブロックを仕込む
    for (nY = 0; nY < HEIGHT; ++nY)
    {
        for (nX = 0; nX < WIDTH; ++nX)
        {
            stField.stBlock[nX][nY].nColor = rand() % COLOR + 1;
            stField.stBlock[nX][nY].nVanish = 0;
        }
    }

    // 初期状態の描画
    printf("初期状態\n");
    ShowField(&stField);
    getchar();

    // 消去箇所が存在する間はループを続ける
    while (Check(&stField) != 0)
    {
        // 消去チェック後の状態を描画
        printf("%2d連鎖\n", ++nChain);
        printf("チェック後\n");
        ShowField(&stField);
        getchar();

        // 消去処理後の状態を描画
        printf("消去後\n");
        Vanish(&stField);
        ShowField(&stField);
        getchar();

        // 空白を詰める為に１段ずつ落下させる
        while (Slide(&stField) != 0)
        {
            printf("１段落下後\n");
            ShowField(&stField);
            getchar();
        }
    }

    printf("%2d連鎖で終了しました\n", nChain);
    return 0;
}

// フィールドを描画
void ShowField(struct FIELD* pField)
{
    int nX = 0;
    int nY = 0;

    for (nY = 0; nY < HEIGHT; ++nY)
    {
        for (nX = 0; nX < WIDTH; ++nX)
        {
            // 色と消去フラグを表示する
            printf("[%2d,%2d] ", pField->stBlock[nX][nY].nColor, pField->stBlock[nX][nY].nVanish);
        }
        putc('\n', stdout);
    }
    putc('\n', stdout);
}

// 全ブロックの同色で隣接している個数をチェックする
int Check(struct FIELD* pField)
{
    int nX = 0;
    int nY = 0;
    int nReturn = 0;
    struct FIELD stDummy;

    for (nX = 0; nX < WIDTH; ++nX)
    {
        for (nY = 0; nY < HEIGHT; ++nY)
        {
            // 空白＝０としているので、０の場合は何もしない
            if(pField->stBlock[nX][nY].nColor == 0)
            {
                continue;
            }

            // 消去フラグをクリアしておく
            pField->stBlock[nX][nY].nVanish = 0;

            // フィールド構造体をコピーして、検査用の構造体領域を作成する
            memcpy(&stDummy, pField, sizeof(struct FIELD));

            // 同色で隣接している個数をカウントする
            Count(&stDummy, nX, nY, &pField->stBlock[nX][nY].nVanish);

            // 同色で隣接している個数がVANISH定数を超えていたら、戻り値を１にする
            nReturn |=(pField->stBlock[nX][nY].nVanish >= VANISH);
        }
    }

    // １箇所でも消去される箇所があれば１、なければ０が返る
    return nReturn;
}

// VANISH定数よりたくさん同色で隣接していたら消去する
void Vanish(struct FIELD* pField)
{
    int nX = 0;
    int nY = 0;

    for (nX = 0; nX < WIDTH; ++nX)
    {
        for (nY = 0; nY < HEIGHT; ++nY)
        {
            // 同色での隣接数がVANISH定数以上か？
            if(pField->stBlock[nX][nY].nVanish >= VANISH)
            {
                // ブロック情報をクリアする
                memset(&pField->stBlock[nX][nY], 0, sizeof(struct BLOCK));
            }
        }
    }
}

// 消去されて空いた隙間を１段だけ詰める
int Slide(struct FIELD* pField)
{
    int nX = 0;
    int nY = 0;
    int nReturn = 0;

    for (nY = HEIGHT - 1; nY >= 1; --nY)
    {
        for (nX = 0; nX < WIDTH; ++nX)
        {
            // 検査箇所が空白で、１つ上が空白ではない場合
            if(pField->stBlock[nX][nY].nColor == 0 &&
                pField->stBlock[nX][nY - 1].nColor != 0)
            {
                // 検査箇所へ１つ上のブロック情報をコピーする
                memcpy(&pField->stBlock[nX][nY], &pField->stBlock[nX][nY - 1], sizeof(struct BLOCK));

                // １つ上のブロック情報をクリアする
                memset(&pField->stBlock[nX][nY - 1], 0, sizeof(struct BLOCK));

                // 動いた箇所があったので、戻り値を１にする
                nReturn  = 1;
            }
        }
    }

    // 動いた箇所があった場合は１、そうでない場合は０が返る
    return nReturn;
}

// 同色で隣接している個数を数える（再帰関数）
void Count(struct FIELD* pField, int nX, int nY, int* pCount)
{
    // 検査箇所の色を保持する
    int nColor = pField->stBlock[nX][nY].nColor;

    // ダブって検査しないように、検査した箇所のブロック情報をクリアしておく
    memset(&pField->stBlock[nX][nY], 0, sizeof(struct BLOCK));

    // カウンタをインクリメントする
    ++(*pCount);

    // １つ上のブロックを検査
    if(nY - 1 >= 0 && nColor == pField->stBlock[nX][nY - 1].nColor)
    {
        Count(pField, nX, nY - 1, pCount);
    }

    // １つ下のブロックを検査
    if(nY + 1 < HEIGHT && nColor == pField->stBlock[nX][nY + 1].nColor)
    {
        Count(pField, nX, nY + 1, pCount);
    }

    // １つ左のブロックを検査
    if(nX - 1 >= 0 && nColor == pField->stBlock[nX - 1][nY].nColor)
    {
        Count(pField, nX - 1, nY, pCount);
    }

    // １つ右のブロックを検査
    if(nX + 1 < WIDTH && nColor == pField->stBlock[nX + 1][nY].nColor)
    {
        Count(pField, nX + 1, nY, pCount);
    }
}

[バグ]

もし、コラムスでしたら、Check関数とCount関数を下記のものと入れ替えてください。
こちらの関数でしたら、縦・横・斜めに３つ以上並んでいたら消えます。

int Check(struct FIELD* pField)
{
    int nX = 0;
    int nY = 0;
    int nCount = 0;
    int nReturn = 0;

    // 消去フラグをクリア
    for (nX = 0; nX < WIDTH; ++nX)
    {
        for (nY = 0; nY < HEIGHT; ++nY)
        {
            pField->stBlock[nX][nY].nVanish = 0;
        }
    }

    for (nX = 0; nX < WIDTH; ++nX)
    {
        for (nY = 0; nY < HEIGHT; ++nY)
        {
            // 空白＝０としているので、０の場合は何もしない
            if(pField->stBlock[nX][nY].nColor == 0)
            {
                continue;
            }

            // 同色で並んでいる個数をカウントする
            // 上方向
            nCount = 0;
            Count(pField, nX, nY, 0, -1, &nCount);

            // 右上方向
            nCount = 0;
            Count(pField, nX, nY, 1, -1, &nCount);

            // 右方向
            nCount = 0;
            Count(pField, nX, nY, 1,  0, &nCount);

            // 右下方向
            nCount = 0;
            Count(pField, nX, nY, 1,  1, &nCount);

            // 同色で並んでいる個数がVANISH定数を超えていたら、戻り値を１にする
            nReturn |= (pField->stBlock[nX][nY].nVanish >= VANISH);
        }
    }

    // １箇所でも消去される箇所があれば１、なければ０が返る
    return nReturn;
}

void Count(struct FIELD* pField, int nPosX, int nPosY, int nMoveX, int nMoveY, int* pCount)
{
    // 次の検査箇所の座標を求める
    int nNextX = nPosX + nMoveX;
    int nNextY = nPosY + nMoveY;

    // カウンタをインクリメントする
    ++(*pCount);

    // 次の検査箇所へ
    if (nNextX >= 0 && nNextX < WIDTH && nNextY >= 0 && nNextY < HEIGHT &&
        pField->stBlock[nPosX][nPosY].nColor == pField->stBlock[nNextX][nNextY].nColor)
    {
        Count(pField, nNextX, nNextY, nMoveX, nMoveY, pCount);
    }

    // 同色で並んでいる個数がVANISH定数以上ならば消去フラグをVANISHにする
    if (*pCount >= VANISH)
    {
        pField->stBlock[nPosX][nPosY].nVanish = VANISH;
    }
}

[ちゅるん]

皆さんありがとうございます！
たくさんのアルゴリズムが合ってまだ全部見れてないし、まだそこを考える段階まで行ってませんが、がんばります。
初心者な為、またちょくちょく質問に来ると思いますがよろしくお願いします。
とりあえず解決とさせていただきます。