Picture puzzle на C++. Часть 3

9 мар. 2025 г. 19:00:14 MSK

Заключительная часть. Разбор алгоритма A* для решения головоломки. Внедрение его в программу.

Возвращение к callback-фукнциям

Перед тем как перейти к описанию алгоритму A*, нужно завершить рассмотрение callback-функций, которые связаны с подпунктами меню-бара. Напомню, в первой статье был код из файла main.cpp. Часть из него была следующей:

34    sys_bar->add("&File/&New game", nullptr, new_game_callback, params);
35    sys_bar->add("&File/&Load file", nullptr, load_file_callback);
36    sys_bar->add("&File/&Exit", nullptr, exit_callback);
37    sys_bar->add("&Options/&Show solution", nullptr, solve_problem_callback,
38                 params);
39    sys_bar->add("&About", nullptr, about_callback);

Здесь через метод add передаём callback-функции и данные для неё. При нажатии на подпункт будет вызвана соответствующая функция, а также будут переданы ей параметры (если такие есть). load_file_callback() была рассмотрена в предыдущей статье, поэтому будут рассмотрены new_game_callback(), exit_callback(). solve_problem_callback(), about_callback(). Все они располагаются в файле menu_callbacks.cpp (заголовок для него получается тривиальным, поэтому пропустим его описание).

menu_callbacks.cpp

Каждая функция будет рассмотрена по порядку.

13void new_game_callback(Fl_Widget*, void *gp)
14{
15    if(!reinterpret_cast<GameParams*>(gp)->GetAStarActive())
16        PuzzleGame::StartGame(reinterpret_cast<GameParams*>(gp));
17}

Вышеописанная функция вызывается при выборе в меню New game (новая игра). Перед тем, как действительно создать новую игру, надо удостовериться, взведён ли флаг is_a_star_active: такое происходит, если запущено решение головоломки с помощью алгоритма A*, и пока она решается, мы запрещаем создание новой игры и повторный запуск решения. Вызов метода GetAStarActive() позволяет проверить этот флаг. Он возвращает логическое значение is_a_star_active. Если оно false, то вызывается статический метод StartGame, который уже описывался в 1-ой статье (кратко говоря, выбирает случайное изображение и создаёт виджеты-пазлы).

Далее exit_callback(). Здесь просто вызываем exit(0) функцию из библиотеки C для завершения процесса с передачей аргумента 0 (код завершения процесса).

53void exit_callback(Fl_Widget *w, void*)
54{
55    exit(0);
56}

Первоначально был вариант с использованием сокрытия главного окна, но он не будет работать в случае, когда пользователь запустил решение головоломки с помощью алгоритма A*: окно действительно будет скрыто, но процесс продолжит выполнять код алгоритма.

Теперь перейдем к описанию метода solve_problem_callback():

58void solve_problem_callback(Fl_Widget *w, void *gp)
59{
60    GameParams *game = reinterpret_cast<GameParams*>(gp);
61    if(game->GetAStarActive())
62        return;
63    game->SetAStarActive();
64    std::unique_ptr<ASearch> algorithm = ASearch::Start(game);
65    Node *goal = algorithm->FindSolution();
66    algorithm->ShowSolution(goal);
67    game->ResetAStarActive();
68    int answer = fl_choice("Play again?", "No", "Yes", nullptr);
69    if(answer)
70        PuzzleGame::StartGame(game);
71    else
72        game->win->hide();
73}

С этой функцией связан подпункт меню Options->Show solution. Сначала мы проверяем флаг is_a_star_active через метод GetAStarActive, чтобы предотвратить повторный запуск решения: такое может произойти, если пользователь нажмёт пункт меню Show solution уже во время выполнения алгоритма A*. В 63 и 67 строках вышеописанного кода взводим и убираем соответственно флаг is_a_star_active. Через std::unique_ptr<ASearch> algorithm = ASearch::Start(game); вызывается статический метод класса ASearch (будет описан ниже в статье) для инициализации начальных параметров необходимых для алгоритма A*. Метод вернёт объект ASearch. Мы этот объект сразу оборачиваем в интеллектуальный указатель, т.к. он создан в динамической памяти — это поможет не отслеживать момент освобождения занятой памяти объектом ASearch. Далее мы из него вызывыаем метод FindSolution(), который отвечает за запуск вычисления алгоритмом A* решения головоломки:

65Node *goal = algorithm->FindSolution();

Здесь, как видим, возвращается указатель на объект Node, представляющий собой финальное состояние игры. В нём будет храниться самый короткий путь от текущего состояния головолоки до финального. Чтобы пройти этот путь и показать по порядку каждый шаг игры, вызывается algorithm->ShowSolution(goal) с передачей аргумента goal.

После отображения пазлов в фильном порядке выводим диалоговое окно с выбором:

68    int answer = fl_choice("Play again?", "No", "Yes", nullptr);
69    if(answer)
70        PuzzleGame::StartGame(game);
71    else
72        game->win->hide();

Принцип передачи аргументов уже был описан в первой статье: там тоже использовался этот метод. Исходя из того, что выбрал пользователь, будет создана новая игра или организован выход из программы.

Последняя callback-функция — это about_callback:

75void about_callback(Fl_Widget *w, void*)
76{
77    fl_message_title("About");
78    fl_message("This app is devoted to my friends, to who I'm appreciative for"
79               " their support:\nIlya Korsak\nMaxim Fadeev\n\n"
80               "For all questions, please contact me:\n"
81               "m@@scratko.xyz");
82}

Тут всё просто. fl_message представляет собой информационное диалоговое окно. Через его конструктор передаётся строковый литерал с информацией об программе.

Алгоритм A*

Краткие сведения

В игре сделана возможность “сдаться” — это запустит алгоритм решения головоломки. Правда стоит отметить, что в игре с 8 пазлами такая фича может показаться излишней, но при реализации игры с большим количеством пазлов (один из популярных вариантов — 15) может быть вполне оправдана. Алгоритм был внедрён в текущую игру для наглядности и проверки его работоспособности. Он называется A*.

