6
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

Union-Find で一人用ぷよぷよの実装をちょっと楽に

Last updated at Posted at 2020-03-17

ぷよぷよ、なんて実装の難しいプログラムであろうか。
…多くは対戦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

6
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?