ぷよぷよ、なんて実装の難しいプログラムであろうか。
…多くは対戦AIなどが語られるが、一人用の実装でも難易度は十分に高い。
そこで、本記事では競プロでお馴染みのデータ構造「素集合データ構造(Union Find木)」を利用して、実装をちょっとだけでも楽にできるんだぜ…という話をしてみる。
どこで使う？
- 同じ色のぷよを繋がりを消去
- 消去したぷよの数を計算
…こんなものだが
従来使われていた探索アルゴリズムでは、とにかく実装が面倒なのである。 なんとなく想像はつくと思うので詳細は省略するが、個人的にはおそらく探索よりもUnionFind木を利用する方が圧倒的に実装が楽であると思う。
ただ、メモリは探索よりも消費する。…といっても、実用範囲ではせいぜい80個分くらいの配列が付け足されるだけなので、マシンにとっちゃもはや「ない」ようなもんでしょう(初心者観点から)
計算効率もちょっと悪いが、同じく雀の涙程度である。
Union Find木とはなにか
初めて知る人はこちらのページを参考にしてほしい。良い解説である。https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396
動作確認はオンラインジャッジより行うのが良い。以下はAtCoderのもの。https://atc001.contest.atcoder.jp/tasks/unionfind_a
使い方
とりあえず、わかりやすくイメージできるように、次のようなぷよの配列があると仮定して考えてみよう。
\ ⬜️⬜️⬜️⬜️⬜️⬜️ / 0, 1, 2, 3, 4, 5
/ ⬜️⬜️⬜️⬜️⬜️⬜️ \ 6, 7, 8, 9,10,11
\ ⬜️⬜️⬜️⬜️⬜️⬜️ / 12,13,14,15,16,17
/ ⬜️⬜️⬜️⬜️⬜️⬜️ \ 18,19,20,21,22,23
\ ⬜️⬜️⬜️⬜️⬜️⬜️ / 24,25,26,27,28,29
/ 🟥⬜️⬜️⬜️⬜️⬜️ \ 30,31,32,33,34,35
\ 🟩⬜️⬜️⬜️⬜️⬜️ / 36,37,38,39,40,41
/ 🟥🟦⬜️⬜️⬜️⬜️ \ 42,43,44,45,46,47
\ 🟦🟦🟦🟩🟩🟩 / 48,49,50,51,52,53
/ 🟥🟥🟧🟩🟥🟩 \ 54,55,56,57,58,59
\ 🟥🟩🟩🟧🟧🟥 / 60,61,62,63,64,65
/ 🟩🟧🟧🟥🟥🟩 \ 66,67,68,69,70,71
左は置かれているぷよ、右はそれぞれの配列を識別する番号を表す。
(任意の番号をnとおくと、xy座標型には (n%6,n/6) として変換できる。 )
今に発火せんとしている。
この状態から、まずこれら72個すべての配列の要素において、それらをパラメータとしたUnion Find木を定義する。
そして
- 横に隣り合っている要素同士(13-15, 63-64など)
- 縦に隣り合っている要素同士(17-23, 43-49など)
のすべての組み合わせにおいて、「その座標にあるぷよの種類が同じであればuniteする」という作業を行う。
すると、
\ ⬜️⬜️⬜️⬜️⬜️⬜️ / 0, 0, 0, 0, 0, 0
/ ⬜️⬜️⬜️⬜️⬜️⬜️ \ 0, 0, 0, 0, 0, 0
\ ⬜️⬜️⬜️⬜️⬜️⬜️ / 0, 0, 0, 0, 0, 0
/ ⬜️⬜️⬜️⬜️⬜️⬜️ \ 0, 0, 0, 0, 0, 0
\ ⬜️⬜️⬜️⬜️⬜️⬜️ / 0, 0, 0, 0, 0, 0
/ 🟥⬜️⬜️⬜️⬜️⬜️ \ 30, 0, 0, 0, 0, 0
\ 🟩⬜️⬜️⬜️⬜️⬜️ / 36, 0, 0, 0, 0, 0
/ 🟥🟦⬜️⬜️⬜️⬜️ \ 42,43, 0, 0, 0, 0
\ 🟦🟦🟦🟩🟩🟩 / 43,43,43,51,51,51
/ 🟥🟥🟧🟩🟥🟩 \ 54,54,56,51,58,51
\ 🟥🟩🟩🟧🟧🟥 / 54,61,61,63,63,65
/ 🟩🟧🟧🟥🟥🟩 \ 66,67,67,69,69,71
となる。
こうなればあとは簡単である。
存在するrootごとにその要素の数を数え(30なら1個、36なら1個………43なら4個、51なら5個……71なら1個 といった具合。0はたくさんあるが、ぷよの置かれていない集合なので無視する)、4つ以上なら消す対象の木としてrootの数値を保持しておく。
そしてもう一度ループしてその木の要素のぷよを消し、その数に応じてスコアを加算。
ぷよが消せたら、空中に浮いているぷよを落としてもう一度この作業を行う。そして、消せるぷよがなくなるまで繰り返したら次のループへ。
という感じ。おしまい。
備考
僕が実際に実装した例。なお、上記のアルゴリズムとは若干異なる部分もいくつかあるが、仕組みは同じである。
https://github.com/Perukii/PeruPuyo