Генерация и решение из лабиринта методом поиска в глубину на графе

Генерация и решение из лабиринта методом поиска в глубину на графе

1496

Это 1-ый из пары запланированных статей, посвященных генерации и решения лабиринтов. В данной статье мы побеседуем о более обычный в реализации метод, используемый для сотворения «безупречного» лабиринт » и ее применение для поиска пути.
Метод не самый стремительный, достаточно требовательны, по сопоставлению с Эйлеровой либо метод Крускала, но чрезвычайно прост в реализации и дозволяет создавать ветвящиеся лабиринты с чрезвычайно длинноватой тупиковой ветки. Мы разглядим метод, основанный на поиске с возвратом, что дозволяет создавать лабиринты без циклов, с той только путь меж 2-мя точками.
Заинтересованных — прошу под кат.
Ссылки на британский язык и ресурсов проекта вы отыщите в конце статьи. Примеры кода на языке Си, а также полный начальный код проекта доступен на github под лицензией GNU gplv3 нет. В русскоязычном вебе чрезвычайно не достаточно инфы о методы генерации лабиринтов, что послужило предпосылкой для написания данной статьи.
Описание метода
Примечание: предполагается, что сначало любая ячейка может иметь стенки со всех 4 сторон, отделяя ее от примыкающих клеток.
По другому, раз стек не пуст
1. Сделать начальный текущей ячейке и пометить его как посетил. По другому
1. Вынуть клеточку из стека
2. Выберите случайную ячейку из примыкающих
3. 2. Пока есть непросмотренные клеток
1. Удалить стенку меж текущей ячейки и избранной
4. Сделать его текущим
3. Надавите на текущую ячейку в стеке
2. 1. Сделать избранные в текущей ячейке и пометить его как посетил. Выбрать случайный непосещенных клеточки, сделать его текущим и пометить как посетил. Раз текущая ячейка имеет непосещенных соседей
1. 2.
Вы, наверняка, увидели, что при выполнении условия 3, готовый лабиринт, возможно, будет иметь единичный масштаб. Это условие врубается в метод в виде исключения, на практике, при обычной работе метода и правильных начальных данных, то он никогда не выполняется.
Реализация
Как уже упоминалось выше, предполагается, что в начале метода все клеточки разделены стенками.
< — Исходная матрица. Иллюстрация метода
0.
< — Выберите исходную точку. 1.
2.1. < — Перейти к случайной соседке непосещенных пока никаких.
< — Непосещенных соседей нет. 2.2. Возвращение обратно в стек до тех пор, пока нет непосещенных соседей.
2.1. < — Непосещенных соседей. Перейти к случайной непосещенных соседа.
2. < — Нет непосещенных клеток. Лабиринт генерируется.
Код
Приступаем к самому увлекательному.
Для удобства мы согласны с тем, что все типы клеток указан в объявлении. Мы будем действовать по порядку и поначалу сгенерировать начальные матрица, с которой будет работать метод.
инт лабиринт[высота][ширина]; //создание матрицы — двумерный массив
для(я = 0; я < высота; я++){
для подпункте J = 0; J с < Ширина; с J++){
раз((я % 2 != 0 && J в% 2 != 0) && //Раз ячейка нечетная по X и Y,
(я < Высота-1 && J в < Ширина-1)) //и он размещен в пределах стенок лабиринта
лабиринт[я][Дж] = ячейка; //эта ячейка
еще лабиринт[я][Дж] = стенка; //в других вариантах это стенка. }
}

Сейчас, когда все заготовки изготовлены, можно приступить к генерации.
оператор typedef struct (структура ячейки{ //структура для хранения координат клеток в матрице
без знака int х;
без знака int у;
} ячейки;

оператор typedef struct не cellString{
клеточка* клеточки;
Размер int без знака;
} cellString;

Структуры существенно упростит жизнь в обмене информацией меж функциями.
Кусочек кода, ответственный за создание:
сотовый startCell = {1, 1}
сотовый currentCell = startCell;
сотовый neighbourCell;
делать{
cellString соседей = getNeighbours(ширина, высота, лабиринта, исходную, 2);
раз(соседями.Размер != 0){ //Раз ячейка непосещенных соседей
randNum = randomRange(0, соседями.Размер-1);
neighbourCell = cellStringNeighbours.клеток[randNum]; //выбрать случайный сосед
толчок(разум.исходную); //добавляем текущую точку в стек
лабиринт = removeWall(currentCell, neighbourCell, лабиринт); //убрать стенки меж текущим и sosandra очков
currentCell = neighbourCell; //сделать последующий текущей точки и пометить его посетил
лабиринт = setMode(разум.исходную д’.лабиринта, посетили);
безвозмездно(cellStringNeighbours.клеток);
}
по другому раз(размером stacksize > 0){ //Раз нет соседей, вернитесь к предыдущему пт
точка отсчета = поп();
}
else{ //раз нет соседей и очки в стеке, но не все точки посетили, выбрать случайное из непосещенных
cellString cellStringUnvisited = getUnvisitedCells(ширина, высота, лабиринт);
randNum = randomRange(0, cellStringUnvisited.Размер-1);
currentCell = cellStringUnvisited.клеток[randNum];
безвозмездно(cellStringUnvisited.клеток);
}
пока(unvisitedCount() > 0);

Как видно, реализация метода проста и абстрактные теории, как говорится, «даже ребенок». Чтобы не перегружать статью, код функции, используемые в вышеприведенном отрывке, под спойлер.

Функции кодфункции getNeighbours () возвращает массив из непосещенных соседей клеточки
cellString getNeighbours(без знака int Ширина, int без знака высота, Тип int** лабиринт, ячейка C){
без знака int я;
без знака int х = АР.х;
без знака int у = АР.у;
клеточка ввысь = {х, у, расстояние};
клеточка РТ = {х + расстояние, по Y};
ячейка ДГ = {х, у + расстояние};
сотовый ЛТ = {х — расстояние, у};
клеточка д[4] = {ДГ, РТ, до, ЛТ};
без знака int Размер = 0;

cellString клеток;
клеток.клеточки = функция malloc(4 * sizeof на(клеточки));

для(я = 0; я < 4; я++){ //для каждого направления
раз(г[я].х > 0 && д[я].х < ширина && д[я].для y > 0 && д[я].для Y < высота){ //раз не выходит за границы лабиринта
без знака int mazeCellCurrent = лабиринт[д[я].Г][Д[Я].х];
сотовый cellCurrent = д[я];
раз(mazeCellCurrent != Стенки && mazeCellCurrent != Посетил){ //не посещалистенки
клеток.клеток[Размер] = cellCurrent; //записать в массив;
Размер++;
}
}
}
клеток.Размер = Размер;
возвращение ячейки;

Функция removeWall удаляет стенки меж 2-мя клеточками:
(xDiff / АБС(xDiff)) : 0;
адди = (yDiff != 0)? (yDiff / АБС(yDiff)) : 0;

цель.х = во-первых.х + addX; //координаты стенки
цель.у = во-первых.Y в + адди;

лабиринт[выбр.г][выбр.х] = посетил;
возвращение лабиринт;
}

Во-первых, вычислить значение разности координат первой и 2-ой точек. mazeMatrix removeWall(первую ячейку, вторую ячейку, инт** лабиринт){
маленький int xDiff = 2-ой.х — 1-ый.х;
маленький int yDiff = 2-ой.у — 1-ая.у;
маленький int addX, адди;
клеточки-мишени;

addX = (xDiff != 0)? Разумеется, значение может быть отрицательным либо положительным либо 0.
Необходимо отыскать координаты X и Y, так что, раз вы добавляете их координаты первой точки были получены координаты стенки.
Так как мы знаем, что векторная разность меж координатами стенке и 1-ое очко или (|1|, 0) либо (0, |1|), мы можем применять его.
Получение добавки для X и Y, мы просто вычисляемые координаты стенки меж первой и 2-ой ячеек и присвоить к ячейке по координатам, которые вы посетили. Для Y, соответственно. Таковым образом, добавка координата x при xDiff != 0 будет равен xDiff / |xDiff|, xDiff = 0, ноль.
Итак, сейчас у нас есть генератор лабиринтов, что можно строить лабиринты, размер которых ограничен лишь размером оперативной памяти.
В итоге мы можем получить нечто схожее:

100х100 Берегитесь трафика! Лабиринты.
500х500

Поколение работает, сейчас дело за малым: отыскать в этом лабиринте выход.
Методы поиска пути несколько больше, чем поколение алгоритмов, и некие из их, раз будет энтузиазм читателей, я будут освещать в последующих статьях, а пока будем наслаждаться тем, что есть, и «прогулка» лабиринт с тем же методом.
И еще посильнее становится легче, поэтому что мы больше не придется очищать стенки.
Выберите случайную ячейку из примыкающих
3. 2. По другому, раз стек не пуст
1. Вынуть клеточку из стека
2. Сделать начальный текущей ячейке и пометить его как посетил. До тех пор, пока вы отыскать выход
1. Сделать избранные в текущей ячейке и пометить его как посетил. Метод поиска пути поиска с возвратом:
1. Раз текущая ячейка имеет непосещенных соседей
1. 2. По другому выхода нет Сделать его текущим
3. Надавите на текущую ячейку в стеке
2.
Смотри, что вышло:

100х100 Трафик!Красноватый путь, голубая — клеток. Решена лабиринты.

500х500

Ч

Ч в уникальном разрешении (16000px, 30 Мб):
яди.СК/я/YS0ImN-PhoLcZ
яди.СК/я/YZjzwPu5hoLcd
Это все, что необходимо для более обычная реализация генератора случайных лабиринтов.
Для тех кому любопытно, полный начальный код проекта на github: Лабиринт генератор и Решатель (внеэкранный рендеринг)

Внимание!Интеграции compiz не поддерживается некими драйверами на базе Unix и Windows — не поддерживается, так что желающие, кому не подфартило с ОС/оборудования, могу предложить ознакомиться с примыкающего проекта: Лабиринт генератор и Решатель
В обоих проектах реализованы одни и те же методы, но рисует в первой памяти и выходам последовательность PNG изображений, а 2-ой на экране. Сборка компакт выстроить && ../настроить && сделать, раз неловко, в папке src есть файл-проект QtCreator а.
Источники
1. 2. habrahabr.ru Пуллен: Думаю Лабиринта. Википедия: метод генерации Лабиринта. Уолтер Д.