Алгоритм A* можно рассматривать как модификацию алгоритма Дейкстры. Последний учитывает только веса рёбер, заданные в графе, тогда как A* дополнительно использует эвристическую функцию для предсказания расстояния до цели. В качестве алгоритма поиска пути был выбран A*, так как он эффективнее Дейкстры в задачах, где важно быстро найти оптимальное решение. В программе A* использует эвристику для оценки расстояния (Манхэттенское расстояние) до целевого состояния, что позволяет быстрее прийти к правильному решению, избегая лишних переборов.

Алгоритм A* традиционно применяется для поиска кратчайшего пути в графах, где рёбра имеют различные веса. Однако в программе используется дерево поиска состояний, а не общий граф. Это связано с тем, что каждое состояние (конфигурация плиток) порождает новые состояния путём перемещения пустой клетки, и при таком подходе мы не строим весь граф состояний заранее, а динамически формируем только ту его часть, которая нужна для поиска решения.

Хотя одно и то же состояние может встречаться на разных путях, алгоритм A* позволяет фильтровать повторные состояния. Если новое состояние уже встречалось ранее, то оно либо игнорируется, либо обновляется, если найден более короткий путь к нему. Это позволяет эффективно организовать поиск, сохраняя структуру разворачиваемого дерева вместо хранения всего графа.

Кроме того, в данной задаче все переходы между состояниями имеют одинаковую стоимость, равную 1, поскольку любое перемещение пустой клетки считается единичным шагом. Это делает применение A* особенно удобным: алгоритм учитывает пройденный путь и эвристику (Манхэттенское расстояние), что позволяет быстрее находить оптимальное решение, избегая избыточных вычислений.

Таким образом, вместо графа используется дерево поиска, поскольку оно формируется в процессе работы алгоритма, а повторные состояния обрабатываются без явного построения всей структуры.

В итоге во время работы алгоритма получается вот такая примерно структура:

tree

На изображении выше видно, что каждый узел дерева представляет собой определённое состояние игры. Также очевидно, что чем дальше от корня дерева находится узел, тем больше будет длина до него (сложение рёбер).

На каждой итерации алгоритм A* выбирает из множества открытых состояний то, у которого оценочная функция f(n) имеет наименьшее значение. Эта функция помогает определить, какое состояние доски стоит рассмотреть в первую очередь.

Формула f(n) выглядит так: f(n) = g(n) + h(n), где:

g(n) — стоимость пути от начального состояния до текущего состояния nn, то есть сколько ходов уже было сделано.

h(n) — эвристическая оценка расстояния от текущего состояния до конечного. В данной задаче используется Манхэттенское расстояние, которое приближённо оценивает, сколько ещё ходов потребуется, если двигать плитки по кратчайшему пути без учёта препятствий.

Такой подход позволяет алгоритму одновременно учитывать уже пройденный путь (g(n)) и делать прогноз, насколько далеко находится цель (h(n)), что ускоряет поиск решения.

Псевдокод алгоритма A*

С учётом его реализации в текущей программе:

search(initial, goal)
    initial.depth = 0  // depth = g(n)
    score(initial)  // Вычисляем f(n) = g(n) + h(n)
    open = new PriorityQueue
    closed = new UnorderedSet
    insert(open, initial)

    while open не пуст do
        n = minimum(open)  // Достаем узел с наименьшим f(n)
        remove(open, n)
        insert(closed, n)  // Добавляем узел в closed

        if n = goal then return "Решено"

        foreach допустимый ход next_state из состояния n do
            if существует узел в closed с таким же состоянием then continue

            next_state.depth = n.depth + 1  // depth = g(n) + 1
            score(next_state)  // Пересчитываем f(n)

            if next_state отсутствует в open then
                insert(open, next_state)
            else if next_state.score < score(соответствующего узла из open) then
                erase(open, соответствующий узел)
                insert(open, next_state)

    return "Решения нет"
end

depth отражает g(n). Функция score() должна вычислять f(n) = g(n) + h(n). PriorityQueue является очередью с приоритетом: узлы с наименьшей оценкой (высокий приоритет) будут в самом начале. UnorderedSet — это неупорядоченный набор, который реализован через хэш-таблицу для быстрого поиска уже посещенных узлов.

solution_algorithm.hpp

Реализация алгоритма A* содержится в заголовочном файле solution_algorithm.hpp и файле реализации solution_algorithm.cpp. Сначала рассмотрим первый из них.

Так как полное содержание файла будет неудобно к рассмотрению, то естественно разбить его на части с последующим описанием. Начнём с класса Node:

13class Node {
14private:
15    std::vector<GameParams::coordinates> state;
16    Node *parent_p;
17    int depth;
18    int evaluation;
19public:
20    Node(std::vector<GameParams::coordinates>& s, Node *p = nullptr,
21         int d = 0, int e = 0)
22        : state(s), parent_p(p), depth(d), evaluation(e) {}
23    bool operator==(const Node& n) const { return this->state == n.state; }
24
25    struct Comp {
26        bool operator()(const std::shared_ptr<Node>& first,
27                        const std::shared_ptr<Node>& second) {
28            return first->evaluation > second->evaluation;
29        }
30    };
31    struct EqualNode {
32        bool operator()(const std::shared_ptr<Node>& first,
33                        const std::shared_ptr<Node>& second) const {
34            return *first == *second;
35        }
36    };
37
38    friend struct std::hash<std::shared_ptr<Node>>;
39    friend class ASearch;
40};

Как очевидно из названия, класс представляет собой узел дерева поиска состояний. Сам узел состоит из:

Состояние игры state. Это контейнер vector, в котором по порядку будут добавляться координаты каждого виджета на текущем шагу (т.е. после передвижения плитки). Главное понять, что нумерация виджетов у нас происходит сверху вниз (по столбцам).
Указатель на родительское состояние *parent_p. Это нужно для того, чтобы легко было восстановить порядок прохода при отображении результата.
depth является g(n). Длина пути до текущего состояния. Также это глубина прохода по дереву.
evaluation хранит f(n), т.е. итоговую оценку состояния. Исходя из нее будут выбираться узлы из очереди std::priority_queue (open) рассматриваемых состояний.

