Эффективное отображение позиций игровых объектов в 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 или меньше до рассматриваемой сущности.

Более сложный метод разделения заключается в динамическом разбиении пространствав дереве, гарантируя, что ни один раздел не может содержать больше, чем данное число объектов.Если раздел заполняется, вы делите его по пространственному среднему и создаете два двухпространственных раздела, каждый из которых содержит половину сущностей исходного раздела.Это делает вставки и поиски логарифмической средой выполнения, так как вы больше не можете обнаружить нужные разделы в постоянное время, но удаления становятся постоянными, учитывая заполненные разделенные разделы.

Answer 2

Если между Entity и Point существует взаимно-однозначное сопоставление, и вы хотите иметь возможность отображать в обоих направлениях, то двунаправленная диаграмма является наиболее естественной структурой данных.

Guava имеет реализацию BiMap<K,V>, которая поддерживает операцию просмотра BiMap<V,K> inverse(). Это всего лишь вид, поэтому он совсем не дорогой.

В качестве альтернативы вы можете управлять своими Map<Entity,Point> и Map<Point,Entity>, но это будет изобретением колеса.

Answer 3

неэффективно, так как я не знаю его точку в точке раньше времени
Правильно ли, этот объект сущности не содержит информации о позиции? Я бы предложил добавить его. Или, в противном случае, у вас может быть карта текущих позиций объекта Map<EntityIdType, Point> и выборочная позиция первой. Ничего особенного.