Я использую C # и XNA. Мой текущий алгоритм освещения - рекурсивный метод. Тем не менее, это дорого , до такой степени, что один кусок 8x128x8 рассчитывается каждые 5 секунд.
- Существуют ли другие методы освещения, которые будут создавать тени переменной темноты?
- Или рекурсивный метод хорош, и, возможно, я просто делаю это неправильно?
Просто кажется, что рекурсивные вещи в корне дороги (вынуждены проходить около 25 тыс. Блоков на кусок). Я думал об использовании метода, подобного трассировке лучей, но я понятия не имею, как это будет работать. Еще я пытался хранить источники света в Списке, и для каждого блока получать расстояние до каждого источника света и использовать его для освещения до нужного уровня, но тогда освещение будет проходить через стены.
Мой текущий код рекурсии ниже. Это вызывается из любого места в чанке, где уровень освещения не равен нулю, после очистки и повторного добавления солнечного света и света факела.
world.get___atэто функция, которая может получать блоки вне этого чанка (это внутри класса чанка). Locationмоя собственная структура, которая похожа на a Vector3, но использует целые числа вместо значений с плавающей запятой. light[,,]это карта света для куска.
private void recursiveLight(int x, int y, int z, byte lightLevel)
{
Location loc = new Location(x + chunkx * 8, y, z + chunky * 8);
if (world.getBlockAt(loc).BlockData.isSolid)
return;
lightLevel--;
if (world.getLightAt(loc) >= lightLevel || lightLevel <= 0)
return;
if (y < 0 || y > 127 || x < -8 || x > 16 || z < -8 || z > 16)
return;
if (x >= 0 && x < 8 && z >= 0 && z < 8)
light[x, y, z] = lightLevel;
recursiveLight(x + 1, y, z, lightLevel);
recursiveLight(x - 1, y, z, lightLevel);
recursiveLight(x, y + 1, z, lightLevel);
recursiveLight(x, y - 1, z, lightLevel);
recursiveLight(x, y, z + 1, lightLevel);
recursiveLight(x, y, z - 1, lightLevel);
}
Ответы:
LR.|VP - LP| < LR, где VP - это вектор положения вокселя относительно источника иLPвектор положения источника относительно источника. Для каждого источника света, радиус которого ток вокселей оказывается в, это приращение световой фактор на расстоянии от светового центра,|VP - LP|. Если вы нормализуете этот вектор и затем получите его величину, это будет в диапазоне 0.0-> 1.0. Максимальный уровень освещенности, который может достичь воксель, составляет 1,0.Время выполнения - это
O(s^3 * n)гдеsдлина стороны (128) вашей воксельной области иnколичество источников света. Если ваши источники света статичны, это не проблема. Если ваши источники света перемещаются в режиме реального времени, вы можете работать только с дельтами, а не пересчитывать весь шебанг при каждом обновлении.Вы даже можете хранить воксели, на которые влияет каждый источник света, в качестве ссылок в этом источнике. Таким образом, когда источник света перемещается или уничтожается, вы можете просмотреть только этот список, соответствующим образом скорректировав значения света, вместо того, чтобы снова пересекать всю кубическую сетку.
источник
Сам Minecraft таким образом не делает солнечный свет.
Вы просто заполняете солнечный свет сверху вниз, каждый слой собирает свет от соседних вокселей в предыдущем слое с ослаблением. Очень быстро - один проход, без списков, без структур данных, без рекурсии.
Вы должны добавить факелы и другие не затопляющие огни в более позднем проходе.
Есть так много других способов сделать это, включая причудливое направленное распространение света и т. Д., Но они, очевидно, медленнее, и вы должны выяснить, хотите ли вы инвестировать в дополнительный реализм, учитывая эти штрафы.
источник
Кто-то сказал, чтобы ответить на ваш вопрос, если вы поняли, так что да. Разобрался с методом.
Что я делаю, так это: во-первых, создайте трехмерный логический массив «уже измененных блоков», наложенных на чанк. Затем залейте солнечный свет, факел и т. Д. (Просто осветите включенный блок, пока нет заливки). Если вы что-то изменили, нажмите «измененные блоки» в этом месте на true. Также перейдите и измените каждый сплошной блок (и, следовательно, не нужно рассчитывать освещение) на «уже измененный».
Теперь о тяжелом материале: Пройдите через весь блок с 16 проходами (для каждого уровня освещенности), и если его «уже изменили», просто продолжайте. Затем получите уровень света для блоков вокруг себя. Получить самый высокий уровень света из них. Если этот уровень освещенности равен текущему уровню освещенности проходов, установите текущий уровень для блока, в котором вы находитесь, и установите для «уже измененного» для этого местоположения значение true. Продолжить.
Я знаю, что это сложно, я пытался объяснить, как лучше. Но важный факт, это работает и быстро.
источник
Я бы предложил алгоритм, который объединяет ваше многопроходное решение с оригинальным рекурсивным методом и, скорее всего, немного быстрее, чем любой из них.
Вам понадобится 16 списков (или любых видов коллекций) блоков, по одному на каждый уровень освещенности. (На самом деле, есть способы оптимизировать этот алгоритм, чтобы использовать меньше списков, но этот способ проще всего описать.)
Сначала очистите списки и установите уровень освещенности всех блоков на ноль, а затем инициализируйте источники света, как в текущем решении. После (или во время) добавления любых блоков с ненулевым уровнем освещенности в соответствующий список.
Теперь просмотрите список блоков с уровнем освещенности 16. Если какой-либо из соседних с ними блоков имеет уровень освещенности меньше 15, установите уровень освещенности на 15 и добавьте их в соответствующий список. (Если они уже были в другом списке, вы можете удалить их из него, но это не принесет никакого вреда, даже если вы этого не сделаете.)
Затем повторите то же самое для всех остальных списков, в порядке убывания яркости. Если вы обнаружите, что блок в списке уже имеет более высокий уровень освещенности, чем должен быть в этом списке, вы можете предположить, что он уже обработан, и даже не беспокоиться о проверке своих соседей. (Опять же, может быть быстрее просто проверить соседей - это зависит от того, как часто это происходит. Возможно, вам следует попробовать оба способа и посмотреть, какой путь быстрее.)
Вы можете заметить, что я не указал, как должны храниться списки; на самом деле, любая разумная реализация должна делать это, поскольку вставка данного блока и извлечение произвольного блока являются быстрыми операциями. Связанный список должен работать, но так же, как и любая другая достойная реализация массивов переменной длины. Просто используйте то, что работает лучше для вас.
Приложение: Если большинство ваших источников света движутся не очень часто (и стены тоже не двигаются), для каждого освещенного блока может быть даже быстрее сохранить указатель на источник света, который определяет его уровень освещения (или на один из их, если несколько связаны). Таким образом, вы можете почти полностью избежать глобальных обновлений освещения: если новый источник света добавлен (или уже прояснился), вам нужно всего лишь сделать один рекурсивный проход освещения для блоков вокруг него, в то время как один из них удален (или затемнение), вам нужно обновить только те блоки, которые на него указывают.
Вы даже можете обрабатывать изменения стены следующим образом: когда стена удалена, просто начните новый рекурсивный проход освещения в этом блоке; когда один из них добавлен, выполните пересчет освещения для всех блоков, которые указывают на тот же источник света, что и на новый блок.
(Если происходит несколько изменений освещения, например, если источник света перемещается, что считается удалением и дополнением, вы должны объединить обновления в одно, используя алгоритм, приведенный выше. По сути, вы обнуляете уровень освещенности всех блоки, указывающие на удаленные источники света, добавьте любые освещенные блоки, окружающие их, а также любые новые источники света (или существующие источники света в обнуленных областях) в соответствующие списки и запустите обновления, как указано выше.)
источник