3

我有一组任意的体素来定义游戏的房间。我的目标是根据道具的特定规则在这个房间内放置各种道具（绑定到体素的大小）。一些简单的规则示例（体素维度为 xyz，props 远不止这三个）：

  • 书架 (2x3x1) 需要靠墙和地面放置。
  • 需要在地面上放置一张桌子（4x1x2）。
  • 壁挂式灯 (1x1x1) 需要靠墙放置。

道具不能与其他道具或现有体素相交。我试图找到一些有效的数据结构和/或算法，可以让我相当快地做到这一点。我目前的方法是这样的：

  • 创建一组可能的道具位置，这是一组与填充体素相邻的空体素。
  • 如果是地板、墙壁、角落等，请在S中标记每个项目。
  • 选择要放置的道具P。
  • 选择满足道具放置规则的 S 的子集S ' （仅限墙壁、角落等）。
  • 从S'中选择任意元素E。
  • 这是非最佳部分：尝试以某种方式将P拟合到E周围。看看P的边界是否允许它被放置在E之上而不与其他道具和体素相交。如果不合适，请尝试旋转和/或平移P的边界，直到它位于包含E的合法位置。
  • 如果合适，则更新S以包含新道具，并开始放置更多道具。
  • 如果仍然不合适，则从S'中选择另一个任意元素并重试。

它在技术上是可行的，但不是非常理想，并且在最坏的情况下表现得非常糟糕，例如当道具不能放在房间的任何地方时，或者如果我要挑选许多大型地板道具放在一个房间里地面空间被柱子和洞打破。

如果我能在选择E时以某种方式考虑P的尺寸，那将是理想的。我正在研究生成体素网格的 3D卷积图（本质上是制作网格的模糊图像），以便每个体素都有一些关于它周围有多少空间的粗略数据，但问题是我需要更新地图每次我放下一个新道具，这听起来很贵。

另一个想法是将世界存储在八叉树中，并以某种方式进行更好的位置检查，但我似乎无法想象这会有多大帮助。八叉树是否允许我确定任意框是否包含比位置键控的字典更有效的任何点？

TLDR：您将如何使用比单个体素更大的装饰物以编程方式装饰 Minecraft 中的房子？

4

1 回答 1

1

如果您在 S 中没有太多体素，则在创建墙壁和地板后，您可以简单地创建 3 组详尽的有效放置，每种道具类型一组。我们将类型为 p 的道具的有效展示位置集合称为 ValidPlacements(p)。

然后，当您成功地将新对象放置到世界中时，对于每个道具类型 p，生成将与刚刚放置的对象在至少 1 个体素中相交的类型 p 的放置集，并从 ValidPlacements(p) 中删除它们. （其中一些位置可能已经不存在，因为它们已经知道由于早期放置的对象而不可能 - 这不是错误条件，它可以被忽略。）使用哈希表或平衡树结构来保存每个一组展示位置，以便可以分别在 O(1) 时间或 O(log n) 时间内查找和删除每个位置

因为你的对象很小，放置一个对象只会消除少量其他可能的对象放置，因此任何对象删除的放置数量都会很小（它应该大致与相交的两个对象的体积的乘积成正比）。如果您需要回溯并尝试对象 x 的其他放置，请记录在放置 x 时实际从允许放置集中删除的放置，并在删除 x 时重新插入它们。

示例：在 (x, y, z) 处放置一个具有左上角最前角的书架将消除 2*3*1 = 6 个可能的灯放置位置（即，现在桌子占据的每个体素 1 个放置位置），而更大的桌子和书架放置的数量（即与刚刚放置的书架以任何方式重叠的每个可能的放置1个放置）。

于 2012-12-13T06:47:05.943 回答