Проверка на столкновения, оптимизация процесса.

[Frost47rus]

При проверке каждого с каждым - займёт 9.900 проверок.

Положим, разобьём всю сцену на 10 секторов.
По 10 объектов в каждом.
Итого, каждый объект пройдёт в среднем по 9 проверок = 990 проверок. Вроде бы WIN и PROFIT.
Но, как быть с теми вариантами, когда объект находится сразу в 4 областях?
Ок. Берём квадрат(прямоугольник). углы - границы.
Добавляем к каждому проверку его границ к секторам. Ещё +4 проверки к каждому мувику.
итого порядка 1500 проверок.
вроде бы WIN и PROFIT.
но каким тогда образом прогонять сам факт столкновения между объектами? запара.

и если движение рандом - то получится, что будут возникать случаи, когда 1 сектор вместит в себя большое количество объектов, стремящееся к 100. И тогда разницы между обычным способом и навороченным с секторами - практически не будет. и вместо (если они будут) лагов постоянно - получим "рандомные" лаги. что для большиства ещё хуже чем перманентные.

мой вывод: вопрос сложный.

[Tetraeon]

Пробую проверить столкновение экземпляров 1го класса... никак не получается правильно обратиться к ним..

if ((Point.distance(enemyPoint,enemyPoint)<10) && (Point.distance(enemyPoint,enemyPoint)>1))
{
  trace('1');
}

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

[wvxvw]

Если хочется сложно и с наворотами... можно почитать про цепочки Маркова: http://ru.wikipedia.org/wiki/%D0%A6%...BE%D0%B2%D0%B0 с их помощью можно описать перемещение объектов, а так же использовать для поиска того, что в последнее время переместилось, соседей с которыми потенциально могли столкнуться объекты и т.п.

Есть еще такой вариант: построить структуру данных типа дерева, только с той разницей, что у узла может быть более одного родителя, и узлы знают про своих родителей. В таком случае для обычной сетки построенной из прямоугольников степень ветвления будет равной 4. Найти всех бизжайших соседей - за 1 * 4 + 2 * 4 операций. Соответственно, каждый узел хранит список объектов, которые в данный момент находятся в его координатах.
Отдельно от этой структуры хранить хеш-таблицу, в которой записывать в каких узлах произошли изменения. Таким образом вы минимизируете задачу проверок до сравнения только тех узлов в которых произошли изменения * 8.

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

Ну и соответственно, такое решение будет тем лучше работать, чем более однородные объекты. Объекты не должны быть больше ячеек сетки.

[Tetraeon]

Как думаете насчет такого варианта: создать поле вокруг MovieClip и объект внутри этого поля не касающийся его и при столкновении с краями другого поля будит засчитываться столкновение? Вопрос как сделать такое поле...

[ramshteks]

математически описываете и вперед =)

[Tetraeon]

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

[PlutDem]

Подскажите, пожалуйста, как реализовать такую вещь:
Есть танк, и его контур представлен несколькими накладывающимися прямоугольниками. В танк был выпущен с снаряд с очень большой скоростью. Нужно отследить попадание снаряда по контуру танка и просчитать отскок(рикошет) снаряда от контура. Подскажите в какую сторону копать?
Вот некоторые непонятные мне моменты:
1.Снаряд остановился внутри сразу двух чекбоксов. Мы понимаем, что столкновение произошло с гусеницей, а не с корпусом, но как это програмно отличить?
2. Между последним и текущим кадром снаряд прошил танк насквозь. Мы знаем, что столкновение было и было с гусеницей, но как это проверить?
3. Думаю рикошет будет легко вычислить если решить предыдущие проблемы, но для полноты картины оставлю.

[Hauts]

PlutDem, поищите на тему определения столкновения быстродвижущихся объектов.

http://animbook.mirmap.com/content/view/32/43/

Смотрите "Обнаружение столкновений с применением математики".

Как вариант — можно проверять столкновения несколько раз за одну итерацию. То есть если длина вектора движения в 5 раз больше размерности танка, при перемещении снаряда в новое положение в цикле двигайте снаряд на 1/5-ую его скорости и тут же проверяйте.

Как другой вариант — использовать две битмапдаты. Одна с отрисованым залитым контуром танка. Вторая с траекторией пули. Накладывая битмапдаты одну на другую с некоторым blendMode`ом (сейчас не скажу точно с каким) можно получить отличный от танка и траектории цвет на битмапдате, который как раз проявится в месте пересечения танка и траектории. Потом уже не составит труда получить Rectangle области пересечения (области определенного цвета) и, зная, с какой стороны выпущен снаряд, расчитать первую точку соприкосновения.

[kiloT]

На хабре была статья http://habrahabr.ru/post/135948/. Там есть несколько алгоритмов для решения вашей задачи. И еще несколько полезных статей для определения столкновений:
http://noregret.org/tutor/n/grid/
http://www.playchilla.com/as3-spatial-hash - готовое решение

[Den_root]

Я вот тут почитал про ТРО и никак не пойму как найти проекцию прямоугольника на ось. Подскажити, пожалуйста, как ее вычислить?