Работа с множеством кубов. Улучшение производительности?

12

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

Я работаю над проектом, в котором мир состоит из большого количества кубов (я бы дал вам число, но это миры, определяемые пользователем). Мой тест - один (48 х 32 х 48) блоков.

По сути, эти блоки сами по себе ничего не делают. Они просто сидят там.

Они начинают использоваться, когда дело доходит до взаимодействия с игроком.

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

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

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

Тем не менее, я все еще иду на удручающие 2fps.

У кого-нибудь есть другие идеи о том, как я могу уменьшить это отставание?

Кстати, я использую XNA (C #) и да, это 3d.

Joel
источник
Вы имеете в виду Minecraft-как? То есть воксель?
Коммунистическая утка
4
Вы смотрели в октри? en.wikipedia.org/wiki/Octree
bummzack
1
Вы пробовали профилировать свою игру? Это может показать некоторые ключевые области, где больше всего времени тратится. Это может быть не то, что вы думаете.
замедленная
2
Вместо того, чтобы рисовать все 6 граней каждого куба, вы можете нарисовать только грани, которые ни с чем не соприкасаются
Дэвид Эшмор
1
@ Дэвид: Да, или он мог бы прекратить сначала делать один вызов для каждого куба, а потом беспокоиться об отдельных полигонах.
Ольховский

Ответы:

20

Похоже, вы хотите узнать о деревьях!

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

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

Теперь, чтобы определить эту зону, нам нужно отобразить координатное пространство нашего игрока в координатное пространство карты куба; то есть нам нужно отобразить положение игрока с плавающей запятой на дискретный индекс многомерного массива кубов (примерная нотация может быть world[31][31][31], то есть точная середина для многомерного массива 64 * 64 * 64).

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

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

Вопрос в том, как мы это реализуем?

Для мира 64 * 64 * 64 представьте, что он разбит на 8 * 8 * 8 зон . Это означает, что в вашем мире у вас будет 8 зон на ось (X, Y, Z). Каждая из этих зон будет содержать 8 кубов, которые можно легко найти с помощью этого нового упрощенного индекса.

Если вам нужно выполнить операцию с набором соседних кубов, вместо того, чтобы выполнять итерации каждого куба в вашем мире, вы можете просто выполнить итерацию по этим зонам , разбив максимальное число итераций от исходного 64 * 64 * 64 (262144) до всего 520 (8 * 8 * 8 + 8).

Теперь отойдите от этого мира зон и поместите зоны в большие суперзоны ; где каждая суперзона содержит 2 * 2 * 2 регулярных зоны . Поскольку ваш мир в настоящее время содержит 512 (8 * 8 * 8) зон , мы можем разбить 8 * 8 * 8 зон на 64 (4 * 4 * 4) суперзоны , разделив 8 зон на 2 зоны на суперзону . Применяя ту же логику сверху, это сломало бы максимальные итерации от 512 до 8, чтобы найти супер-зону ; а затем максимум 64, чтобы найти исходящую зону(всего макс. 72)! Вы можете видеть, как это уже экономит много итераций (262144: 72).

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

Диаграмма ниже должна помочь вам визуализировать концепцию. (изображение из Википедии: Octrees ): Octree

Отказ от ответственности:

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

deceleratedcaviar
источник
Я бы сказал, что понял, но, к сожалению, нет. Коробки столкновения блоков не двигаются, только коробка столкновения игрока. И теперь у меня есть метод, который (без циклического прохождения всех блоков) возвращает все блоки, которые находятся в радиусе 5 блоков от игрока. Извините за неприятности, но есть какие-то разъяснения? Кстати, чтобы сделать это проще, вы могли бы предположить, что мир 64 х 64 х 64?
Джоэл
И я все еще получаю около 5 кадров в секунду :(
Джоэл
Я перефразировал мой ответ, дайте мне знать, помог ли он.
замедленная
Поэтому я сужаю блоки, в которых может находиться игрок, используя эту технику октри. Я почти уверен, что понял. Но вы предлагаете мне использовать мое обнаружение столкновений, как только я сузил его до небольшого выбора блоков, или у вас есть какой-то другой метод?
Джоэл
2
Если игрок не очень большой по размеру кубов, то проверка столкновения вокруг игрока, вероятно, самый быстрый способ. Например, если игрок занимает не больше места, чем один куб, ему нужно проверить не более 27 окружающих кубов, чтобы найти столкновение. Это не требует дерева, поскольку вы можете индексировать непосредственно в эти местоположения куба, предполагая, что он хранит кубы в массиве, в который он может индексировать, с одним слотом, выделенным для каждого возможного местоположения куба.
Ольховский
13

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

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

Есть много способов профилировать ваш код, вы можете свернуть свой собственный класс анализа производительности (который может использовать класс секундомера (MSDN) ), или вы можете использовать PIX, чтобы получить общее представление о том, насколько занят CPU / GPU ,

Вы также можете поместить маркеры событий PIX в свой код, которые будут отображаться как цветные области в показаниях PIX. Официального интерфейса C # для этих функций не существует, но этот поток показывает, как вы можете создать интерфейс C # самостоятельно.

CiscoIPPhone
источник
2
+1, полностью согласен. Вы не должны смотреть на алгоритмы, вы должны смотреть на профилирование вашего кода. Я думаю, это не имеет ничего общего с тем, что вы перебираете блоки (это не так много), это то, что вы делаете с каждым блоком. В конечном счете, да, вам нужен лучший метод, чем грубая сила, но если вы не можете справиться с простой итерацией на кубах 48x32x48, вам нужно переосмыслить то, что вы делаете с каждым кубом, а не то, как вы выполняете цикл.
Тим Холт
4
@Tim: Если его игрок не достаточно большой, чтобы занимать пространство 48x32x48, то он не должен перебирать где-нибудь рядом с таким количеством кубов. Если он выполняет итерацию по 73000 кубов на кадр, то я могу сказать вам, не выполняя какого-либо профилирования, что ему стоит это исправить, если только по какой-то другой причине, кроме как научиться избегать выполнения итераций в десятки тысяч раз больше, чем необходимы. Это не то, что я бы назвал микро или преждевременной оптимизацией.
Ольховский
Мой игрок меньше, чем размер 1 куба, хотя может быть больше на некоторой стадии (но не намного)
Джоэл
Randomman159: Тогда вам нужно всего лишь проверить его окружающие 27 кубов, чтобы найти столкновение. Смотри мой ответ.
Ольховский
6

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

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

Так как ваш игрок меньше 1 куба, вам нужно всего лишь проверить на столкновение с соседними 27 кубами, максимум.

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

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

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

Ольховский
источник
Или вы можете иметь «ограничивающую рамку», которая окружает игрока, и затем вы просто проверяете, с какими объектами он сталкивается, чтобы определить, с какими объектами должен столкнуться игрок. Хороший физический движок сможет сделать все оптимизации для вас; это также позволит столкнуться не только с «блоками».
замедленная
Лично я не хотел бы полагаться на широкофазу физического движка для тестирования для меня 73000 кубов, когда я мог просто написать две дюжины строк кода для эффективного тестирования на столкновение для меня. Кроме того, он, вероятно, не имеет физического движка, чтобы задействовать в это время.
Ольховский
1

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

Очевидно, что Minecraft делает что-то похожее на это - я однажды ударил незаряженный кусок, который дал мне взгляд на мир - я мог видеть сквозь твердую землю, все, что было видно, это открытые пространства (дальняя сторона их была открытая поверхность и, следовательно, оказана.)

Лорен Печтель
источник
-1

У меня была такая проблема с моим воксельным двигателем.

Решение: (Гораздо проще, чем октры) Вместо того, чтобы проходить по всем блокам, просто используйте уравнение, чтобы определить положение блока в массиве блоков.

BlockIndex = (x * WorldWidth * WorldHeight) + (z * WorldHeight) + y;

Затем, если вы хотите увидеть, существует ли блок:

Blocks[BlockIndex].Type > -1;

Или, однако, вы определяете, существует ли блок.

BMW
источник
Проблема здесь более сложная, потому что у вас есть только 2 координаты для вашей мыши, чтобы протестировать с трехмерным миром. Если бы вид был сверху вниз, вы могли бы найти 2 из 3 правильных индексов для позиции мыши, а затем выполнить цикл для высоты, начиная сверху - ближе к камере, и найти первый вхождение блока.
Маркус фон Броади