Конструктор у этого класса один. Обязательно нужно передать контейнер vector с соответствующим состоянием. У родительского состояния parent_p будет содержать nullptr, остальные должны заполнить указатель на родитель. Оставшиеся параметры будут заполнены нулями:

20    Node(std::vector<GameParams::coordinates>& s, Node *p = nullptr,
21         int d = 0, int e = 0)
22        : state(s), parent_p(p), depth(d), evaluation(e) {}

Далее можно заметить переопределение операции ==. Это сделано для того, чтобы в std::priority_queue (очередь рассматриваемых вершин) при сравнении на равенство узлов сравнивалось именно состояние: каждая координата виджетов по x и y. Таким образом, мы узнаем, были ли уже в этом состояние и, при необходимости, изменяем оценку узла. Однако сравнение контейнеров состояний происходит через сравнение элементов GameParams::coordinates. Описание класса GameParams было в 1-ой части, сейчас же просто продублирую ту часть, которая отвечает за сравнение:

37class GameParams {
38public:
39    struct coordinates {
40        int x, y;
41        bool operator==(const coordinates& v) const {
42            return this->x == v.x && this->y == v.y;
43        }
44    };

Далее в классе Node располагаются 2 структуры: Comp и EqualNode:

25    struct Comp {
26        bool operator()(const std::shared_ptr<Node>& first,
27                        const std::shared_ptr<Node>& second) {
28            return first->evaluation > second->evaluation;
29        }
30    };
31    struct EqualNode {
32        bool operator()(const std::shared_ptr<Node>& first,
33                        const std::shared_ptr<Node>& second) const {
34            return *first == *second;
35    };

Comp нужен для PriorityQueue. По умолчанию он сравнивает элементы через операцию <, из-за чего большие по значению элементы оказываются в начале. Можно было бы использовать предопределенный функтор std::greater<T>, но нам нужно сравнивать не сами элементы, а их оценки. Да и к тому же у нас элементы обёрнуты в интеллектуальные указатели shared_ptr (при обычном сравнении будут сравниваться адреса). Поэтому выражение first->evaluation > second->evaluation гарантирует, что узлы с минимальными оценками будут находиться в начале очереди.

EqualNode потребуется для std::unordered_set (close). Дело в том, что для каждого элемента вычисляется его хэш, а затем элемент попадает в один из бакетов. Иногда может случиться так, что разные элементы дадут одинаковый хэш — в этом случае все такие элементы окажутся в одном бакете. После этого для поиска нужного элемента выполняется попарное сравнение внутри бакета. У нас это сравнение реализовано через переопределённую операцию == (описана выше в классе Node).

Далее в solution_algorithm.hpp рассмотрим следующий кусок кода:

42template<>
43struct std::hash<std::shared_ptr<Node>> {
44    std::size_t operator()(const std::shared_ptr<Node>& node) const {
45        std::string str_hash;
46        std::for_each(node->state.begin(), node->state.end(),
47                      [&str_hash](const GameParams::coordinates& c) {
48                          str_hash.append(std::to_string(c.x));
49                          str_hash.append(std::to_string(c.y));
50                      });
51        return std::hash<std::string>()(str_hash);
52    }
53};

Здесь у нас специализация шаблонного класса std::hash из стандартной библиотеки. Она необходима для вычисления хэша элементов типа std::shared_ptr<Node>, хранящихся в std::unordered_set. Для встроенных типов стандартная библиотека уже предоставляет реализацию std::hash, но для пользовательских типов (например, std::shared_ptr<Node>) требуется определить свою версию. Специализация std::hash требует переопределения операции (), которая должна вычислять целочисленный хэш для переданного объекта. В данном случае операция принимает элемент контейнера std::unordered_set. Внутри неё:

Создаётся строка str_hash, которая будет использоваться для вычисления хэша.
Все координаты состояния узла (node->state) последовательно добавляются в str_hash. Для этого используется алгоритм std::for_each. Каждая координата (c.x, c.y) преобразуется в строку и добавляется в str_hash.
После завершения цикла вызывается std::hash<std::string>()(str_hash), который вычисляет хэш строки. Для типа std::string в стандартной библиотеке уже реализована своя специализация std::hash, поэтому её можно использовать напрямую.

Зачем это нужно? В std::unordered_set хранятся уже рассмотренные узлы дерева. Когда мы генерируем новые состояния (возможные ходы), нужно быстро определить, встречалось ли оно раньше. Для этого используется ключ, по которому можно эффективно проверять наличие элемента в std::unordered_set. Поле state содержит контейнер std::vector<GameParams::coordinates>, представляющий текущее расположение элементов на доске. Поэтому в качестве ключа используется последовательность координат. Формирование строки из координат гарантирует, что одинаковые состояния дадут одинаковый хэш. Это позволяет std::unordered_set корректно сравнивать узлы.

В std::unordered_set элементом контейнера является std::shared_ptr<Node>, и он формально считается ключом. Однако для корректного поиска мы вычисляем хэш и выполняем сравнение не по самому указателю, а по его полю state. Это позволяет std::unordered_set воспринимать узлы с одинаковым состоянием как одинаковые, даже если это разные объекты std::shared_ptr<Node>.

Продолжаем дальше рассматривать содержимое файла solution_algorithm.hpp. Сейчас будет описан основной класс, который как раз отвечает за реализацию алгоритма A*:

55typedef std::vector<std::shared_ptr<Node>> vect_node; // using of
56                                                      // ComputeFreeMoves
57class ASearch {
58    std::priority_queue<std::shared_ptr<Node>, vect_node, Node::Comp>
59                                                                 open_queue;
60    std::unordered_set<std::shared_ptr<Node>,
61                       std::hash<std::shared_ptr<Node>>,
62                       Node::EqualNode> close_set;
63    Node initial;
64    Node goal;
65    GameParams *gp;
66    ASearch(Node i, Node g, GameParams *a_gp = nullptr)
67        : initial(i), goal(g), gp(a_gp) {}
68public:
69    static std::unique_ptr<ASearch> Start(GameParams *gp);
70    Node *FindSolution();
71    void ApplyFairEvaluator(Node &n) const;
72    vect_node ComputeFreeMoves(const std::shared_ptr<Node>& n) const;
73    void ShowSolution(Node *goal);
74};

В первую очередь хочу отметить, что псевдоним типа vect_node используется как std::priority_queue контейнером, так и в методе ComputeFreeMoves(). Исходя из названия, это просто вектор узлов (они обёрнуты в интеллектуальный указатель std::shared_ptr).

Перейдем непосредственно к классу ASearch. Начнём с его полей. 2 основных контейнера:

std::priority_queue<std::shared_ptr<Node>, vect_node, Node::Comp> open_queue. В псевдокоде он назывался open. Это приоритетная очередь узлов, которые будет рассматривать алгоритм. Стоит сказать, что это класс-адаптер, в его основе по умолчанию используется контейнер vector. Через <> передаём параметры шаблона, а конкретно: std::shared_ptr<Node> — тип элементов очереди, vect_node — тип базового контейнера (по умолчанию оставляем vector), Node::Comp — компаратор, который рассматривался ранее для сравнения узлов по их оценкам.
std::unordered_set<std::shared_ptr<Node>, std::hash<std::shared_ptr<Node>>, Node::EqualNode> close_set — это неупорядоченный ассоциативный контейнер, использующий хэш-таблицу для быстрого поиска рассмотренных узлов. В псевдокоде обозначался под closed, т.е. содержит уже рассмотренные узлы, которые не подлежат переоценке. Параметры шаблона: std::shared_ptr<Node> — тип элементов, std::hash<std::shared_ptr<Node>> — тип объекта, через который будет вычисляться хэш ключа. Напомню, его описывали выше; Node::EqualNode — тип объекта для сравнения на равенство ключей. Этот объект тоже описывался в текущей статье.

Следующие поля Node initial и Node goal. Первое представляет собой начальный узел, т.е. с этого состояния был запущен алгоритм. Второе является финальным узлом, т.е. когда все виджеты будут на своих местах после перестановок.

GameParams *gp — указатель на объект GameParams нужен для доступа к координатам, чтобы заполнить состояния initial и goal, а также при вычислении Манхэттенского расстояния при эвристической оценке. Конструктор ASearch инициализирует начальный и конечный узлы, а также сохраняет указатель на объект GameParams.

Теперь перейдём к объявлению методов класса. Конструктор класса приватный. Обязанность на создание класса возлагается на статический метод, который как раз подготовит необходимые данные, чтобы передать их в конструктор. Метод этот называется Start:

69    static std::unique_ptr<ASearch> Start(GameParams *gp);

Статический метод Start создаёт объект ASearch в динамической памяти, оборачивает его в std::unique_ptr и возвращает вызывающей стороне (callback-функции solve_problem_callback(). Для полученного объекта можно вызывать методы: FindSolution() — для запуска алгоритма A*, ApplyFairEvaluator() — оценка очередного узла, ComputeFreeMoves() — получение смежных узлов от текущего. Последние 2 метода используется непосредственно в алгоритме. Последний метод ShowSolution() вызывается после того, как алгоритм вычислит путь до финального узла. Тогда он каждое состояние будет отрисовывать пошагово, передвигая вижеты.

Последний участок кода в файле solution_algorithm.hpp:

76/*
77 * Priority_queue does not allow to get begin() and end()
78 * So we get underlying container vector<shared_ptr<Node>>
79 *
80 * The container is a protected member of the priority_queue
81 */
82template <class T, class S, class C>
83S& GetPQContainer(std::priority_queue<T, S, C>& q) {
84    struct HackedQueue : private std::priority_queue<T, S, C> {
85        static S& Container(std::priority_queue<T, S, C>& q) {
86            return q.*(&HackedQueue::c);    // is pointer to member of class
87        }
88    };
89    return HackedQueue::Container(q);
90}

С помощью вышеописанного шаблонного метода мы получаем доступ к базовому контейнеру приоритетной очереди std::priority_queue. Зачем это нужно? Дело в том, что при получении смежного узла надо узнать, находится ли он уже в open, т.е. в очереди рассматриваемых узлов. Для этого нужно пройтись от начала до конца очереди, проверяя на равенство состояний узлов. Однако std::priority_queue не позволяет получить итераторы вообще: приходится извлекать базовый контйнер std::vector<std::shared_ptr<Node>> путём наследования.

Хак с `std::priority_queue`

В std::priority_queue есть защищённый (protected) член c, который и хранит сам контейнер (по умолчанию это std::vector<T>). Прямой доступ к нему невозможен, но можно обойти это ограничение через механизм указателей на члены класса.

Внутри GetPQContainer объявляется вложенная структура HackedQueue, которая наследуется закрыто от std::priority_queue<T, S, C>. Это позволяет HackedQueue унаследовать член c.

Далее создаётся статический метод Container(), который принимает ссылку на priority_queue и получает доступ к его контейнеру. Однако сам priority_queue не имеет доступа к c, так как он не является наследником HackedQueue. Поэтому прямой доступ к c невозможен, и используется указатель на член класса:

86    return q.*(&HackedQueue::c);

Здесь &HackedQueue::c — это указатель на член (member pointer), который указывает на c в HackedQueue. Такой указатель можно разыменовать (.*), передав объект того класса, которому этот член принадлежит. Когда HackedQueue наследует std::priority_queue, член c остаётся в том же месте в памяти, просто с изменённым уровнем доступа. Поэтому компилятор может вычислить смещение c внутри HackedQueue и правильно его вернуть через q.*(&HackedQueue::c), даже если q сам по себе является std::priority_queue<T, S, C>.

Выбор статического метода обусловлен тем, что HackedQueue создаётся только для доступа к c, но нам не нужен её объект. Статический метод позволяет обойтись без создания экземпляра HackedQueue, напрямую получая контейнер из переданного priority_queue.

После вызова HackedQueue::Container(q) возвращается ссылка на базовый контейнер priority_queue, позволяя работать с ним, как с обычным vector.

Настала пора переходить к рассмотрению реализации методов класса ASearch.

solution_algorithm.cpp

Начнём со статического метода инициализации начальных параметров Start:

13typedef std::vector<GameParams::coordinates> state_type;
14
15std::unique_ptr<ASearch> ASearch::Start(GameParams *gp)
16{
17    /*
18     * init_xy numbering of puzzles in the correct sequence
19     */
20    state_type init_xy(puzzle_pieces, GameParams::coordinates{});
21    std::for_each(gp->puzzles.begin(), gp->puzzles.end(),
22                  [&init_xy](const std::unique_ptr<Puzzle>& p) {
23                      init_xy[p->sequence_number] = {p->x(), p->y()};
24                  });
25    init_xy[puzzle_pieces-1] = {gp->empty_box.x, gp->empty_box.y};
26    Node initial(init_xy);
27    state_type goal_xy(gp->standard_puzzle_coordinates.begin(),
28                       gp->standard_puzzle_coordinates.end());
29    Node goal(goal_xy);
30    return std::unique_ptr<ASearch>(new ASearch(initial, goal, gp));
31}

Тут стоит отметить, что в самом начале задействован typedef state_type для std::vector<GameParams::coordinates>. Этот псевдоним типа используется для представления состояния всей головоломки, то есть для хранения координат всех её частей.

Метод Start создаёт 2 узла: initial, который соответствует текущему состоянию головоломки, и goal, описывающий её финальное (завершённое) состояние. Как мы помним, узлы хранят состояния. Здесь как раз задействуем typedef state_type для их создания. Порядок хранения координат в state_type очень важен для корректного сравнения (идентификации) состояний в алгоритме. Договоримся, что индексы соответствуют правильному порядку следования виджетов. Этот порядок уже рассматривался в предыдущих частях статьи. Если кратко: мы нумеруем виджеты по столбцам, сверху вниз. В виджетах у нас есть поле sequence_number, которое указывает, на каком месте должен находиться виджет (а также является номером части картинки). Этот sequence_number по сути и будет являться индексом, а текущие координаты виджета извлекаем, сохраняем под нужным индексом. Всё это как раз делается с помощью кода:

20    state_type init_xy(puzzle_pieces, GameParams::coordinates{});
21    std::for_each(gp->puzzles.begin(), gp->puzzles.end(),
22                  [&init_xy](const std::unique_ptr<Puzzle>& p) {
23                      init_xy[p->sequence_number] = {p->x(), p->y()};
24                  });

Сначала создаём puzzle_pieces элементов типа GameParams::coordinates, проинициализированных значением по умолчанию. Так как GameParams::coordinates — агрегатный класс, его поля встроенных типов при value initialization (GameParams::coordinates{}) инициализируются нулями. Далее проходимся по контейнеру puzzles, который содержит все пазлы. Они расположены в порядке создания, но это не имеет значения. Нам главное просто перебрать все пазлы. Используем sequence_number пазла, чтобы под нужным индексом заполнить текущее местоположение виждета по x и y.

После этого ещё надо заполнить местоположение пустой клетки. Эту информацию берём из класса GameParams. Поскольку пустая клетка логически считается последним элементом, её координаты записываются в init_xy[puzzle_pieces-1] из gp->empty_box. Полученное состояние тут же передаётся в качестве инициализатора для создания начального узла (Node initial). Следующим этапом нужно подобное проделать и для конечного узла (Node goal). Но здесь заполнение состояния будет проще: оно совпадает с вектором standard_puzzle_coordinates из класса GameParams. Напомню, этот контейнер нужен был при создании игры для размещения виджетов по порядку. Здесь же мы перебираем его, заполняем состояние goal_xy.

В конце метода создаём объект ASearch в динамической памяти, передав ему созданные начальный и конечный узлы, а также указатель на GameParams. Инициализируем std::unique_ptr, сохраняем адрес объекта в интеллектуальном указателе: std::unique_ptr<ASearch>(new ASearch(initial, goal, gp)). Возвращаем его callback-функции solve_problem_callback.

Теперь рассмотрим метод FindSolution(), который является основой алгоритма A*. Разделю его на 2 части, так как в первой есть ещё зависимость от 2-ух важных методов: ApplyFairEvaluator() и ComputeFreeMoves(). Итак, часть FindSolution() выглядит следующим образом:

33Node* ASearch::FindSolution()
34{
35    ApplyFairEvaluator(initial);
36    open_queue.push(std::shared_ptr<Node>(&initial, [](Node*){}));
37    while(!open_queue.empty()) {
38        std::shared_ptr<Node> best_node = open_queue.top();
39        open_queue.pop();
40        if(goal == *best_node) {
41            close_set.insert(best_node);
42            return best_node.get();
43        }
44        close_set.insert(best_node);
45        vect_node free_moves = ComputeFreeMoves(best_node);

Метод FindSolution() соответствует псведокоду алгоритма A*, который был описан выше в статье. Оценка g(n) для начального узла (initial) установилась ещё на стадии инициализации объекта Node в методе Start (напомню, её можно рассматривать как глубину прохода по дереву). Нам остаётся вычислить эвристическую оценку h(n) и итоговую f(n). Для этого как раз служит метод ApplyFairEvaluator(). Поэтому нужно рассмотреть и его описание:

78/*
79 * g(n) + W(n)
80 * g(n) is path length
81 * W(n) is sum of Manhattan distances
82 */
83void ASearch::ApplyFairEvaluator(Node& n) const
84{
85    int sum_md = 0;
86    for(int i = 0; i < puzzle_pieces; ++i)
87        sum_md +=
88            compute_manhattan_distance(n.state[i],
89                                       gp->standard_puzzle_coordinates[i]);
90    n.evaluation = n.depth + sum_md;
91}

В этом методе мы проходимся по каждому виджету, вычисляя для него Манхэттенское расстояние. Чтобы его вычислить, необходимо получить текущие координаты, а также координаты, где должен находиться виджет в конечном состоянии. Так как у нас состояние state содержит координаты виджетов в нужно нам порядке (по нумерации виджетов), то standard_puzzle_coordinates будет содержать коодинаты этих же виджетов, но уже для конечного состояния.Поэтому индексы и для state, и для standard_puzzle_coordinates будут соответствовать.

Извлечённые координаты передаются в функцию compute_manhattan_distance(). Прежде чем переходить к объяснению сути Манхэттенского расстояния, стоит сказать, что полученная оценка для одного виджета суммируется с остальными, sum_md как раз будет хранить итоговую сумму. f(n) вычисляется последней строчкой: n.evaluation = n.depth + sum_md.

Манхэттенское расстояние для двух точей с координатами (x1, y1) и (x2, y2) вычисляется по формуле: |x2-x1|+|y2-y1|. Функция compute_manhattan_distance как раз это выполняет:

72static int compute_manhattan_distance(GameParams::coordinates first,
73                                      GameParams::coordinates second)
74{
75    return std::abs(first.x - second.x) + abs(first.y - second.y);
76}

Так что ApplyFairEvaluator() устанавливает оценку для состояния в поле evaluation.

Вернёмся к методу FindSolution(). После того, как оценка для самого начального узла получена, мы добавляем узел в PriorityQueue согласно псевдокоду: open_queue.push(std::shared_ptr<Node>(&initial, [](Node*){}));. Здесь в приоритетную очередь рассматриваемых узлов добавляем самый начальный. Но замечу, что std::shared_ptr получает адрес объекта initial не через new, а просто через операцию взятия адреса (&). Потому что initial у нас хранится как поле объекта ASearch, его адрес (поля) не изменится пока существует этот объект. Адреса объектов нам нужны для восстановления цепочки после решения алгоритмом. Также для shared_ptr передаём deleter в виде лямбда-выражения [](Node*){} для того, чтобы удаление не происходило. В самом деле, удаление этого поля будет возлагаться на объект (через деструктор) как это и полагается. Остальные узлы уже будут создаваться непосредственно через операцию new, а удаляться стандартным deleter’ом в std::shared_ptr.

Далее в цикле while будем извлекать узлы из std::priority_queue до тех пор, пока они не закончатся, либо мы найдем узел с финальным состоянием и выйдем из цикла через break. Извлекаем узел из очереди в самом начале: он будет самой низкой оценкой, т.е. наиболее приоритетный для нас. Затем сверяем его с узлом с конечным состоянием. Если они совпадают, то это значит, что алгоритм нашёл решение головоломки. В этом случае возвращаем этот последний узел (он будет содержать адрес родительского узла, чтобы восстановить последовательность решения). Проблема тут ещё в том, что узлы были обёрнуты в std::shared_ptr, а последний возвращаем просто как Node*, при этом он извлечён из std::priority_queue, и в то же время не хранится в std::unordered_set. То есть когда метод завершится, то локальный объект shared_ptr<Node> best_node в случае окончания решения уничтожится, что повлечёт за собой и освобождении динамической памяти под послединй Node. Поэтому перед выходом из цикла необходимо сохранить std::shared_ptr с указателем на наш последний Node. Это можно сделать путём добавление в std::unordered_set (close). Причём с другими узлами такой трюк не нужен, потому что они уже хранятся в std::unordered_set (close). Сам std::unordered_set хранится как поле объекта ASearch, так что все хранимые в нём shared_ptr останутся, а значит — и узлы (Node) тоже. Ещё раз приведу отрывок кода, который отображает эти действия:

37    while(!open_queue.empty()) {
38        std::shared_ptr<Node> best_node = open_queue.top();
39        open_queue.pop();
40        if(goal == *best_node) {
41            close_set.insert(best_node);
42            return best_node.get();
43        }
44        close_set.insert(best_node);
45        vect_node free_moves = ComputeFreeMoves(best_node);

41 строка как раз позволяет сохранить shared_ptr перед выходом из локальной области.

Если извлечённый узел не является последним, то добавляем его в std::unordered_set (closed queue). Это значит, что для того состояния, которое хранит данный узел, оценка больше не будет пересмотрена. Когда будут искаться смежные узлы, если они будут с таким же состоянием, то будут просто пропускаться.

Затем ищем от текущего состояния узла best_node смежные состояния. То есть какие варианты передвижения виджетов в пустую область можно рассматривать. Вычисляем мы это через вызов метода ComputeFreeMoves(), который вернёт нам вектор узлов со смежными состояними: vect_node free_moves = ComputeFreeMoves(best_node). Перейдем теперь к его описанию:

117vect_node ASearch::ComputeFreeMoves(const std::shared_ptr<Node>& parent) const
118{
119    vect_node free_moves;
120    GameParams::coordinates empty_box_coord = parent->state[puzzle_pieces-1];
121    std::for_each(parent->state.begin(), parent->state.end()-1,
122                    MovesCreator(free_moves, empty_box_coord, parent->state));
123    std::for_each(free_moves.begin(), free_moves.end(),
124                  [parent](std::shared_ptr<Node>& child) {
125                      child->depth = parent->depth + 1;
126                      child->parent_p = parent.get();
127                  });
128    return free_moves;
129}

В ComputeFreeMoves() передаётся узел best_node, который был извлечён из std::priority_queue (open) и теперь играет роль родительского (parent). В empty_box_coord сохраняем координаты пустой клетки. Это делается просто, так как state содержит координаты всех виджетов в правильном порядке, и последнему элементу всегда соответствует пустая клетка.

Далее происходит формирование смежных узлов для текущего. Каждый смежный узел представляет состояние, которое можно получить, переместив пустую клетку. Чтобы создать такой узел, пустая клетка должна находиться рядом с одним из виджетов. Как раз поэтому координаты каждого виджета передаются в стандартный алгоритм for_each, который вызывает функтор MovesCreator. Перед разбором MovesCreator стоит отметить, что он должен хранить полезные данные:

free_moves — вектор узлов, в который будут добавляться новые смежные узлы,
empty_box_coord — координаты пустой клетки,
state — текущее состояние узла best_node, которое будет использовано для создания нового состояния: оно останется неизменным, за исключением обмена координат между пустой клеткой и соответствующим виджетом.

Описание класса MovesCreator следующее:

 93class MovesCreator {
 94    vect_node& free_moves;
 95    GameParams::coordinates empty_box_coord;
 96    state_type cur_state;
 97
 98public:
 99    MovesCreator(vect_node& fm, GameParams::coordinates ebc,
100                 state_type cs)
101                : free_moves(fm), empty_box_coord(ebc), cur_state(cs)
102                {}
103    void operator()(const GameParams::coordinates& c) {
104        if(is_next_to_empty_box(empty_box_coord, c)) {
105            state_type next_state = cur_state;
106            auto found_pos =
107                std::find_if(next_state.begin(), next_state.end()-1,
108                             [c](const GameParams::coordinates& next_coord) {
109                                 return next_coord == c;
110                             });
111            std::swap(*found_pos, next_state[puzzle_pieces-1]);
112            free_moves.push_back(std::shared_ptr<Node>(new Node(next_state)));
113        }
114    }
115};

С полями здесь, думаю, всё понятно: они как раз представляют собой данные, переданные в конструктор. Так как объект MovesCreator используется как функтор, переопределение операции () обязательно: именно этот метод и вызывается в for_each. Алгоритм for_each проходит по элементам типа GameParams::coordinates, поэтому метод operator() принимает аргумент этого типа.

Метод operator() должен определить, находятся ли координаты переданного виджета рядом с пустой клеткой. Здесь опять же используется функция is_next_to_empty_box(), которая уже рассматривалась в 1-ой части. Если виджет действительно расположен рядом с пустой клеткой, создаём копию текущего состояния:

105            state_type next_state = cur_state;

Теперь в копии нужно найти координаты этого виджета. Чтобы это сделать, проходимся от начала до предпоследнего элемента (ведь последний - это пустая клетка) в next_state, используя алгоритм find_if. Третьим аргументом передаём лямбда-выражение с захватом координат виджета (c) для сравнения. В результате found_pos получает итератор на нужные нам координаты.

Осталось обменять координаты пустой клетки и виджета. Функция std::swap() выполняет обмен элементов в std::vector, что происходит за O(1), поскольку операция не изменяет сам вектор, а лишь меняет местами два его элемента:

111            std::swap(*found_pos, next_state[puzzle_pieces-1]);

Полученное next_state представляет собой одно из возможных смежных состояний. Последней строкой добавляем его в вектор free_moves в виде узла Node, обёрнутого в интеллектуальный указатель shared_ptr.

Вернёмся к методу ComputeFreeMoves(). Оставшаяся часть:

123    std::for_each(free_moves.begin(), free_moves.end(),
124                  [parent](std::shared_ptr<Node>& child) {
125                      child->depth = parent->depth + 1;
126                      child->parent_p = parent.get();
127                  });
128    return free_moves;

После заполнения вектора free_moves узлами со смежными состояниями, надо задать для них глубину прохода depth (оценка g(n), длина пути) и указатель на родительское состояние parent_p (для восстановления решения). Именно это и выполняется в for_each. Заполненный вектор free_moves возвращается методу FindSolution().

Вернёмся к основному методу FindSolution() алгоритма A*. Последнее рассмотренное действие: vect_node free_moves = ComputeFreeMoves(best_node);. То есть мы получили смежные состояния, и дальнейшие действия будут связаны именно с ними. Остаток метода FindSolution():

46        for(auto child_node : free_moves) {
47            if(close_set.find(child_node) != close_set.end())
48                continue;
49            ApplyFairEvaluator(*child_node);
50            auto& PQ_cont = GetPQContainer(open_queue);
51            auto found_pos =
52                std::find_if(PQ_cont.begin(), PQ_cont.end(),
53                             [&child_node](const std::shared_ptr<Node>& n) {
54                                 return *n == *child_node;
55                             });
56            /* Open_queue doesn't contain child node */
57            if(found_pos == PQ_cont.end())
58                open_queue.push(child_node);
59            else if(child_node->evaluation < (*found_pos)->evaluation) {
60                PQ_cont.erase(found_pos);
61                /*
62                 * reorder priority queue
63                 */
64                std::make_heap(PQ_cont.begin(), PQ_cont.end(), Node::Comp());
65                open_queue.push(child_node);
66            }
67        }
68    }
69    return nullptr;
70}

Через цикл for обрабатывается вектор free_moves, содержащий смежные узлы. Согласно псевдокоду, если полученное новое смежное состояние уже присутствует в std::unordered_set (close), то узел в free_moves пропускатся: он не подлежит переоценке и добавлению в std::priority_queue. Это условие проверяется так:

47            if(close_set.find(child_node) != close_set.end())
48                continue;

Если узел не найден в close_set, производится его оценка через метод ApplyFairEvaluator(), аналогично тому, как это делалось для начального узла best_node: ApplyFairEvaluator(*child_node). После оценки необходимо проверить, существует ли узел с таким же состоянием в std::priority_queue. Это нужно для того, чтобы при наличии более выгодной (меньшей) оценки заменить старую версию узла новой.

В разделе этой статьи про “Хак с priority_queue” рассматривалась шаблонная функция GetPQContainer. Она как раз и пригодится нам сейчас. Дело в том, что мы хотим с помощью стандартного алгоритма find_if пройтись по контейнеру priority_queue через итераторы — в поисках узла с таким же состоянием, как у child_node.

Итак, с помощью GetPQContainer получаем ссылку на базовый контейнер std::vector, и уже у этого контейнера, который хранит узлы с состониями, получаем итераторы. Остаётся лишь передать в find_if унарный предикат — в нашем случае это лямбда-выражение, которое сравнивает состояния между элементами std::vector и child_node:

50            auto& PQ_cont = GetPQContainer(open_queue);
51            auto found_pos =
52                std::find_if(PQ_cont.begin(), PQ_cont.end(),
53                             [&child_node](const std::shared_ptr<Node>& n) {
54                                 return *n == *child_node;
55                             });

Важно не забывать, что состояния хранятся внутри Node, который, в свою очередь, обёрнут в std::shared_ptr. Поэтому при сравнении необходимо разыменовывать оба операнда. Сравнение использует перегруженную операцию == для Node. Она у нас как раз была описана:

23    bool operator==(const Node& n) const { return this->state == n.state; }

Эта операция, в свою очередь, использует сравнение состояний. Они представляют собой тип vector<GameParams::coordinates>. То есть вектор будет сравнивать каждый элемент типа GameParams::coordinates с использованием его собственной операции ==, которая тоже у нас определена:

41        bool operator==(const coordinates& v) const {
42            return this->x == v.x && this->y == v.y;
43        }

Здесь просто происходит попарное сравнение координат для одного из виджетов.

В результате found_pos будет либо указывать на элемент в контейнере, совпадающий по состоянию с child_node, либо равен итератору end(), если такого узла не найдено.

То есть сейчас мы должны рассмотреть 2 случая:

Если узел не найден в std::priority_queue (итератор равен end()), то просто добавляем child_node в этот контейнер:

57            if(found_pos == PQ_cont.end())
58                open_queue.push(child_node);

В ином случае, если итоговая оценка у child_node меньше, чем у найденного узла, то нужно сделать переоценку. found_pos содержит итератор на узел, и его можно просто удалить из контейнера std::priority_queue, передав итератор методу erase(). Однако тут есть один нюанс: std::priority_queue, хоть и является адаптором контейнера std::vector, использует другую структуру данных — кучу (heap). Кратко говоря, это частично упорядоченное дерево, вершина которого всегда содержит либо максимальный элемент (по умолчанию), либо минимальный — в зависимости от компаратора.

Так как при создании std::priority_queue мы передали компаратор Comp реализующий операцию operator() с логикой сравнения по >, то на вершине дерева будет минимальный элемент (узел с минимальной оценкой). При каждом вызове push для std::priotiry_queue структура кучи пересчитывается, но только если элемент добавляется в конец контейнера.

Однако в нашем случае мы из базового контейнера удалили элемент, нарушив структуру кучи. Поэтому после erase необходимо вручную пересчитать кучу, вызвав:

64std::make_heap(PQ_cont.begin(), PQ_cont.end(), Node::Comp());

После этого можно просто вставить новый узел (с тем же состоянием, но меньшей оценкой), используя push():

59            else if(child_node->evaluation < (*found_pos)->evaluation) {
60                PQ_cont.erase(found_pos);
61                /*
62                 * reorder priority queue
63                 */
64                std::make_heap(PQ_cont.begin(), PQ_cont.end(), Node::Comp());
65                open_queue.push(child_node);

Это было окончание цикла while. В случае, если мы из него выйдем, то просто возвращаем nullptr.

В этой статье, в пункте про описание menu_callbacks.cpp нам уже встречалась функция solve_problem_callback(), откуда вызывался рассмотренный метод FindSolution(). Приведу пару строк из solve_problem_callback():

65    Node *goal = algorithm->FindSolution();
66    algorithm->ShowSolution(goal);

Итак, переменная goal будет хранить указатель на Node, представляющий конечное состояние, в котором каждый пазл находится на своём месте. Для пошагового показа решения мы передаём этот узел в метод ShowSolution(), который выглядит так:

131void ASearch::ShowSolution(Node *goal)
132{
133    if(goal->parent_p == nullptr)
134        return;
135    ShowSolution(goal->parent_p);
136    for(int i = 0; i < puzzle_pieces-1; ++i) {
137        auto puzzle_pos = std::find_if(gp->puzzles.begin(), gp->puzzles.end(),
138                                       [i](const std::unique_ptr<Puzzle>& p) {
139                                           return p->sequence_number == i;
140                                       });
141        (*puzzle_pos)->position(goal->state[i].x, goal->state[i].y);
142        gp->win->redraw();
143        Fl::check();
144        usleep(40000);
145    }
146}

Этот метод вызывается рекурсивно, чтобы дойти до самого начала цепочки ходов. Точкой остановки рекурсии является проверка условия на nullptr, потому что самый первый узел не имеет родителя:

133    if(goal->parent_p == nullptr)
134        return;

На строке с рекурсивным вызовом ShowSolution(goal->parent_p) мы передаём указатель на родительский узел, тем самым постепенно продвигаясь к самому первому действию. Это позволяет воспроизводить решение от начального состояния к конечному. Когда стек рекурсивных вызовов начинает разворачиваться обратно, на каждом шаге производится визуальное отображение следующего перемещения виджетов.

Узел goal хранит в state координаты всех пазлов согласно правильному порядку следования виджетов. Его индекс соответствует sequence_number виджета. С помощью цикла мы проходим по номерам от 1-го до последнего (не включая пустую клетку) и через алгоритм std::find_if ищем соответствующий виджет в puzzles. Итератор puzzle_pos будет указывать на нужный объект типа Puzzle, и остаётся только вызвать метод position(), чтобы изменить координаты:

141(*puzzle_pos)->position(goal->state[i].x, goal->state[i].y);

После этого окно перерисовывается с помощью gp->win->redraw();, а затем вызывается функция Fl::check();, которая немедленно обновляет содержимое окна и одновременно позволяет интерфейсу оставаться отзывчивым. Это особенно важно при пошаговом отображении решения — пользовательский интерфейс не “зависает” и продолжает реагировать на действия, такие как попытка закрытия окна или переключение между приложениями.

Завершается каждый шаг небольшой задержкой usleep(40000);, что позволяет визуально наблюдать за перемещением пазлов.

В итоге, после завершения всех перемещений, программа предложит пользователю начать новую игру.

Это была третья и заключительная часть цикла статей о разработке игры “Picture Puzzle” на C++. Исходный код можно найти в репозитории: https://git.scratko.xyz/picture-puzzle/. Я постарался изложить всё максимально понятно — и для новичков, и для тех, кто уже давно в теме C++. Если что-то осталось непонятным или хочется обсудить детали — пишите на эл. почту: m@scratko.xyz. Буду рад обратной связи!