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

[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 области, то сюда стенку не ставим, а если остаётся связным - ставим. и так до тех пор, пока можно ставить стенки...

[TomCaT]

Именно так моя программа строит под IBM. Но боюсь на Speccy переводить - генерация долгая.
Правда, проверка "распада на 2 части" могла бы быть быстрее, я сецас думаю. По моему алгоритму, проходимость алгоритма ПОСЛЕ КАЖДОЙ поднятой стенки (комнатный вариант, 2 по картинкам от Sinus) проверялась по правилу правой руки. Если от одной комнаты рядом со стенкой можно дойти до отгороженной комнаты (с той стороны стенки) и вернуться затем назад (вот это, кажется, лишнее), лабиринт считается всё ещё проходимым. Иначе стенка помечается неподнимаемой. И так со всеми стенками.
Думаю, можно бы улучшить как-нибудь проверку...

2Dexus: сомневаюсь, что к-л без карты удалось пройти игру с ПЕРВОГО РАЗА. С картой всё проще...но и интерес теряется А вот если генератор лабиринтов + беск. (или очень большой) лимит времени... Тогда, имхо, было бы просто захватывающе играть.

Кстати, проверка окончания построения - нет ли какой-то прямой (не примерной, а точной) зависимости площадь/макс. число поднимаемых стенок? Может, есть формула? Я попробую собрать стат. данные по этому поводу своей прогой. Может, есть зависимость

[elf/2]

можно дернуть алгоритм из opensource игр, например angband'а (http://www.thangorodrim.net/). я когда то смотрел, там сначала комнаты случайным образом расставляют, а потом тоннели между ними организуют. исходники качественно прокомментированы и организованы