Как эффективно имитировать сетку статических прямоугольников в физическом движке?

Question

Я делаю космический шутер, который происходит в большом подземелье, которое состоит из больших прямоугольников для определения стен.Все в игре физически моделируется с использованием Farseer Physics.Однако есть одна проблема: я хочу, чтобы подземелье выглядело достаточно большим, но для этого необходимо, чтобы в моей сетке было как минимум 80x80 прямоугольников, а это означает, что в худшем случае у меня 6400 физически смоделированных тел, что не совсем точно.как вы можете догадаться, производительность.

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

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

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

РЕДАКТИРОВАТЬ: Вот небольшой пример того, как тела сейчас выглядят: (каждое число является телом)

И вот как я хочу, чтобы они были:

Answer 1

Вот что я использовал в одной из моих игр (не в C #, также):

Сначала создайте массив со сплошными стенками, создайте структуру, подобную Wall, с интергерами x,y, width и height, создайте их много, по одному для каждого блока.

Затем выполните цикл по ним и объедините те, которые имеют одинаковые y и height, исоседей (x₁ + width₁ = x₂).

Затем повторите цикл, на этот раз, используя x вместо y (и наоборот), и используя width вместо height (и наоборот).

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

При выполнении этого генерируется 38 тел (это то же количество тел, что и в примере, который вы опубликовали):

При изменении порядка в двух последних шагах создается 36 тел:

Answer 2

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

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

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

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

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

Сложность этого алгоритма для прямоугольной матрицы n*m интуитивно равна O(n*n*m*m). На практике я думаю, что это будет довольно быстро с вашими данными. Обратите внимание, что этот алгоритм не обеспечивает наименьшее количество объектов, но максимизирует сумму всех областей (в соответствии с вашим вопросом). Я понимаю, что проблема минимизации общего числа тел намного сложнее с точки зрения сложности.

Answer 3

Используя Farseer, нужно использовать EDGES вместо того, чтобы строить свою карту / мир / уровень с таким количеством тел, что может привести к проблемам с производительностью.

Если вы можете найти способ конвертироватьваша карта в список последовательных координат вершин, возможно, алгоритм, который отслеживает стены и генерирует список, вы можете сделать это ...

Создать 1 тело и добавить ПЕРВОЕ ребро:

Body dungeon = BodyFactory.CreateEdge(world, start, end);

Затем переберите все остальные координаты вершин в последовательности, а затем присоедините каждое новое ребро к предыдущей конечной координате ребра.(объединение ребер в последовательность до выполнения)

FixtureFactory.AttachEdge(start, end, dungeon);

В результате получается 1 тело вместо 35 +.