ホーム < ゲームつくろー! < IKD備忘録

Cocos2d-x
マッチNアルゴリズム

(2015. 2. 1)


 今回もCocos2d-xからちょっと離れるかもしれませんが、前章の「○×Evolution」のゲームルールを実現する為に必要な「マッチNアルゴリズム」についての解説です。



@ 同じ種類が連なってる

 「コラムス」や「パズル&ドラゴン」、「ぷよぷよ」「Candy Crush」など何種類かの色が連なるとアクションが起こるパズルゲームは多種多様にあります。これらのパズルに共通するのは「隣合う色があるかどうか?」を検索出来る必要があると言う事です。ここでいう「隣」には上下左右の場合と斜めを含む場合があります。

 連なりには「一定方向のみ連なりとする」場合と「隣り合っている物はすべて連なっている」という場合がさらにあります。その連なりの数Nがある数以上になるとアクションが起こります。

 例えば下のような配置:

これで、一定方向の連なりでN=3以上の○は以下の通りです:

今回のルールは一定方向の連なりのみでOK。これを検出する方法を考えようと言う話です。



A 縦横斜めで行(列)飛ばしで検索

 一定方向で良い場合、方法は結構単純です。例えば3連以上を有効列としましょう。まず、縦に3連以上あるかどうかをチェックしていきます。それには、上から3行目の左端から検索をスタートします:

なぜ上2行は飛ばせるのか?それは3行目の検索マスが○以外だった場合、上の2つが○だったとしても連が成立しない事が確定しているからです。検索マスが○だった場合は縦列が成立しているかチェックを行います。チェックはまず上方向へ、それが終わったら下方向へチェックします:

チェックした○にはマークを付けておきましょう。これは「2重検索」を避けるためです。こんな感じで右方向へ検索を続け、右端まで行ったら、また2行飛ばして6行目を検索します:

2列目に○が検索されますが、これはすでにマークが付いているので飛ばします。その右の3連は新しく見つかる有効列ですね。こうして右端まで検索したら、縦列のチェックは終わりです(下2列で3連にはならないのでやっぱり飛ばせる)。

 今度は横方向の3連以上の検索を行います:

横方向の場合は縦方向に検索していくのがスマートです。縦列の時と同じで、最初の2列は見る必要がありません。3列目の上からスタートです。下まで見たら2列飛ばして6列目を。そうして○を見つける度に横方向に3連以上連なっているかを都度チェック。これを繰り返すだけです。

 次は右斜め下方向の検索:

右斜め下方向の検索は縦列と一緒。3行目と6行目の○検索と、○を見つけた時は左斜め上及び右斜め下への3連以上チェックとなります。

 最後は左斜め下検索:

左斜め下検索も縦列の時と同じです。このように、N連以上が有効とするならば、N-1行(列)飛ばしで○を検索し、○を見つけたらN連以上あるかのチェックをするというアルゴリズムにする事で、全マス検索をするより随分手間が省けます。



B N連(以上)検索クラス

 マルペケ恒例コードの公開です。本章にある「一定方向でN連以上の列」を検索して返してくれるMatchNクラスを作りました:

matchN.h
#ifndef __IKD_MATCHN_H__
#define __IKD_MATCHN_H__

// N連検索クラス

#include <vector>

class MatchN {
public:

    enum Error {
        ERR_ID = 0xffffffff
    };

    // 検索方向指定フラグ
    static const unsigned Horizontal = 1; // 水平方向
    static const unsigned Vertical = 2; // 垂直方向
    static const unsigned Diagonal = 4; // 斜め方向
    static const unsigned All = Horizontal | Vertical | Diagonal; // 全方向

