Алгоритм заполнения области комнатами и лабиринтом

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

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

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

1) Выбор отправных точек.

Я использую опцию, названную Степенью детализации (Granularity), для выбора точки. Если Granularity=1, любая старая точка может быть выбрана, и концы лабиринта как кусок стены в большинство случаев. Если Granularity=2, то точки выбраны на каждом другом ряду/колонке, так, чтобы мужде ними осталось место. Granularity=2 производит лабиринты с коридорами в одну ячейку. Чем более высока степень детализации, тем шире коридоры. Остерегайтесь выбора Степени детализации, которая не соответствует фактору размера лабиринта, или Вы можете получить тощие коридоры на границах, или удвоенные стены.

(SX, SY) - точка
SX = Granularity * (rand() % (MAPWIDTH/Granularity));
SY = Granularity * (rand() % (MAPHEIGHT/Granularity));

2) Длина стен

Я люблю установить минимальную и максимальную длину стен. Многие стены, конечно, будут остановлены до выбранной длины, но в среднем ваши стены будут попадать в пределах диапазона. Min=2 Max=4 произвел бы лабиринт с большим количеством крошечных небольших стен, в то время как Min=16 Max=32 произвел бы лабиринт с длинными, прямыми коридорами.

3) Число стен

Вы можете изменить плотность лабиринта, изменяя число стен. Я вообще использую N = число "попыток", чтобы рисовать, если подходящий точка может быть расположена. Отправные точки выбраны, только если местоположение - не стена, так алгоритм не войдет в бесконечный цикл поиска местоположения, когда все доступные местоположения заполнены.

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

Недостаток в настоящее время состоит в том, что карты смотрятся только подобными лабиринту. Приложенные, отдельные комнаты редки, как Вы увидите, если попробуете это. Я люблю смешивать этот алгоритм с одним из размещающих беспорядочно расположенные *шаблонные* доли. Другими словами, я разместил бы некоторые специальные комнаты (хранилища, тронные залы, тюремные корпуса темниц, и т.д ...), после чего заполнил бы остальное прежним алгоритмом, используя Степень детализации 4 или возможно даже 8, для широких коридоров, и приличного размера комнат. Уровни имеют тенденцию быть довольно скучными, если Вы не смешиваете алгоритмы.

Так или иначе, у меня есть надежда, что эта статья даст Вам некоторые собственные идеи.



Автор: Josh (VertexNortmal) Tippetts.
Источник: Fill-area-with-rooms and Maze - algorithms.
Перевел: Сергей В. Ждановских [Alchemist], 04.08.2005.