Постановка задачи
У лабиринта нет стен, но он окружен кустами по внешним краям. Если игрок зашел в куст, то он проиграл. Лабиринт представлен как матрица (список (list) списков): 1 - это куст и 0 - это дорожка. Размер лабиринта N на N клеток и внешние клетки всегда кусты. Игрок начинает в клетке (1, 1). Выход в клетке (N-2, N-2). Вам нужно найти маршрут через Лабиринт. Игрок может двигатся только в четырех направлениях:
- Юг(S) (вниз [1,0]);
- Север(N) (вверх [-1,0]);
- Восток(E) (вправо [0,1]);
- Запад(W) (влево [0, -1]).
Маршрут описывается строкой состоящей из следующих символов: "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))
Ссылки по теме
- Необыкновенный способ генерации лабиринтов
- Алгоритмы на лабиринтах