在Java(Swing)中,假设我有一个2D游戏,在屏幕上有各种类型的实体,例如玩家,坏人,通电等。玩家在屏幕上移动,为了高效地检查玩家附近的东西,我想我会希望根据他们的位置索引访问角色附近的东西。Java中游戏实体位置的高效映射
例如,如果玩家 'P' 走上元素 'E' 在下面的例子中...
| | | | | |
| | | |P| |
| | |E| | |
| | | | | |
...会做这样的事情:
if(player.getPosition().x == entity.getPosition().x &&
entity.getPosition.y == thing.getPosition().y)
{
//do something
}
而且这很好,但这意味着这些实体持有他们的立场,因此,如果我在屏幕上有很多实体,我将不得不遍历所有可能的实体,并根据玩家位置检查每个实体的位置。这看起来效率很低,特别是如果你开始获得大量的实体。
所以,我怀疑我会需要某种地图像
Map<Point, Entity> map = new HashMap<Point, Entity>();
还有存储我点的信息,这样我就可以在固定时间内访问这些实体。这种方法唯一的问题是,如果我想要将实体移动到屏幕上的不同点,我必须搜索HashMap的值,以查找要移动的实体(效率低,因为我不知道它的值点位置提前),然后一旦我发现它从HashMap中删除它,并重新插入它与新的位置信息。
对于我应该在这里使用什么类型的数据结构/存储格式的任何建议或建议,以便根据实体的位置以及基于实体的位置有效地访问实体?
感谢您的提示,我会研究更多的空间分区。 – 2010-06-12 06:30:38
我键入了两个游戏板实现,用于保存随机添加到1920x1080区域的1,000,000个实体。使用一个1080x1920的容器阵列,我有0.004毫秒插入,0.003毫秒的删除和0.004毫秒要求在3×3区域的所有容器的清单。使用动态二进制空间分区,对于与3x3区域相交的分区,我有0.007 ms的插入,0.003 ms的删除和0.007 ms的查询。对于非均匀分布的实体,BSP上的性能和内存使用情况应该更好。 – Gunslinger47 2010-06-12 21:22:16