    // 有効列構造体
    struct MatchIDInfo {
        int val_; // 対象ID
        std::vector<int> ids_; // マスID
    };

protected:
    // 検索イテレータ
    class Iterator {
    protected:
        unsigned x_, y_, minN_, w_, h_;
    public:
        Iterator( unsigned w, unsigned h, unsigned minN ) : x_(), y_(), minN_(minN), w_(w), h_(h) {}
        virtual bool isEnd() = 0;
        virtual void next() = 0;
        void getXY( unsigned &x, unsigned &y ) {
            x = x_; y = y_;
        }
    };

    // 縦・斜め方向用イテレータ
    class HIterator : public Iterator {
        unsigned counter_;
    public:
        HIterator( int w, int h, unsigned minN ) : Iterator( w, h, minN ), counter_() {
            y_ = minN_ - 1;
        }
        virtual bool isEnd() {
            return ( y_ >= h_ );
        }
        virtual void next() {
            counter_++;
            x_ = counter_ % w_;
            y_ = minN_ - 1 + minN_ * (counter_ / w_);
        }
    };

    // 横方向用イテレータ
    class VIterator : public Iterator {
        unsigned counter_;
    public:
        VIterator( int w, int h, unsigned minN ) : Iterator( w, h, minN ), counter_() {
            x_ = minN_ - 1;
        }
        virtual bool isEnd() {
            return ( x_ >= w_ );
        }
        virtual void next() {
            counter_++;
            y_ = counter_ % h_;
            x_ = minN_ - 1 + minN_ * (counter_ / h_);
        }
    };

    // 指定位置イテレータ
    class PosIterator : public Iterator {
        bool isNext_;
    public:
        PosIterator( int w, int h, unsigned minN, unsigned x, unsigned y ) : Iterator( w, h, minN ), isNext_() {
            x_ = x; y_ = y;
        }
        virtual bool isEnd() {
            return isNext_;
        }
        virtual void next() {
            isNext_ = true;
        }
    };

    std::vector< int > board_; // 盤(width_×height)
    unsigned width_; // 盤の列数
    unsigned height_; // 盤の行数
    const int nullity_; // 空の値

protected:
    // 指定連結方向のチェック
    // idArys: 有効列を格納する配列
    // minN : 最小連結数
    // maxN : 最大連結数
    // : 調べる方向
    unsigned checkDir( std::vector<MatchIDInfo> &idArys, int ofsX, int ofsY, unsigned minN, unsigned maxN, Iterator &it ) const;

    // 次のマッチをチェック
    // checkedIds: すでにチェックされているId群
    // x : 直前のX位置
    // y : 直前のY位置
    // ofsX : チェック方向X
    // ofsY : チェック方向Y
    // info : 連結格納
    // minN : 最小連結数
    // maxN : 最大連結数
    bool checkNextMatch( std::vector<int> &checkedIds, unsigned x, unsigned y, int ofsX, int ofsY, MatchIDInfo &info, unsigned minN, unsigned maxN ) const;

public:
    // コンストラクタ
    // nullity: 空の値
    // width : 盤の列数(幅)
    // height : 盤の行数(高さ)
    MatchN( int nullity );
    MatchN( int nullity, unsigned width, unsigned height );

    // ボードを設定
    // width : 盤の列数(幅)
    // height : 盤の行数(高さ)
    bool init( unsigned width, unsigned height );

    // ボードの大きさを取得
    // width : 盤の列数(幅)
    // height : 盤の行数(高さ)
    void getBoardSize( unsigned &width, unsigned &height ) const ;

    // ボードの値をクリア
    void clear();

    // XY位置に値をセット
    // x: 盤の行(横位置)
    // y: 盤の列(縦位置)
    bool setVal( unsigned x, unsigned y, int val );

    // Idに値をセット
    // id: 盤のマスID
    bool setVal( unsigned id, int val );

    // XY位置をIdに変換
    // x: 盤の行(横位置)
    // y: 盤の列(縦位置)
    unsigned getId( unsigned x, unsigned y ) const;

    // XY位置の値を取得
    // x: 盤の行(横位置)
    // y: 盤の列(縦位置)
    int getVal( unsigned x, unsigned y ) const;

