一个3D体积的数据结构和算法？

Question

我一直在尝试开发Minecraft Bukkit插件，并且目前正在开发一个需要定义空间“体积”的功能，以及确定实体（玩家）何时从该体积的外部移动到内部（或反之亦然）。

如果我将“体积”限制为方块，则应该很简单。数据结构只需维护X/Y/Z边界整数（因此总共6个整数），并且通过给出两个点（从一个点移动到另一个点）来计算进入/退出，应该只需确定A）所有三个目标值是否在所有三个范围内，以及B）至少一个起始值是否在其对应的范围之外。

（但是，如果有更好的、更高效的存储和计算方法，我很愿意听听。）

然而，如果“体积”不是一个简单的盒子呢？假设我有一个奇怪形状的房间，想要围住该房间的体积。我可以单独安排多个“体积”来填充整个空间，但是当实体从一个“体积”移动到另一个“体积”时，这将导致错误的结果。

由于我以前没有从事过游戏或3D引擎方面的工作，我对如何构建这样的东西感到困惑。但是我想到这很可能是一个已经解决并且有已知的模式的问题。基本上，我正在尝试：

1.定义一个数据结构，该数据结构可以表示一个奇怪形状的空间体积（至少基于块坐标）。

2.定义一种算法，该算法可以在给定移动的源和目的地时，确定移动是否跨越了定义空间的边界。

这方面是否有已知的模式和做法？

- David

Answer 1

我不知道这种方法是否在任何一种视频游戏中被使用过，但我首先想到的是经典的埃拉托斯特尼筛法实现，唯一的变化就是将布尔数组变成3D，并使用键作为坐标。显然，在Minecraft中，由于x和y值可能非常大，您可能希望通过保存世界0,0位置和您的选择之间的偏移量来节省空间，例如：

class OddArea
{
    static final int MAX_SELECTION_SIZE = 64; //Or whatever

    public final int xOffset, yOffset;

    // 256 = Chunk height
    public final boolean[][][] squares = new boolean[MAX_SELECTION_SIZE][MAX_SELECTION_SIZE][256];

    OddArea()
    {
        this(0, 0);
    }

    OddArea(final int xOffset, final int yOffset)
    {
        this.xOffset = xOffset;
        this.yOffset = yOffset;
    }

    void addBlock(final int x, final int y, final int z)
    {
        this.squares[x - this.xOffset][y - this.yOffset][z] = true;
    }

    boolean isInsideArea(final int x, final int y, final int z)
    {
        return this.squares[x - this.xOffset][y - this.yOffset][z];
    }
}

"

z不需要偏移量，因为Minecraft世界只有256个方块高。

我能想到的此设置唯一的问题是，在填充对象之前，您必须知道最低的x、y坐标。

"

- MrLore

---

寻找质数的算法（厄拉多塞筛法）如何应用于边界交叉问题？ - Jim Garrison

@JimGarrison 我指的是使用实际关心的值作为键来存储布尔数组的风格。 - MrLore

我非常喜欢这种存储所有包含块的方法，而不是计算碰撞。根据我的存储方式，编辑存储的块可能是一个繁重的操作。但是编辑体积很少，可能需要一两分钟，没有问题。这将处理移动到该步骤，使“碰撞检测”部分潜在地更快。我甚至可以以二进制可搜索的方式存储坐标，使计算真正快速。 - David

@MrLore 仅仅使用布尔数组并不能使某些东西与筛子有关。 - nobody

Answer 2

一般来说，您应该使用类似于kd树的数据结构。您可以将您的体积表示为立方体或球体的并集，并且很容易评估物体是否进入了该体积。

顺便说一下，要计算两个球体是否相交，请检查中心之间的距离是否小于半径之和。

- ElKamina