🗺️ Описание проекта
Данный проект представляет собой визуализатор алгоритма поиска кратчайшего пути A* (A-Star) на сетке (Grid Map), реализованный на Python с использованием библиотеки PyQt6. Приложение позволяет генерировать случайные лабиринты, вручную добавлять или удалять препятствия (стены) и в реальном времени наблюдать за процессом поиска оптимального пути между стартовой и конечной точкой.
✨ Реализация пользовательских запросов
На основе предоставленного кода были проанализированы и реализованы следующие функции:
-
Простые изменения
-
Клик для добавления/удаления стен
-
Статус: Реализовано.
-
Как реализовано: Пользователь может кликать и перетаскивать левую кнопку мыши (ЛКМ) по карте, чтобы рисовать или стирать стены. Логика находится в методах GridMapWidget.mousePressEvent и GridMapWidget.mouseMoveEvent.
-
Показать длину пути
-
Статус: Реализовано.
-
Как реализовано: По завершении поиска в информационном окне (self.lbl_info) отображается точное количество шагов (ребер) в найденном пути. Расчет и вывод происходит в методе AStarWorker.reconstruct_path.
-
-
-
Новые функции и гибкость
-
Разрешить движение по диагонали
-
Статус: Не реализовано.
-
Комментарий: Текущий код использует только 4-направленное (кардинальное) движение. Для активации диагоналей необходимо изменить функцию AStarWorker.get_neighbors (добавить 8 направлений) и использовать более точную эвристику, например, Евклидово расстояние.
-
Дополнительная интерактивная функция (Гибкость)
-
Статус: Реализована.
-
Комментарий: Функция интерактивного рисования/стирания стен с помощью ЛКМ и перетаскивания является ключевой интерактивной функцией приложения.
-
-
🎓 Теория алгоритма A*
-
Алгоритм A* является одним из самых эффективных алгоритмов поиска пути, поскольку он объединяет информированный поиск (использует эвристику) и гарантию оптимальности.
-
Используемые формулы
-
A* использует функцию стоимости
$F(n)$ , которая определяет приоритет узла$n$ : -
$$F(n) = G(n) + H(n)$$ -
$F(n)$ (Общая стоимость): Оценочная общая стоимость пути от старта до финиша, проходящего через узел$n$ . -
$G(n)$ (Фактическая стоимость): Фактическая стоимость (длина) пути от начальной точки до узла$n$ . -
$H(n)$ (Эвристическая стоимость): Оценочная стоимость пути от узла$n$ до конечной точки.
-
-
В текущем коде используется Манхэттенское расстояние (Manhattan Distance) для расчета эвристики
$H(n)$ , что подходит для 4-направленного движения: -
$$H(n) = |x_{n} - x_{end}| + |y_{n} - y_{end}|$$
Ответы на теоретические вопросы
-
Как компьютер знает, в каком направлении искать?
Алгоритм всегда ищет узел с наименьшей F-стоимостью (
$F = G + H$ ) из своего Открытого списка. Эвристика ($H$ ) направляет поиск к цели, а фактическое расстояние ($G$ ) гарантирует, что найденный путь будет кратчайшим (оптимальным). -
Что будет, если не угадать направление (эвристика окажется неточной)?
Если эвристика приведет алгоритм по неоптимальному пути, G-стоимость (фактическое пройденное расстояние) для этой ветки пути быстро возрастет, что увеличит общую
$F$ -стоимость. Благодаря этому, этот путь будет отброшен в пользу другого кандидата с более низкой$F$ -стоимостью. При использовании допустимой эвристики (как Манхэттенское расстояние) A* всегда находит оптимальный путь. -
Зачем вести два списка клеток?
Open Set (Открытый список): Хранит кандидатов — узлы, которые были обнаружены, но еще не полностью обработаны. Этот список отсортирован по
$F$ -стоимости (используется heapq).Closed Set (Закрытый список): Хранит клетки, уже проверенные и оцененные. Это предотвращает повторную обработку и зацикливание, повышая эффективность.
-
Зачем проверять клетки больше одного раза?
Узел, который уже был добавлен в Open Set, может быть переоценен, если алгоритм находит более короткий путь к нему через другого соседа (то есть, находит более низкую
$G$ -стоимость). В этом случае,$G$ -стоимость узла обновляется, и он заново обрабатывается с новым, лучшим приоритетом$F$ , чтобы обеспечить оптимальность.
💻 Структура кода и назначение компонентов
-
Конфигурация (config.json и load_config)
-
Настройки приложения загружаются из файла config.json или используются значения по умолчанию.
-
Назначение: Определяет размеры сетки, задержку симуляции, плотность стен и цветовые схемы для визуализации.
-
-
Класс Node (Модель данных)
Класс, представляющий одну клетку на сетке.
-
Атрибуты:
-
row, col: Координаты узла.
-
is_wall: Булево значение, указывающее, является ли узел препятствием.
-
state: Текущее состояние узла (empty, open, closed, path, start, end).
-
g_cost, h_cost: Параметры стоимости A*.
-
parent: Ссылка на предыдущий узел в кратчайшем найденном пути.
-
-
Свойства и методы:
-
f_cost: Вычисляемое свойство (
$G + H$ ). -
lt: Реализует сравнение, необходимое для корректной работы кучи приоритетов (heapq).
-
reset_calc: Сбрасывает все стоимостные параметры при запуске нового поиска.
-
-
Класс GridMapWidget (Виджет отрисовки карты)
Виджет PyQt6, отвечающий за визуальное представление сетки и обработку взаимодействия с пользователем.
-
Методы отрисовки:
-
paintEvent(event): Оптимизированный метод отрисовки. Использует QPainter для заполнения прямоугольников цветами, соответствующими состоянию узлов. Рисует только ту часть сетки, которая нуждается в обновлении (partial update).
-
update_node(r, c): Вызывает перерисовку только одной конкретной клетки для повышения производительности во время симуляции.
-
-
Методы взаимодействия:
- mousePressEvent и mouseMoveEvent: Обрабатывают клики и перетаскивание ЛКМ. Определяют, находится ли пользователь в режиме рисования или стирания стен (self.drawing_wall_mode) и вызывают apply_wall.
-
-
Класс AStarWorker (Рабочий поток алгоритма A*)
-
Наследник QThread, выполняет сложный алгоритм A* в отдельном потоке, чтобы избежать зависания графического интерфейса.
-
Сигналы:
-
cell_updated(r, c, state): Отправляет информацию в основной поток, чтобы виджет карты мог обновить цвет измененной клетки.
-
finished_signal(msg): Отправляет сообщение о завершении работы (найден путь или нет).
-
-
Ключевые методы A*:
-
run(): Основной цикл A*. Извлекает узел с минимальным
$F$ из open_set (куча приоритетов), проверяет его соседей и обновляет их стоимости. -
heuristic(node_a, node_b): Вычисляет эвристическое расстояние (
$H$ ) — Манхэттенское расстояние. -
get_neighbors(node): Возвращает список из 4-х соседних узлов (вверх, вниз, влево, вправо), исключая стены.
-
reconstruct_path(end_node): После достижения цели, восстанавливает путь, идя от конечного узла к стартовому по ссылкам parent, и отправляет сигналы на отрисовку найденного пути.
-
-
-
Класс AStarApp (Главное окно приложения)
Основной класс QMainWindow, объединяющий все компоненты.
-
Методы управления данными:
-
init_data: Создает начальную структуру узлов (self.grid_nodes).
-
reset_data: Сбрасывает только параметры поиска или полностью очищает все стены.
-
generate_random_walls: Случайно расставляет стены на карте согласно заданной плотности.
-
-
Методы I/O:
-
load_maze_from_file: Загружает карту из текстового файла (S — старт, E — финиш, # — стена).
-
save_maze_to_file: Сохраняет текущую карту в текстовый файл.
-
-
Управление потоком:
-
start_thread: Инициализирует и запускает AStarWorker.
-
on_cell_updated и on_finished: Слоты, принимающие сигналы от рабочего потока и обновляющие UI (виджет карты и информационную метку).
-
