用于platformer游戏地图的java数据结构

Question

我正在用Java for Android编写一个2D platformer游戏

目前我有所有的游戏实体（除了阿凡达，存储在“实体”数组中）

Entity[][]

每当我需要检查一些东西时——比如我要在屏幕上画什么或者碰撞检测——我只需要抓取化身周围的小半径项目，然后使用继承和多态性系统做任何事情

问题是，这意味着我只能在特定的网格坐标中放置一个实体。这在很大程度上过去是可以接受的，但现在我有了移动的项目（比如敌人或移动块），当它们发生碰撞时，最终会相互删除，基本上它们会被覆盖

那么我应该使用什么样的数据结构呢？我在想

ArrayList<Entity>[][] 

但这将非常昂贵，而且会浪费内存，因为重复的项目是例外，而不是规则

我也在考虑将移动的项目分离到它们自己的ArrayList中，并在它们之间循环，但这是一个丑陋的解决方案

我能用什么呢？我想要一些速度很快，但不太占用内存的东西

Answer 1

正如您所注意到的，用于存储实体的二维数组会浪费内存（大多数块不会被占用），并且不允许重叠实体。由于实体很少，一个简单的ArrayList（不涉及可见数组）可能就足够了

如果你有很多实体，你可以考虑一个四叉树数据结构或一些其他的空间索引结构（检查http://en.wikipedia.org/wiki/Spatial_index）。

作为一种更简单、更“传统”的方法，如何保持实体的两层视图——所有活动（可见）实体的ArrayList，以及所有非活动（太远而无暇顾及）实体的ArrayList？如果性能很重要，可以对后者禁用碰撞检测，并对其执行少量或不执行AI/维护

Answer 2

那么您如何将实体保留为：

Entity[][]

假设你查找实体，比如：

Entity e = entities[i][j]

但是把你的敌人关在一个

Map<String,List<Entity>> map

其中，键是通过将i和j与随机中间字符串联而成的字符串（例如，如果i==1和j==15，则为“1.15”）。现在你可以快速查找实体，也可以快速查找敌人（尽管不如数组快），而不需要多余的空白空间