|
|
|
|
Канал Игры Мечты: «collision detection: проблемы быстродействия.» |
|
|
|
forbidden
 425 EGP
  
Репутация: 93
Сообщения: 895
Откуда: Москва
Зарегистрирован: 26.12.2004
  |
|
Сразу прошу прощения, если в данном канале проглядел большой топик на данную тему. Находил только касаемо DeepSpace Saga, но там информации по нужной проблеме нет.
Итак, пусть у нас имеется:
Веб-ориентированная наработка игрушки на mysql+php, внутренний мир которой в зачатке составляет сферическую систему диаметром 1000км. По системе разбросаны объекты: статические и перемещающиеся. Движение может быть линейным и равноускоренным. Перепросчет положений осуществляется каждые 5 секунд.
Задача:
Ввести систему просчета (определения) столкновений. При худшем исходе - используя в качестве габаритных контейнеров сферы, в лучшем - базовые стандартные примитивы (boxes, cylinders etc).
Немного покопавшись по просторам Интеренета, нашел дипломную работу некоего товарища Симонова Станислава Вадимовича. Прочитав треть работы, пришел к выводу, что большинство алгоритмов рассчитано.. как бы это сказать.. на очень частую интерполяцию по времени. В данном же случае временной интервал - 5 секунд. За это время хорошо разогнанный корабль может пролететь станцию насквозь.
Возвращаясь к дипломке. Очень понравился алгоритм Лина-Кэнни. Пересказывая дипломку, алгоритм заключается в просчете для каждой пары объектов времени до столкновения, создании массива и сортировки его по по возрастанию. Далее в описываемом случае выбиралось бы то столкновение(-ия), которое произойдет через < 5 секунд.
Но встает стеной проблема быстродействия. Если система будет не одна, в каждой системе будет минимум сто объектов и для каждой пары придется считать время до столкновения, несчастный php начнет быстро загибаться. Для ускорения процесса не вижу другого способа, кроме написания бинарника на том же C++, который будет заниматься этой отдельной проблемой.
Интересует опыт людей, которые занимались этой темой. Если для них это не стратегическая информация и коммерческая тайна, естественно 
_________________
как каштан под палой листвой.. |
|
|
|
Crimson
560 EGP
 
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
Ыыыы... во-первых какого рода объектов-то? Каких габаритов по отношению к скоростям? Почему нельзя считать что если скорость корабля больше или равна расстоянию до станции то корабль с ней просто стыкуется (а если не хочет, то выполняет маневр уклонения и они мирно расходится по своим делам)? Насколько часто объекты меняют скорость, и каким образом? Зачем вообще реализовывать физику в веб-ориентированной игрушке на пхп - тебе же на этом самом пхп придется всем кораблям автопилоты писать и просчитывать?
По поводу столкновений - просчитывать каждую пару объектов нужно только при запуске сервера. Потом пересчитываются только те объекты, которые в конкретный момент маневрируют. Иначе у тебя и бинарник захлебнется. Если объектов очень дохрена и все любят поманеврировать - можно разделить пространство на кубики и просчитывать пары только внутри того же кубика. Но вообще хаотические системы действительно не очень бодро просчитываются на любом движке, и без особой необходимости их лучше не вводить в принципе.
|
|
|
|
forbidden
425 EGP
Репутация: 93
Сообщения: 895
Откуда: Москва
Зарегистрирован: 26.12.2004
|
|
| Crimson : |
|
Почему нельзя считать что если скорость корабля больше или равна расстоянию до станции то корабль с ней просто стыкуется?
|
Помимо крупного объекта-станции может быть таких же размеров и астероид. А стыковка со станцией планировалась как подлет на некоторое расстояние от габаритной сферы, которая по совместительству - силовое поле.
Да, про габариты и скорости. Допустим, корабль радиусом метров 25-30, летящий на скорости около 2-3км/5сек. Но это разве что на пике своего разгона
| Crimson : |
|
Зачем вообще реализовывать физику в веб-ориентированной игрушке на пхп?
|
Да, замахнулся, есть немного Но надо же с чего-то начинать. Конечно, лучше бы написать сначала бильярд, там попроще будет. Но... В конце-концов ежели вся физика окажется лишней, можно запросто остановиться на линейных перемещениях в пространстве и эфемерных объектах. Но это же не так интересно, имхо!
| Crimson : |
|
придется всем кораблям автопилоты писать и просчитывать?
|
Каждое действие есть по сути автопилот, который используется и игроком, и НПС. Есть стандартная функция: "двигаться объектом n в точку k". Как написал выше, можно и оставить линейное перемещение с постоянной скоростью. Можно ввести равноускоренное движение. Можно приписать инерцию. Да, всё это будет крайне сложно, и вряд ли отчисленный студент-гуманитарник [оч. приятно  ] это с ходу напишет. Особенно распознавание столкновения и манёвры уклонения.
| Crimson : |
|
пересчитываются только те объекты, которые в конкретный момент маневрируют
|
Про это я не подумал. Плюс сделать НПС поведение такое, чтоб без дела не летали. Уже экономия.
| Crimson : |
|
хаотические системы действительно не очень бодро просчитываются
|
То есть надо по возможности вводить как можно больше ограничений, чтобы уменьшать необходимость просчетов всех возможных взаимодействий? Бороться с энтропией, так сказать?
_________________
как каштан под палой листвой.. |
|
|
|
Pegasus
1039 EGP
  
