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

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

сколько объектов может быть максимально?
статичные ли они или движутся?

Если объектов много, а их положение дискретно (по клеткам), тогда м.б. завести массив-карту "поля", в элементы оного записывать "id" объектов. А потом производить мониторинг массива в необходимом радиусе клеток вокруг искомого объекта.

Максимальное число не оговаривалось, но думаю в пределах тысячи и да, они движутся.
alexxus, спасибо, вариант понравился, но движение персонажей происходит по 5 пикселей, к карта может быть ну очень большая, гдет до 10 тысяч и хранить 2000 координат не улыбается. Хотя все равно спасибо, приму на заметку.

Любопытная задача. Это какая-то модель броуновского движения получается.
Каковы размеры объектов?

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

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

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

Это хороший способ если ваши юниты равномерно распределены по экрану. И при делении этого экрана скажем на 9 частей, в каждой из которых будет где то по X = 2000/9 юнитов, то в худшем случае, вам придется просчитать 4*X юнитов, что гораздо лучше чем все 2000. Нельзя забывать про накладные расходы связанные с определением привязки юнита к конкретному под-полю. Так же такое решение имеет нюанс: размер подполя. Его нужно подбирать экспериментально и исходя из вашей задачи(вам все таки лучше знать). Слишком большие под-поля, просто не дадут прироста в скорости, маленькие увеличат накладные расходы на переопределение причастности юнита к под-полю.

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

И уж если по хорошему, то подобная вещь должна решаться все таки на сервере.

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

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

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

Если объектов много, а двигаются они не часто - можно использовать рб-дерево, где за единицу измерения принять угол (синус угла, например) от верхнего правого края сцены до центра объекта. Таким образом можно будет легко выделить те объекты, которые потенциально находятся в нужном диапазоне.
Возможно даже два дерева было бы лучше (из двух углов сцены) - в таком случае искомые предметы были бы на пересечении множеств веток дерева.
Опять же, такая сложность может быть неоправданной, когда объектов мало, (до 1000 я бы не заморачивался, ну только если ради того, чтобы заморочиться :)).

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

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

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

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

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

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

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

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

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

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