Какой хороший алгоритм для создания лабиринта?

Question

Скажем, вы хотите простой лабиринт на сетке N by M, с одним проходом и большим количеством тупиков, но это выглядит "правильным" (то есть, как будто кто-то сделал это вручную без слишком большого количества маленьких тупиков и всего такого). Есть ли известный способ сделать это?

Answer 1

С http://www.astrolog.org/labyrnth/algrithm.htm

Рекурсивный бэктрекер: Это в некоторой степени связано с методом решения рекурсивного бэктрекера, описанным ниже, и требует стека до размера лабиринта. При вырезании будьте как можно более жадными, и всегда делайте вырезки на необработанный участок, если он находится рядом с текущей ячейкой. Каждый раз, когда вы переходите в новую ячейку, вставляйте прежнюю ячейку в стек. Если рядом с текущей позицией нет неразделенных ячеек, вставьте стек в предыдущую позицию. Лабиринт делается, когда вы вытаскиваете все из стека. Этот алгоритм приводит к лабиринтам с как можно более высоким "речным" фактором, с меньшим, но более длинным тупиком, и, как правило, очень длинным и извилистым решением. Он работает довольно быстро, хотя алгоритм Прима немного быстрее. Рекурсивное отслеживание в обратном направлении не работает как сумматор, так как это приводит к пути решения, который следует за внешним краем, где вся внутренняя часть лабиринта прикреплена к границе одним стержнем.

Они дают только 10% тупиков

пример лабиринта, созданного этим методом

Answer 2

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

1. Краскала
2. Прима
3. Рекурсивный Backtracker
4. Олдос-Бродер
5. Растущее дерево
6. Hunt-и Безубойные
7. Уилсона
8. Эллер - х
9. Сотовый Автомат (Легкий)
10. Рекурсивное деление (очень легко)
11. Sidewinder (предсказуемый)
12. Бинарное дерево

Для получения дополнительной информации, ознакомьтесь с mazelib на GitHub, библиотеке Python, реализующей все стандартные алгоритмы создания / решения лабиринтов.

Answer 3

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

Лучшая дискуссия об алгоритмах генерации лабиринтов: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (была на HN пару дней назад).

Answer 4

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

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

https://mtimmerm.github.io/webStuff/maze.html

Answer 5

Достаточно странно, что, слегка изменив "канонические" правила и начав со случайной конфигурации, игра "Жизнь" Конвея, похоже, генерирует довольно приятные лабиринты!

(Я не помню точное правило, но это очень простая модификация, которая имеет тенденцию "уплотнять" популяцию клеток...)

Answer 6

Рекурсивный поиск с возвратом - самый простой для реализации алгоритм.

Вот реализация Java:

Здесь Cell - это класс, представляющий ячейку в 2D-сетке, а cells - это 2D-массив объектов Cell. Ячейка имеет логические переменные top, bottom, left и right, чтобы указать, есть ли у ячейки стены с этих сторон, логическая переменная, которую посещают, чтобы проверить, прошли ли мы ее, и две целочисленные переменные row и col, чтобы указать ее положение в сетке.

Cell current = cells[0][0] , next;
    current.visited=true;
    do{
        next = getNeighbour(current);
        if(next!=null){
            removeWall(current , next);
            st.push(current);
            current = next;
            current.visited = true;
        }
        else {
            current = st.pop();
        }
    }
    while (!st.empty());


    private Cell getNeighbour(Cell cell){
    ArrayList<Cell> ara = new ArrayList<>();
    if(cell.col>0 && !cells[cell.col-1][cell.row].visited)
         ara.add(cells[cell.col-1][cell.row]);

    if(cell.row>0 && !cells[cell.col][cell.row-1].visited)
         ara.add(cells[cell.col][cell.row-1]);

    if(cell.col<col-1 && !cells[cell.col+1][cell.row].visited)
         ara.add(cells[cell.col+1][cell.row]);
    if(cell.row<row-1 && !cells[cell.col][cell.row+1].visited)
         ara.add(cells[cell.col][cell.row+1]); 


    if(ara.size()>0){
        return ara.get(new Random().nextInt(ara.size()));
    }else{
        return null;
    }
}
private void removeWall(Cell curr , Cell nxt){
    if((curr.col == nxt.col) && (curr.row == nxt.row+1)){/// top
        curr.top=nxt.botttom=false;
    }
    if(curr.col==nxt.col && curr.row == nxt.row-1){///bottom
        curr.botttom = nxt.top = false;
    }
    if(curr.col==nxt.col-1 && curr.row==nxt.row ){///right
        curr.right = nxt.left = false;
    }
    if(curr.col == nxt.col+1 && curr.row == nxt.row){///left
        curr.left = nxt.right = false;
    }
}

Answer 7

Одним из методов создания лабиринта является рандомизированная версия алгоритма Прима.

Начните с сетки, полной стен. Выберите клетку, отметьте ее как часть лабиринта. Добавьте стены ячейки в список стен. Пока в списке есть стены:

Выберите случайную стену из списка. Если ячейка на противоположной стороне еще не в лабиринте:

(i) Сделайте стену проходом и отметьте клетку на противоположной стороне как часть лабиринта.

(ii) Добавьте соседние стены ячейки в список стен.

Если ячейка на противоположной стороне уже была в лабиринте, удалите стену из списка.

Для большего понимания нажмите здесь

Answer 8

Я предпочитаю версию алгоритма рекурсивного деления. Подробно это описано здесь.

Я дам краткий обзор:
оригинальный алгоритм рекурсивного деления работает следующим образом. Сначала начните с пустой области для лабиринта. Добавьте одну прямую стену, чтобы разделить камеру надвое, и проделайте где-нибудь одно отверстие в этой стене. Затем рекурсивно повторите этот процесс для каждой из двух новых камер, пока не будет достигнут желаемый размер прохода. Это просто и хорошо работает, но есть очевидные узкие места, которые позволяют легко решить лабиринт.

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

Answer 9

Вот алгоритм DFS, написанный как псевдокод:

создать CellStack (LIFO) для хранения списка местоположений ячеек
set TotalCells = количество ячеек в сетке
выберите ячейку наугад и назовите ее CurrentCell
set VisitedCells = 1

в то время как VisitedCellsесли один или несколько найдены, выберите один случайным образом
сбить стену между ней и CurrentCell
нажмите расположение CurrentCell на CellStack
сделать новую ячейку CurrentCell
добавьте 1 в VisitedCells, иначе извлеките самую последнюю запись ячейки из CellStack
сделать это CurrentCell endIf endWhile

Answer 10

https://github.com/yuchinchenTW/MazeGenerate/tree/master

попробуйте этот генератор лабиринтов

с использованием поиска в глубину и метода рекурсивного деления

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