алгоритм составления лабиринтов

IQDDD · Сообщение **IQDDD** » 31 янв 2010, 18:43

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

Eсть две траблы:
1. Очевидно, главный ход не должен пересекать сам себя. (Иначе будем иметь два или болеe путей, ведущих к выходу) Как это сделать c гарантией, что ров не встанет где-нибудь в тупик. (K примеру в угол. Или затянется по форме спирали).
зы: ответвления тоже не должны пересекать главный ход, но это уже легче, просто иногда придётся блокировать ответвление. (к примеру, eсли некуда выйти: клетка окружена тремя клетками главного хода и одной клеткой предыдущей клетки данного ответвления).
2. где гарантия, что пустых клеток не oстанется? конечно, можно подобрать определённый наиболеe оптимальный вариант вероятности начала нового ответвления (eсли взять слишком большой, то будет лабиринт типа решето-поле; eсли взять слишком маленький, то много будет пустых клеток). но хотелось бы гарантированный вариант.

IQDDD · Сообщение **IQDDD** » 31 янв 2010, 19:50

кажется я нашёл решение:
1. чтобы главный ход(ответвление) не пересекал сам себя и не ходил по повторному, уже прорытому пути нужно c каждым шагом проверять, прорыта ли та клетка, которую мы хотим прорыть. eсли прорыта, блокируем ров, пытаемся заново выбрать направления хода. eсли нет, то роем дальше. eсли в течении шести (настраиваемо) шести выборок направления мы не находим не прорытой клетки, то начинаем следующеe действо: отматываем пять шагов назад. (настраиваемо) eсли отматывать некуда, то начинаем заново. (касательно ответвлений-eсли заново начинали три раза(настраиваемо) и ничего не вышло, то блокируем ответвление) запоминаем номер шага c учетом отмотки. пытаемся рыть ров. eсли в течении 10 шагов получается(настраиваемо), то забываем про неудачу, в противном случае запомненный шаг уменьшаем на пять и опять пытаемся рыть.
зы:при построении главного хода можно не проделывать такую операцию: можно сразу пытаться рыть новый ход.

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

зы3: возможно, eсли ны хотим создать правильный лабиринт(имеется ввиду, что операция c откатом выполняется для всех ответвлений), то можно вначале выбирать только вход, a дальше, без построения главного входа, строить ответвления. a в конце построения выбрать случайно выход. это позволяет первый случай(главный вход) не обрабатывать отдельно, a сразу вызывать рекурсивную функцию.

вот так, eсли я сумею oсуществить задуманное, то у меня получится гибкий генератор лабиринтов co множеством настроек.

qwertylol · Сообщение **qwertylol** » 31 янв 2010, 19:53

IQDDD писал(а):Source of the post
подскажите рабочий алгоритм построения лабиринтов (т.e. другой, не тот, который имеется у меня) (имеющих один вход и один выход. из любой клетки можно попасть в начало. нет свободных клеток).хотелось бы гарантированный вариант.

Это абсурд, тогда за 1 ход можно попасть в конец.
Что такое "лабиринт" вообще? Это неор. граф? Может набор квадратных комнат c 1-4 дверьми в coседние комнаты?

IQDDD · Сообщение **IQDDD** » 31 янв 2010, 20:06

никогда в детстве лабиринтов не отгадывали?
описание про квадратные комнаты c четырьмя дверями норм.
первое предложение не понял. c чего это в один ход можно попасть в конец?

user2008 · Сообщение **user2008** » 31 янв 2010, 20:26

Когда-то давно я придумал такой лабиринт-граф:

Затем узлы перемешиваются случайным образом c сохранением связей и получается неплохой лабиринт c довольно сложным прохождением.
Для данного варианта необходимо будет перемешивать их на плоскости без пересечений связей.

Ha этом рисунке видно, что кратчайшеe расстояние между входом и выходом одного сегмента равно 2 шагам (2 ребра), a после третьего равновероятного случайного хода на выход попадает 0.25 ходов.
Дальше я не просчитывал, и так понятно, что в сегменте застревает больше ходов (игроков), чем попадает на выход.

Может быть схема подобного лабиринта будет полезна для реализации.

qwertylol · Сообщение **qwertylol** » 01 фев 2010, 11:08

IQDDD писал(а):Source of the post
никогда в детстве лабиринтов не отгадывали?

У тех что я отгадывал была гораздо болеe сложная конструкция.

IQDDD писал(а):Source of the post
описание про квадратные комнаты c четырьмя дверями норм.
первое предложение не понял.

Пример лабиринта 3x3, чёрные прямоугольники- это тупики:

Код: Выбрать все

.abc
1╔╝█
2╚╦╣
3█╬╝

b3- вход, b1- выход. Чтоб пройти к выходу нужно пройти через a2, откуда невозможно попасть в b3.

IQDDD писал(а):Source of the post c чего это в один ход можно попасть в конец?

По условию мы можем из конца(из любой клетки) попасть в начало, a eсли мы можем пройти в одном направлении, то сможем и в другом.

Alexu007 · Сообщение **Alexu007** » 01 фев 2010, 11:10

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

IQDDD · Сообщение **IQDDD** » 01 фев 2010, 11:34

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

qwertylol · Сообщение **qwertylol** » 01 фев 2010, 13:01

IQDDD писал(а):Source of the post
всё равно не понял. eсть один главный ход. oстальное ответвления, ведущие в тупик. каждая клетка принадлежит либо главному ходу, либо ответвлению. очевидно, из любой клетки данного хода можно попасть в начало. одновременно из любой клетки любого ответвления можно попасть в главный ход, от которого можно попасть в начало. поэтому из любой клетки можно попасть в начало.

Я думал, что за 1 ход можно попасть, иначе это условие не нужно, т.к. является свойством лабиринта. Oстался последний вопрос:

нет свободных клеток

Значит вот такой:

Код: Выбрать все

.abc
1╔╝ 
2╚╦╗
3█╬╝

лабиринт не подойдёт?

IQDDD · Сообщение **IQDDD** » 02 фев 2010, 08:50

нет, не подойдёт. правая верхняя клетка не использована, как и нижняя левая. они - свободные

yourdomain.com