    // Idの値を取得
    // id: 盤のマスID
    int getVal( unsigned id ) const;

    // 指定タイプでN連マッチを検出
    // idArys : マッチ情報を出力
    // checkTypes: 縦横斜めのチェック方向フラグ(orで連結)
    // minN : 最小連結数
    // maxN : 最大連結数
    unsigned checkAll( std::vector<MatchIDInfo> &idArys, unsigned checkTypes, unsigned minN, unsigned maxN ) const;

    // 指定位置がN連マッチしているか検出
    // idArys : マッチ情報を出力
    // checkTypes: 縦横斜めのチェック方向フラグ(orで連結)
    // minN : 最小連結数
    // maxN : 最大連結数
    // x : 盤の行(横位置)
    // y : 盤の列(縦位置)
    unsigned check( std::vector<MatchIDInfo> &idArys, unsigned checkTypes, unsigned minN, unsigned maxN, unsigned x, unsigned y ) const;
};



//////////////////////
// ユーティリティ

class MatchNUtil {
public:
    // マッチしたIDを重複無く列挙
    static std::vector<int> getMatchIds( const std::vector<MatchN::MatchIDInfo> &idArys );

    // MatchNが保持している値配列をクローン取得
    static std::vector<int> cloneValueAry( const MatchN &match );
};

#endif
matchN.cpp
#include "matchN.h"
#include <set>

MatchN::MatchN( int nullity ) : width_(), height_(), nullity_( nullity ) {
}

MatchN::MatchN( int nullity, unsigned width, unsigned height ) : width_(width), height_(height), nullity_( nullity ) {
    board_ = std::vector< int >( width * height, nullity );
}

// ボードを設定
bool MatchN::init( unsigned width, unsigned height ) {

    if ( width == 0 || height == 0 )
        return false;

    width_ = width;
    height_ = height;

    // 既存のボードは初期値でクリア
    clear();

    return ( width != 0 && height != 0 );
}

// ボードの大きさを取得
// width : 盤の列数(幅)
// height : 盤の行数(高さ)
void MatchN::getBoardSize( unsigned &width, unsigned &height ) const {
    width = width_;
    height = height_;
}

// ボードをクリア
void MatchN::clear() {

    board_ = std::vector< int >( width_ * height_, nullity_ );
}

// XY位置に値をセット
bool MatchN::setVal( unsigned x, unsigned y, int val ) {
    int id = getId( x, y );
    return setVal( id, val );
}

// Idに値をセット
bool MatchN::setVal( unsigned id, int val ) {

    if ( id >= board_.size() )
        return false;

    board_[ id ] = val;

    return true;
}

// XY位置をIdに変換
unsigned MatchN::getId( unsigned x, unsigned y ) const {

    if ( x >= width_ || y >= height_ )
        return ERR_ID;

    return width_ * y + x;
}

// XY位置の値を取得
int MatchN::getVal( unsigned x, unsigned y ) const {

    if ( x >= width_ || y >= height_ )
        return ERR_ID;

    return board_[ getId( x, y ) ];
}

// Idの値を取得
int MatchN::getVal( unsigned id ) const {

    if ( id >= board_.size() )
    return nullity_;

    return board_[ id ];
}

