Алгоритмы генерации и прохождения идеального лабиринта

Лабиринт (др.-греч. λαβύρινθος) — структура (обычно в двухмерном или трехмерном пространстве), состоящая из запутанных путей к выходу (и/или путей, ведущих в тупик).

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

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

Алгоритмы генерации лабиринтов

• Алгоритм Эллера
• Наивный алгоритм
• Лабиринт на таблице
• BSP деревья
• Генерация лабиринтов с использованием клеточного автомата
• Метод поиска в глубину по графу.
• Алгоритм «Sidewinder»
• Алгоритм Уилсона
• Алгоритм Олдоса-Бродера
• Применение алгоритмов генерации и прохождения лабиринтов в реальной жизни

Алгоритм Эллера

Алгоритм Эллера — это математический генератор, позволяющий создавать лабиринты, в которых между каждыми двумя точками существует единственный путь, то есть лабиринты не содержат циклов. По сравнению с другими генераторами, этот алгоритм является одним из самых быстрых и требует небольшое количество оперативной памяти — пропорциональную длине строки лабиринта. Нужно хранить в памяти только последний созданный ряд, что позволяет генерировать лабиринты с неограниченным количеством рядов.

Алгоритм Эллера - это алгоритм генерации идеального лабиринта. Лабиринт считается идеальным, если у него нет замкнутых и зацикленных участков, и от любой точки до любой другой точки существует ровно один путь.

Алгоритм представляет собой цикл добавления новых строк. Строка содержит одно и то же количество ячеек, которое произвольно задается в начале. Клетки относятся к множествам, которые служат для контроля возможности прохода между ячейками. На момент генерации текущей строки клетки одного множества соединены между собой, одновременно клетки из разных множеств находятся в изолированных между собой частях лабиринта. В общем, стенки лабиринта генерируются случайным образом, но при соблюдении определенных правил, которые гарантируют отсутствие зацикливаний.

Описание алгоритма

Метод поиска в глубину по графу для генерации лабиринта.

Генерация и решение лабиринта с помощью метода поиска в глубину по графу. Иллюстрация работы алгоритма.

1. Создаем начальную матрицу.
2. Выбираем начальную точку.
3. Перемещаемся к случайной соседней непосещенной ячейке, пока таковые есть.
4. Если непосещенных соседних ячеек нет, то возвращаемся назад по стеку
5. Непосещенные соседние ячейки есть. Перемещаемся к случайной непосещенной соседней ячейке.
6. Нет непосещенных клеток. Лабиринт сгенерирован.

Программный код

Начнем действовать по порядку и сначала сгенерируем начальную матрицу, с которой будет работать алгоритм.
Для удобства условимся, что все типы клеток заданы в перечислении.

int maze[height][width]; //создаем матрицу - двумерный массив
for(i = 0; i < height; i++){
        for(j = 0; j < width; j++){
            if((i % 2 != 0  && j % 2 != 0) && //если ячейка нечетная по x и y, 
               (i < height-1 && j < width-1))   //и при этом находится в пределах стен лабиринта
                   maze[i][j] = CELL;       //то это КЛЕТКА
            else maze[i][j] = WALL;           //в остальных случаях это СТЕНА.
        }
    }

Теперь, когда все приготовления сделаны, можно приступать к генерации.

typedef struct cell{ //структура, хранящая координаты клетки в матрице
    unsigned int x;
    unsigned int y;
} cell;

typedef struct cellString{ 
    cell* cells;
    unsigned int size;
} cellString;

Структуры значительно упростят жизнь при обмене информацией между функциями.

Отрывок кода, отвечающий за генерацию:

