グラフ理論って何に使うのさ（ゲーム開発編）
まえがき
今月二回目のアドカレ記事になります。二本目のテーマは、グラフ理論のアルゴリズムの具体的な活用例です。
想定している対象読者は、ゲーム開発に興味がある人等です。あまり難しい話ではありませんので、気軽に読んでいただければと思います。
君はMinecraftを知っているか
この世にはMinecraftというゲームがあります。まあ、多くの方は既にご存知かと思うのですが。
このゲームはいわゆるサンドボックスというカテゴリのもので、たくさんのブロックを最小単位として構成された世界で自由に遊ぶことができます。
立方体の形状でないブロックもある
ブロックを積んでもよし、壊してもよし。あるいはPvPだけをひたすらに極めても良いし、クリエイティブモードで建築だけをしてもいい世界ですが、今回はゲームプレイに関する内容というよりMinecraftの中身の話をしようと思います。
今回のトピック
さて、Minecraftのブロックには多種多様なものがあるのですが、その中でも面白い性質を持つ1つのブロックがあります。スポンジです。
喋りません
Minecraftにおけるスポンジブロックの機能は、自分の周囲にある水を吸うことです。もっと具体的に言うと、自分を中心として距離6[1]までの範囲にある水[2]を、最大65ブロックまで吸収することができます。
今回の記事では、このブロックの機能について取り扱っていきたいと思います。
どう実装しますか？
突然ですが、上で説明した「水を吸収する」という処理を作ろうと思ったら、あなたはどんなコードを書きますか？
といっても、前提として与える情報がまだ不足していると思うので、ちょっと補足します。
Minecraftの世界は一般的な3次元の座標空間と同一視できます。立方体ブロックの一辺を1とするようなスケールの座標系です。これは、実際にゲーム内のデバッグ情報からも見ることができます。
ここで、座標空間上の格子点に各ブロックの頂点が来るように並べていってあげれば、空間内に自然にブロックが配置できる、という感じです。
また、各ブロックの8つの頂点のうち、最も
プログラム的にも、格子点の座標を扱うだけなら整数型で良いのでコストがあまりかからずに済みます。
このため、Minecraftには整数の3つ組の座標を効率良く扱うためにBlockPosというクラス[4]があります。
あと、同様にこのゲーム特有のオブジェクトとして、Level（各ディメンションを管理するクラス）やDirection（上下と東西南北を表現する用のenum）などが出てきますが、関数名等でなんとなく読めるかな～と思うので、解説はちょっと省略します。
一番簡単そうな例
以下のように、現在いるワールドと設置されたスポンジの座標を引数にとるような関数を考えましょう。（ちょっとTopCoderっぽい感じがしますね！）
private boolean removeWater(Level level, BlockPos spongePos) {
// 水を吸収する処理
}
返り値は、1ブロックでも吸水したらtrue、そうでないならfalseです。Minecraftのスポンジは水を吸うと濡れたスポンジというブロックに変化するので、この処理に使われることになります。今回はこの部分には触れないので、特に気にする必要はありません。
さて、自分の周囲のブロックに干渉したいとなると、一番単純なコードとして以下のようなアルゴリズムが思いつく人が多いのではないでしょうか。
public static final int MAX_DEPTH = 6;
public static final int MAX_COUNT = 64;
private boolean removeWater(Level level, BlockPos spongePos) {
// 水を吸収する処理
int spongeX = spongePos.getX();
int spongeY = spongePos.getY();
int spongeZ = spongePos.getZ();
int i = 0;
for (int x = -MAX_DEPTH; x <= MAX_DEPTH; x++) {
for (int y = -MAX_DEPTH; y <= MAX_DEPTH; y++) {
for (int z = -MAX_DEPTH; z <= MAX_DEPTH; z++) {
BlockPos pos = new BlockPos(spongeX + x, spongeY + y, spongeZ + z);
if (posの位置のブロックが水だったら) {
ブロックを消す;
i++;
}
if (i > 64) return true;
}
}
}
return i > 0;
}
3重ループによって、自分を中心とする13x13の範囲のブロックを参照するようなプログラムです。これで上手くいくでしょうか？
少し頭の中でシミュレーションをしてみてください。ちょっと変な挙動のスポンジになりますよね？
何が変なのかと言えば、スポンジの周辺から水が消えていくような処理の順にならないことです。
あとこのアルゴリズムにはもう一つ致命的なミスがあって、スポンジから見て水だけを辿って到達できない位置の水も消してしまう可能性があります！
順序を工夫するような処理をすれば、もしかしたらこの3重ループのような処理でもスポンジを実装できるかもしれませんが、それはあまり簡単では無さそうです。もっと簡単に、理想のスポンジを実装できないでしょうか？
少し視点を変えてみる
シンプルな3重ループだけでは、スポンジは作れなさそうです。
やりたいことと言うと、スポンジを始点として、そこから放射状（？）に吸水されるような処理の順番にしたいわけです。あとついでに、スポンジからちゃんと到達可能な水だけ吸われるようにしたい。
と、ここまで要件をまとめてみると、「これってグラフ上の問題と似てるな…？」という気がしてきます。
ここで、Minecraftのワールドを3次元のグリッドグラフだと思ってみます。ワールド上の各ブロックを頂点として、その各頂点から上下と東西南北に6本無向辺を張ることで、グラフが構成できます。（言葉通りに辺を張ると多重辺になってしまいますが、1本だけあるものとしてください）
競技プログラミングだとしばしば2次元のグリッドグラフ上での問題がありますが、これの次元が一つ上がっただけと思うと分かりやすいかもしれません。
そういうことで、スポンジの実装をグラフ理論の観点から考えてみると、幅優先探索(BFS)すれば良さそうじゃない？と思えてきます。
幅優先探索についての解説は素晴らしい先駆者の方々の記事がありますので、そちらを参照ください。
実装してみる
先に、実際のMinecraftの内部実装を紹介します。
権利の関係などもあるので、複雑な部分は少し省略したりしています。
public static final int MAX_DEPTH = 6;
public static final int MAX_COUNT = 64;
private boolean removeWaterBreadthFirstSearch(Level level, BlockPos spongePos) {
Queue<Tuple<BlockPos, Integer>> queue = Lists.newLinkedList();
queue.add(new Tuple<>(spongePos, 0));
int i = 0;
while(!queue.isEmpty()) {
Tuple<BlockPos, Integer> tuple = queue.poll();
BlockPos blockpos = tuple.getA();
int j = tuple.getB(); // スポンジからの距離
// blockposから6方向へ探索する
for(Direction direction : Direction.values()) {
BlockPos blockpos1 = blockpos.relative(direction);
BlockState blockstate = level.getBlockState(blockpos1);
FluidState fluidstate = level.getFluidState(blockpos1);
Material material = blockstate.getMaterial();
if (fluidstateが水) {
if (blockstate.getBlock()が水源or水流) {
blockpos1の位置に空気ブロックを置く;
++i;
if (j < MAX_DEPTH) {
queue.add(new Tuple<>(blockpos1, j + 1));
}
}
else if (materialが海藻) {
海藻からドロップアイテムを出す;
blockpos1の位置に空気ブロックを置く;
++i;
if (j < MAX_DEPTH) {
queue.add(new Tuple<>(blockpos1, j + 1));
}
}
}
}
if (i > MAX_COUNT) break;
}
return i > 0;
}
JavaにTupleは無いのでは？と思った方もいるかもしれませんが、これは独自実装されているもので、2つのオブジェクトを保持できます。どちらかというと、C++のpair等に近いです。
一般的なBFSでは、探索する予定の頂点idを入れるキューと、始点からの距離を保存していく用の配列の2つを用意すると思いますが、この実装ではTupleを用いて一つにまとめています。
では、既に到達した頂点か否かの判定はどうしているのか？という疑問が湧きますが、これは頂点を探索したと同時にそのブロックを水から空気ブロックに変えてしまっているので、二度探索されることはない、という仕組みになっています。
Minecraftって面白いゲームなんです
今回はスポンジのアルゴリズムについて話しましたが、これ以外にも面白い話がたくさんあります。別にプログラミングに関係ない話も、たくさんあるんですよね。そういう話も、どこかで書けたらいいな～と思いつつ、今回は締めにしたいと思います。
Minecraftっていうゲーム、本当に面白いのでやったことない人はぜひ！教育効果もめちゃくちゃに高いゲームです。（私はマイクラのお陰で数学と英語ができるようになったのでとても感謝）
では、よいクリスマスを！
Discussion