Как найти выход из лабиринта с помощью Python

Создание лабиринта

Наш лабиринт будет в виде матрицы размером n*m с нулями для проходов и единицами для стен.

a = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

И ещё мы установим точки старта и финиша:

start = 1, 1
end = 2, 5

Итак, лабиринт готов, смотрите:

Точки начала и завершения пути в лабиринте

Алгоритм

Алгоритм для прохождения по лабиринту следующий:

  • Создаём нулевую матрицу подходящего размера.
  • Ставим 1 в точку старта.
  • Во все позиции вокруг 1 ставим 2 , если нет стены.
  • Вокруг двоек ставим тройки ( 3). Тоже, если нет стены.
  • И так далее…
  • Как только ставим цифру в точку финиша, останавливаемся. Это число и является минимальной длиной пути.

Создаём матрицу

Это просто. Возможно, есть функция по типу нулей или что-то подобное, но я знаю только один способ. Итак, создаем матрицу вручную и устанавливаем точку старта:

m = []
for i in range(len(a)):
    m.append([])
    for j in range(len(a[i])):
        m[-1].append(0)
i,j = start
m[i][j] = 1

Получаем следующую матрицу:

0  0  0  0  0  0  0  0  0  0  
0  1  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0

Рассчитываем шаг

Теперь создадим функцию только для одного шага:

def make_step(k):
  for i in range(len(m)):
    for j in range(len(m[i])):
      if m[i][j] == k:
        if i>0 and m[i-1][j] == 0 and a[i-1][j] == 0:
          m[i-1][j] = k + 1
        if j>0 and m[i][j-1] == 0 and a[i][j-1] == 0:
          m[i][j-1] = k + 1
        if i<len(m)-1 and m[i+1][j] == 0 and a[i+1][j] == 0:
          m[i+1][j] = k + 1
        if j<len(m[i])-1 and m[i][j+1] == 0 and a[i][j+1] == 0:
           m[i][j+1] = k + 1

Она принимает число шагов k в качестве аргумента. Функция выполняет очень простые вещи:

  • Сканирует матрицу при помощи цикла for.
  • Если находится число, которое соответствует количеству шагов k , смотрим на ячейки вокруг и проверяем:
    1. Нет ли здесь пока еще числа.
    2. Нет ли здесь стены.
    И ставим k+1 этим ячейкам.

Если запустить эту функцию 8 раз, получится вот что:

make_step(1)
make_step(2)
make_step(3)
make_step(4)
make_step(5)
make_step(6)
make_step(7)
make_step(8)

Получаем следующую матрицу:

0  0  0  0  0  0  0  0  0  0  
0  1  0  0  0  0  0  0  0  0  
0  2  0  0  0  0  0  0  0  0  
0  3  0  0  0  0  0  0  0  0  
0  4  0  0  0  0  0  0  0  0  
0  5  0  9  0  0  0  0  0  0  
0  6  7  8  9  0  0  0  0  0  
0  7  0  9  0  0  0  0  0  0  
0  8  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0

Она соответствует такому изображению:

Первые 8 шагов

Давайте продолжим, как и делали, пока не будет заполнена точка финиша:

k = 0
while m[end[0]][end[1]] == 0:
    k += 1
    make_step(k)

Теперь у нас будет вот такая матрица:

0  0  0  0  0  0  0  0  0  0  
0  1  0  13 0  0  22 21 20 0  
0  2  0  12 0  22 21 20 19 0  
0  3  0  11 0  0  0  0  18 0  
0  4  0  10 11 12 13 0  17 0  
0  5  0  9  10 11 12 0  16 0  
0  6  7  8  9  10 11 0  15 0  
0  7  0  9  10 11 12 13 14 0  
0  8  0  10 11 12 13 14 15 0  
0  0  0  0  0  0  0  0  0  0

Лабиринт по ней будет выглядеть вот так:

Поиски точки

Что такое путь?

Задача теперь — найти кратчайший путь по этой матрице. 

Шаги для решения следующие:

  • Пойти в точку финиша, допустим, число здесь — k.
  • Найти соседнюю ячейку со значением k-1 , пойти туда, уменьшить k на единицу.
  • Повторить предыдущий шаг, пока не доберемся до начальной точки, а именно: k=1.
i, j = end
k = m[i][j]
the_path = [(i,j)]
while k > 1:
  if i > 0 and m[i - 1][j] == k-1:
    i, j = i-1, j
    the_path.append((i, j))
    k-=1
  elif j > 0 and m[i][j - 1] == k-1:
    i, j = i, j-1
    the_path.append((i, j))
    k-=1
  elif i < len(m) - 1 and m[i + 1][j] == k-1:
    i, j = i+1, j
    the_path.append((i, j))
    k-=1
  elif j < len(m[i]) - 1 and m[i][j + 1] == k-1:
    i, j = i, j+1
    the_path.append((i, j))
    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 и вперёд:

