Генератор лабиринта на питоне
Я попытался написать идеальный (только одно решение) генератор лабиринта в Python, используя обратную трассировку.
Прежде всего, мой лабиринт представлен сеткой x * y
Где каждая строка представляет стену. Моя программа запустится в верхней левой ячейке (с меткой 1) и проверит любые возможные ходы (2 или 6), затем случайным образом выберет эти 2 и добавит метку ячейки в стек, мы повторяем один и тот же процесс, пока стек не будет полный (в данном случае 25 элементов), когда мы заходим в тупик, программа должна иметь возможность вернуться назад, вытолкнув элементы из стека и выбрав другой путь.
Для лучшего объяснения вы можете обратиться к этому веб-сайт
При попытке создать лабиринт 5х5 я в основном застреваю в 23 ячейках, например, мой стек выглядит так: 1, 2, 7, 6, 11, 12, 13, 8, 9, 4, 5, 10, 15 , 14, 19, 20, 25, 24, 23, 22, 21, 16, 17
Я знаю, что ошибка исходит от функции gen ().
2 ответа
Нажав visited , пока вы возвращаетесь, вы уничтожаете свой путь. Вместо этого вы должны использовать индекс для отслеживания вашего возврата:
С этим изменением пример результата visited будет:
Хранение двух переменных, одна для обхода пути и другая для посещенных узлов, решит проблему. Кроме того, ничто не должно выталкиваться из пройденного пути, так как обход должен быть результатом этой программы.
Источник
Как найти выход из лабиринта с помощью Python
Создание лабиринта
Наш лабиринт будет в виде матрицы размером n*m с нулями для проходов и единицами для стен.
И ещё мы установим точки старта и финиша:
Итак, лабиринт готов, смотрите:
Алгоритм
Алгоритм для прохождения по лабиринту следующий:
- Создаём нулевую матрицу подходящего размера.
- Ставим 1 в точку старта.
- Во все позиции вокруг 1 ставим 2 , если нет стены.
- Вокруг двоек ставим тройки ( 3 ). Тоже, если нет стены.
- И так далее…
- Как только ставим цифру в точку финиша, останавливаемся. Это число и является минимальной длиной пути.
Создаём матрицу
Это просто. Возможно, есть функция по типу нулей или что-то подобное, но я знаю только один способ. Итак, создаем матрицу вручную и устанавливаем точку старта:
Получаем следующую матрицу:
Рассчитываем шаг
Теперь создадим функцию только для одного шага:
Она принимает число шагов k в качестве аргумента. Функция выполняет очень простые вещи:
- Сканирует матрицу при помощи цикла for.
- Если находится число, которое соответствует количеству шагов k , смотрим на ячейки вокруг и проверяем:
1. Нет ли здесь пока еще числа.
2. Нет ли здесь стены.
И ставим k+1 этим ячейкам.
Если запустить эту функцию 8 раз, получится вот что:
Получаем следующую матрицу:
Она соответствует такому изображению:
Давайте продолжим, как и делали, пока не будет заполнена точка финиша:
Теперь у нас будет вот такая матрица:
Лабиринт по ней будет выглядеть вот так:
Что такое путь?
Задача теперь — найти кратчайший путь по этой матрице.
Шаги для решения следующие:
- Пойти в точку финиша, допустим, число здесь — k.
- Найти соседнюю ячейку со значением k-1 , пойти туда, уменьшить k на единицу.
- Повторить предыдущий шаг, пока не доберемся до начальной точки, а именно: k=1.
И теперь у нас есть координаты пути:
Лабиринт посложнее
Теперь попробуем, как сработает наш алгоритм в других лабиринтах.
Для начала немного видоизменим лабиринт:
И потом сделаем его больше:
Чтобы визуализировать самостоятельно, как на картинках выше, установите библиотеку Pillow и вперёд:
Я не планировал делиться подробным кодом, так что, возможно, всё выглядит немного неясно. Идея была в том, чтобы визуализировать алгоритм, не показывая, как именно это было сделано 🙂
Источник
Генерация и решение лабиринта с помощью метода поиска в глубину по графу
В этой статье речь пойдет о самом простом в реализации алгоритме генерации «идеального» лабиринта и его применении для поиска пути.
Мы рассмотрим алгоритм, основанный на бэктрекинге, позволяющий создавать лабиринты без циклов, имеющие единственный путь между двумя точками. Алгоритм не самый быстрый, довольно требователен к ресурсам, по сравнению с алгоритмом Эйлера или Крускала, но очень прост в реализации и позволяет создавать ветвистые лабиринты с очень длинными тупиковыми ответвлениями.
Заинтересовавшихся — прошу под кат.
В русскоязычном интернете очень мало информации по алгоритмам генерации лабиринтов, что и стало причиной для написания этой статьи.
Примеры кода на языке Си, а также полный исходный код проекта на GitHub доступны под лицензией GNU GPLv3.
Ссылки на англоязычные ресурсы и проект вы найдете в конце статьи.
Описание алгоритма
Замечание: предполагается, что изначально у каждой клетки есть стенки со всех четырех сторон, которые отделяют ее от соседних клеток.
1. Сделайте начальную клетку текущей и отметьте ее как посещенную.
2. Пока есть непосещенные клетки
1. Если текущая клетка имеет непосещенных «соседей»
1. Протолкните текущую клетку в стек
2. Выберите случайную клетку из соседних
3. Уберите стенку между текущей клеткой и выбранной
4. Сделайте выбранную клетку текущей и отметьте ее как посещенную.
2. Иначе если стек не пуст
1. Выдерните клетку из стека
2. Сделайте ее текущей
3. Иначе
1. Выберите случайную непосещенную клетку, сделайте ее текущей и отметьте как посещенную.
Вы, вероятно, заметили что при выполнении условия 3, готовый лабиринт вероятнее всего будет иметь изолированную область.
Это условие включено в алгоритм в порядке исключения, на практике при нормальной работе алгоритма и правильных исходных данных, оно не выполняется никогда.
Реализация
Как уже сказано выше, предполагается, что при начале работы алгоритма все клетки отделены стенками.
Иллюстрация работы алгоритма
Функция getNeighbours возвращает массив непосещенных соседей клетки
Функция removeWall убирает стенку между двумя клетками:
Сначала вычисляется значение разности координат второй и первой точек. Очевидно, значение может быть либо отрицательное, либо положительное, либо 0.
Надо найти такие координаты xy, чтобы при сложении их с координатами первой точки получались координаты стенки.
Так как мы точно знаем, что вектор разности между координатами стенки и первой точке равен либо (|1|, 0) либо (0, |1|), мы можем этим воспользоваться.
Таким образом, аддитив для x координаты при xDiff != 0 будет равен xDiff / |xDiff|, при xDiff = 0, нулю. Для y соответственно.
Получив аддитивы для x и y, мы легко вычисляем координаты стенки между первой и второй клетками и назначаем клетку по этим координатам посещенной.
Итак, теперь у нас есть генератор лабиринтов, который может строить запутанные лабиринты, размер которых ограничен только размером оперативной памяти.
В итоге, мы можем получить что-то такое:
Генерация работает, теперь дело за малым: найти в таком лабиринте выход.
Алгоритмов поиска пути несколько больше, чем алгоритмов генерации, и некоторые из них, если будет интерес читателей, я освещу в следующих статьях, но пока что будем довольствоваться тем, что есть, и «пройдем» лабиринт тем же алгоритмом.
И все еще сильнее упрощается, так как нам больше не надо убирать стенки.
Алгоритм поиска пути бэктрекингом:
1. Сделайте начальную клетку текущей и отметьте ее как посещенную.
2. Пока не найден выход
1. Если текущая клетка имеет непосещенных «соседей»
1. Протолкните текущую клетку в стек
2. Выберите случайную клетку из соседних
3. Сделайте выбранную клетку текущей и отметьте ее как посещенную.
2. Иначе если стек не пуст
1. Выдерните клетку из стека
2. Сделайте ее текущей
3. Иначе выхода нет
Выходной точкой, как и стартовой, может выступать любая точка лабиринта, не являющаяся стенкой.
Традиционно, выход должен быть «прижат» к одной из стенок, но по сути может находиться где угодно.
Все таки, в данном случае, «вход» и «выход» — всего лишь две точки, между которыми надо найти путь.
Критерий нахождения «выхода» очень прост: достаточно сравнить координаты текущей точки и координаты «выхода»: если они равны, путь между стартовой и выходной точками найден.
Красным обозначен путь, голубым — посещенные клетки.
100×100
500×500
8000х8000
Вот и все, что нужно для самой простой реализации генератора случайных лабиринтов.
Для тех, кто заинтересовался, полный исходный код проекта на GitHub: Maze Generator and Solver (offscreen rendering)
Источник
Учебный проект на Python: алгоритм Дейкстры, OpenCV и UI ( часть 1)
Лабиринты — это распространенная головоломка для людей, но они представляют из себя интересную задачу для программирования, которую мы можем решить, используя методы кратчайшего пути, такие как алгоритм Дейкстры.
Вспоминаем алгоритм Дейкстры
Алгоритм Дейкстры — один из наиболее популярных алгоритмов теории графов. Он используется для поиска кратчайшего пути между узлами на ориентированном графе. Мы начнем с исходного узла и известных длин ребер между узлами.
Сначала мы присваиваем значение расстояния от источника всем узлам. Узел s получает значение 0, потому что это источник; остальные получают значения ∞ для начала.
Наш интересующий узел — это необработанный узел с наименьшим значением (показан серым), то есть s. Сначала мы «ослабляем» каждую смежную вершину до нашего интересующего узла, обновляя их значения до минимума их текущего значения или значения узла интереса плюс длину соединительного ребра…
Узел s теперь завершен (черный), а его соседи a и b приняли новые значения. Новый интересующий узел — b, поэтому мы повторяем процесс «ослабления» соседних узлов b и финализации значения кратчайшего пути для b.
Пройдя через каждый узел, мы в итоге получим график, показывающий кратчайшую длину пути от источника до каждого узла.
Наша финальная диаграмма после запуска алгоритма Дейкстры. Числа в каждом узле представляют кратчайшее возможное расстояние от исходного узла.
Концептуализация изображений лабиринта
Мы можем представить себе изображение как матрицу пикселей. Каждый пиксель (для простоты) имеет значение RGB 0,0,0 (черный) или 255,255,255 (белый). Наша цель — создать кратчайший путь, который начинается на белом и не переходит на чёрные границы. Чтобы представить эту цель, мы можем рассматривать каждый пиксель как узел и рисовать ребра между соседними пикселями с длиной ребер, основанной на разнице значений RGB. Мы будем использовать формулу евклидова квадратного расстояния и добавим 0,1, чтобы гарантировать отсутствие длины пути 0 — (требование для алгоритма Дейкстры):
Эта формула делает расстояние пересечения через границу лабиринта чрезмерно большим. Как мы видим, кратчайший путь от источника к месту назначения будет четко проходить вокруг барьера, а не через него.
Реализация
Мы можем использовать OpenCV, популярную библиотеку компьютерного зрения для Python, чтобы извлечь значения пикселей и показать наши изображения лабиринта. Давайте также определим координаты нашего начального и конечного местоположений, добавив точки в наш лабиринт
Мы создаем класс Vertex, который поможет нам отслеживать координаты. Мы также хотим отслеживать родительский узел, чтобы мы могли восстановить весь путь, как только найдем значения расстояния.
Нам нужно создать матрицу вершин, представляющую двухмерное расположение пикселей на изображении. Это будет основой для алгоритма Дейкстры. Мы также поддерживаем очередь с минимальной кучей приоритетов для отслеживания необработанных узлов.
Нам нужно несколько вспомогательных функций, чтобы помочь найти ребра и длину ребер между вершинами:
Теперь мы можем реализовать алгоритм Дейкстры и присвоить значения расстояния (d) всем вершинам пикселей в изображении лабиринта:
Теперь мы можем вызвать функцию кратчайшего пути и нарисовать решение в нашем лабиринте:
Давайте попробуем другие лабиринты со всего Интернета.
Полный исходный код доступен на GitHub здесь.
Узнайте подробности, как получить востребованную профессию с нуля или Level Up по навыкам и зарплате, пройдя платные онлайн-курсы SkillFactory:
Источник