5414

ぷよぷよプログラミング解説 第3章: 4個くっついてるぷよを探す手順

by
puyolufar
puyolufar
ぷよぷよプログラミング Advent Calendar 2020 | 24日目 (4週目)

メリークリスマス!
いよいよ本日はぷよを消すプログラムについて解説します。

某四角い落ち物パズルのように1行隙間なく敷き詰めればよいわけではなく、
某宝石系落ち物パズルや某アンチウイルス系落ち物パズルのようにまっすぐ並べる必要もない、ぷよぷよ。

これらの「まっすぐ」という制約は、実はプログラミングの難易度を下げる側面があるのです。
 
真四角、鉤形、ぎざぎざ、T字形…
多様な4個組を1本のプログラムで探すのは、実はそこそこ高度です。
でも、その実装例が今手元にあります。そう、ぷよグラミングです!

そんなぷよグラミングでの実装では、先に説明した制御構造関数を応用しています。
さっそく見てみましょう!

場所

前回までは player.js を読みましたが、今回は stage.js に書いてあるプログラムを解説します。

ブックレット8ページ目、 stage.js 152行目にあたります。

        const checkSequentialPuyo = (x, y) => {
            // 中略
        };


前回作った関数とは構文が異なりますが、これも関数です。

再帰

…という言葉を聞いて、ピンとくる方は果たしてここにいるのでしょうか。

上記の checkSequentialPuyo 関数の内側を見ると、終わる直前の182〜183行目で checkSequentialPuyo 関数それ自体を呼んでいます。
このように、関数がそれ自体を呼ぶようなロジックは再帰と呼ばれています。

checkSequentialPuyo 関数は、ある場所の色ぷよとくっついている色ぷよを調べる関数なのですが、
本当に色ぷよが見つかったら、隣のマスに同じ色のぷよがあるか調べるために自分を使用しています。

探索手順
 
きれいな階段積みを例に説明いたします。左から発火して、紫・青・緑・黄色・赤の順に消えます。
左上の空白に対して checkSequentialPuyo 関数を実行します。
右向き(左発火)の階段積みでは、左上には何もありません。
そのマスに色ぷよは居ないので、隣を調べます。
隣のマスには、青ぷよがありました。
checkSequentialPuyo 関数が色ぷよを見つけたら、周りのマスに対しても checkSequentialPuyo を実行します。
これにより、周りの同じ色のぷよがないか調べます。

調べたところ、周りに青ぷよは居ませんでした。これで青ぷよ探索完了です。

結局何ぷよくっついているのか確認すると、1ぷよしかいませんでした。
消すには数が足りないので、見つけた青ぷよは消えずに残ります。
他のぷよも同様に調べます。今回は階段積みの5連鎖なので、てっぺんに発火点のぷよは置いてありません。
上の段を調べ終わったら、次はその下の段です。

紫ぷよを見つけると、青ぷよの時と同様に周りのぷよを checkSequentialPuyo します。
すると、下にも紫ぷよが見つかります。
この場合、新たに見つけた紫ぷよの周りをさらに checkSequentialPuyo します。
そうしてつながっている紫ぷよを次から次へ探してみると、やがて、くっついている紫ぷよが全て見つかります。

結局何ぷよくっついているのか確認すると、4ぷよいました。
消すには充分な数がそろっているので、この紫ぷよは消えます。

(図では即座に消えていますが、実際はすべてのぷよを調べ終えてから同時に消します。)
このように、奥へ奥へと視点を移動しながら探索する手法は、深さ優先探索と呼ばれています。

問題: ぷよぷよを斜めにもくっつける

checkSequentialPuyo 関数が周りのぷよを調べる順番は、下・左・上・右となっています。

この順序は169行目のコードに基づいて決まっているのですが…
この行に、あるコードを書き加えると2マス先や斜めにもくっつけられるようになります。
(ノーヒントでごめんなさい)

まとめ

ぷよグラミングにおいて、あるぷよぷよがくっついているかどうかを判定するには、再帰を利用して深さ優先探索を行っています。

これら二つのキーワード「再帰」「深さ優先探索」はいわゆるアルゴリズムというもので、中級プログラマーにはぜひ調べていただきたいワードです。
最初は気にしなくてもよいですが、もしプログラミングが楽しくなってきたら思い出してあげてください。

それではまたいつかお会いしましょう!

もっとサンプルコードをもてあそびたい

ぷよグラミングをあちこちいじり倒して個性を追加してみたいと思いましたら、以下のシリーズが参考になります。
ぷよグラミングの広範的な解読を目指すシリーズなので、改造にあたっては参考になるはずです。

『ぷよぷよプログラミング』一緒にコードを見てみよう(初心者さん向け)
更新日時:2021/01/09 22:25
(作成日時:2020/12/24 19:00)
コメント( 0 )
コメントするにはログインが必要です
シェア