在Java（秋千），说我有一个2D游戏，我有不同类型的实体在屏幕上，如播放器，坏人，通电等。当在屏幕上播放的动作，为了做的是在玩家附近高效的检查，我想我会想索引访问基于他们的立场是接近的角色的事情。

In Java (Swing), say I've got a 2D game where I have various types of entities on the screen, such as a player, bad guys, powerups, etc. When the player moves across the screen, in order to do efficient checking of what is in the immediate vicinity of the player, I would think I'd want indexed access to the things that are near the character based on their position.

例如，如果在下面的例子中播放器P走上元件E...

For example, if player 'P' steps onto element 'E' in the following example...

| | | | | |
| | | |P| |
| | |E| | |
| | | | | |

...会做这样的事情：

... would be to do something like:

if(player.getPosition().x == entity.getPosition().x && 
              entity.getPosition.y == thing.getPosition().y)
{
    //do something
}

和那优良，但意味着实体拥有自己的立场，并为此如果我有许多实体在屏幕上，我将不得不遍历提供一切可能的实体和检查对球员的位置每一个的人的位置。这似乎真的效率不高，特别是如果你开始得到吨的实体。

And thats fine, but that implies that the entities hold their positions, and therefor if I had MANY entities on the screen I would have to loop through all possible entities available and check each ones position against the player position. This seems really inefficient especially if you start getting tons of entities.

所以，我怀疑我会需要某种地图像

So, I would suspect I'd want some sort of map like

Map<Point, Entity> map = new HashMap<Point, Entity>();

和存储我点的信息有，这样我就可以访问这些实体在固定的时间。用这种方法唯一的问题是，如果我想要一个实体移动到屏幕上的不同之处，我不得不通过HashMap的，因为我想移动（低效实体的值来搜索，因为我不知道它的点位置提前的时间），然后一旦我发现它从HashMap中删除它，并用新的位置信息重新插入。

And store my point information there, so that I could access these entities in constant time. The only problem with that approach is that, if I want to move an entity to a different point on the screen, I'd have to search through the values of the HashMap for the entity I want to move (inefficient since I dont know its Point position ahead of time), and then once I've found it remove it from the HashMap, and re-insert it with the new position information.

任何建议或存储格式，我应该在这里使用，以什么样的数据结构/建议有高效率的访问基于自己的立场实体，以及定位的依据是实体？

Any suggestions or advice on what sort of data structure / storage format I ought to be using here in order to have efficient access to Entities based on their position, as well as Position's based on the Entity?

推荐答案

空间分割可能是有效的。

Space partitioning could be effective.

您既可以做固定的部门，如统一的网格，或者如果你只是那里是热点在你的地图里的东西被异常聚集的加权网格。对于每一个被占领的分区，创建它包含了所有实体的容器。

You can either do fixed divisions, such as a uniform grid, or a weighted grid if you except there to be hot spots on your map where things gets unusually clustered. For each occupied partition, create a container of all entities it contains.

插入为常量时间。去除的 N （实体的总次数）假设几乎无穷分数 N 的是非常大的，你已经有效地设置您的分区。接近looksups共享同一个运行时的清除。技术上仍然O（ N ）无论多小的比例，但。这将成为明显的，如果一个分区以往任何时候都变得异常拥挤。

Insertion is constant time. Removal is a practically infinitesimal fraction of n (your total number of entities) assuming n is very large and you've set up your partitions efficiently. Proximity looksups share the same runtime as removals. Still technically O(n) however small the fraction, though. This would become apparent if a partition ever become unusually crowded.

要获得之内的所有实体的列表的 X 的实体单位，必须首先得到由2 X 的宽阔的广场广场中心跨越所有的分区列表你的实体。如果您使用的是网格划分，这是相当琐碎。接下来，通过在这些分区中的所有实体，你循环，并返回每一个与距离的 X 的以下所讨论的实体。

To get a list of all entities within x units of an entity, you must first get a list of all partitions spanned by a 2x wide square square centered on your entity. If you use a grid partition, this is fairly trivial. Next, you loop through all entities in those partitions and return each one with a distance of x or less to the entity in question.

分区的一个更复杂的方法是在树动态分区空间，确保没有分区可以包含多个实体的给定数目。如果一个分区已满，你把它沿空间均值，并创建二两的空间分区，使每一个拥有一半的原始分区的实体。这使得插入和查找具有对数运行时间，因为你不再发现在固定时间内所需的分区，但清除成为固定的时间给出的上限分区的人口。

A more complicated method of partitioning is to dynamically partition space in a tree, ensuring that no partition can contain more than a given number of entities. If a partition becomes full, you divide it along the spacial mean and create two two space partitions such that each one holds half of the original partition's entities. This makes insertions and lookups have logarithmic runtime since you can no longer discover the desired partitions in constant time, but removals become constant time given the capped partition populations.