Источник: Nuances of Programming
Создание лабиринта
Наш лабиринт будет в виде матрицы размером n*m с нулями для проходов и единицами для стен.
И ещё мы установим точки старта и финиша:
start = 1, 1
end = 2, 5
Итак, лабиринт готов, смотрите:
Алгоритм
Алгоритм для прохождения по лабиринту следующий:
- Создаём нулевую матрицу подходящего размера.
- Ставим 1 в точку старта.
- Во все позиции вокруг 1 ставим 2 , если нет стены.
- Вокруг двоек ставим тройки ( 3). Тоже, если нет стены.
- И так далее…
- Как только ставим цифру в точку финиша, останавливаемся. Это число и является минимальной длиной пути.
Создаём матрицу
Это просто. Возможно, есть функция по типу нулей или что-то подобное, но я знаю только один способ. Итак, создаем матрицу вручную и устанавливаем точку старта:
Получаем следующую матрицу:
Рассчитываем шаг
Теперь создадим функцию только для одного шага:
Она принимает число шагов k в качестве аргумента. Функция выполняет очень простые вещи:
- Сканирует матрицу при помощи цикла for.
- Если находится число, которое соответствует количеству шагов k , смотрим на ячейки вокруг и проверяем:
1. Нет ли здесь пока еще числа.
2. Нет ли здесь стены.
И ставим k+1 этим ячейкам.
Если запустить эту функцию 8 раз, получится вот что:
Получаем следующую матрицу:
Она соответствует такому изображению:
Давайте продолжим, как и делали, пока не будет заполнена точка финиша:
k = 0
while m[end[0]][end[1]] == 0:
k += 1
make_step(k)
Теперь у нас будет вот такая матрица:
Лабиринт по ней будет выглядеть вот так:
Что такое путь?
Задача теперь — найти кратчайший путь по этой матрице.
Шаги для решения следующие:
- Пойти в точку финиша, допустим, число здесь — k.
- Найти соседнюю ячейку со значением k-1 , пойти туда, уменьшить k на единицу.
- Повторить предыдущий шаг, пока не доберемся до начальной точки, а именно: k=1.
И теперь у нас есть координаты пути:
[(2, 5), (2, 6), (2, 7), (2, 8), (3, 8), (4, 8), (5, 8), (6, 8), (7, 8), (7, 7), (7, 6), (6, 6), (6, 5), (6, 4), (6, 3), (6, 2), (6, 1), (5, 1), (4, 1), (3, 1), (2, 1), (1, 1)]
И вот как это выглядит:
Лабиринт посложнее
Теперь попробуем, как сработает наш алгоритм в других лабиринтах.
Для начала немного видоизменим лабиринт:
И потом сделаем его больше:
Надеюсь, вам понравилось!
Чтобы визуализировать самостоятельно, как на картинках выше, установите библиотеку Pillow и вперёд:
Я не планировал делиться подробным кодом, так что, возможно, всё выглядит немного неясно. Идея была в том, чтобы визуализировать алгоритм, не показывая, как именно это было сделано.
Читайте также:
Перевод статьи Dr Pommes: Solve a Maze with Python
