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

Question

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

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

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

像这样，我为游戏中的元素设置了很多不同的层级类型。

我的问题是:

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

1) 获取类型为Entity的对象

2) 获取VisibleEntity类型的对象

3) 获取SomeSpecificGameObject类型的对象

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

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

跟踪所有这些的最佳方式是什么？

感谢任何回复!

Answer 1

另一个简单的解决方案是为每种类型维护一个列表。将每个列表存储在 HashMap 中，以类型作为键。它几乎是即时的，而且每件元素只会花费你一个指针。它还可以将同一对象添加到多个列表中。这将处理您的层次结构。

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

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

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