diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | main.cpp | 11 | ||||
| -rw-r--r-- | menu_callbacks.cpp | 14 | ||||
| -rw-r--r-- | menu_callbacks.hpp | 9 | ||||
| -rw-r--r-- | puzzle.cpp | 17 | ||||
| -rw-r--r-- | puzzle.hpp | 12 | ||||
| -rw-r--r-- | solution_algorithm.cpp | 182 | ||||
| -rw-r--r-- | solution_algorithm.hpp | 93 |
8 files changed, 320 insertions, 22 deletions
@@ -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 @@ -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 @@ -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()); @@ -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 |