ДЗ Лабораторная работа №6 "Алгоритм A*"#

Критерий оценки:
- Реализовать решение для заданной картинки на python (3 балла)
- Реализовать решение для заданной картинки на C++ (5 баллов)
- Добавить решение для случайно сгенерирированного поля (+2 балл)
- Добавить решение для случайно сгенерированной карты (+3 балла) (карта отличается от поля тем, что каждой клетке присвоен некоторый вес)

В отчете должно быть указано следующие:
1. Титульный лист, где указаны ФИО преподавателя, номер задания, номер варианта
2. Формулировка задания (картинка)
3. Ссылка на github-репозиторий с работающим кодом
4. Блок-схема алгоритма А*
5. Листинг 1. Откоментированный код метода А_star.
6. Пример расчета алгоритма А* для вашего варианта (манхэтонское расстоянеи)
7. Рисунки демонстраторы работы проекта с комментариями где была точка старта. Для карт добавить легенду.
8. Листинг 2. Откомментированный полный код вашего проекта.

Описание Алгоритма А*#

A* — это алгоритм поиска пути, находящий кратчайший путь от начальной вершины до целевой в графе, используя эвристическую функцию для оценки стоимости.

Обозначения
- g(n) — стоимость пути от начальной вершины до вершины n.
- h(n) — эвристическая оценка оставшегося расстояния от n до цели.
- f(n) = g(n) + h(n) — полная оценка стоимости пути через n.

Псевдокод

1. Добавить начальную вершину в открытый список (open list).
2. Пока открытый список не пуст:
   - Извлечь вершину `n` с наименьшим `f(n)`.
   - Если `n` — целевая вершина, путь найден.
   - Переместить `n` в закрытый список (closed list).
   - Для каждой соседней вершины `m`:
     - Если `m` в закрытом списке, пропустить.
     - Вычислить `g(m)`, `h(m)`, `f(m)`.
     - Если `m` нет в открытом списке или найден более короткий путь к `m`, сохранить путь и добавить `m` в открытый список.

Пример#

