Алгоритм нахождения соседних объектов

[XimiKDeniS]

Сообщение от ramshteks

Возможно я просто неправильно вас понял или не вас, может просто что-то перепутал =)

Добавлено через 6 минут
Кстати есть небольшой хак, который поможет вам определять попадание юнита в область удара. Скорее всего вы будете дистанцию между эпицентром и самим юнитом, с помощью того же "пифагора" и сравнивать эту дистанцию с радиусом удара. Так вот вы можете сравнивать не реальные радиусы, а квадраты радиусов. Так вы сможете избежать вычисления квадратного корня при расчете гипотенузы(радиус вектора до юнита от эпицентра удара)

Хм.. интересно... Реально поможет несколько ускорить работу, спасибо.

Добавлено через 4 минуты
И кстати насчет рб дерева не очень понял. Хотелось-бы по-подробней...

[ramshteks]

Сообщение от XimiKDeniS

Хм.. интересно... Реально поможет несколько ускорить работу, спасибо.

Добавлено через 4 минуты
И кстати насчет рб дерева не очень понял. Хотелось-бы по-подробней...

насчет красно-черного(Red - black, рб) дерева, вообще говоря не стоит заморачиваться. Это своеобразное бинарное дерево, которое ускорит поиск. Но дело в том, что для вашего случая это будет скорее выпендреж чем действительно необходимость, потому что, накладные расходы на обслуживания рб-дерева съедят все, что вы выиграете при поиске с помощью него. Если бы все ваши юниты действительно оставались статичными или их перемещение было редкО, то рб-дерево было бы оправдано

[wvxvw]

Просто для того, чтобы описать смысл, не как руководство к действию:
При заполнении сцены объектами, каждому объекту присваивается значение синуса угла образуемого прямой проведенных через этот объект к углу сцены и одной из сторон сцены прилягающей к тому же углу.
Дерево строится по принципу: если угол меньше - левая ветка, если больше - правая. Когда вы выбрали объект, то вы сразу можете выделить его соседей (тех кто находится под более-менее одним углом) к этому объекту, и проверять только их на попадение в радиус (т.е. это не полностью решает задачу, просто исключает из нее какое-то количество объектов, которые заранее известны, как находящиеся далеко от выбранного.

Еще может быть такой вариант - каждый объект хранит упорядоченный список всех других объектов, при этом список упорядочен по удаленности от объекта. (Накладные расходы на память - линейные, т.е. можно сказать, незначительные). Это усложняет процесс добавления каждого объекта (т.как его нужно добавить в каждый список, и отсортировать). И, при движении объектов, прийдется сортировать каждый список. Но в ситуациях, когда объекты двигаются редко, такая схема может быть оправданой. В таком случае скорость нахождения всех соседей была бы логарифмической.

[XimiKDeniS]

Во-первых объекты будут двигаться практически постоянно. Насчет рб дерева понял, что вещь интересная, но не подходящая.Во-вторых, алгоритм с сортировкой практически бесполезен из-за того, что под воздействие может попасть 1 объект, а может 40 так что проверять все равно придется, причем порядок придется менять и просчитывать каждое движение, что только понизит скорость выполнения кода. Единственное чем он может помочь, так это в том, что когда находится объект который находится на максимальном или большем чем максимальном расстоянии, остальное может и не просчитываться, это как "пруф линк" на вышесказанное.

[-De-]

Если нужны расстояния между всеми, то или quad tree или сортировать х-овые и у-ковые координаты.

[wvxvw]

Вобщем, с другой стороны, это в худшем (наивном) случае - все равно линейная скорость, и просчет нужный для фильтрование простой, так что нет смысла извращатся с поисками ускорения - много тут все равно не наоптимизируешь.

[Stitch512]

http://habrahabr.ru/post/135948/

[wvxvw]

Ну только это не та же самая задача - тут нужно только для одного за один раз, а не для всех со всеми.
Кстати, для всех со всеми можно использовать еще более интересный алгоритм, например, функцию Кантора для сопоставления декартова произведения натуральным числам. Т.е. она сопоставляет 1 - (1,1), 2 - (1,2), 3 - (2,2) и т.д. И очень простая арфиметически. Взяв ее за основу можно быстро найти соседей если, например, хранить их в массиве где сдвиг в массив является пересчетом их смещения в системе координат.