from PIL import Image, ImageDraw
images = []

a = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0 ,0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0 ,0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0 ,0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0 ,0, 0, 0, 1, 0, 1, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0 ,0, 0, 0, 1, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0 ,0, 0, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0 ,0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0 ,0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
zoom = 20
borders = 6
start = 1,1
end = 5,19

def make_step(k):
  for i in range(len(m)):
    for j in range(len(m[i])):
      if m[i][j] == k:
        if i>0 and m[i-1][j] == 0 and a[i-1][j] == 0:
          m[i-1][j] = k + 1
        if j>0 and m[i][j-1] == 0 and a[i][j-1] == 0:
          m[i][j-1] = k + 1
        if i<len(m)-1 and m[i+1][j] == 0 and a[i+1][j] == 0:
          m[i+1][j] = k + 1
        if j<len(m[i])-1 and m[i][j+1] == 0 and a[i][j+1] == 0:
           m[i][j+1] = k + 1

def print_m(m):
    for i in range(len(m)):
        for j in range(len(m[i])):
            print( str(m[i][j]).ljust(2),end=' ')
        print()

def draw_matrix(a,m, the_path = []):
    im = Image.new('RGB', (zoom * len(a[0]), zoom * len(a)), (255, 255, 255))
    draw = ImageDraw.Draw(im)
    for i in range(len(a)):
        for j in range(len(a[i])):
            color = (255, 255, 255)
            r = 0
            if a[i][j] == 1:
                color = (0, 0, 0)
            if i == start[0] and j == start[1]:
                color = (0, 255, 0)
                r = borders
            if i == end[0] and j == end[1]:
                color = (0, 255, 0)
                r = borders
            draw.rectangle((j*zoom+r, i*zoom+r, j*zoom+zoom-r-1, i*zoom+zoom-r-1), fill=color)
            if m[i][j] > 0:
                r = borders
                draw.ellipse((j * zoom + r, i * zoom + r, j * zoom + zoom - r - 1, i * zoom + zoom - r - 1),
                               fill=(255,0,0))
    for u in range(len(the_path)-1):
        y = the_path[u][0]*zoom + int(zoom/2)
        x = the_path[u][1]*zoom + int(zoom/2)
        y1 = the_path[u+1][0]*zoom + int(zoom/2)
        x1 = the_path[u+1][1]*zoom + int(zoom/2)
        draw.line((x,y,x1,y1), fill=(255, 0,0), width=5)
    draw.rectangle((0, 0, zoom * len(a[0]), zoom * len(a)), outline=(0,255,0), width=2)
    images.append(im)


m = []
for i in range(len(a)):
    m.append([])
    for j in range(len(a[i])):
        m[-1].append(0)
i,j = start
m[i][j] = 1

k = 0
while m[end[0]][end[1]] == 0:
    k += 1
    make_step(k)
    draw_matrix(a, m)


i, j = end
k = m[i][j]
the_path = [(i,j)]
while k > 1:
  if i > 0 and m[i - 1][j] == k-1:
    i, j = i-1, j
    the_path.append((i, j))
    k-=1
  elif j > 0 and m[i][j - 1] == k-1:
    i, j = i, j-1
    the_path.append((i, j))
    k-=1
  elif i < len(m) - 1 and m[i + 1][j] == k-1:
    i, j = i+1, j
    the_path.append((i, j))
    k-=1
  elif j < len(m[i]) - 1 and m[i][j + 1] == k-1:
    i, j = i, j+1
    the_path.append((i, j))
    k -= 1
  draw_matrix(a, m, the_path)

for i in range(10):
    if i % 2 == 0:
        draw_matrix(a, m, the_path)
    else:
        draw_matrix(a, m)

print_m(m)
print(the_path)


images[0].save('maze.gif',
               save_all=True, append_images=images[1:],
               optimize=False, duration=1, loop=0)

Я не планировал делиться подробным кодом, так что, возможно, всё выглядит немного неясно. Идея была в том, чтобы визуализировать алгоритм, не показывая, как именно это было сделано 🙂

Читайте также:

Читайте нас в Telegram, VK и Яндекс.Дзен

Перевод статьи Dr Pommes: Solve a Maze with Python

Предыдущая статьяУровни измерения и их точность
Следующая статьяРазветвление на различные очереди SQS с помощью фильтрации сообщений SNS