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

Если вы впервые отвечаете на этот вопрос, я предлагаю сначала прочитать часть перед обновлением, а затем эту часть. Вот обобщение проблемы:

По сути, у меня есть механизм обнаружения и разрешения коллизий с системой пространственного разбиения сетки, где важен порядок коллизий и группы коллизий. Одно тело за один раз должно двигаться, затем обнаруживать столкновения, а затем разрешать столкновения. Если я перемещаю все тела одновременно, а затем генерирую возможные пары столкновений, это, очевидно, быстрее, но разрешение нарушается, потому что порядок столкновения не соблюдается. Если я перемещаю одно тело за раз, я вынужден заставлять тела проверять столкновения, и это становится проблемой ^ 2. Поместите группы в микс, и вы можете себе представить, почему это происходит очень медленно и очень быстро с большим количеством тел.

Обновление: я очень много работал над этим, но не смог ничего оптимизировать.

Я успешно реализовал «рисование», описанное Уиллом, и превратил группы в наборы битов, но это очень и очень небольшое ускорение.

Я также обнаружил большой проблему: мой двигатель зависит от порядка столкновения.

Я попробовал реализацию генерации уникальной пары столкновений , которые определенно сильно ускоряют все, но нарушают порядок столкновений .

Позволь мне объяснить:

• в моем оригинальном дизайне (не генерация пар) это происходит:

  1. одно тело движется
  2. после перемещения он освежает свои клетки и получает тела, с которыми сталкивается
  3. если он перекрывает тело, против которого нужно разрешить, разрешите столкновение

  это означает, что если тело движется и ударяет стену (или любое другое тело), ​​только тело, которое переместилось, разрешит его столкновение, и другое тело не будет затронуто.

  Это поведение, которое я желаю .

  Я понимаю, что это не характерно для физических движков, но имеет много преимуществ для игр в стиле ретро .

• в обычном сеточном дизайне (создание уникальных пар) это происходит:

  1. все тела движутся
  2. после того, как все тела переместились, обновите все клетки
  3. генерировать уникальные пары столкновений
  4. для каждой пары обрабатывать обнаружение и разрешение столкновений

  в этом случае одновременное перемещение могло бы привести к перекрытию двух тел, и они будут разрешаться одновременно - это эффективно заставляет тела «толкать друг друга» и нарушает устойчивость столкновения с несколькими телами

  Такое поведение характерно для физических движков, но в моем случае оно неприемлемо .

Я также обнаружил еще одну проблему, которая является серьезной (даже если это вряд ли произойдет в реальной ситуации):

• рассмотреть тела группы A, B и W
• А сталкивается и решает против W и A
• B сталкивается и решает против W и B
• А ничего не делает против В
• B ничего не делает против A

может быть ситуация, когда множество тел A и B занимают одну и ту же ячейку - в этом случае существует много ненужных итераций между телами, которые не должны реагировать друг на друга (или только обнаруживать столкновения, но не разрешать их) ,

Для 100 тел, занимающих одну и ту же клетку, это 100 ^ 100 итераций! Это происходит потому, что уникальные пары не генерируются - но я не могу генерировать уникальные пары , иначе я бы получил поведение, которого я не желаю.

Есть ли способ оптимизировать этот тип двигателя столкновения?

Это руководящие принципы, которые необходимо соблюдать:

• Порядок столкновения чрезвычайно важен!

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

• Тела должны иметь 3 групповых набора битов

  • Группы : группы, к которым принадлежит тело
  • GroupsToCheck : группы, в которых тело должно обнаружить столкновение с
  • GroupsNoResolve : группы, в которых тело не должно разрешать конфликты с
  • Могут быть ситуации, когда я только хочу, чтобы столкновение было обнаружено, но не разрешено

Предварительное обновление:

Предисловие : я знаю, что оптимизация этого узкого места не является необходимостью - двигатель уже очень быстрый. Я, однако, для забавных и образовательных целей, хотел бы найти способ сделать двигатель еще быстрее.

Я создаю универсальный C ++ 2D механизм обнаружения / реагирования на столкновения с упором на гибкость и скорость.

Вот очень простая схема его архитектуры:

По сути, основным классом является World, который владеет (управляет памятью) a ResolverBase*, a SpatialBase*и a vector<Body*>.

SpatialBase это чисто виртуальный класс, который имеет дело с обнаружением столкновений в широкой фазе.

