SFML и C++ Уроки \ Разработка игр › Форумы › SFML готовые решения (сниппеты) и советы › Оптимизация взаимодействия объектов списка
В этой теме 1 ответ, 2 участника, последнее обновление Heisenberg 8 года/лет, 6 мес. назад.
-
АвторСообщения
-
Всем привет.
К примеру, проект реализует популярный тип игр “трава – травоядные – хищники”. Столкнулся с тем, что >300 объектов на поле серьезно тормозят процессор i5 с 8 гигами оперативной памяти. Алгоритм взаимодействия элементов списка реализован предельно просто – все сравниваются со всеми. Далее будем рассматривать овец и размножать их, если они сыты и достигли нужного возраста.
Первое, что пришло в голову в процессе мозгового штурма с боссом, это полный отказ от проверки и замена её на симуляцию. К примеру, берутся две случайные овцы из списка, и если они годны, то рядом с одной из них делаем новую овцу. Прирост производительности тут просто зашкаливает Но мне такой вариант не понравился. Будем оптимизировать “честный” вариант.
1 этап. Делать проверку реже. Делаем float переменную LimitUpdateReproduction=0, и перед циклами проверки ставим LimitUpdateSex+=0.1; if(LimitUpdateSex>2). После проработки проверки зануляем переменную. В результате циклы проверки стартуют примерна раз в секунду, а тормоза от проверки пока еще очень серьезные, поэтому игра стала дёргаться. К тому же часть овец за это время проскакивала друг дружку. Не вариант, но оставим, уменьшив предел переменной до 1.
2 этап. Как проверка выглядела в самом начале:
C++123456//перебор всех овец для проверки столкновенияfor (it = entities.begin(); it != entities.end(); it++)for (it2 = entities.begin(); it2 != entities.end(); it2++){//проверка на голод и возраст, с последующим размножением}Блок-схема выглядит так:
Но зачем нам сравнивать второй с первым, третий со вторым и с первым, если мы уже сравнили первый и с вторым, и с третьим? Что бы избежать повторных сравнений, достаточно внести такую правку:
C++123456//перебор всех овец для проверки столкновенияfor (it = entities.begin(); it != entities.end(); it++)for (it2 = it; it2 != entities.end(); it2++) // теперь проверка идет с остатками списка, а не со всеми подряд{//проверка на голод и возраст, с последующим размножением}Блок-схема теперь такая:
3 этап. Получилось неплохо, но мало. Что еще можно сделать? Как я уже говорил, овцы перед размножением проверяются на голод и возраст. Сделаем эту проверку не внутри второго цикла, а перед ним. Тогда второй цикл вообще не стартует, если первая овца “не готова”.
C++1234567891011LimitUpdateSex+=0.1;if(LimitUpdateSex>2){for (it = entities.begin(); it != entities.end(); it++) //перебор всех овец для проверки столкновенияif((*it)->satiety>10 && (*it)->age>3) // если первая овца сыта и подходящего возрастаfor (it2 = it; it2 != entities.end(); it2++) //сверяем овцу с частью списка{//проверка на голод и возраст второй овцы, с последующим размножением}LimitUpdateSex=0;}Неожиданно, но это стало исключительно эффективно в начале игры. Чуть позже овцы наедятся и вызовы второго цикла станут чаще, но сейчас уже оптимизация работает так, что тормозов не заметно совершенно.
4 этап. ограничение видимости. Чаще всего нам не нужно видеть всех овец на карте, тогда делаем лимит на отрисовку только тех, что рядом с нами:
C++1234567//отрисовываем только тех существ, кто рядом с главным героемfor (it = entities.begin(); it != entities.end(); it++){if ((*it)->x < p.x+VisibleDist && (*it)->x > p.x-VisibleDist)if ((*it)->y < p.y+VisibleDist && (*it)->y > p.y-VisibleDist)window.draw((*it)->sprite); //рисуем entities объекты}int VisibleDist я поставил равным 320. Ок, тормозов нет даже на 1000:) А если овец намного больше?
5 этап. Свои варианты кончились, пришло время обратиться к гуглу. Вот один из вариантов, который можно применить здесь. Надо исключить запуск второго цикла проверки для тех овец, которые очень далеко. Значит, наряду с голодом и возрастом нам нужна ещё одна переменная, которая указывает на невозможность встречи конкретной овцы со своими подружками в течении какого-то количества итераций проверки на пересечение.
Вносим в класс существа еще одну переменную – флаг одиночества. Скажем, int FlagLoneliness=0. Первая итерация циклов проверки в том числе увеличивает значение флага до 10, если в пределах 20 клеток вокруг овцы никого из других овец нет. Зная скорость и зная, что две овцы, двигаясь с предельной скоростью друг к другу, за 10 итераций проверки не успеют друг до друга добежать, мы смело исключаем её из проверки, как мы уже делали с голодом и возрастом, но уменьшая флаг на 1 каждый раз. То есть получается, что все действия с овцой с флагом больше нуля сводятся к уменьшению её флага на 1.
Так же гугл рассказал много нового. Оказывается (Кэп?) это очень востребованная тема в разработке игр. Удачи, друзья!
Вложения:
You must be logged in to view attached files.Ещё можно применить “Разрезание циклов” и отправить их в отдельные потоки.
Насчёт (Кэп?) действительно, но всё-же полезно знать ) -
АвторСообщения
Для ответа в этой теме необходимо авторизоваться.