Cocos2d-x
マッチNアルゴリズム
(2015. 2. 1)
今回もCocos2d-xからちょっと離れるかもしれませんが、前章の「○×Evolution」のゲームルールを実現する為に必要な「マッチNアルゴリズム」についての解説です。
① 同じ種類が連なってる
「コラムス」や「パズル＆ドラゴン」、「ぷよぷよ」「Candy Crush」など何種類かの色が連なるとアクションが起こるパズルゲームは多種多様にあります。これらのパズルに共通するのは「隣合う色があるかどうか？」を検索出来る必要があると言う事です。ここでいう「隣」には上下左右の場合と斜めを含む場合があります。
連なりには「一定方向のみ連なりとする」場合と「隣り合っている物はすべて連なっている」という場合がさらにあります。その連なりの数Nがある数以上になるとアクションが起こります。
例えば下のような配置：
これで、一定方向の連なりでN=3以上の○は以下の通りです：
今回のルールは一定方向の連なりのみでOK。これを検出する方法を考えようと言う話です。
② 縦横斜めで行（列）飛ばしで検索
一定方向で良い場合、方法は結構単純です。例えば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連以上あるかのチェックをするというアルゴリズムにする事で、全マス検索をするより随分手間が省けます。
③ 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連以上を判定」という所を作っていくのですが、その前に「置く」というインタラクティブな事を次に作成します。
