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

@Warship · Регистрация: 16.07.2010

Студворк — интернет-сервис помощи студентам

Всех приветствую!
Требуется помощь в решении следующей задачи:
Мне нужно сгенерировать лабиринт в виде двухмерного массива hor * vert, с указанной старторой точкой пути (startHor, startVert) и указанной длиной пути (pathLength).
Причем, путь прохождения лабиринта должен существовать только один (а длина его как-раз и задается pathLength).

Что имеется на сейчас:
Мой двухмерный массив заполняется пустыми блоками (0x00). Затем в этом элементе массива (который соответствует ячейке лабиринта) можно задавать стенки побитовым ИЛИ, т.е.:
WALL_TOP | WALL_RIGHT | WALL_BOTTOM - имеем ячейку с выходом только слева.

Собственно, вопрос: как таким методом можно сгенирировать мой лабиринт? Буду очень благодарен за пример кода или конструктивную крикиту такого подхода (желательно с предложением лучшего

).

@Хохол · 12.09.2010, 08:40

Прохождение лабиринта == выход из него?

Добавлено через 22 минуты
А для чего могло понадобиться указание длины пути? Просто интересно.
А то для лабиринта размером 100 x 100, стартом в точке (2;2) и pathLen = 9000 решение существует, но его как-то сложновато найти. У вас такие хардкорные тесты могут быть?

@Warship · 12.09.2010, 11:39 **[ТС]**

Прохождение лабиринта - да, именно выход.

Длина пути - влияет на сложность прохождения. Но для упрощения этот параметр можно на деле и опустить (а для изменения сложности буду крутить горизонтальную и вертикальную размерность - тоже норм будет). Ну и таких тестов не будет тоже

Собственно, я за день так и не продвинулся дальше. Гуглом нарыл описания некоторых алгоритмов, но они весьма просты и генерят лабиринт на основе "прогрызания" (изначально все заполняется "стеной", в которой потом "прорубаются" ходы - вначала главный, а от него ветвления). Такой подход немного не подходит для реализации моей задачи, т.к. в нем используетя принцип "ячейка == ход или стенка", у меня же в клетку можно пройти, даже если в ней установлены три стены (в ней ж останется один ход)

@Хохол · 12.09.2010, 12:08

А чем плохо прогрызание-то? Грызите стенки и все.

Добавлено через 1 минуту
Простейший алгоритм:

Code
1
2
3
заполнили все стенками
пока нет выхода из лабиринта
     сносим одну стенку

@Warship · 12.09.2010, 12:18 **[ТС]**

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

Вы не могли бы более подробно описать алгоритм прогрызания?
Я, когда строил тестовую реализацию, столкнулся с непонятностью техники генерации ветвлений от основного пути (который строится вначале и соединяет стартовую точку и собственно выход).

@Хохол · 12.09.2010, 12:24

Никакой проблемы с вашим выбором представления стен нет. Не понимаю, чем удаление стены-границы сложнее чем удаление стены-клетки?

Добавлено через 2 минуты

Code
1
2
3
заполнили все стенками
пока нет выхода из лабиринта   //проверяем поиском в глубину
     сносим одну стенку        //выбираем рандомно

вот и все более подробное описание алгоритма.

@Warship · 12.09.2010, 12:25 **[ТС]**

Я тоже не понимаю

С подобными алгоритмами я столкнулся всего-лишь два дня назад, поэтому мои знания в данной теме минимальны.

Vovan-VE · 12.09.2010, 12:26

Помнится, алгоритм примерно такой.

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

Изначально все клетки свободны, все стена проставлены.

Построение ветки (такой-то длины): Из списка свободных клеток берем случайную клетку и в Матрице по свободным клеткам строим ход в случайном направлении (убираем стены, делаем клетки занятыми) до тех пор, пока есть соседние свободные клетки и не закончится Длина прохода. Конец хода по возможности присоединяем (убираем стены) к случайной соседней занятой клетке.

Строим ходы, пока не закончатся свободные клетки.

Не забываем правильно синхронизировать Матрицу и Массив свободных клеток.

Предельная длина ветки - это и есть сложность лабиринта: чем длинее - тем сложнее.

Не по теме:

PS: Был когда-то код на Паскале, но, к сожалению, куда-то сплыл. :(

@Хохол · 12.09.2010, 12:29

Предлагаю сначала научиться генерить рандомный лабиринт, а потом уже, при желании, накладывать какие-то свойства

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Warship 2 / 2 / 0 Регистрация: 16.07.2010 Сообщений: 55

	Генерация лабиринта 11.09.2010, 09:07. Показов 9067. Ответов 8 Метки нет (Все метки) Всех приветствую! Требуется помощь в решении следующей задачи: Мне нужно сгенерировать лабиринт в виде двухмерного массива hor * vert, с указанной старторой точкой пути (startHor, startVert) и указанной длиной пути (pathLength). Причем, путь прохождения лабиринта должен существовать только один (а длина его как-раз и задается pathLength). Что имеется на сейчас: Мой двухмерный массив заполняется пустыми блоками (0x00). Затем в этом элементе массива (который соответствует ячейке лабиринта) можно задавать стенки побитовым ИЛИ, т.е.: WALL_TOP \| WALL_RIGHT \| WALL_BOTTOM - имеем ячейку с выходом только слева. Собственно, вопрос: как таким методом можно сгенирировать мой лабиринт? Буду очень благодарен за пример кода или конструктивную крикиту такого подхода (желательно с предложением лучшего ). 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	12.09.2010, 08:40
	Прохождение лабиринта == выход из него? Добавлено через 22 минуты А для чего могло понадобиться указание длины пути? Просто интересно. А то для лабиринта размером 100 x 100, стартом в точке (2;2) и pathLen = 9000 решение существует, но его как-то сложновато найти. У вас такие хардкорные тесты могут быть? 0

@Warship 2 / 2 / 0 Регистрация: 16.07.2010 Сообщений: 55
	12.09.2010, 11:39 [ТС]
	Прохождение лабиринта - да, именно выход. Длина пути - влияет на сложность прохождения. Но для упрощения этот параметр можно на деле и опустить (а для изменения сложности буду крутить горизонтальную и вертикальную размерность - тоже норм будет). Ну и таких тестов не будет тоже Собственно, я за день так и не продвинулся дальше. Гуглом нарыл описания некоторых алгоритмов, но они весьма просты и генерят лабиринт на основе "прогрызания" (изначально все заполняется "стеной", в которой потом "прорубаются" ходы - вначала главный, а от него ветвления). Такой подход немного не подходит для реализации моей задачи, т.к. в нем используетя принцип "ячейка == ход или стенка", у меня же в клетку можно пройти, даже если в ней установлены три стены (в ней ж останется один ход) 0

@Warship 2 / 2 / 0 Регистрация: 16.07.2010 Сообщений: 55
	12.09.2010, 12:18 [ТС]
	В прогрызании я уперся в "квадратность" последующей отрисовки модели, стены должны получаться размеров с ячейку. В моем варианте (на который видимо стоит забить ввиду его чрезмерной сложности) стенки - свойство самой клетки (а не тип клетки, как при прогрызании), поэтому их можно будет отрисовывать специфически. Вы не могли бы более подробно описать алгоритм прогрызания? Я, когда строил тестовую реализацию, столкнулся с непонятностью техники генерации ветвлений от основного пути (который строится вначале и соединяет стартовую точку и собственно выход). 0

@Warship 2 / 2 / 0 Регистрация: 16.07.2010 Сообщений: 55
	12.09.2010, 12:25 [ТС]
	Я тоже не понимаю С подобными алгоритмами я столкнулся всего-лишь два дня назад, поэтому мои знания в данной теме минимальны. 0

Vovan-VE 13210 / 6599 / 1041 Регистрация: 10.01.2008 Сообщений: 15,069
	12.09.2010, 12:26
	Помнится, алгоритм примерно такой. Есть Матрица клеток будующего лабиринта. Есть Массив свободных клеток, где свободные клетки хранятся не важно в каком порядке. Каждая клетка в Мартице содержит флаги стен (это у Вас уже есть), флаг свободна они или нет и индекс в Массиве свободных клеток. В свою очередь, элементы Массива свободных клеток содержат координаты соответствующей клетки. Изначально все клетки свободны, все стена проставлены. Построение ветки (такой-то длины): Из списка свободных клеток берем случайную клетку и в Матрице по свободным клеткам строим ход в случайном направлении (убираем стены, делаем клетки занятыми) до тех пор, пока есть соседние свободные клетки и не закончится Длина прохода. Конец хода по возможности присоединяем (убираем стены) к случайной соседней занятой клетке. Строим ходы, пока не закончатся свободные клетки. Не забываем правильно синхронизировать Матрицу и Массив свободных клеток. Предельная длина ветки - это и есть сложность лабиринта: чем длинее - тем сложнее. Не по теме: PS: Был когда-то код на Паскале, но, к сожалению, куда-то сплыл. :( 1

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	12.09.2010, 12:29
	Предлагаю сначала научиться генерить рандомный лабиринт, а потом уже, при желании, накладывать какие-то свойства 0