Это интересный вопрос из-за некоторых проблем, которые возникают, когда вы начинаете перемещать алгоритмы в более высокие измерения.
Проблема 1: Основные пути занимают небольшой объем
Начнем с простого математическое наблюдение. Алгоритм генерации уровней работает путем вычисления случайного пути от верхнего ряда мира к нижнему ряду мира. На каждом шаге этот путь может двигаться влево, вправо или вниз, но никогда не делает шаг назад туда, откуда он начинается. Предполагая, что эти три варианта равновероятны, первый шаг на определенном уровне имеет 2/3 шанса остаться на том же уровне, а каждый последующий шаг имеет максимум 1/2 шанса остаться на том же уровне. (Это 50%, без учета стен). Это означает, что ожидаемое количество плиток на уровне будет не более
1 × (1/3) + (2/3) × (1 + 2) (поскольку там 1/3 шанс немедленно сдвинуться вниз, иначе (2/3) шанс получить одну комнату, плюс количество комнат, которые вы получаете в результате случайного процесса, который останавливается с вероятностью 50% на каждом шаге)
= 2,5
Это важно, потому что это означает, что если бы ваш мир представлял собой сетку n × n, вы ожидали бы иметь только около 2,5 «используемых» ячеек на уровень в мире, что в сумме составляет примерно 2,5n » использовали "клетки на пути". Учитывая, что мир имеет размер n × n, это означает, что
2,5n / n 2 = 2,5 / n
доля ячеек мира будет на основном пути, поэтому n должно быть маленьким, чтобы часть мира не на главном пути не стала слишком большой. В видео, которое вы связали, выбрано n = 4, что дает долю 2,5 / 4 = 62,5% мира будет на основном пути. Это хорошая смесь между фразами «Я бы хотел добиться прогресса» и «Мне нужен побочный квест, пожалуйста». И помните, это число является переоценкой количества ячеек пути по сравнению с ячейками побочного квеста.
Теперь давайте сделаем это в трех измерениях. Как и раньше, мы начинаем с верхнего «среза», затем произвольно перемещаемся вперед, назад, влево, вправо или вниз на каждом шаге. Это дает нам максимум 4/5 шанса остаться на нашем уровне с нашим первым шагом, а с этого момента максимум 3/4 шанса остаться на уровне. (Опять же, это завышенная оценка.) Выполнение математических расчетов снова дает
1 × 1/5 + (4/5) × (1 + 4)
= 1/5 + (4/5) × 5
= 4,2
Таким образом, это означает, что в среднем 4,2 ячейки на уровень будут на основном пути для общей длины пути в среднем, если мы переоцениваем. В мире n × n × n это означает, что доля сайтов «на пути» к сайтам «вне пути» составляет
4,2n / n 3
= 4,2 / n 2
Это означает, что ваш мир должен быть очень маленьким, чтобы основной путь не составлял тривиальную долю от общего пространства. Например, выбор n = 3 означает, что у вас будет чуть менее 50% мира вне основного пути и доступного для исследования. Выбор n = 4 даст вам 75% мира вне основного пути, а выбор n = 5 даст вам более 80% мира вне основного пути.
Все это означает, что, сразу же вам нужно уменьшить размер вашего мира, чтобы алгоритм, основанный на основном пути, не оставлял мир в основном пустым. Это не обязательно плохо, но об этом нужно помнить.
Проблема 2: Увеличивается пространство для шаблона
Следующая проблема, с которой вы столкнетесь, - это создание вашей библиотеки шаблонов "для конфигураций помещений. Если вы находитесь в 2D-пространстве, есть четыре возможных входа и выхода в каждую ячейку, и для любого подмножества этих четырех входов (возможно, за исключением ячейки, в которой нет входов вообще) может потребоваться шаблон. Это дает вам
2 4 - 1 = 15
возможных шаблонов входа / выхода для работы, и это только для того, чтобы охватить набор всех возможных вариантов.
В трех измерениях есть шесть возможных входов и выходов из каждой ячейки, поэтому имеется
2 6 - 1 = 63
возможные комбинации входа / выхода, которые следует учитывать, поэтому вам понадобится множество шаблонов, чтобы учесть это. Вероятно, вы можете уменьшить это, используя вращательную симметрию, но это важный момент, о котором следует помнить.
Проблема 3: застревание
Видео, на которое вы ссылаетесь, упоминается как достоинство 2D-генерации алгоритм тот факт, что
он создает веселые и увлекательные уровни, на которых игрок не может легко застрять.
В 2D-пространстве большинство ячеек, за некоторыми исключениями , будет рядом с основным путем. В трехмерном пространстве большинство ячеек, за некоторыми исключениями, не будет примыкать к основному пути. Более того, в 2D-пространстве, если вы заблудитесь, нетрудно найти обратный путь - есть только столько направлений, сколько вы можете go, и вы можете увидеть весь мир сразу. В 3D намного легче заблудиться, потому что вы можете предпринять шаги, которые уводят вас дальше от основного пути, чем в 2D-пространстве, и потому, что, если вы все же заблудитесь, есть больше вариантов, которые нужно учитывать, как вернуться. (Кроме того, вы, вероятно, не сможете увидеть весь мир сразу в трехмерном пространстве.)
Вы могли бы решить эту проблему, просто не заполняя все трехмерное пространство ячеек местами, которые стоит посетить. Вместо этого разрешайте заполнять только те ячейки, которые находятся на расстоянии одного или двух шагов от основного пути, интересными побочными квестами, так как таким образом игрок не сможет слишком затеряться в сорняках.
Подводя итог * Эти три пункта предполагают, что для того, чтобы этот подход работал в 3D, вам, вероятно, потребуется сделать следующее. Сделайте мир меньше, чем вы думаете, что вам может понадобиться , так как в противном случае отношение ячеек на пути к ячейкам вне пути будет большим. туда, где они были раньше. Будьте готовы создать множество шаблонов или выяснить, как использовать ротацию, чтобы сделать ваши шаблоны применимыми в большем количестве мест. Удачи!