cell startCell = {1, 1}
cell currentCell = startCell;
cell neighbourCell;
do{
    cellString Neighbours = getNeighbours(width, height, maze, startPoint, 2);
    if(Neighbours.size != 0){ //если у клетки есть непосещенные соседи
        randNum  = randomRange(0, Neighbours.size-1);
        neighbourCell = cellStringNeighbours.cells[randNum]; //выбираем случайного соседа
        push(d.startPoint); //заносим текущую точку в стек
        maze = removeWall(currentCell, neighbourCell, maze); //убираем стену между текущей и сосендней точками
        currentCell = neighbourCell; //делаем соседнюю точку текущей и отмечаем ее посещенной
        maze = setMode(d.startPoint, d.maze, VISITED);
        free(cellStringNeighbours.cells);
    }
    else if(stackSize > 0){ //если нет соседей, возвращаемся на предыдущую точку
        startPoint = pop();
    }
    else{ //если нет соседей и точек в стеке, но не все точки посещены, выбираем случайную из непосещенных
        cellString cellStringUnvisited = getUnvisitedCells(width, height, maze);
        randNum = randomRange(0, cellStringUnvisited.size-1);
        currentCell = cellStringUnvisited.cells[randNum];
        free(cellStringUnvisited.cells);
    }
while(unvisitedCount() > 0);

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

Функция getNeighbours возвращает массив непосещенных соседей клетки

cellString getNeighbours(unsigned int width, unsigned int height, int** maze, cell c){
    unsigned int i;
    unsigned int x = c.x;
    unsigned int y = c.y;
    cell up = {x, y - distance};
    cell rt = {x + distance, y};
    cell dw = {x, y + distance};
    cell lt = {x - distance, y};
    cell d[4]  = {dw, rt, up, lt};
    unsigned int size = 0;

    cellString cells;
    cells.cells = malloc(4 * sizeof(cell));

    for(i = 0; i < 4; i++){ //для каждого направдения
        if(d[i].x > 0 && d[i].x < width && d[i].y > 0 && d[i].y < height){ //если не выходит за границы лабиринта
            unsigned int mazeCellCurrent = maze[d[i].y][d[i].x];
            cell     cellCurrent     = d[i];
            if(mazeCellCurrent != WALL && mazeCellCurrent != VISITED){ //и не посещена\является стеной
                cells.cells[size] = cellCurrent; //записать в массив;
                size++;
            }
        }
    }
    cells.size = size;
    return cells;

Функция removeWall убирает стенку между двумя клетками:

mazeMatrix removeWall(cell first, cell second, int** maze){
    short int xDiff = second.x - first.x;
    short int yDiff = second.y - first.y;
    short int addX, addY;
    cell target;

    addX = (xDiff != 0) ? (xDiff / abs(xDiff)) : 0;
    addY = (yDiff != 0) ? (yDiff / abs(yDiff)) : 0;

    target.x = first.x + addX; //координаты стенки
    target.y = first.y + addY;

    maze[target.y][target.x] = VISITED;
    return maze;
}

Алгоритм двоичного дерева

Формальный алгоритм (для северо-восточного смещения):

1. Выбрать начальную клетку;
2. Выбрать случайное направление для прокладывания пути. Если соседняя клетка в этом направлении выходит за границы поля, прокопать клетку в единственно возможном направлении;
3. Перейти к следующей клетке;
4. Повторять 2-3 до тех пор, пока не будут обработаны все клетки;

Плюсы:

• Простая реализация;
• Высокая скорость работы;
• Возможность генерировать бесконечные лабиринты;

Минусы:

• Низкая сложность рисунка;
• Сильное смещение по диагонали;
• Отсутствие тупиков по смещению;
• Однообразность сгенерированных лабиринтов;

Алгоритм «Sidewinder»

Алгоритм Уилсона

Формальный алгоритм:

1. Выбрать случайную вершину, не принадлежащую остовному дереву и добавить ее в дерево;
2. Выбрать случайную вершину, не принадлежащую остовному дереву и начать обход графа (лабиринта), пока не придем в уже добавленную вершину дерева; Если образуется цикл, удалить его;
3. Добавить все вершины получившегося подграфа в остовное дерево;
4. Повторять шаги 2-3, пока все вершины не будут добавлены в остовное дерево.

Плюсы:

• Отсутствует какое-либо смещение;
• Лабиринты абсолютно случайны, поэтому невозможно создать определенный алгоритм их решения;
• Сложность решения для человека;
• Нет бессмысленного блуждания;
• Скорость по сравнению с Олдос-Бродером в разы больше;

Минусы:

• Непростая реализация;
• Падения скорости в начале генерации;
• Большие требования к памяти, чем у Олдос-Бродера;

Алгоритм Олдоса-Бродера

Формальный алгоритм:

1. Выбрать случайную вершину (клетку). Абсолютно случайную;
2. Выбрать случайную соседнюю вершину (клетку) и перейти в нее. Если она не была посещена, добавить ее в дерево (соединить с предыдущей, убрать между ними стену);
3. Повторять шаг 2, пока все клетки не будут посещены.

Плюсы:

• Отсутствует какое-либо смещение;
• Лабиринты абсолютно случайны, поэтому невозможно создать определенный алгоритм их решения;
• Сложность решения для человека;
• Простая реализация;

Минусы:

• Скорость. Пока будет генерироваться лабиринт, Вы успеете состариться и умереть;
• Не позволяет генерировать бесконечные лабиринты;
• Сильное падение эффективности под конец генерации;

Применение алгоритмов генерации и прохождения лабиринтов в реальной жизни

Алгоритмы генерации и прохождения лабиринтов находят широкое применение в различных областях реальной жизни. Вот несколько примеров:

Автономные транспортные средства:

1. Навигация внутри помещений: Роботы и беспилотные автомобили используют алгоритмы прохождения лабиринтов для навигации внутри зданий. Это может быть полезно в больших торговых центрах, складах, медицинских учреждениях и других местах.

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

Индустрия:

1. Логистика и складское хозяйство: Автоматизированные системы на складах могут использовать алгоритмы прохождения лабиринтов для оптимизации маршрутов перемещения товаров или роботов-перевозчиков внутри склада.

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

Медицина:

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

Игровая индустрия:

1. Игровые приложения с искусственным интеллектом: В видеоиграх алгоритмы генерации лабиринтов могут создавать уникальные уровни, обеспечивая разнообразие и вызов для игроков.

Компьютерная безопасность:

1. Тестирование безопасности сетей: Алгоритмы прохождения лабиринтов могут применяться для тестирования безопасности компьютерных систем, ища возможные пути атаки или обхода защитных механизмов.

Энергетика:

1. Обследование труднодоступных месторождений: Роботы, оснащенные алгоритмами прохождения лабиринтов, могут использоваться для исследования труднодоступных месторождений энергоресурсов.

Архитектура и дизайн:

1. Оптимизация планировки помещений: В архитектуре и дизайне можно использовать алгоритмы генерации лабиринтов для оптимизации планировки помещений и создания уникальных архитектурных решений.

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

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

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

Эти алгоритмы не только способны эффективно решать задачи конкретных областей, но и обладают универсальностью, что делает их важным компонентом различных технологических исследований и применений в современном мире

Вау!! 😲 Ты еще не читал? Это зря!

• поиск выхода из лабиринта ,