java - 3D 体积的数据结构和算法？

我一直在修补一些 Minecraft Bukkit 插件开发，并且目前正在研究一些我需要能够定义空间“体积”并确定实体(玩家)何时从该体积外部移动到内部(或副反之)。

如果我将“音量”限制为盒子，那应该很简单。数据结构可以只维护 X/Y/Z 边界整数(所以总共 6 个整数)，并且计算给定两个点(移动自和移动到)的进入/退出应该只是确定是否 A)所有三个 To 值都是在所有三个范围内，并且 B) 至少有一个 From 值在其相应范围之外。

(尽管如果有更好、更高效的存储和计算方式，我会全力以赴。)

但是，如果“音量”不是一个简单的盒子呢？假设我有一个形状奇特的房间并且想要封闭那个房间的体积。我可以单独安排多个“卷”来填充整个空间，但是当实体从一个移动到另一个时会导致误报。

之前没有在游戏或 3D 引擎方面工作过，我对如何构建这样的东西感到茫然。但我突然想到，这很可能是一个已经解决并且已知模式的问题。本质上，我试图:

定义一个数据结构，它可以表示一个形状奇特的空间体积(尽管至少基于块坐标)。

定义一个算法，在给定运动源和目的地的情况下，可以确定运动是否跨越了定义空间的边界。

是否有既定的模式和实践？

最佳答案

我不知道这之前是否在任何类型的视频游戏中使用过，但首先想到的是经典的 Sieve of Eratosthenes implementation ，唯一的变化是使 boolean 数组为 3D，并使用键作为坐标。显然，尽管 x 和 y 值在 Minecraft 中可能很大，但您可能希望通过保存世界 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 坐标

关于java - 3D 体积的数据结构和算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24293821/