Суббота, 2017-10-21, 0:41 AM
Приветствую Вас Гость | RSS

WVG-Development

[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Модератор форума: Wins_Vega 
Форум WVG » Креатив - Development » Программирование » Оптимищзация столкновений (Проверка столкновений с большим количеством объектов)
Оптимищзация столкновений
PolzovatelДата: Среда, 2013-10-30, 5:09 PM | Сообщение # 1
Лейтенант
Группа: Пользователь
Сообщений: 50
Репутация: 0
Статус: Offline
Доброго времени суток всем бойцам на фронте оптимизации! Хочу поделиться интересными фактами насчёт уменьшения "аппетита" почти любой игры, использующей проверку коллизий. Я собственно, не буду углубляться в какие-то заумные алгоритмы - суть идеи такова, чтобы как раз не заморачиваться всякой рутиной. Описываемый метод работает в моей игре и работает настолько хорошо, что хочется поделиться находкой.

Речь пойдёт о том, что делать с излишней "прожорливостью" проверок OnCollision и IsOverlaped. Сами по себе это весьма полезные универсальные функции. Но я недаром выделил ключевое слово - универсальность обходится большими затратами, в нашем случае это расточительное использование ресурсов.
Конечно, если Вы одновременно проверяете небольшое количество объектов на взаимные столкновения, можно и не заметить разницы (особенно на достаточно мощном компьютере). Но когда счёт объектов пойдёт за 50, могут возникать заметные просадки FPS (числа кадров в секунду).
Если говорить конкретно, я столкнулся с этой проблемой уже давно, делая игру по мотивам Team Fortress 2 (Valve). Ещё на прежнем форуме я создавал тему, где спрашивал как можно бороться с подобными вещами. Тогда мне посоветовали избавиться от проверки коллизий, однако мне не понравилось решение и пришлось выдумывать нечто другое. Об этом "нечто" я и расскажу.

Как должно быть известно, в играх с большим количеством перестрелок проверяется большое количество коллизий. Однажды, ради интереса, я захотел посмотреть, что будет, если в моей игре отключить Event sheet с обработкой пуль и снарядов (а это и есть основная масса проверок столкновений). Отключил и... стало очень грустно, т.к. у картинки появилась изумительная плавность, а FPS проседал от силы на 3-6 кадров (против обычного снижения на 25-45!) и уверенно держался вблизи отметки 60. То есть львиная доля всех вычислений приходилась на механику пуль и других снарядов, именно отсюда и следовало начать оптимизацию.

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

И тогда внешний вид моих NPC (смайлики по сути - кружочки) натолкнул на мысль: а почему бы не проверять коллизии более простым способом - тупо через дистанцию? Да, теряется ювелирная точность всех проверок, но даже когда NPC не напоминают шарик, вполне можно обойтись чисто проверкой расстояния между центрами!
Чтобы Вы окончательно убедились в эффективности такой замены, попробуйте скачать и проверить в деле небольшую тестовую программку (прилагается к сообщению). В ней создаётся 40000 летающих и один неподвижный объект, а затем выполняется проверка коллизий тем способом, который определяет нажатая кнопка. Столь дикое количество необходимо лишь потому, что программа ничего, кроме тестовых операций, не делает (в реальной игре будет иная картина). Если эффект незаметен, увеличьте либо уменьшите количество объектов на десятки тысяч, можно изменить частоту проверок. Дополнительно, есть exe-файл для непосредственного запуска теста, но в нём не показывается FPS.

Часть 1. Оптимизация коллизий движущихся объектов

Итак, основные кандидаты на проверку:

- стандартное OnCollision
- стандартное IsOverlaped
- очевидно, проверка шарообразных объектов будет осуществляться упрощённо, через Distance(x1,y1,x2,y2)
- попробуем исхитриться заменить distance на проверку суммы квадратов, т.е. (x2-x1)^2+(y2-y1)^2 сравнить с квадратом нужного числа; по идее, отказ от квадратного корня в формуле расстояния должен ещё больше ускорить проверку
- пробуем также PickByDistance
- и, наконец, пробуем PickClosest с последующей проверкой дистанции; по идее, мы отсеиваем _все_ объекты, кроме ближайшего, а затем его-то и проверяем на коллизию (хотя это довольно приблизительно)
- "до кучи" проверим также IsOnScreen...
- ...а также по интервалам (0..ширина окна) и (0..высота окна) координаты X и Y

Нюанс: расстояние определяется таким, чтобы пара объектов как минимум соприкасалась границами (это и есть коллизия). Т.е. вычисляются примерные радиусы т.н. bounding circle - окружностей, ограничивающих Ваших NPC, и складываются для каждой пары объектов. Например, если первый объект умещается в картинке 32х32 пикселя, а второй в 48х48 пикселей, то нужно брать R1=16 пикселей, а R2=24 пикселя. Если не верите - нарисуйте кружочки в этих границах и посчитайте сами Проверочное расстояние для этих двух объектов будет 16+24=40 пикселей (если центры ближе 41 пикселя - есть коллизия). Вместо OnCollision будет сравнение вида: Distance(x1,y1,x2,y2) less or equal 40. Разумеется, в тестовом файле взято другое число, т.к. размеры объектов другие.

Что ж, попробуйте попереключать для начала стандартные coollision и overlaped и понаблюдайте количество FPS, выводимое в заголовке. Видите, как плохо бывает при массовой проверке overlap?
А теперь переключите на Distance... понравилось? Вот и мне тоже очень и очень понравилось, поэтому я перешёл на использование этой великолепной функции. Пусть ускорение небольшое, но оно есть.
Интересен результат проверки суммы квадратов - я ожидал выигрыша, но оказалось, что этот способ хуже чем Distance. Видимо, больше т.н. макровычислений по сравнению с вызовом одной единственной функции. Так что сумма квадратов абсолютно "не прокатывает" (возможно, у кого-то выйдет иначе?).
Также сравните прямую выборку PickByDistance с PickClosest. Оказывается, они примерно одинаковы (я не заметил разницы "на глаз"). И можно не хитрить с выбором ближайшего объекта, учитывая, что ко второму случаю добавится ещё и Distance для полученного методом PickClosest объекта.
Наконец, проверим, заменимо ли условие IsOnScreen на две проверки координат (X и Y). Оказывается, заменять указанную функцию совершенно необязательно - никаких улучшений не замечено.

Подведём итоги
Если количество объектов, проверяемых на коллизии, становится велико, стоит пожертвовать точностью проверок ради быстродействия и отказаться от OnCollision и IsOverlaped. Лучше всего использовать сравнение двух величин: значения функции Distance(x1,y1,x2,y2) и сумму радиусов окружностей, которые примерно охватывают каждый из пары объектов. Если Ваши NPC больше напоминают невращающиеся квадратики или прямоугольники - пробуйте abs(x2-x1) и abs(y2-y1), т.е. проверять разности координат по модулю, сравнивая их с суммой половин соответствующих размеров этих объектов.
В крайнем случае, можно сделать упрощённую коллизионную модель NPC в виде набора шариков, каждый из которых проверять по Distance. Не гарантирую, что это выйдет быстрее стандартной проверки, но попробовать всегда можно.
Напомню: расстояние (проверочное число) берётся между центрами объектов.

Часть 2. Оптимизация коллизий с картой уровня

Если карта уровня рисуется из массива - напрашивается замена проверок коллизий со стенками на проверки по массиву этого уровня. Т.е. вместо OnCollision with Solid Вы пересчитываете координаты динамического объекта на строку и столбец массива карты, а затем смотрите, что находится в данной клетке массива.
Допустим, карта рисуется из элементов 20х20, координаты объекта - x1,y1. Тогда строка и столбец массива будут:
row = Int(y1 / 20) + 1
col = Int(x1 / 20) + 1
И сама проверка:
If map(col, row) > 255 Then ... // в данном случае solid-элементы карты начинаются с номера 256
Заметьте, что по скорости это сравнимо с той же Distance, но в проверке участвует всего 1(!) элемент массива, а не множество solid-объектов.
Примера программы нет, но Вы наверное и сами понимаете, что данный способ даёт выигрыш. Хотя ради справедливости замечу, что результат выходит ну очень приблизительный: коллизия возникает только в том случае, когда объект уже "сидит в стенке". Следовательно, у данного метода низкая точность, но вот скорость... Хотя можно сделать элементы "наружного слоя стенок", при попадании в которые засчитывается столкновение.

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

Произвольную карту можно условно разбить на сетку из квадратов и создать для неё solid-массив. Реализация идеи может быть такой: загружаем карту в слой и перемещаем по нему точку. Тестовая точка последовательно ставится в центр каждого условного квадрата, затем проверяется обычное OnCollision with Solid, и результат заносится в solid-массив.
Само собою, желательно сделать этот процесс не в основной игре, а отдельно, в промежуточной вспомогательной программе. В игре используется уже готовый solid-массив.

Заключение

Когда я в коде своей игры перелопатил все проверки коллизий, стало хоть и не идеально, но преимущественно 45-55 FPS с редким падением до 35 FPS (в особо крупных свалках). То есть снижение FPS составило 15-25 кадров (было 25-45).
Вы можете попробовать то же самое в Вашем проекте, если конечно наличествует желание. Выигрыш по скорости будет однозначно.

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

P.S. Конечно, у меня задействованы и другие хитрости, например, своя функция проверки видимости на основе массива карты. Но об этом как-нибудь в другой раз.

источник: http://c2community.ru/forum/viewtopic.php?f=27&t=865


Сообщение отредактировал Polzovatel - Среда, 2013-10-30, 5:09 PM
 
Форум WVG » Креатив - Development » Программирование » Оптимищзация столкновений (Проверка столкновений с большим количеством объектов)
Страница 1 из 11
Поиск: