Комментарии 19
Примерно 20 лет назад я тоже придумывал алгоритм генерации лабиринта для самопальной игры.
Механизм был следующий: сначала в пустом пространстве рисуем псевдослучайный путь. Главное его длина. После чего заполняем псевдослучайными стенками все, кроме этого пути.
Путь и есть верный способ прохода лабиринта, но часто обнаруживались и альтернативные маршруты. Конечно их можно обнаруживать каким либо алгоритмом и блокировать установкой стены.
https://habr.com/ru/articles/667576/
Простите мне мое занудство, но Хабр превращается в место для "еще одной курсовой/ задачки на курсе". Почему-то каждый студент считает свои труды уникальными. При этом я положительно отношусь к труду автора. Но где новизна? Где сравнение, анализ вариантов, сложности? Просто "смотрите, я написал программу, и она даже работает". Прекратите писать стать-записки о программке для студента на 2 дня.
Мне пожаловались о том, что как раз таки статья которую вы прикрепили, не раскрывает полностью суть данного алгоритма, и лабиринт получается не идеальным.
Плюс в статье, которые вы скинули, нет толкового разбора пошагово на определённых псевдослучайных числах, и поэтому понимание реализации алгоритма на бумаге ухудшается.
Также в той статье не написано как правильно объединять множества, потому что многие считают, что сама по себе ячейка в строке является множеством, но нет, она лишь принадлежит определённому множеству
Напрашивается оптимизация: когда сливаете два множества – надо перекрашивать меньшее в цвет большего (не смотрел код, может, вы так и сделали?)
При случайном выборе ставить/не ставить стенку – какая нужна вероятность установки стены? 0.5? А как повлияет на устройство лабиринта изменение этого параметра?
Структура лабиринта везде однородна или верхний и левый края имеют статистические отличия? Если имеют – можно ли от этого избавиться (например, сделав вероятность стенки зависящей от координат)?
1) Оптимизацию по поводу сливания в более выгодную сторону я не делал у себя в коде, так как это не влияет, в любом случае надо перебирать всю строку, и присваивание копированием примитивных типов работает за константное время
2) Вероятности ставить стену и не ставить стену равны, если например сделать вероятность ставить стенки равной 1, то структура лабиринта будет примерно такой:
Каждая строка, кроме последней, будет иметь всё вертикальные стенки и ни одной горизонтальной, а последняя строка будет иметь всё горизонтальные стенки и ни одной вертикальной
Если же наоборот, вероятность ставить стену 0, то ситуация поворачивается в обратную сторону, первая строка не будет иметь ни вертикальных стенок ни горизонтальных, остальные строки будут иметь все вертикальные стенки
3) Не понял сути вопроса про однородность лабиринта.
3 – вы отчасти ответили (при вероятности, близкой к 0 или 1 – первая или последняя стена соответственно будет отличаться от остальных, если не строго 0/1 – соседние тоже, но уже меньше), а вот что будет при 0.5? Будет полоса, в которой больше вертикальных/горизонтальных линий или всё выровняется? А если будет – то можно ли от неё избавиться, сделав вероятность функцией от номера строки?
Ну и по столбцу тоже может быть какая-то неоднородность.
В общем, поведение алгоритма достаточно неочевидно (за исключением просто доказываемого факта корректного построения лабиринта), есть резон его исследовать (или найти готовое исследование, наверняка автор алгоритма этим занимался).
Это точно хороший алгоритм? Похоже, что среди множества возможных лабиринтов генерация одних лабиринтов более вероятна, чем других.
Например я для поля 2х2 есть всего 4 варианта лабиринта, но вероятность стенки между верхними квадратами больше, чем остальные варианты.
Например, можно обнаружить неравномерность даже на анимации вначале статьи. Количество стенок в верхнем ряду больше, чем в нижнем или в боковых столбцах. Исходя из симметрии, я бы ожидал одинакового распределения. Есть вероятность, что можно проследить и другие паттерны, например неравномерность между вертикальными или горизонтальными стенками.
В этом и суть псевдослучайных чисел, они не случайные, эти числа получаются путем математических алгоритмов, поэтому и такой результат
Математические алгоритмы гегерации псевдослучайных чисел могут давать хорошее распределение. Дело в том, как алгоритм их использует, он изначально не рассчитан генерировать варианты с равной вероятностью.
Просчитайте вероятности для 2х2. Если я правильно понял, то алгоритм ставит стенку между двумя верхними квадратами с вероятностью 50% при первом вызове рандома. И на этом всё, псевдослучайных числа дальше не имеют значения.
В одном из разборов этого алгоритма отмечалось, что генерация самой нижней строки "характеризуется" длинными коридорами. Даже предлагались варианты, как минимизировать их. Лично меня, эта особенность дико раздражает.
Помню в детстве рисовал подобные лабиринты в тетрадке. Пока рисовал, основной моей задачей было запутать путь чтобы его было сложнее пройти. И вот щас возникает вопрос, насколько он трудно проходимый получается? Есть возможность оценить?
Генерация Лабиринта | Алгоритм Эллера