ぷよぷよはアルゴリムが高度なためテトリスで落ちゲーの基礎を習得した方に最適です。
★☆ 注意 ☆★
この解説は「テトリスの作り方」の差分解説になります。
ぷよぷよ独自の内容中心に解説していきますので、
動作するプログラムを組みたい場合は「テトリスの作り方」も参照して下さい。
またゲーム全体の流れ制御や各種エフェクトについても解説しません(公開しているプログラムをご覧下さい)。
■とことんぷよぷよ(ソースファイル / 実行ファイルその他)
私が作った作品の実行画面は以下のようになります。
このプログラムには様々な機能が実装されていますが、
ここではこのプログラムからぷよぷよに最低限必要なプログラムを抜粋して
アルゴリズム中心に解説していきます。
■データ構造の復習
一定の大きさを持つマスを単位に処理します。
画素ごとに処理するのは大変なので、表現の制約はありますがマス座標を用いた方が簡単です。
マス座標の原点は左上とします。
// ピースの横と縦のマス数
#define PW 3
#define PH 3
// ゲームフィールドの横と縦のマス数
#define FW 6
#define FH 13 /// 最上段は表示しない
// マスのピクセル数
#define CW 30
#define CH 30
DWORD Field[FW][FH]={0}; /// ゲームフィールドの色
DWORD Piece[PW][PH]={0}; /// 移動中のピースの色
POINT Pos={0,0}; /* 移動中のピースの位置 */
DWORD Next[PW][PH]={0}; /// 次のピースの色
■「とことんぷよぷよ」のコメント
「とことんぷよぷよ」から付与したコメントは /// に続きます。
// は「SPACE TETRIS」から、
/* */ はそのもとになったプログラムにあったものです。
修正を加えている箇所もあるので、正確には対応していません。
同じ事を意味しているコメントなら以前のコメントとして区別しています。
変数名などが違ってもプログラムの意図が同じ場合もそうです。
■ぷよぷよのデータ構造
ピースとはプレイヤーが操作可能な移動中のぷよの集合です。
初期状態では以下のように配置します。
○●○
○●○
○○○
回転する時は周辺のぷよのみ配置変更します(中心のぷよは固定)。
製品版では壁にぶつかった時の配慮としてピースを移動させる処理がありますが、
私の「とことんぷよぷよ」では実装していません(壁にぶつかる場合は回転できません)。
ぷよが降り積もるゲームフィールドは横6マス、縦13マスとします。
ただし最上段は表示しません。
この仕様は製品版と同じです。
表示しないとは文字通りの意味です。
テトリスではプレイヤーの見えない場所でのゲームオーバーがあることを原因に見合わせましたが、
ぷよぷよは必ず浮いているものは下まで落ちてくるという性質があるため
見えない場所でのゲームオーバーはあり得ません。
Ｆｉｅｌｄ 変数にはゲームフィールドの色を格納します。
「SPACE TETRIS」ではブロックの有無を示す変数と色を示す変数を別々に用意していましたが、
ブロックの有無を示す変数は参考にしたプログラムの名残であり冗長です。
なぜなら色が黒以外ならそこにあると判断できるからです。
もし黒色を使いたいなら限りなく黒に近い灰色を使えばいいでしょう。
Pos 変数に格納されるのはマス座標です。
描画する時には Pos 変数より位置を計算して
その場所の色を Piece 変数から取得して描画します。
■ゲーム全体の流れを制御する
プレイヤーの操作はメインスレッドが処理するものとしますが、
ゲーム全体の流れ制御は複雑なエフェクトなどを実装するために
専用のスレッドから処理しています。
メインスレッドには即座にメッセージループに制御を返さなければならないという制約があります。
プロシージャで処理している間はプレイヤーの入力等の処理ができず、
ビジーと判断されてしまうためです。
従ってエフェクト等の割り込み処理の時間制御が大変です。
しかし他のスレッドならば Sleep 関数を実行するだけで簡単に時間制御が可能です。
スレッドを複数作れば複数の割り込み処理を並列実行させることも容易です。
これから解説する各種処理も動作制御スレッドから呼ばれるものとします。
Sleep 関数を使っていますので、上記の理由よりメインスレッドから呼んではいけません。
■色ぷよがいくつ繋がっているか？
ぷよぷよを作るにあたりポイントとなるのは
・いくつ色ぷよが繋がっているのか？
・ぷよを消す(おじゃまぷよの処理含む)
・浮いているぷよを落とす
・おじゃまぷよの発生
まずはいくつ繋がっているのか？の判定方法から解説します。
今、ゲームフィールドを走査して色ぷよが見つかったとします。
その座標をもとに上下左右に隣接している同色ぷよの有無を波状走査します。
自分を中心に波状走査するには再帰が適しています。
ゲームフィールドからはみ出ないように注意しつつ走査するプログラムは以下のようになります。
/// 自分に隣接している同色ぷよの個数を調べる(探索後に消す)
/// x：現在のx座標 , y：現在のy座標 , *n：個数
void Count(int x,int y,DWORD *n)
{
DWORD c=Field[x][y]; /// 自分の色
Field[x][y]=0; (*n)++;
if(x+1<FW && Field[x+1][y]==c) Count(x+1,y,n);
if(y+1<FH && Field[x][y+1]==c) Count(x,y+1,n);
if(x-1>=0 && Field[x-1][y]==c) Count(x-1,y,n);
if(y-1>=0 && Field[x][y-1]==c) Count(x,y-1,n);
}
外部からこの関数を呼ぶ時の引数の値は走査する中心(走査開始点)となるぷよの座標と
隣接している個数を格納するバッファです。
■ちょっと寄り道
最も簡単な隣接個数チェックと消去アルゴリズムは
個数だけ調べて一定以上隣接していればもう一度関数を呼んで消すという方法です。
これらの処理は個数チェックか消去かを指示する引数を追加すれば一つの関数ですみます。
その場合には個数チェックの際に色を変更してはいけません。
しかし走査のためにはチェック済みマークを付ける必要があります。
なんだかややこしくなってきましたが、
チェック済みマークを元通りの色にしてくれる関数は以下のようになります。
/// 自分に隣接している同色ぷよの個数を調べる(探索後に消す)
/// x：現在のx座標 , y：現在のy座標 , *n：個数
void Count(int x,int y,DWORD *n)
{
DWORD c=Field[x][y]; /// 自分の色
Field[x][y]=0; (*n)++;
if(x+1<FW && Field[x+1][y]==c) Count(x+1,y,n);
if(y+1<FH && Field[x][y+1]==c) Count(x,y+1,n);
if(x-1>=0 && Field[x-1][y]==c) Count(x-1,y,n);
if(y-1>=0 && Field[x][y-1]==c) Count(x,y-1,n);
Field[x][y]=c;
}
再帰って凄いですね。
本当にこんなプログラムで大丈夫なの？
ちょっと検証してみましょう。
以下のような黒丸を走査する事を考えます。
○○○○○○○
○○●○○○○
○●●●●●○
○○●○●○○
○○○○○○○
説明しづらいので黒丸を漢数字に、
そして見やすさのために白丸を黒丸に変更します。
●●●●●●●
●●七●●●●
●六零一二三●
●●五●四●●
●●●●●●●
今、零の座標から走査開始するとします。
走査する順番は右下左上です。
そして走査完了したら漢数字を黒丸に置き換え(走査済みマーク付与)、
行き止まりになったら走査済みマークを元の色に戻します。
零からスタートして順調に三まで来ます。
●●●●●●●
●●七●●●●
●六●●●●●
●●五●四●●
●●●●●●●
三は行き止まりなので再帰を逆戻りします。
この時走査済みマークを元の色に戻します。
●●●●●●●
●●七●●●●
●六●●●三●
●●五●四●●
●●●●●●●
一つ前の二まで戻りました。
以前の呼び出しで右方向はもう調べたので
その次の走査方向である下を調べます。
ここで再び右方向を調べる事は無いというのがポイントです。
下には四があるので移動します。
●●●●●●●
●●七●●●●
●六●●●三●
●●五●●●●
●●●●●●●
四は行き止まりなので一つ前の二に戻ります。
●●●●●●●
●●七●●●●
●六●●●三●
●●五●四●●
●●●●●●●
再び二に戻ってきました。
右と下は調べたので次は左ですが、左には何もありません(走査済みマークまたは空)。
同様に上にも何もありません。
従ってもう一つ前に再帰を逆戻りします。
●●●●●●●
●●七●●●●
●六●●二三●
●●五●四●●
●●●●●●●
一に戻ってきました。
一も右は既に調べたので下左上と調べますが何もありません。
●●●●●●●
●●七●●●●
●六●一二三●
●●五●四●●
●●●●●●●
零に戻り……あとは同じです。
再帰は自分と同じ関数を別に呼び出す処理です。
色はそれぞれの関数が別々に保持していますので、
自分の色を保持したローカル変数の値を再帰から抜けた時に代入してやればいいだけです。
再帰を使う時にはスタックオーバーフローに注意して下さい。
この程度の再帰なら余裕ですが、
1000*1000画素の画像に一画素ずつ走査する処理は無理です。
■隣接個数チェックの高速化
個数を調べて(色は変更しない)もし一定以上隣接していれば消すという処理には無駄があります。
既に調べたぷよに対して何度もチェックが行われるからです。
ちなみに一定以上隣接していた場合だけ消す(一定未満の場合だけ色を元に戻す)
という都合のいい再帰処理は実現できないと思われます。
何度も同じぷよをチェックしないためには走査済みのぷよは操作対象から外す必要があります。
最初に示したプログラムでは消していました。
ただしバックアップをとっておかないと情報が失われてしまいます。
Field 変数は作業用にして、完成状態を作る変数 f に最初の状態をコピーしておきましょう。
おじゃまぷよ＆固ぷよについては直接消えることはないので走査対象から外します。
実際に消去する時にはおじゃまぷよの処理もあるので Vanish 関数が担当します。
#define OJAMA 0x007f7f7f /// おじゃまぷよ
#define KATA 0x00ffffff /// 固ぷよ
/// ゲームフィールドの色をコピーする
/// to[FW][FH]：コピー先の配列 , from[FW][FH]：コピー元の配列
void CopyField(DWORD to[FW][FH],DWORD from[FW][FH])
{
for(int y=0;y<FH;y++){
for(int x=0;x<FW;x++){
to[x][y]=from[x][y];
}
}
}
/// 四方に Delete 以上隣接している色ぷよを消す
/// (おじゃま＆固ぷよについてはVanish関数が処理)
/// 戻り値：削除した色ぷよの数
int DeletePuyo(void)
{
int x,y;
DWORD f[FW][FH],n,d=0;
CopyField(f,Field); /// f[][] に完成状態を作っていく( Field[][] は作業用)
for(y=0;y<FH;y++){
for(x=0;x<FW;x++){
n=Field[x][y];
if(n && n!=OJAMA && n!=KATA){ /// 色ぷよだけ
n=0; Count(x,y,&n); /// いくつ繋がっているか？
if(n>=Delete){Vanish(f,x,y); d+=n;} /// 削除した色ぷよの数をカウント
} /// ↑ぷよを消す
}
}
CopyField(Field,f); /// 処理結果を反映させる
return d;
}
OJAMA はおじゃまぷよの色、KATA は固ぷよの色です。
DeletePuyo 関数の戻り値は削除した色ぷよの数です。
この値を使えば点数計算が行えます。
Vanish 関数は以下のようになります。
Count 関数のカウント処理を廃しておじゃまぷよの処理が追加された感じです。
/// ぷよを消す(Count関数の応用)
/// f[FW][FH]：ゲームフィールドの色
/// x：現在のx座標 , y：現在のy座標
void Vanish(DWORD f[FW][FH],int x,int y)
{
DWORD c=f[x][y]; /// 自分の色
f[x][y]=0; /// 色ぷよを消す
/// 固ぷよ→おじゃまぷよ or おじゃまぷよ→消す
if(x+1<FW){
if(f[x+1][y]==KATA) f[x+1][y]=OJAMA;
else if(f[x+1][y]==OJAMA) f[x+1][y]=0;
}
if(y+1<FH){
if(f[x][y+1]==KATA) f[x][y+1]=OJAMA;
else if(f[x][y+1]==OJAMA) f[x][y+1]=0;
}
if(x-1>=0){
if(f[x-1][y]==KATA) f[x-1][y]=OJAMA;
else if(f[x-1][y]==OJAMA) f[x-1][y]=0;
}
if(y-1>=0){
if(f[x][y-1]==KATA) f[x][y-1]=OJAMA;
else if(f[x][y-1]==OJAMA) f[x][y-1]=0;
}
if(x+1<FW && f[x+1][y]==c) Vanish(f,x+1,y);
if(y+1<FH && f[x][y+1]==c) Vanish(f,x,y+1);
if(x-1>=0 && f[x-1][y]==c) Vanish(f,x-1,y);
if(y-1>=0 && f[x][y-1]==c) Vanish(f,x,y-1);
}
■連鎖
ぷよぷよには連鎖というものがあります。
ぷよを消したら上のぷよが落ちてきてまた消えるという一連の動作です。
DeletePuyo 関数は連鎖をサポートしません。
連鎖の制御は外部から行う必要があります。
ぷよの消滅時には何かエフェクトを付けたくなるかもしれません。
私のプログラムではそのような処理を DeletePuyoEffect 関数にまとめました。
ここでは解説しませんがこれを参考に独自のエフェクトを考えてみて下さい。
■浮いているぷよを落とす
テトリスと違い浮いているぷよは落とさなければなりません。
落とすと言っても一気に落とすのではなく一マスずつ徐々に落としていきましょう。
重要なのは浮いているぷよを判別する方法ですが、
下から見ていき、空白があり更に上にぷよがあればそのぷよは浮いていると断定できます。
更にその上にも空白を挟みぷよがあるかもしれません(下図参照)。
●
○
●
○
○ ３
●
●
● 一番下
今、下から見ていき３に空白を見付けました。
この座標は保存しておきます。
更に上を見ていくとぷよがありました。
このぷよは浮いていると断定できます。
そうしたら３より上を全て一マスずつ下にシフトします。
○
●
○
●
○
●
●
● 一番下
３は空白だったので上からのシフトにより上書きしてしまいます。
また上にはまだ空白がありますが、
みんな一緒に落ちてくるのが自然の理ですので、
これ以上重ねて落下処理をしてはいけません。
この処理を列毎に適応して(一回の処理終了)、
また最初の列に戻り浮いているぷよが無くなるまでループします。
● ○ ○ ○
○ ● ○ ○
● ○ ● ○
○ ● ○ ●
○ ○ ● ●
● ● ● ●
● ● ● ●
● ● ● ●
→ → → → → → 処理の流れ
/// 浮いているぷよを１マスだけ落とす
/// 戻り値：ぷよを落とした列数
int FallPuyo(void)
{
int x,y,iy,n=0;
for(x=0;x<FW;x++){ /// 列方向
for(y=FH-1;y>=0;y--){ /// 下から調べる
if(Field[x][y]==0){ /// 空のマスが見つかれば上にある(かもしれない)ぷよを探す
for(iy=y-1;iy>=0 && Field[x][iy]==0;iy--); /// 空のマスを読み飛ばす
if(iy<0) break; /// 上にぷよが無い(次の列へ)
n++; /// ぷよを落とした列数
for(iy=y;iy>=0;iy--){ /// ぷよを１マスだけ落とす
if(iy-1>=0) Field[x][iy]=Field[x][iy-1];
else Field[x][iy]=0; /* 0 行より上はないので 0 で埋める */
}
break; /// 次の列へ
}
}
}
return n;
}
/// 浮いているを１マスずつ落とす
/// hWnd：ウィンドウのハンドル
/// 戻り値：待機した合計時間
DWORD FallPuyoAuto(HWND hWnd)
{
for(DWORD sleep=0;FallPuyo();sleep+=100){ /// 浮いているぷよが無くなるまで続ける
InvalidateRect(hWnd,NULL,FALSE); Sleep(100);
}
return sleep;
}
■おじゃまぷよの発生
本来おじゃまぷよは敵から送られてくるものですが、
「とことんぷよぷよ」は一人用なので仮想の敵を想定してランダムにおじゃまぷよを発生させてみましょう。
おじゃまぷよは見えない最上段に配置していきます。
最上段の何処に配置するかはランダムです。
配置したおじゃまぷよは FallPuyoAuto 関数を使えば自動的に落ちていきます。
これだけ聞くと簡単に思えるかもしれませんが、意外と難しい問題を孕んでいます。
複数行のおじゃまぷよを発生させるにはどうすればいいの？
一行おいたら一行だけシフトして( FallPuyo 関数を使う)また最上段に配置すればいいでしょう。
置く場所がなかったらどうするの？
最上段が埋め尽くされたということはすなわちゲームオーバーです。
置く必要ありません。
製品版では最上段より上に溢れてしまったおじゃまぷよは無視しますが、
私のは希望する個数を意地でも配置する仕様になっています。
従って二行分(12個)のおじゃまぷよを発生させる時は、
必ずしも二行で降ってくるわけではなく、
最上段の詰まり具合によっては三行以上になる列も現れます。
/// おじゃまぷよをランダムに作って落とす
/// hWnd：ウィンドウのハンドル
/// 戻り値：待機した合計時間
DWORD FallOjama(HWND hWnd)
{
if(Ojama==0) return 0;
if(rand()%OjaRand) return 0; /// ランダムに生成
int r=rand()%OjaMax+1; /// 作りたいおじゃまぷよの数
int fx[FW],n,a,b;
DWORD sleep=0;
while(1){
n=0;
for(int x=0;x<FW;x++){
if(Field[x][0]==0) fx[n++]=x; /// 最上段にぷよが無いマスのx座標と個数を記録
}
if(n==0) return sleep; /// 置ける場所がない
if(r<n){ /// 作りたい数 ＜ 置ける場所の数
for(x=0;x<n;x++){a=fx[x]; fx[x]=fx[b=rand()%n]; fx[b]=a;} /// シャッフル
for(x=0;x<r;x++) Field[fx[x]][0]=(Ojama==1)?OJAMA:(Ojama==3)?KATA:(rand()%3)?OJAMA:KATA;
sleep+=FallPuyoAuto(hWnd); return sleep; /// ↑Ojama==2
}else{ /// とりあえず置けるだけ置く(作りたい数 ＞ 置ける場所の数)
for(x=0;x<n;x++) Field[fx[x]][0]=(Ojama==1)?OJAMA:(Ojama==3)?KATA:(rand()%3)?OJAMA:KATA;
FallPuyo(); InvalidateRect(hWnd,NULL,FALSE); Sleep(100);
r-=n; sleep+=100; /// 一段落として残っているおじゃまぷよを置く
} /// (全て置くか置く場所が無くなるまで)
}
}
Ojama==0 は おじゃま＆固ぷよ無し
Ojama==1 は おじゃまぷよ有り
Ojama==2 は おじゃま＆固ぷよ有り
Ojama==3 は 固ぷよ有り
モードを意味します。
さらっと言ったランダムに配置するにも工夫が必要です。
置きたい場所にはもうぷよがいるかもしれないので、
単純にランダムな場所を選択していては無駄が生じます。
そこであらかじめ置ける場所の一覧(配列)を作り、それをシャッフルして
一覧の先頭から置いていくという方法が考えられます。
このシャッフルのアルゴリズムはカードゲームでよく使われると思います。
■まとめ
ぷよぷよに最低限必要なアルゴリズムは一通り解説しました。
どれも高度なアルゴリズムを用いていますので難しいかもしれませんが、
作る方からするとそこが面白いはずです。
ゲームとして完成させるには頭の痛い動作制御を実装しなければなりませんが、
動作制御スレッドの内容は「SPACE TETRIS」のそれによく似ているので
「テトリスの作り方」を参照して下さい。
メインスレッドでは描画処理や(間接的な)音楽制御、更に入力処理も行っています。
入力処理はキーコンフィグを実装しているために
ちょっと見慣れないものになっているかもしれませんが、基本は同じです。
キーコンフィグの実装方法については別に解説します(キーコンフィグの実装)。
ここで解説していない内容については私のプログラムを参考にしても構いませんし、
可能なら自分で考えてみて下さい。
きっと何かが得られるはずです。