Алгоритмы на лабиринтах

Постановка задачи

У лабиринта нет стен, но он окружен кустами по внешним краям. Если игрок зашел в куст, то он проиграл. Лабиринт представлен как матрица (список (list) списков): 1 - это куст и 0 - это дорожка. Размер лабиринта N на N клеток и внешние клетки всегда кусты. Игрок начинает в клетке (1, 1). Выход в клетке (N-2, N-2). Вам нужно найти маршрут через Лабиринт. Игрок может двигатся только в четырех направлениях:
Маршрут описывается строкой состоящей из следующих символов: "S"=Юг, "N"=Север, "E"=Восток, and "W"=Запад.
Пример:
maze = [
	[1, 1, 1, 1, 1],
	[1, 0, 1, 0, 1],
	[1, 0, 1, 0, 1],
	[1, 0, 0, 0, 1],
	[1, 1, 1, 1, 1]
]
solve = "SSEE"
В общем виде в такого рода задачах лабиринт можно представить в виде графа. Где пустые клетки - это вершины, а ребрами соединены те клетки- вершины, которые прилегают друг к другу, т.е. те на которые можно пойти. Реализуем граф, как словарь. Координаты клеток будем представлять кортежем. В словаре ключами будут координаты клетки-вершины, а значениями будет список кортежей из координат соседних клеток и направлении по которым можно добраться до клетки-вершины. Например, для лабиринта выше. Возьмем клетку с координатами (1, 1). В эту клетку можно попасть только из клетки (2, 1) двигаясь на Юг. Должны получить: {(1, 1): [('S', (2, 1))]} Имеем, что каждая вершина имеет уникальное имя - это координаты клетки. А направление мы будет использовать для восстановления пути. Функция преобразования лабиринта в граф будет выглядеть:
def maze2graph(maze):
    height = len(maze)
    width = len(maze[0]) if height else 0
    graph = {(i, j): [] for j in range(width) for i in range(height) if not maze[i][j]}
    for row, col in graph.keys():
        if row < height - 1 and not maze[row + 1][col]:
            graph[(row, col)].append(("S", (row + 1, col)))
            graph[(row + 1, col)].append(("N", (row, col)))
        if col < width - 1 and not maze[row][col + 1]:
            graph[(row, col)].append(("E", (row, col + 1)))
            graph[(row, col + 1)].append(("W", (row, col)))
    return graph
Сначала мы создаем словарь с ключами, которые равны координатам наших свободных клеток.
height = len(maze)
width = len(maze[0]) if height else 0
graph = {(i, j): [] for j in range(width) for i in range(height) if not maze[i][j]}
Получаем словарь:
{(1, 1): [],
(1, 3): [],
(2, 1): [],
(2, 3): [],
(3, 1): [],
(3, 2): [],
(3, 3): []}
Далее приступаем к заполнению списков
Окончательный результат преобразования выглядит так:
{(1, 1): [('S', (2, 1))],
(1, 3): [('S', (2, 3))],
(2, 1): [('N', (1, 1)), ('S', (3, 1))],
(2, 3): [('N', (1, 3)), ('S', (3, 3))],
(3, 1): [('E', (3, 2)), ('N', (2, 1))],
(3, 2): [('E', (3, 3)), ('W', (3, 1))],
(3, 3): [('W', (3, 2)), ('N', (2, 3))]}
Полный пример кода.
#!/usr/bin/env python
# -*- coding: utf-8 -*
# file: maze2graph_example.py
import pprint
pp = pprint.PrettyPrinter()

def maze2graph(maze):
    height = len(maze)
    width = len(maze[0]) if height else 0
    graph = {(i, j): [] for j in range(width) for i in range(height) if not maze[i][j]}
    pp.pprint(graph)
    for row, col in graph.keys():
        if row < height - 1 and not maze[row + 1][col]:
            graph[(row, col)].append(("S", (row + 1, col)))
            graph[(row + 1, col)].append(("N", (row, col)))
        if col < width - 1 and not maze[row][col + 1]:
            graph[(row, col)].append(("E", (row, col + 1)))
            graph[(row, col + 1)].append(("W", (row, col)))
    return graph

maze = [
    [1, 1, 1, 1, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1]
]
pp = pprint.PrettyPrinter()
pp.pprint(maze2graph(maze))

Нахождение пути

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

Поиск в ширину. Breadth-first searching (BFS)

Полный пример кода.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# file: bfs_maze_example.py
from collections import deque
import pprint
pp = pprint.PrettyPrinter()

