Получить из Java HashMap на основе 2-го расстояния

Question

Я делаю стратегическую игру для Android с большим количеством юнитов, и я подошел к точке, где мне нужно проверить положение каждого отдельного объекта относительно каждого другого, чтобы увидеть, достаточно ли близки эти два, чтобы они началиборьба.Прямо сейчас единственный способ, которым я могу определить, достаточно ли близки две единицы, заключается в этом методе:

public boolean inProximity(float x2, float y2) {
        return Math.sqrt((x2 - x) * (x2 - x) + (y2 - y) * (y2 - y)) <= proximityRadius;
    }

Я не хочу повторять все единицы n-квадрат раз.Я смотрел на TreeMap для хранения позиций, но как тогда (если это вообще возможно) получить ключи, основанные на расстоянии от единицы?

Answer 1

Возможно, вы захотите пересмотреть структуру данных здесь и взглянуть на квадри. По сути, они позволяют вам разделять 2D-пространство и обнаруживать столкновения, что, по-видимому, является вашим вариантом использования.

http://en.wikipedia.org/wiki/Quadtree

Просто сделать Google на Java Quadtree производит некоторые хиты реализации. Я не использовал ни одного из них, поэтому я не могу за них поручиться, но это должно дать вам кое-что для продолжения.

Answer 2

1) Прежде всего, вам не нужно брать квадратный корень.Квадрат и квадратный корень увеличиваются с ростом чисел, так что это будет одна оптимизация.

2) Это известно как проблема «ближайшей пары», и существуют алгоритмы на основе «разделяй и властвуй»решить ее.

Взгляните на: http://en.wikipedia.org/wiki/Closest_pair_of_points_problem