Added A* solution algorithm

8 files changed, 320 insertions, 22 deletions

diff --git a/Makefile b/Makefile
index a963df0..d564c15 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
-SRCMODULES = puzzle.cpp gameplay.cpp menu_callbacks.cpp main.cpp
+SRCMODULES = puzzle.cpp gameplay.cpp menu_callbacks.cpp solution_algorithm.cpp main.cpp
 OBJMODULES = $(SRCMODULES:.cpp=.o)
 CXX = g++
-CXXFLAGS = -Wall -g
+CXXFLAGS = -Wall -g -D DEBUG
 LIBS = -lfltk -lfltk_images
 
 all: main
diff --git a/main.cpp b/main.cpp
index 4224965..d5ce3a1 100644
--- a/main.cpp
+++ b/main.cpp
@@ -12,13 +12,14 @@
 int main()
 {
     srand(time(nullptr));
-    Fl_Window *win = new Fl_Window(325, 355, "Picture puzzle");
-    Fl_Sys_Menu_Bar *sys_bar = new Fl_Sys_Menu_Bar(0, 0, 165, 20, nullptr);
-    sys_bar->add("&File/&Load picture", nullptr, load_file_callback);
+    Fl_Window *win = new Fl_Window(320, 355, "Picture puzzle");
+    GameParams *params = GameParams::SetUpParams(win);
+    Fl_Sys_Menu_Bar *sys_bar = new Fl_Sys_Menu_Bar(0, 0, 150, 20, nullptr);
+    sys_bar->add("&File/&Load file", nullptr, load_file_callback);
     sys_bar->add("&File/&Exit", nullptr, exit_callback);
-    sys_bar->add("&Option/&Show solution", nullptr, solve_problem_callback);
+    sys_bar->add("&Help/&Show solution", nullptr, solve_problem_callback,
+                 params);
     sys_bar->add("&About", nullptr, about_callback);
-    GameParams *params = GameParams::SetUpParams(win);
     PuzzleGame::StartGame(params);
     win->show();
     return Fl::run();
diff --git a/menu_callbacks.cpp b/menu_callbacks.cpp
index df70514..d43d848 100644
--- a/menu_callbacks.cpp
+++ b/menu_callbacks.cpp
@@ -1,10 +1,12 @@
 #include <FL/Fl_Native_File_Chooser.H>
+#include <memory>
 #include <stdio.h>
 #include <string>
 
 #include "menu_callbacks.hpp"
+#include "solution_algorithm.hpp"
 
-void load_file_callback(Fl_Widget *sender, void *window)
+void load_file_callback(Fl_Widget *sender, void*)
 {
     auto dialog = Fl_Native_File_Chooser{};
     dialog.type(Fl_Native_File_Chooser::BROWSE_FILE);
@@ -20,15 +22,19 @@ void load_file_callback(Fl_Widget *sender, void *window)
         printf("%s\n", dialog.filename());
 }
 
-void exit_callback(Fl_Widget *w, void *params)
+void exit_callback(Fl_Widget *w, void*)
 {
     w->parent()->hide();
 }
 
-void solve_problem_callback(Fl_Widget *w, void *params)
+void solve_problem_callback(Fl_Widget *w, void *gp)
 {
+    std::unique_ptr<ASearch> algorithm =
+        ASearch::Start(reinterpret_cast<GameParams*>(gp));
+    Node *goal = algorithm->FindSolution();
+    algorithm->ShowSolution(goal);
 }
 
-void about_callback(Fl_Widget *w, void *params)
+void about_callback(Fl_Widget *w, void*)
 {
 }
diff --git a/menu_callbacks.hpp b/menu_callbacks.hpp
index 61967a5..561263e 100644
--- a/menu_callbacks.hpp
+++ b/menu_callbacks.hpp
@@ -1,10 +1,11 @@
 #ifndef MENU_CALLBACKS_HPP_SENTRY
+#define MENU_CALLBACKS_HPP_SENTRY
 
 #include <FL/Fl_Widget.H>
 
-void load_file_callback(Fl_Widget *sender, void *window);
-void exit_callback(Fl_Widget *w, void *params);
-void solve_problem_callback(Fl_Widget *w, void *params);
-void about_callback(Fl_Widget *w, void *params);
+void load_file_callback(Fl_Widget *sender, void*);
+void exit_callback(Fl_Widget *w, void*);
+void solve_problem_callback(Fl_Widget *w, void *gp);
+void about_callback(Fl_Widget *w, void*);
 
 #endif
diff --git a/puzzle.cpp b/puzzle.cpp
index a42be91..1addc73 100644
--- a/puzzle.cpp
+++ b/puzzle.cpp
@@ -7,6 +7,8 @@
 #include <utility>
 #include <memory>
 
+GameParams* GameParams::instance = nullptr;
+
 void GameParams::CalculateStandardPuzzlePos()
 {
     coordinates tmp;
@@ -14,8 +16,6 @@ void GameParams::CalculateStandardPuzzlePos()
     int i, j, k = 0;
     for(i = 0; i < puzzles_per_side; ++i)
         for(j = 0; j < puzzles_per_side; ++j, ++k) {
-            if(i == puzzles_per_side-1 && j == puzzles_per_side-1)
-                break;
             tmp.x = i * (puzzle_size + spacing) + spacing;
             tmp.y = j * (puzzle_size + spacing) + spacing + 30;
             standard_puzzle_coordinates[k] = tmp;
@@ -49,15 +49,22 @@ void GameParams::NextUntestedPuzzles()
      */
     win->begin();
     for(int i = 0; i < puzzle_pieces; ++i) {
-        tmp_puzzle =
-            std::unique_ptr<Puzzle>(new Puzzle(standard_puzzle_coordinates[i].x,
-                                standard_puzzle_coordinates[i].y));
         idx_random_puzzle =
             0 + (int)((double)puzzle_pieces * rand()/(RAND_MAX + 1.0));
         while(!free_puzzles[idx_random_puzzle])
             idx_random_puzzle =
                 0 + (int)((double)puzzle_pieces * rand()/(RAND_MAX + 1.0));
         free_puzzles[idx_random_puzzle] = 0;
+        /* empty puzzle */
+        if(idx_random_puzzle == puzzle_pieces-1) {
+            SetXYEmptyBox(standard_puzzle_coordinates[i].x,
+                          standard_puzzle_coordinates[i].y);
+            continue;
+        }
+        /* common puzzle */
+        tmp_puzzle =
+            std::unique_ptr<Puzzle>(new Puzzle(standard_puzzle_coordinates[i].x,
+                                standard_puzzle_coordinates[i].y));
         tmp_puzzle->sequence_number = idx_random_puzzle;
         find_path_to_picture(tmp_puzzle->path, tmp_puzzle->sequence_number);
         Fl_JPEG_Image *img = new Fl_JPEG_Image(tmp_puzzle->path.c_str());
diff --git a/puzzle.hpp b/puzzle.hpp
index e8d85d6..9370763 100644
--- a/puzzle.hpp
+++ b/puzzle.hpp
@@ -9,7 +9,7 @@
 #include <memory>
 
 enum {
-    puzzle_pieces       = 8,
+    puzzle_pieces       = 9,
     puzzles_per_side    = 3,
     puzzle_size         = 100,
     spacing             = 5
@@ -27,8 +27,12 @@ class GameParams {
 public:
     struct coordinates {
         int x, y;
+        bool operator==(const coordinates& v) const {
+            return this->x == v.x && this->y == v.y;
+        }
     };
 private:
+    static GameParams *instance;
     coordinates standard_puzzle_coordinates[puzzle_pieces];
     char free_puzzles[puzzle_pieces];
     coordinates empty_box;
@@ -42,15 +46,19 @@ private:
     void NextUntestedPuzzles();
     bool IsSolvability();
     void CreateNewPuzzles();
+
     friend class PuzzleGame;
+    friend class ASearch;
     friend void press_button_callback(Fl_Widget*, void*);
+    friend void solve_problem_callback(Fl_Widget*, void*);
 public:
     void SetXYEmptyBox(int x, int y) { empty_box.x = x; empty_box. y = y; }
     coordinates GetXYEmptyBox() { return empty_box; }
     static GameParams *SetUpParams(Fl_Window *win) {
+        if(instance)
+            return instance;
         GameParams *gi = new GameParams(win);
         gi->CalculateStandardPuzzlePos();
-        gi->SetXYEmptyBox(215, 245);
         return gi;
     }
 };
diff --git a/solution_algorithm.cpp b/solution_algorithm.cpp
new file mode 100644
index 0000000..0955534
--- /dev/null
+++ b/solution_algorithm.cpp
@@ -0,0 +1,182 @@
+#include "solution_algorithm.hpp"
+#include "puzzle.hpp"
+
+#include <memory>
+#include <vector>
+#include <algorithm>
+#include <stdio.h>
+#include <unistd.h>
+#include <FL/Fl.H>
+
+typedef std::vector<GameParams::coordinates> state_type;
+
+std::unique_ptr<ASearch> ASearch::Start(GameParams *gp)
+{
+    /*
+     * init_xy numbering of puzzles in the correct sequence
+     */
+    state_type init_xy(puzzle_pieces, GameParams::coordinates{});
+    std::for_each(gp->puzzles.begin(), gp->puzzles.end(),
+                              [&init_xy]
+                              (const std::unique_ptr<Puzzle>& p) {
+                                    init_xy[p->sequence_number] =
+                                                        {p->x(), p->y()};
+                              });
+    init_xy[puzzle_pieces-1] = {gp->empty_box.x, gp->empty_box.y};
+    Node initial = Node(init_xy);
+    state_type goal_xy;
+    for(GameParams::coordinates& c : gp->standard_puzzle_coordinates)
+        goal_xy.push_back(c);
+    Node goal = Node(goal_xy);
+    return std::unique_ptr<ASearch>(new ASearch(initial, goal, gp));
+}
+
+Node* ASearch::FindSolution()
+{
+    ApplyFairEvaluator(initial);
+    open_queue.push(std::shared_ptr<Node>(new Node(initial)));
+    while(!open_queue.empty()) {
+        std::shared_ptr<Node> best_node = open_queue.top();
+        open_queue.pop();
+#ifdef DEBUG
+        printf("Current: \n");
+        for(GameParams::coordinates c : best_node->state)
+            printf("%d %d ", c.x, c.y);
+        printf("VALUE: %d\n", best_node->evaluation);
+#endif
+        if(goal == *best_node) {
+            open_queue.push(best_node);
+            return best_node.get();
+        }
+        close_set.insert(best_node);
+        vect_node free_moves = ComputeFreeMoves(best_node);
+        for(auto child_node : free_moves) {
+            if(close_set.find(child_node) != close_set.end())
+                continue;
+            ApplyFairEvaluator(*child_node);
+#ifdef DEBUG
+            printf("Child\n");
+            for(GameParams::coordinates c : child_node->state)
+                printf("%d %d ", c.x, c.y);
+            printf("HASH %ld ", std::hash<std::shared_ptr<Node>>()(child_node));
+            printf("VALUE: %d\n", child_node->evaluation);
+#endif
+            auto& PQ_cont = GetPQContainer(open_queue);
+            auto found_pos = std::find_if(PQ_cont.begin(),
+                                          PQ_cont.end(),
+                                     [&child_node]
+                                     (const std::shared_ptr<Node>& n) {
+                                        return *n == *child_node;
+                                     });
+            /* Open_queue doesn't contain child node */
+            if(found_pos == PQ_cont.end())
+                open_queue.push(child_node);
+            else if(child_node->evaluation < (*found_pos)->evaluation) {
+                PQ_cont.erase(std::remove(PQ_cont.begin(), PQ_cont.end(),
+                              *found_pos));
+                /*
+                 * reorder priority queue
+                 */
+                std::make_heap(PQ_cont.begin(), PQ_cont.end(), Node::Comp());
+                open_queue.push(child_node);
+            }
+        }
+    }
+    return nullptr;
+}
+
+static int compute_manhattan_distance(GameParams::coordinates first,
+                                      GameParams::coordinates second)
+{
+    return std::abs(first.x - second.x) + abs(first.y - second.y);
+}
+
+/*
+ * g(n) + W(n)
+ * g(n) is path length
+ * W(n) is sum of Manhattan distances
+ */
+void ASearch::ApplyFairEvaluator(Node& n) const
+{
+    int sum_md = 0;
+    for(int i = 0; i < puzzle_pieces; ++i)
+        sum_md +=
+            compute_manhattan_distance(n.state[i],
+                                       gp->standard_puzzle_coordinates[i]);
+    n.evaluation = n.depth + sum_md;
+}
+
+
+class MovesCreator {
+    vect_node& free_moves;
+    GameParams::coordinates empty_box_coord;
+    state_type cur_state;
+
+public:
+    MovesCreator(vect_node& fm, GameParams::coordinates ebc,
+                 state_type cs)
+                : free_moves(fm), empty_box_coord(ebc), cur_state(cs)
+                {}
+    void operator()(const GameParams::coordinates& c) {
+        if(IsNearEmptyBox(c, empty_box_coord)) {
+            state_type next_state = cur_state;
+            auto found_pos =
+                std::find_if(next_state.begin(), next_state.end()-1,
+                             [c]
+                             (const GameParams::coordinates& next_coord) {
+                                return next_coord == c;
+                             });
+            std::swap(*found_pos, next_state[puzzle_pieces-1]);
+            free_moves.push_back(std::shared_ptr<Node>(new Node(next_state)));
+        }
+    }
+private:
+    bool IsNearEmptyBox(GameParams::coordinates cur_puzzle,
+                        GameParams::coordinates empty_box) const;
+};
+
+bool MovesCreator::IsNearEmptyBox(GameParams::coordinates cur_puzzle,
+                                  GameParams::coordinates empty_box) const
+{
+    return (empty_box.x-spacing-puzzle_size == cur_puzzle.x &&
+            empty_box.y == cur_puzzle.y) ||
+            (empty_box.x == cur_puzzle.x &&
+             empty_box.y-spacing-puzzle_size == cur_puzzle.y) ||
+            (empty_box.x+puzzle_size+spacing == cur_puzzle.x &&
+             empty_box.y == cur_puzzle.y) ||
+            (empty_box.x == cur_puzzle.x &&
+             empty_box.y+puzzle_size+spacing == cur_puzzle.y);
+}
+
+vect_node ASearch::ComputeFreeMoves(const std::shared_ptr<Node>& parent) const
+{
+    vect_node free_moves;
+    GameParams::coordinates empty_box_coord = parent->state[puzzle_pieces-1];
+    std::for_each(parent->state.begin(), parent->state.end()-1,
+                    MovesCreator(free_moves, empty_box_coord, parent->state));
+    std::for_each(free_moves.begin(), free_moves.end(),
+                                    [parent]
+                                    (std::shared_ptr<Node>& child) {
+                                        child->depth = parent->depth + 1;
+                                        child->parent_p = parent.get();
+                                    });
+    return free_moves;
+}
+
+void ASearch::ShowSolution(Node *goal)
+{
+    if(goal->parent_p == nullptr)
+        return;
+    ShowSolution(goal->parent_p);
+    for(int i = 0; i < puzzle_pieces-1; ++i) {
+        auto puzzle_pos = std::find_if(gp->puzzles.begin(), gp->puzzles.end(),
+                                            [i]
+                                            (const std::unique_ptr<Puzzle>& p) {
+                                                return p->sequence_number == i;
+                                            });
+        (*puzzle_pos)->position(goal->state[i].x, goal->state[i].y);
+        gp->win->redraw();
+        usleep(80000);
+        Fl::wait();
+    }
+}
diff --git a/solution_algorithm.hpp b/solution_algorithm.hpp
new file mode 100644
index 0000000..440264b
--- /dev/null
+++ b/solution_algorithm.hpp
@@ -0,0 +1,93 @@
+#ifndef SOLVING_ALGORITHM_SENTRY
+#define SOLVING_ALGORITHM_SENTRY
+
+#include "puzzle.hpp"
+
+#include <memory>
+#include <vector>
+#include <queue>
+#include <unordered_set>
+#include <algorithm>
+#include <string>
+
+class Node {
+private:
+    std::vector<GameParams::coordinates> state;
+    Node *parent_p;
+    int depth;
+    int evaluation;
+    friend struct std::hash<std::shared_ptr<Node>>;
+    friend class ASearch;
+public:
+    Node(std::vector<GameParams::coordinates>& s, Node *p = nullptr,
+         int d = 0, int e = 0)
+        : state(s), parent_p(p), depth(d), evaluation(e) {}
+    bool operator==(const Node& n) const { return this->state == n.state; }
+
+    struct Comp {
+        bool operator()(const std::shared_ptr<Node>& first,
+                        const std::shared_ptr<Node>& second) {
+            return first->evaluation > second->evaluation;
+        }
+    };
+};
+
+template<>
+struct std::hash<std::shared_ptr<Node>> {
+    std::size_t operator()(const std::shared_ptr<Node>& node) const {
+        std::string str_hash;
+        std::for_each(node->state.begin(), node->state.end(),
+                          [&str_hash](const GameParams::coordinates& c) {
+                                str_hash.append(std::to_string(c.x));
+                                str_hash.append(std::to_string(c.y));
+                          });
+        return std::hash<std::string>()(str_hash);
+    }
+};
+
+typedef std::vector<std::shared_ptr<Node>> vect_node; // using of
+                                                      // ComputeFreeMoves
+class ASearch {
+    struct EqualNode {
+        bool operator()(const std::shared_ptr<Node>& first,
+                        const std::shared_ptr<Node>& second) const {
+            return *first == *second;
+        }
+    };
+
+    std::priority_queue<std::shared_ptr<Node>, vect_node, Node::Comp>
+                                                                 open_queue;
+    std::unordered_set<std::shared_ptr<Node>,
+                       std::hash<std::shared_ptr<Node>>,
+                       EqualNode> close_set;
+    Node initial;
+    Node goal;
+    GameParams *gp;
+    ASearch(Node i, Node g, GameParams *a_gp = nullptr)
+        : initial(i), goal(g), gp(a_gp) {}
+public:
+    static std::unique_ptr<ASearch> Start(GameParams *gp);
+    Node *FindSolution();
+    void ApplyFairEvaluator(Node &n) const;
+    vect_node ComputeFreeMoves(const std::shared_ptr<Node>& n) const;
+    bool IsNearEmptyBox(const GameParams::coordinates c) const;
+    void ShowSolution(Node *goal);
+};
+
+/*
+ * Priority_queue does not allow to get begin() and end()
+ * So we get underlying container vector<shared_ptr<Node>>
+ *
+ * The container is a protected member of the priority_queue
+ */
+template <class T, class S, class C>
+S& GetPQContainer(std::priority_queue<T, S, C>& q) {
+    struct HackedQueue : private std::priority_queue<T, S, C> {
+        static S& Container(std::priority_queue<T, S, C>& q) {
+            return q.*(&HackedQueue::c);    // is pointer to member of class
+        }
+    };
+    return HackedQueue::Container(q);
+}
+
+#endif