def maze2graph(maze):
    height = len(maze)
    width = len(maze[0]) if height else 0
    graph = {(i, j): [] for j in range(width) for i in range(height) if not maze[i][j]}
    for row, col in graph.keys():
        if row < height - 1 and not maze[row + 1][col]:
            graph[(row, col)].append(("S", (row + 1, col)))
            graph[(row + 1, col)].append(("N", (row, col)))
        if col < width - 1 and not maze[row][col + 1]:
            graph[(row, col)].append(("E", (row, col + 1)))
            graph[(row, col + 1)].append(("W", (row, col)))
    return graph

def find_path_bfs(maze):
    start, goal = (1, 1), (len(maze) - 2, len(maze[0]) - 2)
    queue = deque([("", start)])
    visited = set()
    graph = maze2graph(maze)
    while queue:
        pp.pprint(queue)
        path, current = queue.popleft()
        if current == goal:
            return path
        if current in visited:
            continue
        visited.add(current)
        for direction, neighbour in graph[current]:
            queue.append((path + direction, neighbour))
    return "NO WAY!"

maze = [
    [1, 1, 1, 1, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1]
]

pp = pprint.PrettyPrinter()
pp.pprint(find_path_bfs(maze))

Поиск в глубину. Depth-first search (DFS)

Полный пример кода.
#!/usr/bin/env python
# -*- coding: utf-8 -*
# file: dfs_maze_example.py
from collections import deque
import pprint
pp = pprint.PrettyPrinter()

def maze2graph(maze):
    height = len(maze)
    width = len(maze[0]) if height else 0
    graph = {(i, j): [] for j in range(width) for i in range(height) if not maze[i][j]}
    for row, col in graph.keys():
        if row < height - 1 and not maze[row + 1][col]:
            graph[(row, col)].append(("S", (row + 1, col)))
            graph[(row + 1, col)].append(("N", (row, col)))
        if col < width - 1 and not maze[row][col + 1]:
            graph[(row, col)].append(("E", (row, col + 1)))
            graph[(row, col + 1)].append(("W", (row, col)))
    return graph

def find_path_dfs(maze):
    start, goal = (1, 1), (len(maze) - 2, len(maze[0]) - 2)
    stack = deque([("", start)])
    visited = set()
    graph = maze2graph(maze)
    while stack:
        path, current = stack.pop()
        if current == goal:
            return path
        if current in visited:
            continue
        visited.add(current)
        for direction, neighbour in graph[current]:
            stack.append((path + direction, neighbour))
    return "NO WAY!"

maze = [
    [1, 1, 1, 1, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1]
]

pp = pprint.PrettyPrinter()
pp.pprint(find_path_dfs(maze))

Умный поиск. A* Search

Полный пример кода.
#!/usr/bin/env python
# -*- coding: utf-8 -*
# file: aseach_maze_example.py
from heapq import heappop, heappush
import pprint
pp = pprint.PrettyPrinter()

def maze2graph(maze):
    height = len(maze)
    width = len(maze[0]) if height else 0
    graph = {(i, j): [] for j in range(width) for i in range(height) if not maze[i][j]}
    for row, col in graph.keys():
        if row < height - 1 and not maze[row + 1][col]:
            graph[(row, col)].append(("S", (row + 1, col)))
            graph[(row + 1, col)].append(("N", (row, col)))
        if col < width - 1 and not maze[row][col + 1]:
            graph[(row, col)].append(("E", (row, col + 1)))
            graph[(row, col + 1)].append(("W", (row, col)))
    return graph

def heuristic(cell, goal):
    return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])


def find_path_astar(maze):
    start, goal = (1, 1), (len(maze) - 2, len(maze[0]) - 2)
    pr_queue = []
    heappush(pr_queue, (0 + heuristic(start, goal), 0, "", start))
    visited = set()
    graph = maze2graph(maze)
    while pr_queue:
        _, cost, path, current = heappop(pr_queue)
        if current == goal:
            return path
        if current in visited:
            continue
        visited.add(current)
        for direction, neighbour in graph[current]:
            heappush(pr_queue, (cost + heuristic(neighbour, goal), cost + 1,
                                path + direction, neighbour))
    return "NO WAY!"

maze = [
    [1, 1, 1, 1, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1]
]

pp = pprint.PrettyPrinter()
pp.pprint(find_path_astar(maze))

Ссылки по теме

  1. Необыкновенный способ генерации лабиринтов
  2. Алгоритмы на лабиринтах
"../js/highlight.pack.js">