Генерация лабиринтов

[TomCaT]

Ищу совета и информации по этому поводу. Единственный генератор лабиринтов с настраиваемыми параметрами мне удалось написать только под IBM. И то подтормаживает.
Второй неплохой генератор, с которым я знаком -- встроен в MAZIACS. Однако он ненастраиваемый, создаёт битовый лабиринт 64x64 причём правая часть каждой строки соединяется не с левой частью не самой себя, а строки следующей(!) -- явное упрощение для экономии времени создания. Когда-то я выдирал этот генератор и строил на его основе свои проги с лабиринтами. Однако до сих пор не дебаггил и потому не в курсе насчёт алгоритма...

Выдранный генератор из MAZIACS, а также свою прогу на Delphi 6 (с исходниками) могу выложить по требованию. Но больше всего меня интересует, не знает ли кто быстрого и дост. универсального алгоритма построения 2D лабиринтов в прямоугольнике?

[Advertiser]

[Sinus]

Т.е. тебе нужен 2D лабиринт, причём для любых точек (x1,y1) и (x2,y2) где (x1,y1)!=(x2,y2) и lab[y1][x1]=FLOOR и lab[y2][x2]=FLOOR существует путь между точками (x1,y1) и (x2,y2).
По этому поводу есть какая-то спековская книжка по бейсику, там есть примерчик. Книжку мне искать лень, если будет время, то накатаю сам.
Однако, на самом деле сделать так, что бы этот генератор лаиринтов тормоил довольно сложно

PS. Тебе нужен лабиринт вида (1) или вида (2)? (см. аттач)

[rasmer]

Т.е. тебе нужен 2D лабиринт, причём для любых точек (x1,y1) и (x2,y2) где (x1,y1)!=(x2,y2) и lab[y1][x1]=FLOOR и lab[y2][x2]=FLOOR существует путь между точками (x1,y1) и (x2,y2).
По этому поводу есть какая-то спековская книжка по бейсику, там есть примерчик. Книжку мне искать лень, если будет время, то накатаю сам.
Однако, на самом деле сделать так, что бы этот генератор лаиринтов тормоил довольно сложно

PS. Тебе нужен лабиринт вида (1) или вида (2)? (см. аттач)

ну уж поищи книжицу, сделай милость, или вспомни название, народ сканнлист выложит...

[TomCaT]

Вид лабиринта не имеет значения. Но т.к. вариант 2 легко преобразовывается в 1 (я встроил такую фичу в свою прогу), то лучше 2. Но 1 меня тоже бы устроил.

[TomCaT]

Однако, на самом деле сделать так, что бы этот генератор лаиринтов тормоил довольно сложно

Нет, если лабиринт, скажем, 20x20, ето без проблем. А вот попробуйте хорошо салгоритмизировать (во загнул генератор для 80x80... Такие большие лабиринты, может, и редки в играх. Но ведь подавляющее большинство интересных игр имеют один-единственный, заранее сделанный лабиринт. Обидно, что второй, третий... пятый раз проходишь уже по проторенной дорожке, обходя тупики и опасности. Вот и захотелось мне разработать свой генератор, причём такой, на основе которого игра каждый раз создавала новое игровое поле. Ну пусть даже 2D, зато - представьте: запускаешь Saboteur, и каждый раз перед тобой другое здание Конечно, до этого далеко, но ведь в принципе осуществимо?

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

[Dexus]

Ну пусть даже 2D, зато - представьте: запускаешь Saboteur, и каждый раз перед тобой другое здание

Тяжелый случай.
Я так думаю - что саботер (тем более второй) было бы невозможно пройти, если бы карта была изменяемой.

[SMT]

ну если с отгрузками, другое дело

[SMT]

а навскидку, самый простой алгоритм такой: начиная с поля без стенок, случайно выбираем, куда поставить стенку. если лабиринт не распадается на 2 области, то сюда стенку не ставим, а если остаётся связным - ставим. и так до тех пор, пока можно ставить стенки...

[SMT]

если ещё подумать, можно предложить делить карту на несколько частей извилистыми линиями, в каждой замкнутой области строить свой лабиринт (ведь время построения зависит от площади нелинейно и быстрее создать 4 по 16 клеток, чем 1 из 64) и сломать по одной из стен в изначальной линии между подчастями, чтобы соединить лабиринты в один

а вот что получится, если дальше развить эту идею. пусть каждая клетка может быть в одном из множеств А или Б. клетки из А - те, которые внутри лабиринта, Б - внешние для лабиринта. алгоритм простой: ставим все возможные стенки на поле. одну любую клетку включаем в А, остальные - в Б
шаг1. выбираем случайно одну клетку из Б, граничащую с некоторой клеткой из А (можно наоборот). стираем между ними стенку, перемещаем клетку из множества Б а А. повтор шага 1, пока Б не пусто

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

[TomCaT]

а вот что получится, если дальше развить эту идею. пусть каждая клетка может быть в одном из множеств А или Б. клетки из А - те, которые внутри лабиринта, Б - внешние для лабиринта. алгоритм простой: ставим все возможные стенки на поле. одну любую клетку включаем в А, остальные - в Б
шаг1. выбираем случайно одну клетку из Б, граничащую с некоторой клеткой из А (можно наоборот). стираем между ними стенку, перемещаем клетку из множества Б а А. повтор шага 1, пока Б не пусто

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

По порядку - если Ваш вариант с мн-вами А и Б служит как бы для "расширения данного лабиринта в произвольном направлении" (как я понял), то как вы собираетесь организовывать незабвенные тупики?

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