Java中游戏实体位置的有效映射

Question

在Java(Swing)中,假设我有一个2D游戏,我在屏幕上有各种类型的实体,例如玩家,坏人,通电等.当玩家在屏幕上移动时,为了做到高效检查玩家附近的内容,我认为我希望根据他们的位置索引访问角色附近的东西.

例如,如果玩家'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中删除它,然后用新的位置信息重新插入它.

有关我应该使用何种数据结构/存储格式的建议或建议,以便根据实体的位置有效访问实体,以及基于实体的职位？

Answer 1

空间划分可能是有效的。

您可以进行固定划分，例如统一网格，也可以使用加权网格（如果地图上存在热点，其中事物异常聚集）。对于每个占用的分区，创建它包含的所有实体的容器。

插入时间恒定。假设n非常大并且您已经有效地设置了分区，则删除实际上是n（实体总数）的无限小部分。邻近查找与删除共享相同的运行时间。不管分数有多小，从技术上讲仍然是 O( n ) 。如果分区变得异常拥挤，这一点就会变得明显。

要获取实体x单位内的所有实体的列表，您必须首先获取以实体为中心的 2 x宽正方形所跨越的所有分区的列表。如果您使用网格分区，这相当简单。接下来，循环遍历这些分区中的所有实体，并返回与相关实体距离为x或更小的每个实体。

一种更复杂的分区方法是动态分区树中的空间，确保任何分区都不能包含超过给定数量的实体。如果某个分区已满，则沿空间均值将其划分并创建两个两个空间分区，以便每个分区都包含原始分区实体的一半。这使得插入和查找具有对数运行时间，因为您无法再在恒定时间内发现所需的分区，但在给定上限分区数量的情况下，删除将成为恒定时间。