Пусть есть следующая сетка (S — старт, G — цель, # — стена):

S . . .
# # . #
. . . G

Координаты:
- S = (0, 0)
- G = (2, 3)

Допущения:
- Стоимость перехода на соседнюю клетку (вверх, вниз, влево, вправо) = 1
- Эвристика h(n) = манхэттенское расстояние

Шаг	Текущая	Open list	Closed list	Примечание
1	(0,0)	[(0,1), (1,0)]	[(0,0)]	h(0,0)=5
2	(0,1)	[(1,0), (0,2)]	[(0,0),(0,1)]	f=1+4=5
3	(0,2)	[(1,2)]	[(0,0),(0,1),(0,2)]	f=2+3=5
4	(1,2)	[(2,2)]	...	f=3+2=5
5	(2,2)	[(2,3)]	...	f=4+1=5
6	(2,3)	[]	...	f=5+0=5, цель достигнута

Итоговый путь (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,3)

Подсказки по написанию и работе кода#

Создание и работа с ячейками (`Cell`)#

Каждый объект Cell представляет отдельную ячейку на сетке.
Метод update_neighbors обновляет список соседей, в которые можно перейти (не препятствия).
Методы make_start(), make_end(), make_barrier() и др. задают тип и цвет ячейки.

Работа с сеткой#

Сетка создаётся функцией make_grid(), которая возвращает список списков объектов Cell.
Функция draw_grid(win, grid) отрисовывает ячейки и линии сетки.

Алгоритм A*#

Реализован в функции a_star_algorithm.
Используется манхэттенское расстояние: abs(x1 - x2) + abs(y1 - y2).
Каждая ячейка содержит:
g — расстояние от старта;
h — оценка до цели;
f = g + h.

Поиск пути#

PriorityQueue используется для выбора ячейки с минимальным f.
open_set_hash — вспомогательное множество для ускоренной проверки наличия в очереди.
reconstruct_path восстанавливает путь по словарю came_from.

Обработка событий и клавиш#

Нажмите SPACE, чтобы запустить алгоритм A*.
Нажмите R, чтобы сгенерировать новое случайное поле.
Окно закрывается при событии QUIT.

Цвета в визуализации#

Цвет	Значение
Белый	Пустая ячейка
Чёрный	Препятствие
Оранжевый	Начало
Бирюзовый	Конец
Зелёный	В очереди
Красный	Посещена
Фиолетовый	Путь

Некоторые фрагменты кода с комментариями#

PythonC++

    import pygame
    import random
    import math
    from queue import PriorityQueue

    # Инициализация Pygame
    pygame.init()

    # Константы
    WIDTH = 600
    GRID_SIZE = 30  # Размер поля NxN
    CELL_SIZE = WIDTH // GRID_SIZE
    WIN = pygame.display.set_mode((WIDTH, WIDTH))
    pygame.display.set_caption("A*")

    # Цвета
    RED = (255, 0, 0)
    GREEN = (0, 255, 0)
    BLUE = (0, 0, 255)
    YELLOW = (255, 255, 0)
    WHITE = (255, 255, 255)
    BLACK = (0, 0, 0)
    PURPLE = (128, 0, 128)
    ORANGE = (255, 165, 0)
    GREY = (128, 128, 128)
    TURQUOISE = (64, 224, 208)

    # Типы ячеек
    EMPTY = 0
    OBSTACLE = 1
    START = 2
    END = 3
    PATH = 4
    VISITED = 5

    def make_grid():
        grid = []
        for i in range(GRID_SIZE):
            grid.append([])
            for j in range(GRID_SIZE):
                cell = Cell(i, j)
                grid[i].append(cell)
        return grid

    def draw_grid(win, grid):
        for row in grid:
            for cell in row:
                cell.draw(win)

        # Рисуем сетку
        for i in range(GRID_SIZE):
            pygame.draw.line(win, GREY, (0, i * CELL_SIZE), (WIDTH, i * CELL_SIZE))
            pygame.draw.line(win, GREY, (i * CELL_SIZE, 0), (i * CELL_SIZE, WIDTH))

        pygame.display.update()

    def generate_random_grid(grid):
        # Очищаем сетку
        for row in grid:
            for cell in row:
                cell.reset()

        # Выбираем случайные начальную и конечную точки
        start_row, start_col = random.randint(0, GRID_SIZE-1), random.randint(0, GRID_SIZE-1)
        end_row, end_col = random.randint(0, GRID_SIZE-1), random.randint(0, GRID_SIZE-1)

        # Убедимся, что начальная и конечная точки разные
        while (start_row, start_col) == (end_row, end_col):
            end_row, end_col = random.randint(0, GRID_SIZE-1), random.randint(0, GRID_SIZE-1)

        start = grid[start_row][start_col]
        end = grid[end_row][end_col]

        start.make_start()
        end.make_end()

        # Добавляем случайные препятствия (20% ячеек)
        obstacle_count = int(GRID_SIZE * GRID_SIZE * 0.2)
        for _ in range(obstacle_count):
            row, col = random.randint(0, GRID_SIZE-1), random.randint(0, GRID_SIZE-1)
            cell = grid[row][col]
            if not cell.is_start() and not cell.is_end():
                cell.make_barrier()

        return start, end

    #include <SFML/Graphics.hpp>
    #include <iostream>
    #include <vector>
    #include <queue>
    #include <cmath>
    #include <algorithm>
    #include <random>

    using namespace std;
    using namespace sf;

    const int GRID_SIZE = 30; // Размер поля NxN
    const int CELL_SIZE = 25;  // Размер одной ячейки в пикселях
    const int WINDOW_SIZE = GRID_SIZE * CELL_SIZE;

    // Типы ячеек
    enum CellType {
        EMPTY,
        OBSTACLE,
        START,
        END,
        PATH,
        VISITED
    };

    // Структура для представления ячейки
    struct Cell {
        int x, y;
        CellType type;
        int f, g, h; // Для алгоритма A*
        Cell* parent;

        Cell(int x, int y) : x(x), y(y), type(EMPTY), f(0), g(0), h(0), parent(nullptr) {}

        // Перезагрузка оператора == для сравнения ячеек
        bool operator==(const Cell& other) const {
            return x == other.x && y == other.y;
        }
    };

            // Функция для вычисления эвристики (манхэттенское расстояние)
    int heuristic(const Cell& a, const Cell& b) {
        return //ваш код здесь
    }

    // Функция для проверки, находится ли ячейка в пределах сетки
    bool isValid(int x, int y) {
        return //ваш код здесь
    }

Также подсказка как отрисовать

    for (int i = 0; i < GRID_SIZE; ++i) {
        for (int j = 0; j < GRID_SIZE; ++j) {
            RectangleShape cell(Vector2f(CELL_SIZE - 1, CELL_SIZE - 1));
            cell.setPosition(i * CELL_SIZE, j * CELL_SIZE);

            switch (grid[i][j].type) {
            case EMPTY: cell.setFillColor(Color::White); break;
            case OBSTACLE: cell.setFillColor(Color::Black); break;
            case START: cell.setFillColor(Color::Green); break;
            case END: cell.setFillColor(Color::Red); break;
            case PATH: cell.setFillColor(Color::Blue); break;
            case VISITED: cell.setFillColor(Color::Cyan); break;
            }

            window.draw(cell);
        }
    }