用于基于类型的查询的最佳数据结构是什么？

Question

我正在制作一个游戏，在这个过程中我遇到了一些问题。

我有许多不同类型的游戏元素。这些都是Entity类型。

实体有很多种类型，包括可见且需要在屏幕上绘制的实体。这些实体的类型为VisibleEntity，它扩展了Entity。

像这样，我对游戏中的元素有许多不同的层次类型。

我的问题是：

在发出以下类型的查询时，哪种数据结构具有最佳的运行时复杂性？

1) 获取 Entity 类型的对象

2) 获取 VisibleEntity 类型的对象

3) 获取 SomeSpecificGameObject 类型的对象

最简单的解决方案是将它们全部存储起来放在一个列表中，并遍历它们全部，如果它们是指定的类型，则将它们添加到要返回的列表中。

显然，对于屏幕中的某些元素每帧都进行计算是不可行的。

跟踪这一切的最佳方法是什么？

我很感激任何回应！

Answer 1

另一个简单的解决方案是为每种类型维护一个列表。将每个列表存储在哈希图中，以类型作为键。它几乎是您能得到的最快速度，并且每个项目只花费您一个指针。它还使得将同一对象添加到多个列表成为可能。这将处理你的层次结构。

如果要减少上述方法所需的空间，请让每个实体列表对象还存储指向其子类列表的指针。这样，VisibleEntity 将仅存在于 VisibleEntity 列表中，而不存在于其子类的列表中。要查找所有 VisibleEntities，您可以对主列表进行哈希查找，然后对子类的子类进行递归搜索。这是一个简单的树结构。

class MyEntityList {
    List<Entity> entityList = new ArrayList();
    List<MyEntityList> subclassLists = new ArrayList();
}

根据树的高度和对象的数量，第一种方法可能会更好。这是复杂性与时间与空间的权衡。

Answer 2

我真的不认为使用类层次结构来指示对象是否具有某个属性是最好的主意。

您可能希望将可以在游戏引擎中渲染的对象保留在 八叉树 中，当然它们需要有某种绘制方式；因此这可能是类型的一个很好的候选者（从接口是类型的意义上来说）。

至于其他任意属性，您可以通用地表示它们，然后维护索引以便快速检索，或者像您所说的那样，将它们保留在列表中并具有一个简单的过滤函数，可以返回匹配特定条件的对象子集。如果对象不是太多，那么第二种方法应该可以正常工作。 “太多”的阈值是您可能需要通过一些测试找出的值。

Answer 3

显然，对于屏幕中的某些元素每帧都进行计算是不可行的。

这实际上取决于对象的数量。现代 CPU 每秒循环数十亿次。假设检查并添加到列表需要 10 个周期，并且每秒执行 100 帧，则为每帧迭代 1000 个元素的列表将导致 cpu 利用率为 0.1%。所以相反，天真的解决方案是非常可行的，除非你有数千个游戏对象，或者需要每帧多次按类型查询。与往常一样，建议是实施可能有效的最简单的方法，衡量性能影响，并仅在影响显着时进行优化。

也就是说，下一个最简单的事情是：

abstract class Entity {
    private static Map<Class<?>, Set<? extends Entity>> byType = new HashMap<>();

    public static <E extends Entity> Set<E> allOfType(Class<E> clazz) {
        @SuppressWarnings("unchecked")
        Set<E> set = (Set<E>) byType.get(clazz);
        if (set == null) {
            set = new LinkedHashSet<E>();
            byType.put(clazz, set);
        }
        return set;
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    protected Entity() {
        for (Class c = getClass(); c != Object.class; c = c.getSuperclass()) {
            allOfType(c).add(this);
        }
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    protected void destroy() {
        for (Class c = getClass(); c != Object.class; c = c.getSuperclass()) {
            allOfType(c).remove(this);
        }
    }
}

您

for (VisibleEntity ve : Entity.allOfType(VisibleEntity.class)) {
    ve.render();
}

可以使用该方法来概括为按类以外的事物进行索引，只需为映射使用另一种键类型，并在适当的时间从类别集中插入和删除。