はじめに
いま、Siv3Dでパズルゲームを制作しています。本当はこの記事を書くまでにゲームを遊べるようにして、ゲームの紹介も含めてこの記事を書く予定だったのですが、公開できるまでにはもう少し時間が必要そうです。初めてのゲーム制作で、勝手がわからず苦労しています...
この記事では、制作中のゲームを少しだけ紹介して、そのあとゲームで使われているアルゴリズムについて紹介していきます。
どんなゲーム？
いま作ってるパズルゲーム（アドカレに載せる用） pic.twitter.com/8eQOgJbZbO
— こいソー (@koikuchi_sosu) December 15, 2022
まだ開発中の画面なので、見た目は大きく変更されるかもしれませんが、遊びの根本は大きくは変わらないと思います。ゲームの概要はこんな感じです。
- このゲームをクリアするには、上にある黄色い敵（このような図形をポリオミノといいます）のブロックをすべて破壊しなければなりません。
- 下にあるカラフルなポリオミノたちを、一筆書きして倒すとポイントがたまります。
- 同じ色を連続させて一筆書きすると、より大きくポイントがたまります。
- ポイントがたまるたびに、黄色い敵のブロックを破壊していくことができます。
ゲームのおもしろポイント？
ここまでだと、ゲームとしての目新しさはないかもしれません。このゲーム独自の内容（だと思っている）としては、
- ポリオミノの外周をゲージが周回しており、これが一周するたびに、ポリオミノたちが攻撃してきます。
- 黄色い敵のブロックを破壊していくと、はじめはひとつだったポリオミノがタテヨコに繋がらなくなることで、いくつものポリオミノに分裂してそれぞれが独立に行動を始めます。
というのがあります。つまり、黄色いポリオミノのブロックをテキトーに破壊してしまうと、外周の短いポリオミノが量産されてとんでもない頻度で攻撃が飛んでくるわけです。
黄色い敵のブロックはある程度ランダムに壊れるようにしていますので、ゲームが進行するに連れて、自然と敵が分裂していき外周の長さも短くなっていきます。これによって、はじめは簡単でだんだん難しくなっていくという、ゲームの基本的な流れを自然な形で組み込めたのがよかったと思います。
また、敵の体力、敵の強さ、いま優勢なのか劣勢なのか、などの情報を、できるだけ数字などに頼らず、図形的に表現することも考えて作っています。
ポリオミノの外周を計算する
さて、ゲームの概要を紹介したところで本題に入っていきます。ゲーム中の「ポリオミノの外周をゲージが周回する」というのを実現するために思いついたアルゴリズムを紹介します。
問題設定は？
0と1の二次元グリッドの形でポリオミノが入力されるので、ポリオミノの外周を構成する点列を時計回りに出力するというものです。
早速ですが、こんなアルゴリズムで実現できました
二次元グリッド上の格子点を頂点として、有向グラフを構築します。なお、以下で「辺」といっているのは、グリッドのセルの辺ではなくて、グラフの（有向）辺のことです。
-
ポリオミノを構成するすべてのセルについて、以下をおこないます。
セルの各頂点を、左上から時計回りにA, B, C, Dとして、- 上のセルが埋まっていないならA→Bの辺をはる。
- 右のセルが埋まっていないならB→Cの辺をはる。
- 下のセルが埋まっていないならC→Dの辺をはる。
- 左のセルが埋まっていないならD→Aの辺をはる。
-
ポリオミノの外周上に始点をとって、一周するまで辺をたどっていくと、所望の点列が得られます。始点としては、例えばポリオミノを構成するセルのうち、座標が辞書順最小のセルの左上の点をとることができます。
コーナーケース？
これでほとんどよいのですが、注意すべきケースがあります。
図のようなポリオミノにおいて、左と右のどちらを外周とするかという問題があります。
左のように、できるだけ中に入っていくものを外周としてみましょう。このときは、「できるだけ右向け右をしたい人」になって辺をたどっていく必要があります。つまり、直前にたどった辺が
- →の向きなら、次は可能なら↓の向き
- ↓の向きなら、次は可能なら←の向き
- ←の向きなら、次は可能なら↑の向き
- ↑の向きなら、次は可能なら→の向き
にたどるようにすればよいです。
図の右のものを外周として出力したい場合は、「できるだけ左向け左をしたい人」になりましょう。
複数のポリオミノがある場合
与えられたグリッドにおいて、埋まっているセルがタテヨコに繋がったかたまりが複数ある場合、つまり複数のポリオミノが存在する場合を考えます。この場合は、各ポリオミノを幅優先探索、深さ優先探索などでひとつずつ抽出しながら外周を計算していけばよいです。
ただ、各ポリオミノに対して有向グラフを構築するときに、毎回二次元配列を初期化していては無駄が大きいです。実は、コーナーケースで紹介した2つの外周のうち「できるだけ中に入っていくもの」を採用した場合は、ひとつの二次元配列を再初期化することなく使いまわしても不具合が生じないことが確認できます。逆に、もう一方の外周を採用すると、異なるポリオミノが斜めに接している場合にうまくいきません（解決策はいくつか思いつきますが、いずれも実装が少し煩雑になるかと思います）。
以下で紹介する実装例でも、この事実を念頭において実装しています。
アルゴリズムの実装例
上で紹介したアルゴリズムを用いて、Siv3Dでポリオミノエディタを書いてみました。ポリオミノにマウスオーバーすると、外周をまわるゲージが前進します。
ソースコードはこちら
#include <Siv3D.hpp> // OpenSiv3D v0.6.6
class MyGrid {
public:
MyGrid() {
for (auto y : step(height)) {
for (auto x : step(width)) {
rects[y][x] =
Rect{cell_size * x, cell_size * y, cell_size, cell_size};
}
}
random_fill();
compute_perimeters();
}
// すべてのポリオミノの外周のパスを計算する
void compute_perimeters() {
perimeters.clear();
polyomino_id.fill(none);
num_polyominos = 0;
// 訪問済みのセルかどうか
Grid<bool> seen{width, height, false};
// 訪問中のセルを入れておく配列
Array<Point> stack;
// 各格子点から出ていく辺を4方向について管理する
Grid<std::array<Optional<Point>, 4>> graph{
width + 1, height + 1, {none, none, none, none}};
for (auto y : Range(1, height - 1)) {
for (auto x : Range(1, width - 1)) {
if (not grid[y][x] or seen[y][x]) {
continue;
}
/* ここを抜けるごとに新しいポリオミノを処理 */
seen[y][x] = true;
stack.emplace_back(x, y);
polyomino_id[y][x] = num_polyominos;
// ポリオミノの各セルを見ていき、グラフを構成する
while (not stack.empty()) {
auto [x, y] = stack.back();
stack.pop_back();
polyomino_id[y][x] = num_polyominos;
// 上のセルが埋まっていないなら右向きに辺をはる
if (not grid[y - 1][x]) {
graph[y][x][0] = Point{x + 1, y};
} else if (not seen[y - 1][x]) {
seen[y - 1][x] = true;
stack.emplace_back(x, y - 1);
}
// 右のセルが埋まっていないなら下向きに辺をはる
if (not grid[y][x + 1]) {
graph[y][x + 1][1] = Point{x + 1, y + 1};
} else if (not seen[y][x + 1]) {
seen[y][x + 1] = true;
stack.emplace_back(x + 1, y);
}
// 下のセルが埋まっていないなら左向きに辺をはる
if (not grid[y + 1][x]) {
graph[y + 1][x + 1][2] = Point{x, y + 1};
} else if (not seen[y + 1][x]) {
seen[y + 1][x] = true;
stack.emplace_back(x, y + 1);
}
// 左のセルが埋まっていないなら上向きに辺をはる
if (not grid[y][x - 1]) {
graph[y + 1][x][3] = Point{x, y};
} else if (not seen[y][x - 1]) {
seen[y][x - 1] = true;
stack.emplace_back(x - 1, y);
}
}
// はじめに訪問したセルの左上を始点とする
Point now{x, y};
// 4方向のうち、直前に通ってきた方向をもっておく
int32 prev_dir{3};
perimeters.emplace_back();
// ポリオミノの外周のパスをつくる
do {
// 4方向を順番に見ていき辺がはられていたら先に進むのを、一周するまで繰り返す
for (auto d : Range(1, 5)) {
const auto next_dir = (prev_dir + d) % 4;
if (graph[now][next_dir].has_value()) {
perimeters[num_polyominos].emplace_back(
now * cell_size,
graph[now][next_dir].value() * cell_size);
now = graph[now][next_dir].value();
prev_dir = next_dir;
break;
}
}
} while (now != Point{x, y});
++num_polyominos;
}
}
gauge_lens.resize(num_polyominos, 0.0);
}
// 描画する
void draw() const {
for (auto y : Range(1, height - 1)) {
for (auto x : Range(1, width - 1)) {
if (grid[y][x]) {
rects[y][x].draw(Palette::Green);
}
}
}
// 縦の罫線を描画
for (auto x : Range(1, width)) {
Line{cell_size * x, 0, cell_size * x, cell_size * height}.draw();
}
// 横の罫線を描画
for (auto y : Range(1, height)) {
Line{0, cell_size * y, cell_size * width, cell_size * y}.draw();
}
draw_gauges();
}
// ゲージの進行を更新する
void update_gauges() {
const auto pos = Cursor::Pos() / cell_size;
for (auto polyomino_index : step(num_polyominos)) {
// マウスオーバーされているならゲージを前進させる
if (polyomino_id[pos].has_value() and
*polyomino_id[pos] == polyomino_index) {
gauge_lens[polyomino_index] =
Min(gauge_lens[polyomino_index] +
Scene::DeltaTime() * gauge_speed,
static_cast<double>(
std::size(perimeters[polyomino_index])));
}
// マウスオーバーされていないならゲージを後退させる
else {
gauge_lens[polyomino_index] =
Max(gauge_lens[polyomino_index] -
Scene::DeltaTime() * gauge_speed,
0.0);
}
}
}
// セルをフリップする
void flip() {
const auto pos = Cursor::Pos() / cell_size;
// グリッドの端のセルは埋めない
if ((pos.x <= 0 or width - 1 <= pos.x) or
(pos.y <= 0 or height - 1 <= pos.y)) {
return;
}
if (MouseL.down()) {
grid[pos] = not grid[pos];
cell_state = grid[pos];
} else if (MouseL.pressed()) {
grid[pos] = cell_state;
}
}
// セルをすべてクリアする
void clear() { grid.fill(false); }
// ランダムにセルを埋める
void random_fill() {
for (auto y = 1; y < height - 1; ++y) {
for (auto x = 1; x < width - 1; ++x) {
grid[y][x] = RandomBool();
}
}
}
// ゲージの進行をリセットする
void reset_gauges() { gauge_lens.fill(0.0); }
private:
// ゲージを描画する
void draw_gauges() const {
for (auto gauge_idx : step(num_polyominos)) {
size_t len_int = static_cast<size_t>(gauge_lens[gauge_idx]);
for (auto i : step(len_int)) {
perimeters[gauge_idx][i].draw(5, Palette::Yellow);
}
if (len_int < std::size(perimeters[gauge_idx])) {
perimeters[gauge_idx][len_int]
.stretched(0, cell_size *
((gauge_lens[gauge_idx] - len_int) - 1.0))
.draw(5, Palette::Yellow);
}
}
}
// セルが埋められているか
Grid<bool> grid{width, height, false};
// 各セルを表すRect
Grid<Rect> rects{width, height};
// ポリオミノの個数
int32 num_polyominos;
// 各セルが属するポリオミノの番号
Grid<Optional<int32>> polyomino_id{width, height};
// ポリオミノごとの外周のパスの配列
Array<Array<Line>> perimeters;
// ポリオミノごとのゲージの長さの配列
Array<double> gauge_lens;
// セルをどちらの状態に変更するか
bool cell_state;
// グリッドのセルの個数（横）
static constexpr int32 width{20};
// グリッドのセルの個数（縦）
static constexpr int32 height{15};
// セルの一辺の長さ
static constexpr int32 cell_size{40};
// ゲージが前進、後退する速さ
static constexpr double gauge_speed{20.0};
};
void Main() {
MyGrid grid;
// 編集中かどうか
bool edit_mode{false};
while (System::Update()) {
grid.draw();
if (edit_mode) {
grid.flip();
// 編集モードを終了する
if (SimpleGUI::ButtonAt(U"Done", Vec2{60, 20}, 100)) {
edit_mode = false;
grid.compute_perimeters();
}
} else {
grid.update_gauges();
// 編集モードを開始する
if (SimpleGUI::ButtonAt(U"Edit", Vec2{60, 20}, 100)) {
edit_mode = true;
grid.reset_gauges();
}
}
// 編集モードでないときは無効
if (SimpleGUI::ButtonAt(U"Clear", Vec2{170, 20}, 100, edit_mode)) {
grid.clear();
}
// 編集モードでないときは無効
if (SimpleGUI::ButtonAt(U"Random", Vec2{280, 20}, 100, edit_mode)) {
grid.random_fill();
}
}
}
もっと軽めの実装になる予定だったのですが、ちょっと長くなってしまいました。MyGrid::compute_perimeters()において、各ポリオミノ（連結成分）を抽出しながら外周を計算しています。
自分で書いたアルゴリズムがちゃんと動作しているのが可視化されると感動もひとしおですね。Siv3Dの開発環境がある方は、ぜひ動かしてみてください！
おわりに
ゲームが完成したときには、遊んでいただけたら嬉しいです。ブラウザ上で遊べるようにする予定で、ランキング機能も実装しています。近いうちに公開できるようにがんばります！