地面と接続されているかを計算するアルゴリズム？

Question

マインクラフト上で、ブロックが地面と接続されているかをチェックする仕組みを作りたいのですが、
適用できる既存のアルゴリズムか、数学的な考え方があれば教えていただけますでしょうか。

マインクラフト上でというのは、ゲーム内のレッドストーンブロックでやるのではなく、サーバープラグインを作ってやるつもるなので、
サーバーAPIを利用できます。

例えば下記のように

• ある座標xyzの隣接するブロックの種類（ブロックの場合もあり、空気の場合もある）をチェック
• ユーザーが設置/破壊したブロックの座標や種類を取得

などなど割と自由な操作が可能です。

あるブロックのまとまりが宙に浮いてしまっていることを検知できるようにするのが目的です。

    ■ < 浮いてる
■■  ■ < 浮いてる
■■
-----------
地面

Comments

[jimbe]

「地面」の定義は何でしょう. 土ブロックや草ブロックが「地面」なのでしょうか.

[devsx]

今回の場合は、y座標６４にあるブロックが地面と定義して問題ありません！

[jimbe]

なるほど.
では「あるブロックのまとまりが宙に浮いてしまっていることを検知」というのは, 極端かと思いますが例えばエンドは大小さまざまな島が奈落の上に浮いています. あれも全て「浮いている」判定となる感じでしょうか.

[devsx]

そういうことになりますね・・・

ただ最初から浮いている状態のワールドは想定していなくて、ユーザーが積み上げたり壊したりして、結果的に浮いてしまったブロックを検知する、というようなものを想定しております。

[devsx]

縦に１００ブロック積んで、一番したのブロックを破壊したら、↑の９９ブロックが浮いてしまったｍとかですね。このようにy方向だけの検知ならなんとなくできると思うのですが、これが±x,±y,±z方向もチェックする必要があるので、効率的な検知方法があれば・・・との考えです。

[jimbe]

おそらく, 地面(Y64) と「壊したブロックの周囲の非空気ブロック(?)」との(非空気ブロック経由の)経路を探す問題…のような感じかと思いますが, 私も空中に線路を1000ブロック以上引いたりしていますが, これが接地されているかを調べるのに効率的な方法があるようには...
すいません.

[devsx]

いえいえ、一緒に考えていただけただけでありがたいです！
ありがとうございました！

Answer 1

原理的にはこの質問と同じ考え方になるのではないでしょうか。
これは｢島を数える｣ですが、その探査中に地面(今回の場合、y座標が64のブロック)に行き着かなければ｢浮いている｣と判定できると思います。

Comments

[devsx]

なるほど、幅優先探索で隣接するブロックをフルスキャンして行く形ですね！
その中で、「y座標が64のブロック」であるかどうかをチェックしていく、と。
使えそうな気がしました！ありがとうございます！