ぷよぷよのアルゴリズム

s51517765.hatenadiary.jp
先日投稿したぷよインベーダーのプログラムの中から、ぷよとインベーダーが消せるかどうか、の判定部分について解説します。
技術的には「再帰」と「深さ優先探索」「状態遷移」で構成しています。

画面上（プレイエリア）を升目と考える

緑色の部分には最初にエイリアンが配置されていて、それ以外は空白です。
この空白部分にぷよを配置していきます。

同じ色が4つ以上連結されたら消える、という処理を実装するために、新規に配置されたぷよを含めて縦横に接している升にそってカウントしていきます。
これには再帰と深さ優先探索を使います。

void findAdjacentCells(uint8_t x, uint8_t y, bool sameColor[PLAYAREA_MAP_SIZE_Y][PLAYAREA_MAP_SIZE_X], uint8_t color)
{
    // 上下左右のセルを探索して同じ数字のセルを抽出する
    if (color >= 0x10)
        color = color >> PUYO_COLOR_OFFSET;

    if (x < 0 || x >= PLAYAREA_MAP_SIZE_X || y < 0 || y >= PLAYAREA_MAP_SIZE_Y || sameColor[y][x])
    {
        // 範囲外のセルまたはすでに探索したセルは探索しない
        return;
    }

    if (playAreaMap[y][x] == color || playAreaMap[y][x] == (color << PUYO_COLOR_OFFSET))
    {
        sameColor[y][x] = true;

        // 上下左右のセルを探索
        findAdjacentCells(x - 1, y, sameColor, color); // 左
        findAdjacentCells(x + 1, y, sameColor, color); // 右
        findAdjacentCells(x, y - 1, sameColor, color); // 上
        findAdjacentCells(x, y + 1, sameColor, color); // 下
    }
    else
    {
        return;
    }
}

void checkCanErase(uint8_t y, uint8_t x, uint8_t color)
{
    // 座標が範囲外の場合は処理しない
    if (x < 0 || x >= PLAYAREA_MAP_SIZE_X || y < 0 || y >= PLAYAREA_MAP_SIZE_Y)
    {
        return;
    }

    // 探索したセルを記録する配列を初期化
    bool sameColor[PLAYAREA_MAP_SIZE_Y][PLAYAREA_MAP_SIZE_X] = {false};

    // 特定のセルから探索を開始
    if (!sameColor[y][x])
    {
        findAdjacentCells(x, y, sameColor, color);
    }

    uint8_t count = 0;
    for (uint8_t i = 0; i < PLAYAREA_MAP_SIZE_Y; i++)
    {
        for (uint8_t j = 0; j < PLAYAREA_MAP_SIZE_X; j++)
        {
            if (sameColor[i][j])
            {
                // printf("(%d, %d) ", j, i); // (x, y) 形式で座標を表示
                count += 1;
            }
        }
    }
    printf("\n");
}

ぷよを打ち込んだら、まずcheckCanErase()が呼び出されます。
引数は、ぷよの座標と色です。
このとき、探索したエリアを記憶しておく必要があり、以下のようなプレイエリアと同じサイズの配列を用意しておきます。

// 探索したセルを記録する配列を初期化
bool sameColor[PLAYAREA_MAP_SIZE_Y][PLAYAREA_MAP_SIZE_X] = {false};

呼び出されたエリアが探索済みでなければ、深さ優先探索が呼び出されます。

if (!sameColor[y][x])
{
    findAdjacentCells(x, y, sameColor, color);
}

エリアに配置されているのが、エイリアンかぷよか、またその色が何かはエリアマップの配列上に数値で保存されていて、0がBlankで1から白、黄色、マゼンタ、緑となっています。
また、ぷよも同様の色で0x10～同じ色に設定しています。

uint32_t colors[] = {
    BLACK, // Blank
    WHITE,
    YELLOW,
    MAGENTA,
    GREEN,
};

つまり、この配列を読み取ったとき、(0x)1であれば白のエイリアンで、0x20なら黄色のぷよ、といった具合になっています。

同じ色のインベーダーまたは、同じ色のぷよであればさらに再帰的に呼び出します。また、ぷよは2つ連結なので、それぞれについてこの処理を呼び出します。呼び出せるものがなくなったらカウントが終了です。

if (playAreaMap[y][x] == color || playAreaMap[y][x] == (color << PUYO_COLOR_OFFSET))
{
    sameColor[y][x] = true;

    // 上下左右のセルを探索
    findAdjacentCells(x - 1, y, sameColor, color); // 左
    findAdjacentCells(x + 1, y, sameColor, color); // 右
    findAdjacentCells(x, y - 1, sameColor, color); // 上
    findAdjacentCells(x, y + 1, sameColor, color); // 下
}

状態遷移

思っていたよりは処理が速かったですが、そうは言ってもこの処理や画面の描画等を一気にやってしまうと、ゲームが止まってしまいます。
そこで、これらの処理を適度に分割して、以下のような状態遷移とすることで、その間にloop()が動くようにします。

enum state
{
    WAITING = 0,
    SHOOTING,
    PRINTMAP,
    CHECKERASE,
    END
};
bool subState[2] = {false, false};

ここでもぷよが2つ連結なので、ぷよが設置されたところの判定は2つにおいて行う必要があり、これがsubState[2]となっています。

プレイヤーの移動はM5Stackの組込みのボタンを使っているので、これは割り込みだと思いますが、こちらはこれらの処理に関係なく動きます。