ResolverBase это чисто виртуальный класс, который имеет дело с разрешением коллизий.

Тела общаются World::SpatialBase*с SpatialInfoобъектами, принадлежащими самим телам.

В настоящее время существует один пространственный класс: Grid : SpatialBaseбазовая фиксированная двумерная сетка. У него есть свой собственный информационный класс GridInfo : SpatialInfo.

Вот как выглядит его архитектура:

GridКласс владеет 2D массив Cell*. CellКласс содержит коллекцию (не принадлежит) Body*: а , vector<Body*>который содержит все тела , которые находятся в клетке.

GridInfo объекты также содержат не владеющие указателями на клетки, в которых находится тело.

Как я уже говорил, двигатель основан на группах.

• Body::getGroups()возвращает a std::bitsetиз всех групп, частью которых является тело.
• Body::getGroupsToCheck()возвращает a std::bitsetиз всех групп, с которыми тело должно проверить столкновение.

Тела могут занимать более одной клетки. GridInfo всегда хранит не принадлежащие указатели на занятые ячейки.

После перемещения одного тела происходит обнаружение столкновений. Я предполагаю, что все тела являются ориентированными по оси ограничительными рамками.

Как работает обнаружение столкновения в широкой фазе:

Часть 1: обновление пространственной информации

Для каждого Body body:

1. • Вычисляются самые верхние левые занятые ячейки и самые нижние правые занятые ячейки.
   • Если они отличаются от предыдущих ячеек, body.gridInfo.cellsочищаются и заполняются всеми ячейками, которые занимает тело (2D для цикла от самой верхней левой ячейки до самой нижней правой ячейки).

2. body Теперь гарантированно знать, какие клетки он занимает.

Часть 2: фактические проверки столкновений

Для каждого Body body:

• body.gridInfo.handleCollisions называется:

void GridInfo::handleCollisions(float mFrameTime)
{
    static int paint{-1};
    ++paint;

    for(const auto& c : cells)
        for(const auto& b : c->getBodies())
        {
            if(b->paint == paint) continue;
            base.handleCollision(mFrameTime, b);
            b->paint = paint;
        }
}

void Body::handleCollision(float mFrameTime, Body* mBody)
    {
        if(mBody == this || !mustCheck(*mBody) || !shape.isOverlapping(mBody->getShape())) return;

        auto intersection(getMinIntersection(shape, mBody->getShape()));

        onDetection({*mBody, mFrameTime, mBody->getUserData(), intersection});
        mBody->onDetection({*this, mFrameTime, userData, -intersection});

        if(!resolve || mustIgnoreResolution(*mBody)) return;
        bodiesToResolve.push_back(mBody);
    }

• Столкновение тогда разрешено для каждого тела в bodiesToResolve.

• Вот и все.

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

Мой вопрос: как я могу оптимизировать широкую фазу моего двигателя столкновения ?

Есть ли какая-то волшебная оптимизация C ++, которая может быть применена здесь?

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

• Фактическая реализация: SSVSCollsion
• Body.h , Body.cpp
• World.h , World.cpp
• Grid.h , Grid.cpp
• Cell.h , Cell.cpp
• GridInfo.h , GridInfo.cpp

Вывод Callgrind для последней версии: http://txtup.co/rLJgz

getBodiesToCheck()

Там может быть две проблемы с getBodiesToCheck()функцией; первый:

if(!contains(bodiesToCheck, b)) bodiesToCheck.push_back(b);

Эта часть O (n ² ) не так ли?

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

loop_count++;
if(!loop_count) { // if loop_count can wrap,
    // you just need to iterate all bodies to reset it here
}
bodiesToCheck.clear();
for(const auto& q : queries)
    for(const auto& b : *q)
        if(b->paint != loop_count) {
            bodiesToCheck.push_back(b);
            b->paint = loop_count;
        }
return bodiesToCheck;

Вы разыменовываете указатель в фазе сбора, но вы все равно будете разыменовывать его в фазе тестирования, поэтому, если у вас достаточно L1, это не проблема. Вы можете повысить производительность, добавив подсказки предварительной выборки в компилятор, например __builtin_prefetch, хотя это проще с классическими for(int i=q->length; i-->0; )циклами и тому подобным.

Это простой трюк, но моя вторая мысль заключается в том, что может быть более быстрый способ организовать это:

Однако вы можете перейти к использованию растровых изображений и избежать всего bodiesToCheckвектора. Вот подход:

