我有一组任意的体素来定义游戏的房间。我的目标是根据道具的特定规则在这个房间内放置各种道具(绑定到体素的大小)。一些简单的规则示例(体素维度为 xyz,props 远不止这三个):
- 书架 (2x3x1) 需要靠墙和地面放置。
- 需要在地面上放置一张桌子(4x1x2)。
- 壁挂式灯 (1x1x1) 需要靠墙放置。
道具不能与其他道具或现有体素相交。我试图找到一些有效的数据结构和/或算法,可以让我相当快地做到这一点。我目前的方法是这样的:
- 创建一组可能的道具位置,这是一组与填充体素相邻的空体素。
- 如果是地板、墙壁、角落等,请在S中标记每个项目。
- 选择要放置的道具P。
- 选择满足道具放置规则的 S 的子集S ' (仅限墙壁、角落等)。
- 从S'中选择任意元素E。
- 这是非最佳部分:尝试以某种方式将P拟合到E周围。看看P的边界是否允许它被放置在E之上而不与其他道具和体素相交。如果不合适,请尝试旋转和/或平移P的边界,直到它位于包含E的合法位置。
- 如果合适,则更新S以包含新道具,并开始放置更多道具。
- 如果仍然不合适,则从S'中选择另一个任意元素并重试。
它在技术上是可行的,但不是非常理想,并且在最坏的情况下表现得非常糟糕,例如当道具不能放在房间的任何地方时,或者如果我要挑选许多大型地板道具放在一个房间里地面空间被柱子和洞打破。
如果我能在选择E时以某种方式考虑P的尺寸,那将是理想的。我正在研究生成体素网格的 3D卷积图(本质上是制作网格的模糊图像),以便每个体素都有一些关于它周围有多少空间的粗略数据,但问题是我需要更新地图每次我放下一个新道具,这听起来很贵。
另一个想法是将世界存储在八叉树中,并以某种方式进行更好的位置检查,但我似乎无法想象这会有多大帮助。八叉树是否允许我确定任意框是否包含比位置键控的字典更有效的任何点?
TLDR:您将如何使用比单个体素更大的装饰物以编程方式装饰 Minecraft 中的房子?