从 3D 图形中获取对象的最有效方法

Question

所以，我正在制作游戏，但遇到了问题。我需要一些方法来有效地获取位于 3d 图形中的对象。

但是，问题是它们都可以覆盖多个值来获取。因此，例如，值 'foo' 可能涵盖 x 范围 400-500、y 范围 10-20 和 z 范围 30-60。

我想知道是否有更有效的方法来存储和获取这些值，然后将它们存储在数组中并搜索它们，我不想这样做，因为这些值很多。

这是为游戏选择生物群落。但是，我选择将其放在此处而不是 GameDev，因为这似乎更像是一个数据结构问题。然而，我可能是错的，如果我是错的，我会很乐意关闭它并在那里打开一个。

还有其他方法吗？

public static Tile getTile(int height, int moisture, int temperature) {
    for(Tile tile : tileList){

        boolean isTile = true;

        if(!(tile.heightMax > height && tile.heightMin < height)){
            isTile = false;
        }

        if(!(tile.temperatureMax > temperature && tile.temperatureMin < temperature)){
            isTile = false;
        }

        if(!(tile.moistureMax > moisture && tile.moistureMin < moisture)){
            isTile = false;
        }

        if(isTile){
            return tile;
        }
    }
}

这是我的搜索方法。如您所见，我正在使用一个列表来存储所有图块，并搜索符合条件的图块。有没有其他方法可以尽可能快地处理许多图块？

Answer 1

我过去解决这个问题的方法是定义代表 3D 区域的区域 space，然后将地图存储到对象 space 重叠的所有区域的每个对象.然后，当您想在某个位置查找对象时，您首先使用地图查找与该位置区域重叠的所有对象，然后遍历它们以查找该位置的对象。

让我给你一个代码视图。要构建区域地图：

Map<Region, List<Item>> regionMap = new TreeMap<>();

添加项目时：

item.getOverlappingRegions().forEach(region -> {
    if (!regionMap.containsKey(region))
        regionMap.put(region, new ArrayList<>());
    regionMap.get(region).add(item)
});

然后当您在某个位置搜索项目时：

if (regionMap.containsKey(location.getRegion()) {
    regionMap.get(location.getRegion()).stream()
        .filter(item -> item.contains(location))
        ....
}

这肯定有开销，但如果您的区域足够小，搜索速度非常快。

这是为 3D space 设计的，但它可以根据需要扩展到任意多的维度：它全部在 Region 和 Location 类.

Answer 2

我不完全确定我已经理解你的问题是什么，但它看起来与 3D 中的碰撞检测算法非常相似 space。如果是这种情况，八叉树可能就是您要找的：http://www.codeproject.com/Articles/108761/Octrees

从 3D 图形中获取对象的最有效方法

Most efficient way to get an object from a 3D Graph

java

data-structures