Оптимизация взаимодействия объектов списка

[OlegУчастник Сообщений:11 Зарегистрирован:09.08.2015 Репутация:4]

Всем привет.

К примеру, проект реализует популярный тип игр “трава – травоядные – хищники”.  Столкнулся с тем, что >300 объектов на поле серьезно тормозят процессор i5 с 8 гигами оперативной памяти.  Алгоритм взаимодействия элементов списка реализован предельно просто – все сравниваются со всеми. Далее будем рассматривать овец и размножать их, если они сыты и достигли нужного возраста.

Первое, что пришло в голову в процессе мозгового штурма с боссом, это полный отказ от проверки и замена её на симуляцию. К примеру, берутся две случайные овцы из списка, и если они годны, то рядом с одной из них делаем новую овцу. Прирост производительности тут просто зашкаливает Но мне такой вариант не понравился. Будем оптимизировать “честный” вариант.

1 этап. Делать проверку реже. Делаем float переменную LimitUpdateReproduction=0, и перед циклами проверки ставим LimitUpdateSex+=0.1; if(LimitUpdateSex>2). После проработки проверки зануляем переменную. В результате циклы проверки стартуют примерна раз в секунду, а тормоза от проверки пока еще очень серьезные, поэтому игра стала дёргаться. К тому же часть овец за это время проскакивала друг дружку. Не вариант, но оставим, уменьшив предел переменной до 1.

2 этап. Как проверка выглядела в самом начале:

C++

//перебор всех овец для проверки столкновения for (it = entities.begin(); it != entities.end(); it++) for (it2 = entities.begin(); it2 != entities.end(); it2++) { //проверка на голод и возраст, с последующим размножением }

1 2 3 4 5 6

//перебор всех овец для проверки столкновения for (it = entities.begin(); it != entities.end(); it++) for (it2 = entities.begin(); it2 != entities.end(); it2++) { //проверка на голод и возраст, с последующим размножением }

Блок-схема выглядит так:

Но зачем нам сравнивать второй с первым, третий со вторым и с первым, если мы уже сравнили первый и с вторым, и с третьим? Что бы избежать повторных сравнений, достаточно внести такую правку:

C++

//перебор всех овец для проверки столкновения for (it = entities.begin(); it != entities.end(); it++) for (it2 = it; it2 != entities.end(); it2++) // теперь проверка идет с остатками списка, а не со всеми подряд { //проверка на голод и возраст, с последующим размножением }

1 2 3 4 5 6

//перебор всех овец для проверки столкновения for (it = entities.begin(); it != entities.end(); it++) for (it2 = it; it2 != entities.end(); it2++) // теперь проверка идет с остатками списка, а не со всеми подряд { //проверка на голод и возраст, с последующим размножением }

Блок-схема теперь такая:

3 этап. Получилось неплохо, но мало. Что еще можно сделать? Как я уже говорил, овцы перед размножением проверяются на голод и возраст. Сделаем эту проверку не внутри второго цикла, а перед ним. Тогда второй цикл вообще не стартует, если первая овца “не готова”.

C++

LimitUpdateSex+=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; }

1 2 3 4 5 6 7 8 9 10 11

LimitUpdateSex+=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++

//отрисовываем только тех существ, кто рядом с главным героем 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 объекты }

1 2 3 4 5 6 7

//отрисовываем только тех существ, кто рядом с главным героем 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.

[HeisenbergУчастник Сообщений:320 Зарегистрирован:01.04.2015 Репутация:146]

Ещё можно применить “Разрезание циклов” и отправить их в отдельные потоки.
Насчёт (Кэп?) действительно, но всё-же полезно знать )

[Автор]

Сообщения