DXライブラリを使ってぷよぷよもどき
DXライブラリをつかってぷよぷよもどきをつくりました。
そこでぷよぷよを作るうえで重要な、消す処理、すなわち探索についていろいろ躓いたりしたのでまとめてみる。
おまけみたいな感じでMinGWでのDXLibのセットアップ方法も。
環境は
MinGW + msys
DXライブラリ GCC版
DXライブラリのセットアップ
まずDXライブラリですが、VisualStudioで作ることはあってもあまりGCCで作ることはないと思います。
セットアップは公式からGCC版のDXライブラリをとってきて、解凍したら解凍したフォルダのプロジェクトに追加すべきファイル_GCC(MinGW用)のなかみを全部MinGWのGCCのインクルードディレクトリをコピーします。そしたら同じく、インクルードディレクトリに以下のようなヘッダを保存します。
ファイル名はDXLib_GCC.hかなんかにしておくとわかりやすいでしょう。
#define DDX_GCC_COMPILE #define DDX_NON_INLINE_ASM #include "DxLib.h"
これでコード側からは
#inlcude <DXLib_GCC.h>
ってやるだけで済みます。
ちなみにGCCのインクルードフォルダは
MinGW\lib\gcc\(バージョン)\include
です。
.aとかのライブラリファイルはその一個上の階層に置きます。
makefileはちゃちゃっとこんな感じ。
TARGET=../puyo CC=gcc CXX=g++ CFLAGS=-g -O2 -w -mwindows CXXFLAGS=$(CFLAGS) LDFLAGS=-static-libgcc -static-libstdc++ INCDIR=-I"../DXLib/" LIBDIR=-L"../DXLib/" LIBS=-lDxLib -lDxUseCLib -lDxDrawFunc -ljpeg -lpng -lzlib -ltiff -ltheora_static -lvorbis_static\ -lvorbisfile_static -logg_static -lbulletdynamics -lbulletcollision -lbulletmath LIBS+=-lgdi32 OBJS=main.o dxApp.o board.o player.o control.o .cpp.o: $(CXX) $(CXXFLAGS) -c $< $(TARGET): $(OBJS) $(CXX) $(CXXFLAGS) $(LDFLAGS) $(INCDIR) $(LIBDIR) -o $@ $^ $(LIBS) clean: @rm -fr $(TARGET).exe $(OBJS) *~ *.swp
これであとはmakeするだけ。簡単。
本題
ようやく本題ですが、その前にプロジェクト全体のソースをgithubに上げてるのでみたいかたはどうぞ（ただしめちゃめちゃ汚いしコメント少ないので正直読みづらい）
->github
一応コンパイル後も -> 後日投げますぷよぷよの消す処理については一般的には探索をすこし改良して使うのが一般的だと思います。
今回自分も場合も探索を使用しています。(board.cpp の DeletePuyo関数)
いわゆるあるノードに関して、そのノードに接続するすべてのノードを深さ優先で展開していく、っていう深さ優先探索を使っています。（たぶん深さ優先になってるはず。）
深さ優先探索はある数を探したりカウントアップしたりするときに使用します。
探索を継続する条件は、
①探索中のノードの訪問フラグがfalseの場合。 ②探索中のノードが0でない場合。 ③親ノードと要素が一致する場合。
となっています。
①のフラグはノードを訪問した際にtrueにして訪問済みであることを示します。
②はもちろんノードにぷよがなければ探索は必要ありません。
③も要素が違っていればその先を探索する必要はありません。
さらにぷよぷよのような今回の場合は、探索と同時につながってる同色のぷよを数え上げます。
そして探索を終了したときにフラグがtrueになっている位置と対応する位置のぷよを0にしています。(0:ぷよが配置されていない。)
trueになっているところを消す都合上、②の条件もしくは③の条件が当てはまらなかった場合はフラグを折るようにしています。
そうすることでいい感じで消えてくれます。
それを6 * 12それぞれのマスを基準に探索を行います。
これもぷよが置いてあるところのみ探索するようにすれば若干計算量が減ります。
①、②、③のすべて当てはまれば、そのノードと接しているノード(4方向)をみてさらに探索を進めています。
この部分
if(x + 1 < P_X) cnt = del(x + 1,y,cnt,stat_board[y][x]); if(x - 1 >= 0) cnt = del(x - 1,y,cnt,stat_board[y][x]); if(y + 1 < P_Y) cnt = del(x,y + 1,cnt,stat_board[y][x]); if(y - 1 >= 0) cnt = del(x,y - 1,cnt,stat_board[y][x]);
cnt = とすることでカウントアップを適用していっています。
以上をまとめると探索はこんな順序で行っていることになります。
この場合消えるのは赤だけですね。
黄色は
①左上から開始して(カウント1)
②下にいって(カウント2)
③右にいった時点で回りに黄色がいないので戻ってきます。(カウント3)
④カウントは3で消えないのでフラグを初期化いて一つ右にの赤を探索基準にします。
赤色は
①左上左１つ目から開始(カウント1)
②右にいって(カウント2)
③右に行きますが、周りに赤がないので戻ってきます。(カウント3)
④２つ目の下に赤があるのでそちらを探索します。(カウント4)
⑤周りに赤がないのでもどります。
⑥カウントが4以上(ぷよぷよは4つで消える)なのでtrueのところを消します。
のようになります。
同じように青ともう一つの黄色も探索しますが、4つ以上つながっていないので消去はしません。
このようにして消去の判定を行うことができます。
ぷよぷよの場合はこの後落下の判定をして消去が起こらなかった場合は次のぷよを生成するって感じにすればいいと思います。
また自分の場合、一瞬で消えていったら味気ないのでループ回数をカウントして、一定カウントのところで処理させるようにしています。
その都合上、若干不安定ではありますが、（普通は時間でとったりするもの。）
正直12時間で書いたのでバグがあるかもしれないのでリファクタリングしてから、闇に葬る予定です。
探索はほかにもビームサーチとか幅優先とかいろいろあるので、とても興味はある（わかるとはいってない）
