🧩 Как найти путь из лабиринта с помощью Python

🧩 Как найти путь из лабиринта с помощью Python?

Представь себе лабиринт, в котором нужно дойти от точки S (Start) до точки E (End), обходя стены #. Звучит как игра, но на деле — это задача поиска пути в графе.

Вот такой лабиринт:

S..#...

##.#...

.......

.#.....

..#....

..#....

..#....

E##....

📌 Решаем с помощью алгоритма поиска в ширину (BFS). Он подходит, если нам нужен самый короткий путь.

Код короткий, но мощный: он находит путь шаг за шагом, отмечает посещённые клетки и возвращает маршрут.

🔍 Главное:

1. Старт и финиш находятся автоматически

2. Препятствия (#) обойти нельзя

3. Если путь есть — он будет найден

💻 Пример реализации:

MAZE = [

list("S..#..."),

list("##.#..."),

list("......."),

list(".#....."),

list("..#...."),

list("..#...."),

list("..#...."),

list("E##...."),

]

ROWS = len(MAZE)

COLS = len(MAZE[0])

DELAY = 0.1

def find_start_and_end(maze):

start = end = None

for i in range(ROWS):

for j in range(COLS):

if maze[i][j] == 'S':

start = (i, j)

elif maze[i][j] == 'E':

end = (i, j)

return start, end

def draw_maze(stdscr, maze, path=None):

stdscr.clear()

for i, row in enumerate(maze):

for j, ch in enumerate(row):

color = curses.color_pair(0)

if ch == '#':

color = curses.color_pair(1)

elif ch == '.':

color = curses.color_pair(2)

elif ch == '*':

color = curses.color_pair(3)

elif ch == 'S':

color = curses.color_pair(4)

elif ch == 'E':

color = curses.color_pair(5)

elif ch == 'o':

color = curses.color_pair(6)

stdscr.addstr(i, j * 2, ch + ' ', color)

stdscr.refresh()

time.sleep(DELAY)

def bfs_visual(stdscr, maze):

start, end = find_start_and_end(maze)

visited = set()

queue = deque()

queue.append((start, [start]))

visited.add(start)

while queue:

(x, y), path = queue.popleft()

if maze[x][y] not in ('S', 'E'):

maze[x][y] = '*'

draw_maze(stdscr, maze)

if (x, y) == end:

return path

for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:

nx, ny = x + dx, y + dy

if 0 <= nx < ROWS and 0 <= ny < COLS:

if maze[nx][ny] in ('.', 'E') and (nx, ny) not in visited:

visited.add((nx, ny))

queue.append(((nx, ny), path + [(nx, ny)]))

return None

def mark_final_path(stdscr, maze, path):

for (x, y) in path:

if maze[x][y] not in ('S', 'E'):

maze[x][y] = 'o'

draw_maze(stdscr, maze)

def main(stdscr):

curses.curs_set(0)

curses.start_color()

curses.init_pair(1, curses.COLOR_BLACK, curses.COLOR_WHITE) # стена

curses.init_pair(2, curses.COLOR_WHITE, curses.COLOR_BLACK) # пусто

curses.init_pair(3, curses.COLOR_RED, curses.COLOR_BLACK) # текущая ячейка

curses.init_pair(4, curses.COLOR_CYAN, curses.COLOR_BLACK) # старт

curses.init_pair(5, curses.COLOR_GREEN, curses.COLOR_BLACK) # финиш

curses.init_pair(6, curses.COLOR_YELLOW, curses.COLOR_BLACK) # финальный путь

final_path = bfs_visual(stdscr, MAZE)

time.sleep(0.5)

if final_path:

mark_final_path(stdscr, MAZE, final_path)

stdscr.addstr(ROWS + 1, 0, "Путь найден!", curses.color_pair(5))

else:

stdscr.addstr(ROWS + 1, 0, "Путь не найден!", curses.color_pair(3))

stdscr.refresh()

stdscr.getch()

if __name__ == "__main__":

curses.wrapper(main)

✨ Такой алгоритм лежит в основе навигации в играх, робототехнике и даже GPS-системах!