Система предотвращения столкновений

← →
Da Stranger © (2005-05-10 23:28) [0]

Задача такая. Есть много (10-700) объектов, которые двигаются в пространстве по определённым траекториям, которые возможно пересекаются. Нужно разработать систему, которая бы предотвращала столкновения между ними.
Кто-нибудь раньше делал такое на Delphi?

← →
cerber (2005-05-11 00:14) [1]

Дружище, эта задача из области линейного либо нелинейного програмирования в части поиска оптимума. Читай книги. У тебя очень частный случай, хотя...

← →
Da Stranger © (2005-05-11 04:59) [2]

А по-моему из области программирования Искусственного Интеллекта. Я уже видел пару проектов, которые решили эту задачу, но они на C ниписаны. Например, OpenSteer.

← →
boalse © (2005-05-11 05:44) [3]

> А по-моему из области программирования Искусственного Интеллекта.
>

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

← →
Кефир87 (2005-05-11 17:53) [4]

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

PCollisQube = ^CollisQube; CollisQube = record w,h,l:glfloat; end; ... TMyObject = class(???) ... colcub : CollisQube; ... end; .. collis : array[1..700] of PCollisQube;

ну а там... по моей идеи... Ничего лучше не остается кроме как...

for i := 0 to 700 do begin for j := 0 to 700 do begin if ... then ... end; end;Но это ужасно!

← →
Zer0[np] (2005-05-11 19:55) [5]

вот мой рецепт:
* создается односвязанный список, в него складываются все обьекты,
* для каждого обьекта формируется ключ ( какая_либо_координата_обьекта - радиус_описывающей_сферы)
* список сортируется при помощи merge_sort (брать тута : http://www.continuit.nl/index.php?LANGUAGE=EN&PAGE=DOCUMENTS_SORTING ) по ключу в порядке возрастания
* далее просиходит процедура проверки столконовений:
берется объект из списка и пока все следующие за ним объекты имеют имеют следущие параметры:
ключ_другого_обьекта - ключ_этого_обьекта< 2*радиус_описывающей_сферы_этого_обькета проверять их на взаимное столкновение (пересечение сфер, и возможно треугольников из которых состоят модельки), в противном случае забить и перейти к следующему объекту из списка.

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

в самом плохом случае (все проекции на ось столкнулись) сложность будет O(N^2), в самом хорошем (нет столкновений по проекциям на ось) - сложность O(N) - простой обход всего списка.

так же этот алгоритм крайне хорошо работает в RTS когда надо проверять видимость и срабатывание AI для юнитов - просто расширяем радиус описывающей сферы до зоны видимости/вероятного столкновения.

есть еще один вариант - привязывать объекты к стеке(разбиение по двум осям), и проверять только соседние ячейки.

boalse

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

Я пишу космическую стратегию реального времени. Исходя из этого все объекты - это либо астероиды, которые не могут изменить своё движение, либо космические корабли, которые обладают текущей скоростью, максимальной скоростью, ускорением, замедлением + определённым радиусом поворота и скоростью поворота.
Сейчас все объекты двигаются по точкам, а всякие ускорения-замедления просчитывает менеджер движения. Короче это долго объяснять, можете скачать пример "Movement Manager" с сайта www.spacefederation.netfirms.com в разделе "Downloads" и сам посмотреть. Там пользователь просто задаёт параметры движения и даёт команды, типа иди в эту точку, а дальше объект двигается сам.

> Как должны предотвращаться столкновения? Объект останавливается, и пропускает другой?

Самым естественным способом, примерно как двигаются пешеходы по улице.

> Или нужно при старте расчитать скорости всех объектов таким
> образом, чтобы не было столкновений?

А это возможно?? Надо учитывать тот факт, что в бою слишком часто надо будет менять траекторию полёта.

> Или нужно предугадать столкновение и замедлить скорость?

Ну да, замедлить скорость, или немного изменить направление, короче сделать всё, чтобы избежать столкновеня, но продолжать двигаться в прежнем направлении с минимальной потерей скорости.

Zer0[np]
Спасибо за твои комментарии, хотя я мало чего понял ;) У меня задача не определить столкновение, а предотвратить его. А насчет ячеек идея интересная - я так сейчас и делаю.

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

← →
Кефир87 (2005-05-12 18:41) [7]

Ах вот оно что... А я то думал речь идет о Collision Check...

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

Система предотвращения столкновений Найти похожие ветки