Как я могу оптимизировать мир вокселей Minecraft-esque?

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

Я предполагаю, что медлительность Minecraft проистекает из:

• Java, так как пространственное разбиение и управление памятью быстрее в родном C ++.
• Слабое разделение мира.

Я могу ошибаться в обоих предположениях. Однако это заставило меня задуматься о том, как лучше управлять большими мирами вокселей. Как это настоящий 3D мир, где блок может существовать в любой части мира, это в основном большой 3D массив [x][y][z], где каждый блок в мире имеет тип (то есть BlockType.Empty = 0, BlockType.Dirt = 1и т.д.)

Я предполагаю, что для того, чтобы этот мир работал хорошо, вам необходимо:

• Используйте дерево определенного сорта ( oct / kd / bsp ), чтобы разбить все кубы; кажется, что oct / kd был бы лучшим вариантом, так как вы можете просто разделить на уровне каждого куба, а не уровне треугольника.
• Используйте некоторый алгоритм, чтобы определить, какие блоки в данный момент можно увидеть, поскольку блоки ближе к пользователю могут запутывать блоки позади, делая их бессмысленными для рендеринга.
• Держите объект блока легким, чтобы его можно было легко добавлять и удалять с деревьев.

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

Что касается Java против C ++, я написал воксельный движок для обоих (версия C ++, показанная выше). Я также пишу воксельные двигатели с 2004 года (когда они не были модными). :) Я могу без малейших колебаний сказать, что производительность C ++ намного выше (но ее также сложнее кодировать). Меньше о скорости вычислений, а больше об управлении памятью. Руки вниз, когда вы выделяете / освобождаете столько данных, сколько в мире вокселей, C (++) - это язык, который нужно побеждать. тем не мениеДумай о своей цели. Если производительность является вашим наивысшим приоритетом, используйте C ++. Если вы просто хотите написать игру без ультрасовременной производительности, Java, безусловно, является приемлемым (как свидетельствует Minecraft). Есть много тривиальных / крайних случаев, но в целом можно ожидать, что Java будет работать примерно в 1,75-2,0 раза медленнее, чем (хорошо написано) C ++. Вы можете видеть , плохо оптимизированный, более старую версию моего двигателя в действии здесь (EDIT: новая версия здесь ). Хотя порция генерации может показаться медленной, имейте в виду, что она генерирует объемные трехмерные диаграммы вороного, вычисляя нормали поверхности, освещенность, АО и тени на процессоре методами грубой силы. Я опробовал различные методы, и я могу получить примерно 100-кратное ускорение генерации фрагментов, используя различные методы кэширования и создания экземпляров.

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

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

2. Передайте как можно меньше данных на видеокарту. Люди часто забывают, что чем больше данных вы передаете в графический процессор, тем больше времени требуется. Я передаю один цвет и положение вершины. Если я хочу делать дневные / ночные циклы, я могу просто сделать цветовую градацию или пересчитать сцену, когда солнце постепенно меняется.

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

4. Играть с размером партии. Если вы используете графический процессор, производительность может сильно различаться в зависимости от размера каждого передаваемого вами массива вершин. Соответственно, поиграйтесь с размером чанков (если вы используете чанки). Я обнаружил, что фрагменты 64x64x64 работают довольно хорошо. Неважно, что ваши куски должны быть кубическими (без прямоугольных призм). Это сделает кодирование и различные операции (например, преобразования) более легкими, а в некоторых случаях более производительными. Если вы храните только одно значение для длины каждого измерения, имейте в виду, что это два меньших регистра, которые меняются местами во время вычисления.

5. Рассмотрим списки отображения (для OpenGL). Даже если они «старые» пути, они могут быть быстрее. Вы должны запечь список отображения в переменную ... если вы вызываете операции создания списка отображения в реальном времени, это будет ужасно медленно. Как список отображения быстрее? Он только обновляет состояние, по сравнению с атрибутами для каждой вершины. Это означает, что я могу передать до шести граней, затем один цвет (по сравнению с цветом для каждой вершины вокселя). Если вы используете GL_QUADS и кубические воксели, это может сэкономить до 20 байт (160 бит) на воксель! (15 байтов без альфа-канала, хотя обычно вы хотите сохранить выравнивание по 4 байта.)

