针对此存储数据运行测试的最有效方法

Question

很抱歉，这个标题不太翔实，我想不出更好的了。当我说高效的时候，我的意思是代码不是cpu密集型的。

问题:想象一艘由积木组成的3D宇宙飞船，就像在《我的世界》中那样。我想把这个形状中每个块的位置存储在一个自制的Ship类中。

为此，我在Ship类中使用private List<ShipBlock> shipBlocks;。ShipBlock是一个自制的类，它以向量Vec3(int x, int y, int z)的形式保存一个位置，以及一些与这个问题无关的其他信息。

但是现在我想在船上做一个测试。船舶是否在特定testPosition (x, y, z)上包含ShipBlock，如果是，则返回此ShipBlock。然而，我没有找到一种有效的方法来做到这一点。循环遍历整个List并根据testposition测试每个位置是非常昂贵的，我希望它能快一些。

因此，我决定制作一个Map<Vec3, ShipBlock> shipBlocksMap来存储信息。关键是船块的位置。我可以简单地执行shipBlocksMap.get(testPosition)，它将返回正确的ShipBlock，如果船在那个位置有一个ShipBlock。如果不是，它将返回null。

这似乎正是我想要的，直到我移动了船，所有的船块都有了新的位置。我在这里学到了映射中的键不会因为你作为键的对象改变而改变。因此，如果我现在使用shipBlocksMap.get(testPosition)使用移动船中的位置，它将返回null，因为键仍然是旧的位置。(对不起，如果它让人困惑，我不知道如何更好地解释它)

问题:我在这里要问的问题是:假设一艘船可以容纳成千上万个船块，那么测试它是否在特定位置上包含一个船块的最有效方法是什么?我应该如何存放船上的船块，这样支票才能有效地进行?

代码:这里是Ship和ShipBlock类的代码。

public class ShipBlock 
{
    public Vec3 position;
    public String shipBlockType;
    public ShipBlock(Vec3 position, String shipBlockType)
    {
        this.position= position;
        this.shipBlockType = shipBlockType;
    }
}
public class Ship 
{
    private Map<Vec3, ShipBlock> shipBlocksMap;
    public Ship(Map<Vec3, ShipBlock> shipBlocksMap)
    {
        this.shipBlocksMap = shipBlocksMap;
    }
    public ShipBlock containsShipBlock(Vec3 position)
    {
        return shipBlocksMap.get(position);
    }
}

Answer 1

我认为最重要的设计变化是保存积木的位置相对于船的位置。

这样，当船移动时，你不需要改变方块的键，并且可以很容易地使用Map<Vec3, ShipBlock> shipBlocksMap进行恒定时间测试，其中键是相对位置。您可以通过计算(概念上的)relative_block_pos = absolute_block_pos - ship_pos来获得相对位置。

这意味着您需要存储船舶的位置。作为一种选择，您可以简单地选择船舶的第一个块作为船舶的位置，因此第一个块始终具有坐标(0, 0, 0)。

这样，更改所有块的坐标被减少到最小(但在大多数情况下应该不是必需的)。

Answer 2

空间分区树可能是您的最佳选择;参见空间分区树。你的模型宇宙的一半可能是空的，在许多这样的结构中，一个单一的测试将揭示这一点，并可以为未来的测试做出贡献，直到宇宙的一半以某种方式发生变化。维护结构是您的责任，但听起来对结构的更改比测试要多。另一种方法可能是用元球或Voronoi壳包围块或块簇，这样您就可以将每个测试卷减少为单个测试。