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

[XimiKDeniS]

Здравствуйте.
Суть вопроса. Есть несколько объектов на сцене, каждый объект имеет имя. Надо узнать наиболее быстрым способом имена объектов которые находятся в определенном радиусе от определенной точки.

for (I=0; I<n; I++)
{
trace(getChildByName(I).x)
}

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

[Jewelz]

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

[alexxus]

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

[XimiKDeniS]

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

[alexxus]

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

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

[XimiKDeniS]

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

[ramshteks]

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

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

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

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

[XimiKDeniS]

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

[ramshteks]

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

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

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

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

[wvxvw]

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

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