ゲームの部屋を定義するボクセルの任意のセットがあります。私の目標は、小道具の特定のルールに従って、この部屋内にさまざまな小道具（ボクセルのサイズにバインドされている）を配置することです。いくつかの簡単なルールの例（ボクセルの次元はxyzであり、これら3つだけよりもはるかに多くの小道具があります）：
- 本棚（2x3x1）を壁と地面に立てかける必要があります。
- テーブル（4x1x2）を地面に置く必要があります。
- 壁に取り付けられたランプ（1x1x1）を壁に立てかける必要があります。
小道具は、他の小道具や既存のボクセルと交差することはできません。これをかなり高速に実行できる効率的なデータ構造やアルゴリズムを見つけようとしています。私の現在の方法はこれです：
- 塗りつぶされたボクセルに隣接する空のボクセルのセットである、可能なプロップ位置のセットSを作成します。
- 床、壁、角などの場合は、 Sで各アイテムにマークを付けます。
- 配置するプロップPを選択します。
- 小道具の配置規則（壁のみ、コーナーなど）を満たすSのサブセットS'を選択します。
- S'から任意の要素Eを選択します。
- これが最適ではない部分です。どういうわけかPをEの周りに合わせてみてください。Pの境界によって、他の小道具やボクセルと交差することなくEの上に配置できるかどうかを確認します。収まらない場合は、Eを含む合法的なスポットになるまで、 Pの境界を回転および/または平行移動してみてください。
- 収まる場合は、 Sを更新して新しい小道具を含め、さらに小道具の配置を開始します。
- それでも収まらない場合は、S'から別の任意の要素を選択して再試行してください。
技術的には機能しますが、あまり最適ではなく、小道具が部屋のどこにも収まらない場合や、大部分の部屋に置くために大きな床の小道具をたくさん選んでいる場合など、最悪のシナリオでひどく実行できます。床面積は柱と穴で分割されています。
Eを選ぶときにPの次元をどうにかして考慮に入れることができれば理想的です。ボクセルグリッドの3D畳み込みマップを生成することを検討していました（基本的にグリッドのぼやけた画像を作成します）。これにより、各ボクセルの周囲のスペースの大まかなデータが得られますが、問題はマップを更新する必要があることです。新しい小道具を置くたびに、それは高価に聞こえます。
もう1つのアイデアは、世界を八分木に保存し、それを使って配置チェックを改善することでしたが、それがどのように役立つかは想像できません。八分木を使用すると、任意のボックスに、位置でキー設定された辞書よりも効率的にポイントが含まれているかどうかを判断できますか？
TLDR：単一のボクセルよりも大きくなる可能性のある装飾を使用して、Minecraftの家をプログラムでどのように装飾しますか？