// 縦横斜めでN個のマッチを検出
unsigned MatchN::checkAll( std::vector<MatchIDInfo> &idArys, unsigned checkTypes, unsigned minN, unsigned maxN ) const {

    // ボードが無い場合は無効
    if ( board_.size() == 0 )
        return 0;

    // 出力配列は空に
    idArys.clear();

    // 最小列数が1だと意味が無い
    if ( minN <= 1 )
        return 0;

    // 最大列数が最小列数より小さい場合は最小列数に合わせる
    if ( maxN < minN )
        maxN = minN;

    // 横方向のチェック
    if ( checkTypes & Horizontal ) {
        VIterator it( width_, height_, minN );
        checkDir( idArys, 1, 0, minN, maxN, it );
    }

    // 縦方向のチェック
    if ( checkTypes & Vertical ) {
        HIterator it( width_, height_, minN );
        checkDir( idArys, 0, 1, minN, maxN, it );
    }

    // 斜め方向のチェック
    if ( checkTypes & Diagonal ) {

        HIterator it1( width_, height_, minN );
        checkDir( idArys, 1, 1, minN, maxN, it1 );

        HIterator it2( width_, height_, minN );
        checkDir( idArys, -1, 1, minN, maxN, it2 );
    }

    return idArys.size();
}

// 指定位置がN連マッチしているか検出
unsigned MatchN::check( std::vector<MatchIDInfo> &idArys, unsigned checkTypes, unsigned minN, unsigned maxN, unsigned x, unsigned y ) const {

    // ボードが無い場合は無効
    if ( board_.size() == 0 )
        return 0;

    // 出力配列は空に
    idArys.clear();

    // 最小列数が1だと意味が無い
    if ( minN <= 1 )
        return 0;

    // 最大列数が最小列数より小さい場合は最小列数に合わせる
    if ( maxN < minN )
        maxN = minN;

    // 横方向のチェック
    if ( checkTypes & Horizontal ) {
        PosIterator it( width_, height_, minN, x, y );
        checkDir( idArys, 1, 0, minN, maxN, it );
    }

    // 縦方向のチェック
    if ( checkTypes & Vertical ) {
        PosIterator it( width_, height_, minN, x, y );
        checkDir( idArys, 0, 1, minN, maxN, it );
    }

    // 斜め方向のチェック
    if ( checkTypes & Diagonal ) {

        PosIterator it1( width_, height_, minN, x, y );
        checkDir( idArys, 1, 1, minN, maxN, it1 );

        PosIterator it2( width_, height_, minN, x, y );
        checkDir( idArys, -1, 1, minN, maxN, it2 );
    }

    return idArys.size();
}

// 指定連結方向のチェック
unsigned MatchN::checkDir( std::vector<MatchIDInfo> &idArys, int ofsX, int ofsY, unsigned minN, unsigned maxN, Iterator &it ) const {

    std::vector<int> checkedIds( board_.size(), 0 ); // マーク配列

    // 指定方向のチェック
    for ( ; !it.isEnd(); it.next() ) {
        unsigned x, y;
        it.getXY( x, y );

        MatchIDInfo info;
        info.val_ = getVal( x, y );

        if ( info.val_ == nullity_ )
            continue; // 空値は評価しない

        unsigned id = getId( x, y );
        if ( checkedIds[ id ] == 1 )
            continue; // チェック済みだったので検索を飛ばす

        // 反対方向のマッチチェック
        info.ids_.push_back( id );
        checkNextMatch( checkedIds, x, y, -ofsX, -ofsY, info, minN, maxN );

        // 検索idを逆順に
        if ( info.ids_.size() > 0 ) {
            std::vector<int> ids;
            for ( unsigned i = 0; i < info.ids_.size(); i++ )
                ids.push_back( info.ids_[ info.ids_.size() - i - 1 ] );
            info.ids_ = ids;
        }

        // 正方向のマッチチェック
        if ( checkNextMatch( checkedIds, x, y, ofsX, ofsY, info, minN, maxN ) == true )
            idArys.push_back( info );

        checkedIds[ id ] = 1; // 現在の基点位置にチェック入れる
    }

    return idArys.size();
}