6. Я использую метод грубой силы рендеринга «кусков» или страниц данных, что является распространенным методом. В отличие от октодеев, данные считываются / обрабатываются намного легче / быстрее, хотя гораздо менее дружественны к памяти (однако, в наши дни вы можете получить 64 гигабайта памяти за 200-300 долларов) ... не так, как у обычного пользователя. Очевидно, что вы не можете выделить один огромный массив для всего мира (набор вокселей размером 1024x1024x1024 составляет 4 гигабайта памяти, при условии, что для каждого вокселя используется 32-разрядное целое число). Таким образом, вы выделяете / освобождаете множество небольших массивов, основываясь на их близости к зрителю. Вы также можете выделить данные, получить необходимый список отображения, а затем сбросить данные для экономии памяти. Я думаю, что идеальным сочетанием может быть использование гибридного подхода октод и массивов - хранение данных в массиве при процедурном генерировании мира, освещении и т. Д.,

7. Рендеринг от ближнего к дальнему ... отсечение пикселя - это сэкономленное время. GPU выбросит пиксель, если он не пройдет проверку буфера глубины.

8. Рендеринг только кусков / страниц в окне просмотра (само за себя). Даже если gpu знает, как обрезать полигоны за пределами области просмотра, передача этих данных все еще занимает время. Я не знаю, какой была бы наиболее эффективная структура для этого («позорно», я никогда не писал дерево BSP), но даже простая лучевая трансляция на основе порций может улучшить производительность, и, очевидно, тестирование на усмотрение просмотра сэкономить время

9. Очевидная информация, но для новичков: удалите каждый отдельный многоугольник, который не находится на поверхности - то есть, если воксел состоит из шести граней, удалите грани, которые никогда не визуализируются (касаются другого вокселя).

