{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9a863658",
   "metadata": {},
   "source": [
    "# Отчёт: Поиск выхода из лабиринта (ООП + паттерны проектирования)\n",
    "\n",
    "## Цель работы\n",
    "\n",
    "Разработать гибкую расширяемую программу для загрузки лабиринта из файла, поиска пути от старта до выхода с возможностью выбора алгоритма и экспериментального сравнения алгоритмов. Применить минимум 3 паттерна проектирования из списка GoF, обосновать их выбор и продемонстрировать преимущества такой архитектуры.\n",
    "\n",
    "---\n",
    "\n",
    "## Описание задачи и выбранных паттернов\n",
    "\n",
    "Программа решает задачу поиска пути в лабиринте, загружаемом из текстового файла. Лабиринт представляет собой сетку клеток, где `#` — стена, пробел — проход, `S` — старт, `E` — выход. Алгоритм поиска выбирается динамически, результаты выводятся через систему событий.\n",
    "\n",
    "В проекте применены паттерны Builder, Strategy, Observer и Command.\n",
    "\n",
    "### 1. Builder (Строитель) — `MazeBuilder.py`\n",
    "\n",
    "**Проблема:** построение объекта `Maze` из текстового файла включает несколько этапов: чтение файла, анализ символов, создание объектов клеток, определение стартовой и конечной позиции, формирование структуры лабиринта.\n",
    "\n",
    "**Решение:** создан абстрактный класс `MazeBuilder` с методом `build_from_file()`. Класс `TextFileMazeBuilder` реализует построение лабиринта из текстового файла.\n",
    "\n",
    "```python\n",
    "class MazeBuilder(ABC):\n",
    "    @abstractmethod\n",
    "    def build_from_file(self, filename) -> Maze:\n",
    "        pass\n",
    "```\n",
    "\n",
    "```python\n",
    "class TextFileMazeBuilder(MazeBuilder):\n",
    "    def build_from_file(self, filename) -> Maze:\n",
    "```\n",
    "\n",
    "Паттерн позволяет изолировать логику построения лабиринта от основной программы. При необходимости можно добавить другой формат загрузки без изменения клиентского кода.\n",
    "\n",
    "### 2. Strategy (Стратегия) — `FindingStrategy.py`\n",
    "\n",
    "**Проблема:** алгоритмы BFS, DFS и A* имеют разную реализацию, но используются одинаковым образом.\n",
    "\n",
    "**Решение:** создан интерфейс `PathFindingStrategy` с методом `find_path()`. Алгоритмы `BFSStrategy`, `DFSStrategy` и `AStarStrategy` реализуют общий интерфейс.\n",
    "\n",
    "```python\n",
    "class PathFindingStrategy(ABC):\n",
    "    @abstractmethod\n",
    "    def find_path(self, maze, start, exit_cell):\n",
    "        pass\n",
    "```\n",
    "\n",
    "Смена алгоритма выполняется динамически:\n",
    "\n",
    "```python\n",
    "solver.set_strategy(BFSStrategy())\n",
    "solver.solve()\n",
    "\n",
    "solver.set_strategy(AStarStrategy())\n",
    "solver.solve()\n",
    "```\n",
    "\n",
    "Паттерн Strategy позволяет добавлять новые алгоритмы поиска без изменения класса `MazeSolver`.\n",
    "\n",
    "### 3. Observer (Наблюдатель) — `MazeSolver.py`\n",
    "\n",
    "**Проблема:** необходимо уведомлять интерфейс о событиях поиска пути без жёсткой связи между логикой и выводом.\n",
    "\n",
    "**Решение:** реализован интерфейс `Observer` с методом `update()`. Класс `ConsoleView` подписывается на события `MazeSolver`.\n",
    "\n",
    "```python\n",
    "class Observer(ABC):\n",
    "    @abstractmethod\n",
    "    def update(self, event, data=None):\n",
    "        pass\n",
    "```\n",
    "\n",
    "```python\n",
    "solver.add_observer(view)\n",
    "```\n",
    "\n",
    "При нахождении пути вызывается уведомление:\n",
    "\n",
    "```python\n",
    "self._notify('path_found', {\n",
    "    'stats': stats,\n",
    "    'strategy': type(self.strategy).__name__\n",
    "})\n",
    "```\n",
    "\n",
    "Паттерн позволяет отделить вывод информации от алгоритмов поиска.\n",
    "\n",
    "### 4. Command (Команда) — `MazeSolver.py`\n",
    "\n",
    "**Проблема:** необходимо реализовать возможность перемещения игрока с поддержкой отмены действий.\n",
    "\n",
    "**Решение:** создан интерфейс `Command` с методами `execute()` и `undo()`. Класс `MoveCommand` хранит предыдущее состояние игрока.\n",
    "\n",
    "```python\n",
    "class Command(ABC):\n",
    "    @abstractmethod\n",
    "    def execute(self):\n",
    "        pass\n",
    "\n",
    "    @abstractmethod\n",
    "    def undo(self):\n",
    "        pass\n",
    "```\n",
    "\n",
    "```python\n",
    "cmd.execute()\n",
    "cmd.undo()\n",
    "```\n",
    "\n",
    "Паттерн инкапсулирует действия в отдельные объекты и позволяет реализовать undo/redo.\n",
    "\n",
    "---\n",
    "\n",
    "## Диаграмма классов (Mermaid)\n",
    "\n",
    "```mermaid\n",
    "classDiagram\n",
    "    class MazeBuilder {\n",
    "        <<interface>>\n",
    "        +build_from_file(filename) Maze\n",
    "    }\n",
    "\n",
    "    class TextFileMazeBuilder {\n",
    "        +build_from_file(filename) Maze\n",
    "    }\n",
    "\n",
    "    class Cell {\n",
    "        +x\n",
    "        +y\n",
    "        +is_wall\n",
    "        +is_start\n",
    "        +is_exit\n",
    "        +is_passable()\n",
    "    }\n",
    "\n",
    "    class Maze {\n",
    "        +width\n",
    "        +height\n",
    "        +get_cell(x, y)\n",
    "        +get_neighbors(cell)\n",
    "        +render(path, player_pos)\n",
    "    }\n",
    "\n",
    "    class PathFindingStrategy {\n",
    "        <<interface>>\n",
    "        +find_path(maze, start, exit)\n",
    "    }\n",
    "\n",
    "    class BFSStrategy\n",
    "    class DFSStrategy\n",
    "    class AStarStrategy\n",
    "\n",
    "    class MazeSolver {\n",
    "        +set_strategy(strategy)\n",
    "        +solve()\n",
    "        +add_observer(observer)\n",
    "    }\n",
    "\n",
    "    class SearchStats\n",
    "\n",
    "    class Observer {\n",
    "        <<interface>>\n",
    "        +update(event, data)\n",
    "    }\n",
    "\n",
    "    class ConsoleView\n",
    "\n",
    "    class Command {\n",
    "        <<interface>>\n",
    "        +execute()\n",
    "        +undo()\n",
    "    }\n",
    "\n",
    "    class MoveCommand\n",
    "    class Player\n",
    "\n",
    "    MazeBuilder <|.. TextFileMazeBuilder\n",
    "    Maze o-- Cell\n",
    "\n",
    "    PathFindingStrategy <|.. BFSStrategy\n",
    "    PathFindingStrategy <|.. DFSStrategy\n",
    "    PathFindingStrategy <|.. AStarStrategy\n",
    "\n",
    "    MazeSolver --> Maze\n",
    "    MazeSolver --> PathFindingStrategy\n",
    "    MazeSolver --> SearchStats\n",
    "\n",
    "    Observer <|.. ConsoleView\n",
    "    MazeSolver --> Observer\n",
    "\n",
    "    Command <|.. MoveCommand\n",
    "    MoveCommand --> Player\n",
    "```\n",
    "\n",
    "---\n",
    "\n",
    "## Ключевые фрагменты реализации\n",
    "\n",
    "### Реализация BFS\n",
    "\n",
    "```python\n",
    "class BFSStrategy(PathFindingStrategy):\n",
    "    def find_path(self, maze, start, exit_cell):\n",
    "        queue = deque([start])\n",
    "        came_from = {(start.x, start.y): None}\n",
    "```\n",
    "\n",
    "Алгоритм BFS выполняет поиск в ширину и гарантирует нахождение кратчайшего пути.\n",
    "\n",
    "### Реализация DFS\n",
    "\n",
    "```python\n",
    "class DFSStrategy(PathFindingStrategy):\n",
    "    def find_path(self, maze, start, exit_cell):\n",
    "        stack = [start]\n",
    "```\n",
    "\n",
    "DFS использует стек и выполняет поиск в глубину.\n",
    "\n",
    "### Реализация A*\n",
    "\n",
    "```python\n",
    "class AStarStrategy(PathFindingStrategy):\n",
    "\n",
    "    def _heuristic(self, cell, goal):\n",
    "        return abs(cell.x - goal.x) + abs(cell.y - goal.y)\n",
    "```\n",
    "\n",
    "A* использует манхэттенскую эвристику для направления поиска к цели.\n",
    "\n",
    "---\n",
    "\n",
    "## Экспериментальная часть\n",
    "\n",
    "### Параметры эксперимента\n",
    "\n",
    "| Параметр   | Значение                             |\n",
    "| ---------- | ------------------------------------ |\n",
    "| Повторений | 7                                    |\n",
    "| Алгоритмы  | BFS, DFS, A*                         |\n",
    "| Метрики    | время, посещённые клетки, длина пути |\n",
    "\n",
    "### Тестовые лабиринты\n",
    "\n",
    "| Название      | Размер  |\n",
    "| ------------- | ------- |\n",
    "| small_10x10   | 10×10   |\n",
    "| medium_50x50  | 50×50   |\n",
    "| large_100x100 | 100×100 |\n",
    "| open_50x50    | 50×50   |\n",
    "| no_exit_20x20 | 20×20   |\n",
    "\n",
    "---\n",
    "\n",
    "## Результаты\n",
    "\n",
    "### Таблица результатов\n",
    "\n",
    "| Лабиринт      | Алгоритм | Время (мс) | Посещено клеток | Длина пути |\n",
    "| ------------- | -------- | ---------- | --------------- | ---------- |\n",
    "| small_10x10   | BFS      | 0.094      | 54              | 15         |\n",
    "| small_10x10   | DFS      | 0.059      | 33              | 33         |\n",
    "| small_10x10   | A*       | 0.078      | 36              | 15         |\n",
    "| medium_50x50  | BFS      | 2.446      | 1639            | 95         |\n",
    "| medium_50x50  | DFS      | 1.480      | 1063            | 185        |\n",
    "| medium_50x50  | A*       | 1.528      | 588             | 95         |\n",
    "| large_100x100 | BFS      | 9.891      | 6564            | —          |\n",
    "| large_100x100 | DFS      | 9.057      | 6564            | —          |\n",
    "| large_100x100 | A*       | 17.578     | 6564            | —          |\n",
    "| open_50x50    | BFS      | 3.296      | 2304            | 95         |\n",
    "| open_50x50    | DFS      | 1.830      | 1223            | 1129       |\n",
    "| open_50x50    | A*       | 5.566      | 2304            | 95         |\n",
    "| no_exit_20x20 | BFS      | 0.368      | 260             | —          |\n",
    "| no_exit_20x20 | DFS      | 0.343      | 260             | —          |\n",
    "| no_exit_20x20 | A*       | 0.607      | 260             | —          |\n",
    "\n",
    "### Визуализация\n",
    "\n",
    "![Время выполнения](data/chart_время-мс.png)\n",
    "\n",
    "![Посещено клеток](data/chart_посещено-клеток.png)\n",
    "\n",
    "![Длина пути](data/chart_длина-пути.png)\n",
    "\n",
    "---\n",
    "\n",
    "## Анализ результатов\n",
    "\n",
    "### BFS\n",
    "\n",
    "Алгоритм BFS во всех случаях находит кратчайший путь. На лабиринте medium_50x50 длина найденного пути составила 95 шагов. Недостатком алгоритма является большое количество посещённых клеток.\n",
    "\n",
    "### DFS\n",
    "\n",
    "DFS выполняет поиск быстрее, однако найденный путь значительно длиннее. На open_50x50 длина пути составила 1129 шагов против 95 у BFS.\n",
    "\n",
    "### A*\n",
    "\n",
    "Алгоритм A* использует эвристику и уменьшает количество посещённых клеток. На medium_50x50 было посещено 588 клеток против 1639 у BFS.\n",
    "\n",
    "На открытом лабиринте преимущества эвристики снижаются, из-за чего время работы увеличивается.\n",
    "\n",
    "### Лабиринты без пути\n",
    "\n",
    "На large_100x100 и no_exit_20x20 путь найден не был. Все алгоритмы корректно завершили работу после обхода доступных клеток.\n",
    "\n",
    "---\n",
    "\n",
    "## Выводы\n",
    "\n",
    "В ходе работы была реализована объектно-ориентированная система поиска пути в лабиринте с применением паттернов проектирования GoF.\n",
    "\n",
    "Паттерн Strategy обеспечил возможность динамической смены алгоритма поиска. Builder отделил процесс создания лабиринта от логики приложения. Observer позволил реализовать систему уведомлений без жёстких зависимостей. Command обеспечил поддержку отмены действий.\n",
    "\n",
    "Экспериментальные результаты показали:\n",
    "\n",
    "* BFS гарантирует кратчайший путь;\n",
    "* DFS работает быстрее, но может находить неоптимальные маршруты;\n",
    "* A* наиболее эффективен на сложных лабиринтах благодаря эвристике.\n",
    "\n",
    "Архитектура программы получилась модульной и расширяемой. Добавление новых алгоритмов или способов загрузки лабиринтов возможно без изменения существующего кода.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9cbb6c6",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