// 次のマッチをチェック
bool MatchN::checkNextMatch( std::vector<int> &checkedIds, unsigned x, unsigned y, int ofsX, int ofsY, MatchIDInfo &info, unsigned minN, unsigned maxN ) const {

    // マッチ数は範囲内?
    if ( info.ids_.size() >= maxN ) {
        // 範囲外なので終了
        return ( info.ids_.size() >= minN );
    }

    // チェックする位置
    unsigned tx = x + ofsX;
    unsigned ty = y + ofsY;

    unsigned id = getId( tx, ty );
    if ( id == ERR_ID ) {
        // 枠外なので終了
        return ( info.ids_.size() >= minN );
    }
    if ( checkedIds[ id ] == 1 )
        return ( info.ids_.size() >= minN ); // すでにチェック済みだった

    // IDは有効
    // 値が同じならマッチ成立
    int val = getVal( tx, ty );

    if ( val == info.val_ ) {

        info.ids_.push_back( id );
        checkedIds[ id ] = 1;

        // さらにマッチチェック
        return checkNextMatch( checkedIds, tx, ty, ofsX, ofsY, info, minN, maxN );
    }

    // マッチしなかった
    return ( info.ids_.size() >= minN );
}


//////////////////////
// ユーティリティ

// マッチしたIDを重複無く列挙
std::vector<int> MatchNUtil::getMatchIds( const std::vector<MatchN::MatchIDInfo> &idArys ) {

    std::vector<int> outAry;
    std::set<int> checker;
    for ( unsigned i = 0; i < idArys.size(); i++ ) {
        for ( unsigned j = 0; j < idArys[ i ].ids_.size(); j++ ) {
            int id = idArys[ i ].ids_[ j ];
            if ( checker.find( id ) == checker.end() )
                outAry.push_back( id );
        }
    }

    return outAry;
}

// MatchNが保持している値配列をクローン取得
std::vector<int> MatchNUtil::cloneValueAry( const MatchN &match ) {

    unsigned w, h;
    match.getBoardSize( w, h );

    std::vector<int> outAry;

    for ( unsigned y = 0; y < h; y++ ) {
        for ( unsigned x = 0; x < w; x++ ) {
            outAry.push_back( match.getVal( x, y ) );
        }
    }

    return outAry;
}

使い方のサンプルはこちら:

#include "stdafx.h"
#include "matchN.h"
#include <time.h>
#include <set>

int _tmain(int argc, _TCHAR* argv[])
{
    srand( (unsigned)time(0) );

    unsigned w = 16;
    unsigned h = 16;

    // マッチN検索オブジェクト
    MatchN match( 0, w, h );

    // 盤に値を設定(0 or 1)
    for ( unsigned y = 0; y < h; y++ ) {
        for ( unsigned x = 0; x < w; x++ ) {
            int val = rand() % 2;
            match.setVal( x, y, val );    // 盤に値を設定
            printf( "%s", val ? "○" : "□" );
        }
        printf("\n");
    }

    // 5連以上8連以下の有効列をすべてチェック
    std::vector< MatchN::MatchIDInfo > infos;
    match.checkAll( infos, MatchN::All, 5, 8 );
    // match.checkAll( infos, MatchN::Diagonal | MatchN::Horizontal, 5, 8 );  // 「斜めと横だけ」どかできます

    // マッチしたIDを列挙
    std::vector<int> ids = MatchNUtil::getMatchIds( infos );

    // MatchNが保持している値配列をクローン取得
    std::vector<int> vals = MatchNUtil::cloneValueAry( match );

    // マッチしている部分を"2"に
    for ( unsigned i = 0; i < ids.size(); i++ )
        vals[ ids[i] ] = 2;

    // マッチ箇所を黒丸で表示
    printf("\n-------------\n");
    for ( unsigned y = 0; y < h; y++ ) {
        for ( unsigned x = 0; x < w; x++ ) {
            int val = vals[ w * y + x ];
            printf( "%s", val == 2 ? "●" : ( val == 1 ? "○" : "□" ) );
        }
        printf("\n");
    }

    return 0;
}

これを使って○×Evolutionの基盤部分となる「置いて3連以上を判定」という所を作っていくのですが、その前に「置く」というインタラクティブな事を次に作成します。