Вы уже используете целочисленные ключи для тел, но затем просматриваете их на картах и ​​прочем и сохраняете их списки. Вы можете перейти к распределителю слотов, который в основном представляет собой массив или вектор. Например:

class TBodyImpl {
   public:
       virtual ~TBodyImpl() {}
       virtual void onHit(int other) {}
       virtual ....
       const int slot;
   protected:
      TBodyImpl(int slot): slot(slot_) {}
};

struct TBodyBase {
    enum ... type;
    ...
    rect_t rect;
    TQuadTreeNode *quadTreeNode; // see below
    TBodyImpl* imp; // often null
};

std::vector<TBodyBase> bodies; // not pointers to them

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

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

проверять только каждое столкновение только один раз

Если вы проверили, сталкивается ли a с b , вам не нужно проверять, сталкивается ли b с тоже a .

Из целочисленных идентификаторов следует, что вы избегаете этих проверок с помощью простого оператора if. Если идентификатор потенциального столкновения меньше или равен текущему идентификатору, для которого выполняется проверка, его можно пропустить! Таким образом, вы будете проверять каждую возможную пару только один раз; это будет более половины числа проверок столкновений.

unsigned * bitmap;
int bitmap_len;
...

for(int i=0; i<bitmap_len; i++) {
  unsigned mask = bitmap[i];
  while(mask) {
      const int j = __builtin_ffs(mask);
      const int slot = i*sizeof(unsigned)*8+j;
      for(int neighbour: get_neighbours(slot))
          if(neighbour > slot)
              check_for_collision(slot,neighbour);
      mask >>= j;
  }

соблюдать порядок столкновений

Вместо того, чтобы оценивать столкновение, как только пара найдена, вычислите расстояние до удара и сохраните его в двоичной куче . Эти кучи - то, как вы обычно делаете приоритетные очереди при поиске пути, поэтому очень полезен служебный код.

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

• A ¹⁰ хиты B ¹² в 6
• A ¹⁰ ударов C ¹² на 3

Очевидно, после того, как вы собрали все коллизии, вы начинаете выталкивать их из очереди с приоритетами, скорее всего первыми. Итак, первое, что вы получите, это A ¹⁰ попаданий C ¹² в 3. Вы увеличиваете порядковый номер каждого объекта ( ¹⁰ бит), оцениваете коллизию, вычисляете их новые пути и сохраняете их новые коллизии в той же очереди. Новое столкновение - A ^11, попадание B ^{12 -} 7. Теперь очередь имеет:

• A ¹⁰ хиты B ¹² в 6
• A ¹¹ хиты B ¹² в 7

Тогда вы выскочить из очереди приоритетов и Св ¹⁰ хитов B ¹² в 6. Но вы видите , что ¹⁰ является устаревшим ; А в настоящее время на 11. Таким образом, вы можете отказаться от этого столкновения.

Важно не пытаться удалить все устаревшие столкновения из дерева; удаление из кучи стоит дорого. Просто откажитесь от них, когда вы их поп

сетки

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

Вот простой Quadtree:

struct Object {
    Rect bounds;
    Point pos;
    Object * prev, * next;
    QuadTreeNode * parent;
};

struct QuadTreeNode {
    Rect bounds;
    Point centre;
    Object * staticObjects;
    Object * movableObjects;
    QuadTreeNode * parent; // null if root
    QuadTreeNode * children[4]; // null for unallocated children
};

Мы храним подвижные объекты отдельно, потому что нам не нужно проверять, не сталкиваются ли статические объекты с чем-либо.

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

Каждый тик игры, вы должны вернуться в quadtree и вычислить движение - и столкновения - каждого подвижного объекта. Это должно быть проверено на столкновения с:

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

Это создаст все возможные столкновения, неупорядоченные. Затем вы делаете ходы. Вы должны расставить приоритеты этих ходов по расстоянию и «кто двигается первым» (что является вашим особым требованием) и выполнять их в таком порядке. Используйте кучу для этого.

Вы можете оптимизировать этот шаблон дерева квадрантов; вам не нужно хранить границы и центральную точку; это полностью выводимо, когда вы идете по дереву. Вам не нужно проверять, находится ли модель в пределах границ, только проверяйте, с какой стороны она находится от центральной точки (тест «оси разделения»).

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

Большие статические объекты должны быть разбиты на составные части; например, в большом кубе каждое лицо должно храниться отдельно.

Бьюсь об заклад, у вас просто тонна промахов при переборе тел. Объединяете ли вы все свои тела, используя какую-то схему, ориентированную на данные? С помощью N ^ 2 широкофазы я могу моделировать сотни и сотни , записывая с помощью fraps, тел без каких-либо кадровых кадров, падающих в нижние области (менее 60), и все это без специального распределителя. Только представьте, что можно сделать при правильном использовании кэша.

Подсказка здесь:

const std::vector<Body *>

Это сразу поднимает огромный красный флаг. Вы наделяете эти органы необработанными новыми звонками? Используется ли пользовательский распределитель? Очень важно, чтобы все ваши тела были в огромном массиве, в котором вы проходите линейно . Если линейный обход памяти - это не то, что вы чувствуете, что можете реализовать, попробуйте вместо этого использовать навязчиво связанный список.

Кроме того, вы, кажется, используете std :: map. Вы знаете, как распределяется память в std :: map? Вы будете иметь сложность O (LG (N)) для каждого запроса карты, и это, вероятно, может быть увеличено до O (1) с хэш-таблицей. Кроме того, память, выделенная std :: map, также будет ужасно перегружать ваш кеш.

Мое решение состоит в том, чтобы использовать навязчивую хэш-таблицу вместо std :: map. Хороший пример как навязчиво связанных списков, так и навязчивых хеш-таблиц находится в базе Патрика Уайетта в рамках его совместного проекта: https://github.com/webcoyote/coho

Короче говоря, вам, вероятно, понадобится создать несколько собственных инструментов, а именно распределитель и несколько навязчивых контейнеров. Это лучшее, что я могу сделать без профилирования кода для себя.

Уменьшите количество тел, чтобы проверить каждый кадр:

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

Используйте квадри. Смотрите мой подробный ответ здесь

Удалите все выделения из вашего кода физики. Вы можете использовать профилировщик для этого. Но я только проанализировал распределение памяти в C #, поэтому я не могу помочь с C ++.

Удачи!

Я вижу двух проблемных кандидатов в вашей функции узкого места:

Во-первых, это «содержит» часть - это, вероятно, главная причина узкого места. Итерирует уже найденные тела для каждого тела. Может быть, вам лучше использовать какой-то тип hash_table / hash_map вместо вектора. Тогда вставка должна быть быстрее (с поиском дубликатов). Но я не знаю никаких конкретных чисел - я понятия не имею, сколько тел здесь повторяется.

Вторая проблема может быть vector :: clear и push_back. Очистить может вызвать или не вызвать перераспределение. Но вы можете избежать этого. Решением может быть некоторый массив флагов. Но у вас может быть много объектов, поэтому неэффективно использование списка всех объектов для каждого объекта. Некоторый другой подход мог бы быть хорошим, но я не знаю, какой подход: /

Примечание: я ничего не знаю о C ++, только Java, но вы должны быть в состоянии понять код. Физика это универсальный язык, верно? Я также понимаю, что это годичный пост, но я просто хотел поделиться этим со всеми.

У меня есть шаблон наблюдателя, который в основном после перемещения объекта возвращает объект, с которым столкнулся, включая объект NULL. Проще говоря:

( Я переделываю майнкрафт )

public Block collided(){
   return World.getBlock(getLocation());
}

Так скажи, что ты бродишь в своем мире. всякий раз, когда вы звоните move(1), звоните collided(). если вы получите нужный блок, то, возможно, частицы летят, и вы можете двигаться влево и вправо, но не вперед.

Используя это более обобщенно, чем просто Minecraft в качестве примера:

public Object collided(){
   return threeDarray[3][2][3];
}

Просто, есть массив для указания координат, который, буквально так, как это делает Java, использует указатели.

Использование этого метода все еще требует чего-то другого, априори метода обнаружения столкновений. Вы можете зациклить это, но это побеждает цель. Вы можете применить это к методам широкого, среднего и узкого столкновений, но в одиночку это чудовищно, особенно когда оно хорошо работает для 3D и 2D игр.

Теперь, еще раз посмотрев, это означает, что в соответствии с моим методом minecraft collide () я окажусь внутри блока, поэтому мне придется переместить игрока за его пределы. Вместо того, чтобы проверять игрока, мне нужно добавить ограничивающий прямоугольник, который проверяет, какой блок поражает каждую сторону поля. Проблема исправлена.

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