10. Как правило, все, что вы делаете в программировании: CACHE LOCALITY! Если вы можете хранить вещи в локальном кэше (даже в течение небольшого промежутка времени, это будет иметь огромное значение. Это означает, что ваши данные должны быть конгруэнтными (в той же области памяти), и не переключать области памяти на обработку слишком часто. в идеале, работайте с одним чанком на поток и сохраняйте эту память исключительно для потока. Это относится не только к кешу ЦП. Представьте себе иерархию кеша следующим образом (медленнее-быстрее): сеть (облако / база данных / и т. д.) -> жесткий диск (получить SSD, если у вас его еще нет), ram (получить тройной канал или больший объем ОЗУ, если у вас его еще нет), кэш-память ЦП, регистры. Постарайтесь сохранить свои данные на последний конец, и не поменяйте его больше, чем нужно.

11. Threading. Сделай это. Воксельные миры хорошо подходят для многопоточности, поскольку каждая часть может быть рассчитана (в основном) независимо от других ... Я увидел буквально почти четырехкратное улучшение (в 4-ядерном, 8-потоковом Core i7) в процедурном поколении мира, когда я писал подпрограммы для работы с потоками.

12. Не используйте типы данных char / byte. Или шорты. У вашего обычного потребителя будет современный процессор AMD или Intel (как и вы, вероятно). Эти процессоры не имеют 8-битных регистров. Они вычисляют байты, помещая их в 32-разрядный слот, а затем преобразуя их (возможно) в память. Ваш компилятор может выполнять все виды вуду, но использование 32- или 64-битного числа даст вам самые предсказуемые (и самые быстрые) результаты. Аналогично, значение "bool" не занимает 1 бит; компилятор часто использует полные 32 бита для bool. Может быть заманчиво сделать определенные типы сжатия ваших данных. Например, вы можете хранить 8 вокселей как одно число (2 ^ 8 = 256 комбинаций), если они имеют одинаковый тип / цвет. Тем не менее, вы должны подумать о последствиях этого - это может сэкономить много памяти, но это также может снизить производительность даже при небольшом времени декомпрессии, потому что даже это небольшое количество дополнительного времени масштабируется в зависимости от размера вашего мира. Представьте себе вычисление лучевого вещания; для каждого шага лучевой трансляции вам придется запускать алгоритм декомпрессии (если только вы не придумали разумный способ обобщения расчета для 8 вокселей за один шаг луча).

13. Как упоминает Хосе Чавес, может быть полезен шаблон дизайна в полулегком весе. Точно так же, как вы используете растровое изображение для представления плитки в 2D-игре, вы можете построить свой мир из нескольких типов 3D-плиток (или блоков). Недостатком этого является повторение текстур, но вы можете улучшить это, используя дисперсионные текстуры, которые подходят друг другу. Как правило, вы хотите использовать экземпляры везде, где можете.

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

15. Размотайте свои петли и держите массивы плоскими! Не делай этого:

    for (i = 0; i < chunkLength; i++) {
     for (j = 0; j < chunkLength; j++) {
      for (k = 0; k < chunkLength; k++) {
       MyData[i][j][k] = newVal;
      }
     }
    }
    //Instead, do this:
    for (i = 0; i < chunkLengthCubed; i++) {
     //figure out x, y, z index of chunk using modulus and div operators on i
     //myData should have chunkLengthCubed number of indices, obviously
     myData[i] = newVal;
    }

    РЕДАКТИРОВАТЬ: путем более тщательного тестирования, я обнаружил, что это может быть неправильно. Используйте тот случай, который лучше всего подходит для вашего сценария. Как правило, массивы должны быть плоскими, но использование многоиндексных циклов часто может быть быстрее в зависимости от случая

РЕДАКТИРОВАТЬ 2: при использовании многоиндексных циклов лучше всего циклически использовать порядок z, y, x, а не наоборот. Ваш компилятор может оптимизировать это, но я был бы удивлен, если бы это произошло. Это максимизирует эффективность доступа к памяти и локальности.

for (k < 0; k < volumePitch; k++) {
    for (j = 0; j < volumePitch; j++) {
        for (i = 0; i < volumePitch; i++) {
            myIndex = k*volumePitch*volumePitch + j*volumePitch + i;
        }
    }
}

16. Иногда вам приходится делать предположения, обобщения и жертвы. Лучшее, что вы можете сделать, это предположить, что большая часть вашего мира полностью статична и изменяется только каждые пару тысяч кадров. Для оживленных частей мира это можно сделать в отдельном проходе. Также предположим, что большая часть вашего мира полностью непрозрачна. Прозрачные объекты могут быть представлены в отдельном проходе. Предположим, что текстуры меняются только каждые x единиц, или что объекты можно размещать только с шагом x. Предположим, фиксированный размер мира ... каким бы заманчивым ни был бесконечный мир, это может привести к непредсказуемым системным требованиям. Например, чтобы упростить генерацию рисунка вороной в вышеупомянутых породах, я предположил, что каждая центральная точка вороноя находится в однородной сетке с небольшим смещением (другими словами, подразумевается геометрическое хеширование). Предположим, что мир не оборачивается (имеет края). Это может упростить многие сложности, связанные с системой координат упаковки, при минимальных затратах для пользователя.

Вы можете прочитать больше о моих реализациях на моем сайте

Майнкрафт мог бы делать более эффективно. Например, Minecraft загружает целые вертикальные колонны размером около 16x16 плиток и рендерит их. Я чувствую, что очень неэффективно отправлять и визуализировать столько плиток без необходимости. Но я не чувствую, что выбор языка важен.

Java может быть довольно быстрой, но для чего-то такого, ориентированного на данные, C ++ имеет большое преимущество со значительно меньшими накладными расходами на доступ к массивам и работу в байтах. С другой стороны, гораздо проще выполнять многопоточность на всех платформах Java. Если вы не планируете использовать OpenMP или OpenCL, вы не найдете такого удобства в C ++.

Моя идеальная система была бы немного более сложной иерархией.

Плитка представляет собой единое целое, вероятно, около 4 байт для хранения информации, такой как тип материала и освещение.

Сегмент будет 32x32x32 блок плиток.

1. Флаги будут установлены для каждой из шести сторон, если вся эта сторона представляет собой сплошные блоки. Это позволит визуализатору перекрывать сегменты позади этого сегмента. Minecraft в настоящее время, по-видимому, не выполняет тестирование окклюзии. Но было упоминание о наличии аппаратной отсечки, которая может быть дорогостоящей, но лучше, чем рендеринг огромного количества полигонов на младших картах.
2. Сегменты будут загружаться в память только во время активности (игроки, NPC, физика воды, рост деревьев и т. Д.). В противном случае они будут отправлены непосредственно с диска клиентам.

Сектора будут 16x16x8 блок сегментов.

1. Секторы будут отслеживать самый высокий сегмент для каждого вертикального столбца, так что сегменты выше этого могут быть быстро определены пустыми.
2. Он также отслеживал бы нижний закупоренный сегмент, так что каждый сегмент, который необходимо визуализировать с поверхности, можно было быстро захватить.
3. Секторы также будут отслеживать следующий раз, когда необходимо обновить каждый сегмент (физика воды, рост деревьев и т. Д.). Таким образом, загрузки в каждом секторе было бы достаточно, чтобы поддерживать мир, и загружать только сегменты, достаточно длинные для выполнения своих задач.
4. Все позиции организаций будут отслеживаться относительно Сектора. Это предотвратит ошибки с плавающей точкой, присутствующие в Minecraft, при путешествии очень далеко от центра карты.

Мир будет бесконечной картой секторов.

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

Minecraft довольно быстрый, даже на моем 2-ядерном. Здесь, похоже, Java не является ограничивающим фактором, хотя есть небольшая задержка сервера. Местные игры, кажется, работают лучше, так что я собираюсь предположить некоторые неэффективности, там.

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

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

Обратите также внимание на то, что существуют блоки FACES, которые можно считать невидимыми из-за того, что они затенены (т. Е. Другой блок покрывает лицо) или в каком направлении направлена ​​камера (если камера направлена ​​на север, вы можете не вижу северной грани ЛЮБЫХ блоков!)

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

Ваш вопрос не ясен, если вы хотите оптимизировать скорость рендеринга, размер данных или что-то еще. Разъяснение там было бы полезно.

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

Причина, по которой Minecraft является медленным, связана с некоторыми сомнительными, низкоуровневыми проектными решениями - например, каждый раз, когда на блок ссылается позиционирование, игра проверяет координаты примерно с 7 операторами if, чтобы убедиться, что он не выходит за пределы , Кроме того, нет никакого способа захватить «чанк» (блок 16x16x256 блоков, с которым работает игра), а затем напрямую ссылаться на блоки в нем, чтобы обойти поиск в кеше и, конечно, глупые проблемы проверки (т. Е. Каждая ссылка на блок также включает в себя просмотр фрагментов, между прочим.) В моем моде я создал способ прямого захвата и изменения массива блоков, что увеличило генерацию массивных подземелий с неиграло запаздывающих до незаметно быстрых.

РЕДАКТИРОВАТЬ: Удалено утверждение, что объявление переменных в другой области привело к повышению производительности, на самом деле это не так. Я полагаю, что в то время, когда я связывал этот результат с чем-то еще, с чем я экспериментировал (в частности, удаляя броски между двойными и поплавковыми значениями в коде, связанном со взрывами, путем объединения в двойные ... понятно, что это оказало огромное влияние!)

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

Поэтому, какой бы язык вы ни выбрали, постарайтесь быть очень близкими к деталям реализации / низкого уровня, потому что даже одна маленькая деталь в проекте, такая как эта, может иметь все значение (один пример для меня в C ++ был «Может ли компилятор статически встроить функцию указатели? «Да, это возможно! Совершенно невероятно изменился один из проектов, над которым я работал, поскольку у меня было меньше кода и преимущество встраивания.)

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

Кроме того, ответ Гэвина охватывает некоторые детали, которые я не хотел бы повторять (и многое другое! Он явно более осведомлен в этом вопросе, чем я), и я согласен с ним по большей части. Мне придется поэкспериментировать с его комментарием относительно процессоров и более коротких переменных размеров, я никогда не слышал об этом - я хотел бы доказать себе, что это правда!

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

Что вы будете делать с этими данными, зависит только от вас. Для производительности GFX вы можете затем использовать Clipping, чтобы обрезать скрытые объекты, объекты, которые слишком малы, чтобы быть видимыми, и т. Д.

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

Что-то, на что стоит обратить внимание, это шаблон дизайна Flyweight . Я считаю, что большинство ответов здесь так или иначе ссылаются на этот шаблон проектирования.

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

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

Очевидно, что единственный способ узнать это - начать реализовывать свои собственные и выполнять некоторые тесты памяти на производительность. Дайте нам знать, как это идет!