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

[ws_mason]

Меня заинтересовала эта тема. Есть сцнарий игры про лабиринт как таковой но некогда писать.

[ws_mason]

Лабиринт по второму варианту это самое оно для моей игры. Если интересно кому могу выложить всю концепцию.

[TomCaT]

Лабиринт по второму варианту это самое оно для моей игры. Если интересно кому могу выложить всю концепцию.

Выкладывай, но в целях антифлейма лучше рядом отд. тема . Имхо.

А если тебе надо помочь с генератором, обращайся, у меня 2-3 варианта есть, вот только хотелось бы ЕЩЁ поскоростнее (чем эти мои варианты). Поэтому и создал тему.

[SMT]

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

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

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

[Sinus]

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

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

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

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

[TomCaT]

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

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

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

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

[Advertiser]

[TomCaT]

Есть более другой, и хотя лабиринты с ним получаются может чуток менее "крутыми", но зато работает он сильно быстрее.

Ну, Вы на этот алгоритм хоть намекните, хоть принцип, а там уже люди сравнят и решат. Просто-напросто этот "неправильный алгоритм" -- единственный, который я знаю (и про который знаю, что он РАБОТАЕТ).

[TomCaT]

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

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

[SMT]

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

сделаю маленький пример, лабиринт 3x3, 9 клеток:

+-+-+-+
|1|2|3|
+-+-+-+
|4|5|6|
+-+-+-+
|7|8|9|
+-+-+-+

клетку 1 - в А, остальные - в Б. по очереди будем выбирать такие пары А-Б: 1-2, 2-3, 3-6, 6-9:

+-+-+-+
|1 2 3|
+-+-+ +
|4|5|6|
+-+-+ +
|7|8|9|
+-+-+-+

потом 6-5, 5-4, 4-7, 5-8

+-+-+-+
|1 2 3|
+-+-+ +
|4 5 6|
+ + + +
|7|8|9|
+-+-+-+

разве не получились тупики?

+-+-+-+
|     |
+-+-+ +
|     |
+ + + +
| | | |
+-+-+-+

кроме того, при соотв. выборе ГСЧ, получается произвольный заранее заданный лабиринт, как и в Вашем алгоритме. они делают примерно одинаковые лабиринты

связность - по правилу правой руки - самая муторная, сложная и времежрущая часть

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

[TomCaT]

сделаю маленький пример, лабиринт 3x3, 9 клеток:

+-+-+-+
|1|2|3|
+-+-+-+
|4|5|6|
+-+-+-+
|7|8|9|
+-+-+-+

клетку 1 - в А, остальные - в Б. по очереди будем выбирать такие пары А-Б: 1-2, 2-3, 3-6, 6-9:

+-+-+-+
|1 2 3|
+-+-+ +
|4|5|6|
+-+-+ +
|7|8|9|
+-+-+-+

потом 6-5, 5-4, 4-7, 5-8

+-+-+-+
|1 2 3|
+-+-+ +
|4 5 6|
+ + + +
|7|8|9|
+-+-+-+

разве не получились тупики?

+-+-+-+
|     |
+-+-+ +
|     |
+ + + +
| | | |
+-+-+-+

Да, я понял. Вы действуете с А и Б в пределах одного прямоугольника. Действительно, м/б быстрее. Я всё же думаю, MAZIACS сей алгоритм не применяли, а там лабиринты О-ГО-ГО какие качественные. Хотя может, я ошибаюсь...

кроме того, при соотв. выборе ГСЧ, получается произвольный заранее заданный лабиринт, как и в Вашем алгоритме. они делают примерно одинаковые лабиринты

Нет. В моём алгоритме не используется ГСЧ. На самом деле предварительно составляется список всех поднимаемых стенок, а затем список "рассортировывается" по ГСЧ, который сложным образом зависит от дата/времени. Т.о. повторяемость лабиринтов минимальна. Но это на IBM. Для Спекки такое малоприменимо. Разве что подсчитывать время, в течение которого юзер разглядывает меню, а затем использовать как SEED

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

Тогда объясните, что вы понимаете под проверкой связности. И почему путь между двумя точками (если эти две точки - в комнатах по обе стороны только что поднятой стенки) не указывает однозначно на наличие/отсутствие связности?

2All:

как и обещал, высылаю выдранный из MAZIACS генератор. Не удосужился дебаггнуть. Если кто-то хочет его использовать, но не знает как, пишите мне на мыло или сюда, я раскопаю свой Labirint на BASIC'е и припомню вх./вых. параметры процедурки.