在體素環境中高效放置盒子

Question

我有一組任意定義一個遊戲房間的體素。我的目標是根據道具的具體規則在這個房間內放置各種道具（綁定體素的大小）。一些簡單的規則示例（體素尺寸是xyz，並且道具比這三個要多得多）：

• 書架（2x3x1）需要放在牆上和地面上。
• 一張桌子（4x1x2）需要放在地上。
• 壁掛燈（1x1x1）需要靠牆放置。

道具不能與其他道具或現有的體素相交。我試圖找到一些有效的數據結構和/或算法，可以讓我以相當快的速度做到這一點。我的當前方法是這樣的：

• 創建一組可能的位置道具小號，這是一組相鄰的體素填充空體素。
• 馬克在每個項目小號如果是地板，牆壁，牆角等
• 選擇一個道具P放置。
• 選擇子集S'的S滿足道具（僅牆，角等）的放置規則。
• 選取任意元素E從S'。
• 這裏是非最佳部分：嘗試以某種方式適合P約E。看看是否允許將它放在E之上，而不與其他道具和體素相交。如果不適合，請嘗試旋轉和/或翻譯P的邊界，直到它位於包含E的合法地點。
• 如果它可以適合，然後更新S包括新的道具，並開始放置更多的道具。
• 如果仍然不合適，則從S'中挑選另一個任意元素，然後重試。

它在技術上的作品，但它不是很優化，可以在最壞的情況下，例如當道具不能在房間的任何地方適合可怕的執行，或者如果我撿很多大型落地道具放在一個房間裏，大部分的地面空間被柱子和 洞打破。

如果我在選擇E時可以採用P的尺寸，那麼這將是理想選擇。我正在研究生成體素網格的3D convolution地圖（本質上是製作網格的模糊圖像），以便每個體素都有一些關於它周圍有多少空間的粗略數據，但問題是我需要更新地圖每次我放下一個新的道具，聽起來都很昂貴。

另一個想法是將世界存儲在八叉樹中，並以某種方式更好地進行佈局檢查，但我似乎無法想象這將如何提供幫助。八叉樹是否允許我確定任意一個盒子是否比任意位置的字典更有效地包含任何點？

TLDR：如何使用可能比單個體素更大的裝飾物以編程方式在Minecraft中裝飾房屋？

Answer 1

如果在S中沒有太多體素，在創建牆壁和樓層後，您可以簡單地創建3個有效位置的詳盡集合，每個屬性類型一個。讓我們調用p型ValidPlacements（p）的道具的有效位置集合。

然後，當您成功地將一個新對象放入該世界中時，對於每個prop類型p，生成至少與剛剛放置的對象的1個體素相交的類型p的位置集合，並將它們從ValidPlacements（p）。 （這些展示位置中的一些可能已經不存在了，因爲由於先前放置的對象而已知它們是不可能的 - 這不是錯誤條件，它可以被忽略。）使用散列表或平衡樹結構來保存每個對象可以在O（1）時間或O（log n）時間分別查找和刪除每個人，因此可以分別在O（1）時間或O（log n）時間刪除每個人。

因爲您的對象很小，放置一個對象只會消除少量其他可能的對象佈局，因此爲任何對象刪除的展示位置數量都會很小（它應該大致與正在交叉的兩個對象的體積的乘積成比例）。如果您需要回溯並嘗試對象x的其他展示位置，請在放置x時記錄哪些展示位置實際上已從允許的展示位置集中刪除，並在刪除x時重新插入它們。例如：將一個書架放在左上角（x，y，z）的書架上將消除燈的2 * 3 * 1 = 6個可能的放置位置（即對於現在佔用的每個體素，放置1個書架） ，以及更多數量的書桌和書架展示位置（即每個可能展示位置有1個展示位置，這些展示位置與剛放置的書架有任何重疊）。