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

Может кто-нибудь сталкивался подобной задачей...
Зараннее спасибо.

ЗЫ. Все пространство в "подземелье" должно быть заполнено, как на скриншоте, только рамка должна быть прямоугольной.

Здравствуйте, AVSCoder, Вы писали:

AVS>Нужен алгоритм генерации случайного подземелья, но не лабиринта, а чего-нить наподобие этого

Нужно: построить подземелье размером X*Y со стенами толщиной в 1 клетку.

Представим себе, что такое подземелье построено — это кирпичная кладка из кирпичей разного размера (размером не менее 1*1), между которыми лежит слой цемента как раз в 1 клетку.

Избавляемся от цемента: нарастим каждый кирпич вправо и вверх на 1 клетку. Получаем...
Эквивалентное подземелье размером (X+1)*(Y+1), заполненное кирпичами размером не менее 2*2 без прослойки.

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

###
..#
..X###X   <- X не может быть дверью, т.к. нет доступа к пространству комнаты
..#...#
1.#.2.#
..#...#
..####X##
..#.....#
..#..3..#

Либо мы допускаем извилистые проходы и сильно усложняем себе задачу.

Всё. Теперь начинаем строить подземелье.

1)
Заполняем "стакан" (X+1)*(Y+1) кирпичами случайного размера, причём очередной кирпич кладём в крайнюю нижне-левую позицию.
Если попытка неудачная — возвращаемся к предыдущему кирпичу, уменьшая его размер.
Когда попытка неудачная:
— если кирпич туда не помещается (он должен быть размером 2*2 или больше),
— если граф достижимости уже положенных кирпичей оказывается несвязным (вершины графа — кирпичи, рёбра — все допустимые двери)

2)
Берём граф достижимости полученного подземелья и удаляем часть рёбер, сохраняя связность. Фактически, мы строим лабиринт на графе.

3)
Для оставшихся рёбер — прорубаем двери. Если ребро связывает два кирпича, чья общая стена шире, чем 1 клетка — рубим дверь в случайной позици.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, AVSCoder, Вы писали:

AVS>>Нужен алгоритм генерации случайного подземелья, но не лабиринта, а чего-нить наподобие этого

К>Нужно: построить подземелье размером X*Y со стенами толщиной в 1 клетку.

К>Представим себе, что такое подземелье построено — это кирпичная кладка из кирпичей разного размера (размером не менее 1*1), между которыми лежит слой цемента как раз в 1 клетку.

К>Избавляемся от цемента: нарастим каждый кирпич вправо и вверх на 1 клетку. Получаем...
К>Эквивалентное подземелье размером (X+1)*(Y+1), заполненное кирпичами размером не менее 2*2 без прослойки.

К>Теперь займёмся дверями. Дверь — это проём в стене, а стены (цемент), как мы помним, интегрированы в кирпичи справа и сверху. То есть, дверь может быть любой клеткой правого или верхнего ряда, кроме правого верхнего угла. И вести к любой клетке смежного кирпича, кроме левого верхнего и правого нижнего углов.
К>

К>###
К>..#
К>..X###X   <- X не может быть дверью, т.к. нет доступа к пространству комнаты
К>..#...#
К>1.#.2.#
К>..#...#
К>..####X##
К>..#.....#
К>..#..3..#
К>

К>Либо мы допускаем извилистые проходы и сильно усложняем себе задачу.

К>Всё. Теперь начинаем строить подземелье.

К>1)
К>Заполняем "стакан" (X+1)*(Y+1) кирпичами случайного размера, причём очередной кирпич кладём в крайнюю нижне-левую позицию.
К>Если попытка неудачная — возвращаемся к предыдущему кирпичу, уменьшая его размер.
К>Когда попытка неудачная:
К>- если кирпич туда не помещается (он должен быть размером 2*2 или больше),
К>- если граф достижимости уже положенных кирпичей оказывается несвязным (вершины графа — кирпичи, рёбра — все допустимые двери)

К>2)
К>Берём граф достижимости полученного подземелья и удаляем часть рёбер, сохраняя связность. Фактически, мы строим лабиринт на графе.

К>3)
К>Для оставшихся рёбер — прорубаем двери. Если ребро связывает два кирпича, чья общая стена шире, чем 1 клетка — рубим дверь в случайной позици.


Спасибо за ответ.
Не совсем понятный алгоритм...
Однако хотелось бы узнать есль ли у кого-нибудь готовые примеры или ссылки на что можно посмотреть.

Здравствуйте, AVSCoder, Вы писали:

Я же в этой

Автор: AVSCoder
Дата: 15.12.05

ветке уже решил задачу.

ЗЫ Кросспостинг запрещен правилами сайта.