Репутация: 335
Сообщения: 7085
Откуда: НН
Зарегистрирован: 09.12.2002
|
|
| Crimson : |
|
Потом пересчитываются только те объекты, которые в конкретный момент маневрируют.
|
| forbidden : |
|
Есть стандартная функция: "двигаться объектом n в точку k".
|
Судя по тому, что ты написал, даже пересчета не нужно, все вычисляется в момент отдачи команды автопилоту.
_________________
There shall be wings! |
|
|
|
forbidden
425 EGP
Репутация: 93
Сообщения: 895
Откуда: Москва
Зарегистрирован: 26.12.2004
|
|
Ну так ничто не запрещает пилоту сначала отдать одному кораблю команду двигаться туда-то, а по истечению одной временной итерации другой пилот \ НПС \ Божественное Провидение придаст движение другому объекту, который в скором времени ляжет на курс исходному объекту Конечно, можно сделать так, что второе действие будет аннулироваться т.к приведет к столкновению. Но почему бы им двум не разлететься, скажем, за 20 секунд до возможного столкновения? Феерично будет. А в случае с астероидом последний вряд ли будет считаться с кораблем
Естественно, возможность ухода с исходной траектории будет реализовываться внутри этой стандартной функции движения. Хотя, с другой стороны, можно по итогам алгоритма Лина-Кэнни потенциальным столкнувшимся сигнал на маневр отсылать.
Вобщем сводится всё к двум задачам:
- Определение времени до столкновения;
- Обучение "автопилота" огибанию цели
Соответственно надо бы сначала проработать оба пункта в случае постоянной скорости (и возможности мгновенно сменить курс, т.е без инерции). И ежели все получится более-менее гладко, то можно рискнуть и попробовать переписать всё это с учетом инерции и невозможности резкой смены курса.
_________________
как каштан под палой листвой.. |
|
|
|
Pegasus
1039 EGP
Репутация: 335
Сообщения: 7085
Откуда: НН
Зарегистрирован: 09.12.2002
|
|
| forbidden : |
|
а по истечению одной временной итерации другой пилот \ НПС \ Божественное Провидение придаст движение другому объекту, который в скором времени ляжет на курс исходному объекту
|
Это сути дела не меняет. В момент "придания движения" ты сразу можешь вычислить те объекты, с которыми возможно столкновение, и время до столкновения.
_________________
There shall be wings! |
|
|
|
forbidden
425 EGP
Репутация: 93
Сообщения: 895
Откуда: Москва
Зарегистрирован: 26.12.2004
|
|
Если под моментом "придания движения" подразумевается обработка команды движения, которая каждый шаг происходит - то да Ежели имеется ввиду именно момент инициализации движения (прописка команды двигаться), то тогда не совсем понял.
_________________
как каштан под палой листвой.. |
|
|
|
Pegasus
1039 EGP
Репутация: 335
Сообщения: 7085
Откуда: НН
Зарегистрирован: 09.12.2002
|
|
Движется один объект, далее появляется второй. Ты сразу можешь определить: столкнутся они или нет, и время до столкновения. Просчитывать все промежуточные состояния не нужно.
_________________
There shall be wings! |
|
|
|
Krom
455 EGP
 
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
В каждый тик времени корабль может задеть объекты, которые попадают в цилиндр элементарного движения. Радиус цилиндра зависит от размеров и скорости объекта (той её составляющей, которая перпендикулярна оси движения нашего корабля), а также размеров корабля. На вычисление всех таких цилиндров, которых у нас sqr(число_объектов), даётся меньше пяти секунд
Я бы решал так - забил на конечный цилиндр и взял бы бесконечный, решив вопрос на много тиков вперёд. Из списка на обработку перво-наперво исключил бы все неподвижные в данный момент объекты (как дефолтно-неподвижные, так и просто тормознувшиеся). Для каждого объекта хранил бы вектор движения, тогда определение возможности столкновения не должно составить трудностей (чтение двенадцати значений из памяти, три вычисления длин векторов и три детерминанта матриц 3х3 (для определения перпендикулярной составляющей скорости объекта, расстояния от курса корабля до объекта и расстояния от корабля до точки предполагаемой коллизии) - самые трудоёмкие операции  ), надо только написать соответствующую библиотечку на компилируемом языке, лучше всего ассемблере. Также использовал бы префильтр по расстоянию между объектами, основанный на константе - максимальном значении игровых скоростей. Префильтр после момента вычисления расстояния между объектами, который поставил бы вперёд всего.
P.S> Правда, тут ни слова про алгоритм ухода от столкновений. Алгоритм ухода для парных и высшей кратности столкновений - вопрос отдельный и на порядок сложнее. Если правильно его оформить, то можно упростить жизнь алгоритму определения столкновений. Например, если при подозрении на грядущую коллизию менять маршрут корабля с бОльшим порядковым номером так, чтобы даже предполагаемая коллизия устранялась, то анализ траекторий потребуется реже, чем раз в тик, а именно - только при появлении новых движущихся объектов.
P.P.S> Всё сказанное - имха, которая мной ни разу в таком виде не программировалась
_________________
Не спешите меня. |
|
|
|
forbidden
425 EGP
Репутация: 93
Сообщения: 895
Откуда: Москва
Зарегистрирован: 26.12.2004
|
|
Серьезная выкладка, премного благодарен На динамической модельке данный алгоритм ("три детерминанта") расписываю. По крайней мере пытаюсь, гы-гы.
_________________
как каштан под палой листвой.. |
|
|
|
Pavlon
80 EGP
Репутация: 15
Сообщения: 107
Откуда: Киев
Зарегистрирован: 18.06.2006
|
|
А можно.. можно я скажу??
Я, конечно, проблемой столкновений серьёзно не занимался (только бильярд однажды сделал... да и тот глючный...). Но! Могу внести одно маленькое предложение (идею из какой-то умной книги спёр):
1. Все фигуры окружай оболочкой - это фигура, в которую объект полностью помещается и для которой расчёт столкновений чрезвычайно прост (например шар или такой кубик, всегда паралельный осям координат). Вот, ну и нормальный расчёт столкновений производить только тогда, когда произошло столкновение оболочек. В нагруженной сцене должно дать прирост производительности.
2. Предложенный выше алгоритм разбиения пространства на части. Всё тоже только части должны пересекаться друг с другом, чтоб не вышло так, что два кораблика летят в лоб друг другу из 2-х разный частей и НЕ сталкиваютсмя. Только есть одно но, если у тебя ньютоновская физика и максимальной скорости нет, то алгоритм может упустить столкновение. Поэтому размер этих частей надо делать зависимыми от максимальной скорости объектов... т.е. размер "кубиков пространства" будет _динамически_ зависить от максимальной скорости... короче это довольно сложно.
Если интересно, я мог бы попытаться придумать какой-то алгоритм построения такой динамеческой решётки, но не уверен, что из-за всех этих вычислений оно себя оправдает, это скорее имеет смысл не при 100 оъектов, а где-то около 1000...
|
|
|
|
Pavlon
80 EGP
Репутация: 15
Сообщения: 107
Откуда: Киев
Зарегистрирован: 18.06.2006
|
|
Гхм.. В догонку.
Во избежание, так сказать.
Насчёт пункта 2. Ежели делать как предложил Кром + Пегасус (а так делать и нужно, имхо), то этот самый пункт 2 теряет смысл и вообще, нафиг, никому не нужен
Вот.
|
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
 |
|
Тут было про коллизии в web-based играх...
| Pavlon : |
|
1. Все фигуры окружай оболочкой - это фигура, в которую объект полностью помещается и для которой расчёт столкновений чрезвычайно прост (например шар или такой кубик, всегда паралельный осям координат)...
|
Bounding volume - наш выбор, правильно.
2 метод странный.. вообще то это как бы quadtree.. но он не определяет столкновения - он их оптимизирует.
| Pavlon : |
|
то алгоритм может упустить столкновение
|
и первый и второй(хотя это не метод определения коллизий) не справятся с этой проблемой.. нужно использовать некоторые "хитрости".. почитай документацию по любым физ. движкам
_________________
MOV topka, C++ |
|
|
|
|
|
|
|
|
Канал Игры Мечты: «collision detection: проблемы быстродействия.» |
|
|
