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

SFML и C++ Уроки \ Разработка игр Форумы SFML готовые решения (сниппеты) и советы Оптимизация взаимодействия объектов списка

В этой теме 1 ответ, 2 участника, последнее обновление Heisenberg Heisenberg 5 года/лет, 4 мес. назад.

Просмотр 2 сообщений - с 1 по 2 (из 2 всего)
  • Автор
    Сообщения
  • #1666
    +3

    Oleg
    Участник
    Сообщений:11

    Зарегистрирован:
    09.08.2015

    Репутация:4

    Всем привет.

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

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

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

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

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

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

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

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

    Неожиданно, но это стало исключительно эффективно в начале игры. Чуть позже овцы наедятся и вызовы второго цикла станут чаще, но сейчас уже оптимизация работает так, что тормозов не заметно совершенно.

    4 этап. ограничение видимости. Чаще всего нам не нужно видеть всех овец на карте, тогда делаем лимит на отрисовку только тех, что рядом с нами:

    int VisibleDist я поставил равным 320. Ок, тормозов нет даже на 1000:) А если овец намного больше?

    5 этап. Свои варианты кончились, пришло время обратиться к гуглу. Вот один из вариантов, который можно применить здесь. Надо исключить запуск второго цикла проверки для тех овец, которые очень далеко. Значит, наряду с голодом и возрастом нам нужна ещё одна переменная, которая указывает на невозможность встречи конкретной овцы со своими подружками в течении какого-то количества итераций проверки на пересечение.

    Вносим в класс существа еще одну переменную – флаг одиночества. Скажем, int FlagLoneliness=0. Первая итерация циклов проверки  в том числе увеличивает значение флага до 10, если в пределах 20 клеток вокруг овцы никого из других овец нет. Зная скорость и зная, что две овцы, двигаясь с предельной скоростью друг к другу, за 10 итераций проверки не успеют друг до друга добежать, мы смело исключаем её из проверки, как мы уже делали с голодом и возрастом, но уменьшая флаг на 1 каждый раз. То есть получается, что все действия с овцой с флагом больше нуля сводятся к уменьшению её флага на 1.

     

    Так же гугл рассказал много нового. Оказывается (Кэп?) это очень востребованная тема в разработке игр. Удачи, друзья!

    Вложения:
    You must be logged in to view attached files.
    #1677
    Heisenberg
    Heisenberg
    Участник
    Сообщений:323

    Зарегистрирован:
    01.04.2015

    Репутация:146

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

Просмотр 2 сообщений - с 1 по 2 (из 2 всего)

Для ответа в этой теме необходимо авторизоваться.