From 90bd5ca05bea4dbeaaeff5cbe13b5671da420c82 Mon Sep 17 00:00:00 2001 From: scratko Date: Fri, 25 Jul 2025 17:04:21 +0300 Subject: July update Added const qualifiers is_next_to_empty_box() became visible to other files(). The size of the main window has been changed. Checking whether the A* algorithm has been launched before starting a new game or the same A* algorithm. Fixed indentation in lambda expressions. The initial node is added to open_queue without additional creation of dynamic memory (the address of the object field is taken). Fixed PQ_cont.erase(). IsNearEmptyBox was removed(). EqualNode moved to the Node class. --- README.md | 13 ++++++-- gameplay.cpp | 6 ++-- gameplay.hpp | 2 ++ image_converter/converter.c | 1 + img_handler.cpp | 8 ++--- main.cpp | 7 ++--- menu_callbacks.cpp | 10 ++++-- puzzle.cpp | 4 +-- puzzle.hpp | 25 ++++++++++----- puzzle.png | Bin 114081 -> 101050 bytes solution_algorithm.cpp | 75 +++++++++++++++----------------------------- solution_algorithm.hpp | 17 +++++----- 12 files changed, 83 insertions(+), 85 deletions(-) diff --git a/README.md b/README.md index 1e87112..84b2fd6 100644 --- a/README.md +++ b/README.md @@ -5,7 +5,7 @@ A desktop game similar to the standard widget in windows 7. The game is written in C++ (including C++17 standard). FLTK was used as a graphics library. This library is not as heavy as Qt, and allows to quickly create an application with -graphical widgets. +graphical widgets. The essence of the game should be clear: to collect the image in its original form, moving one puzzle per move. @@ -27,7 +27,16 @@ The application has the following features: ## Building -For \*nix platform, you need to install FLTK library and then do the following: +Unfortunately, for \*nix platforms, you need to install the FLTK library because +the executable file will require a dynamic library. For example, for +distribution Ubuntu, this can be done as follows: + +``` +$ sudo apt install fltk1.3-dev +``` + +Next, simply download the source files via git and compile the project using +utility Make: ``` git clone https://git.scratko.xyz/picture-puzzle diff --git a/gameplay.cpp b/gameplay.cpp index d6bf59f..0fcb39c 100644 --- a/gameplay.cpp +++ b/gameplay.cpp @@ -7,8 +7,8 @@ #include #include -static bool is_next_to_empty_box(GameParams::coordinates empty_box_pos, - GameParams::coordinates current_pos) +bool is_next_to_empty_box(GameParams::coordinates empty_box_pos, + GameParams::coordinates current_pos) { return (current_pos.x - spacing - puzzle_size == empty_box_pos.x && @@ -30,7 +30,7 @@ static bool is_coordinate_match(GameParams::coordinates& first, bool PuzzleGame::IsFinalPlacement(GameParams *gp) { bool is_match = 1; - auto lambda = [gp, &is_match](std::unique_ptr& next_puzzle) { + auto lambda = [gp, &is_match](const std::unique_ptr& next_puzzle) { GameParams::coordinates pos_next_puzzle = { next_puzzle->x(), next_puzzle->y() }; GameParams::coordinates target_pos = diff --git a/gameplay.hpp b/gameplay.hpp index 0069772..9c26f5b 100644 --- a/gameplay.hpp +++ b/gameplay.hpp @@ -4,6 +4,8 @@ #include "puzzle.hpp" void press_button_callback(Fl_Widget *w, void *params); +bool is_next_to_empty_box(GameParams::coordinates empty_box_pos, + GameParams::coordinates current_pos); class PuzzleGame { public: diff --git a/image_converter/converter.c b/image_converter/converter.c index cccb9ad..c77b9ef 100644 --- a/image_converter/converter.c +++ b/image_converter/converter.c @@ -53,4 +53,5 @@ int main() } fprintf(out,"0xFF };\n\n"); fclose(out); + return 0; } diff --git a/img_handler.cpp b/img_handler.cpp index 6c62728..f4ded05 100644 --- a/img_handler.cpp +++ b/img_handler.cpp @@ -1,5 +1,5 @@ /* - * Processing of images uploaded by the user + * Processing of images uploaded by the user * (resizing, cropping, saving) */ @@ -30,11 +30,11 @@ ImageHandler::ImageHandler(const char *p) : source_path(p) { std::filesystem::create_directory(res_path); #if defined(_WIN32) - auto it = source_path.find_last_of('\\'); + auto idx = source_path.find_last_of('\\'); #else - auto it = source_path.find_last_of('/'); + auto idx = source_path.find_last_of('/'); #endif - std::string file_name = source_path.substr(it + 1); + std::string file_name = source_path.substr(idx + 1); std::string fn_withot_ext = file_name.substr(0, file_name.find_first_of('.')); #if defined(_WIN32) diff --git a/main.cpp b/main.cpp index 539130d..389056c 100644 --- a/main.cpp +++ b/main.cpp @@ -15,7 +15,7 @@ public: /* * Ending program by esc key while the computer is solving a puzzle */ - int handle(int event) { + int handle(int event) override { if(event == FL_KEYDOWN && Fl::event_length() != 0 && Fl::event_key() == FL_Escape) { @@ -28,9 +28,9 @@ public: int main() { srand(time(nullptr)); - MainWindow *win = new MainWindow(320, 355, "Picture puzzle"); + MainWindow *win = new MainWindow(320, 340, "Picture puzzle"); GameParams *params = GameParams::SetUpParams(win); - Fl_Sys_Menu_Bar *sys_bar = new Fl_Sys_Menu_Bar(0, 0, 355, 20, nullptr); + Fl_Sys_Menu_Bar *sys_bar = new Fl_Sys_Menu_Bar(0, 0, 320, 20, nullptr); sys_bar->add("&File/&New game", nullptr, new_game_callback, params); sys_bar->add("&File/&Load file", nullptr, load_file_callback); sys_bar->add("&File/&Exit", nullptr, exit_callback); @@ -40,5 +40,4 @@ int main() PuzzleGame::StartGame(params); win->show(); return Fl::run(); - return 0; } diff --git a/menu_callbacks.cpp b/menu_callbacks.cpp index 5668c67..d6b35dc 100644 --- a/menu_callbacks.cpp +++ b/menu_callbacks.cpp @@ -12,8 +12,8 @@ void new_game_callback(Fl_Widget*, void *gp) { - Fl::check(); - PuzzleGame::StartGame(reinterpret_cast(gp)); + if(!reinterpret_cast(gp)->GetAStarActive()) + PuzzleGame::StartGame(reinterpret_cast(gp)); } static bool check_correct_path_to_img(const char *path) @@ -52,15 +52,19 @@ void load_file_callback(Fl_Widget *sender, void*) void exit_callback(Fl_Widget *w, void*) { - w->parent()->hide(); + exit(0); } void solve_problem_callback(Fl_Widget *w, void *gp) { GameParams *game = reinterpret_cast(gp); + if(game->GetAStarActive()) + return; + game->SetAStarActive(); std::unique_ptr algorithm = ASearch::Start(game); Node *goal = algorithm->FindSolution(); algorithm->ShowSolution(goal); + game->ResetAStarActive(); int answer = fl_choice("Play again?", "No", "Yes", nullptr); if(answer) PuzzleGame::StartGame(game); diff --git a/puzzle.cpp b/puzzle.cpp index e78060b..d957d4e 100644 --- a/puzzle.cpp +++ b/puzzle.cpp @@ -24,7 +24,7 @@ void GameParams::CalculateStandardPuzzlePos() for(i = 0; i < puzzles_per_side; ++i) for(j = 0; j < puzzles_per_side; ++j, ++k) { tmp.x = i * (puzzle_size + spacing) + spacing; - tmp.y = j * (puzzle_size + spacing) + spacing + 30; + tmp.y = j * (puzzle_size + spacing) + spacing + 20; standard_puzzle_coordinates[k] = tmp; } } @@ -133,7 +133,7 @@ void GameParams::NextUntestedPuzzles() bool GameParams::IsSolvability() { int counter = 0; - for(size_t i = 0; i < puzzles.size(); ++i) + for(size_t i = 0; i < puzzles.size()-1; ++i) for(size_t j = i+1; j < puzzles.size(); ++j) if(puzzles[i]->sequence_number > puzzles[j]->sequence_number) ++counter; diff --git a/puzzle.hpp b/puzzle.hpp index 09660c8..88f13ac 100644 --- a/puzzle.hpp +++ b/puzzle.hpp @@ -17,15 +17,21 @@ enum { }; class Puzzle : public Fl_Button{ -public: - unsigned char sequence_number; +private: + unsigned char sequence_number{}; + // Path for file access error handling (ERR_FILE_ACCESS) std::string path; Fl_PNG_Image *stored_img_pointer; +public: Puzzle(int x, int y) : Fl_Button(x, y, puzzle_size, puzzle_size), - stored_img_pointer(nullptr) { - } + stored_img_pointer(nullptr) + { + } ~Puzzle() { delete stored_img_pointer; } + friend class GameParams; + friend class PuzzleGame; + friend class ASearch; }; class GameParams { @@ -43,9 +49,9 @@ private: coordinates empty_box; std::vector> puzzles; Fl_Window *win; - /* - * selecting the current directory where the user image is stored - */ + // True while A* is solving the puzzle; blocks new game and solving again + bool is_a_star_active = false; + // selecting the current directory where the user image is stored std::string cur_directory; GameParams(Fl_Window *a_win = nullptr) @@ -53,14 +59,17 @@ private: {} void CalculateStandardPuzzlePos(); void ResetFreePuzzles(); + void ResetAStarActive() { is_a_star_active = false; } + void SetAStarActive() { is_a_star_active = true; } void NextUntestedPuzzles(); bool IsSolvability(); void CreateNewPuzzles(); void SelectRandomPicture(); Fl_PNG_Image *LoadPictureParts(std::unique_ptr& tmp_puzzle); -public: void SetXYEmptyBox(int x, int y) { empty_box.x = x; empty_box. y = y; } coordinates GetXYEmptyBox() { return empty_box; } +public: + bool GetAStarActive() { return is_a_star_active; } static GameParams *SetUpParams(Fl_Window *win) { if(instance) return instance; diff --git a/puzzle.png b/puzzle.png index 30dd62b..8d6de56 100644 Binary files a/puzzle.png and b/puzzle.png differ diff --git a/solution_algorithm.cpp b/solution_algorithm.cpp index d96374b..922dd01 100644 --- a/solution_algorithm.cpp +++ b/solution_algorithm.cpp @@ -19,24 +19,21 @@ std::unique_ptr ASearch::Start(GameParams *gp) */ state_type init_xy(puzzle_pieces, GameParams::coordinates{}); std::for_each(gp->puzzles.begin(), gp->puzzles.end(), - [&init_xy] - (const std::unique_ptr& p) { - init_xy[p->sequence_number] = - {p->x(), p->y()}; - }); + [&init_xy](const std::unique_ptr& 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); + Node initial(init_xy); + state_type goal_xy(std::begin(gp->standard_puzzle_coordinates), + std::end(gp->standard_puzzle_coordinates)); + Node goal(goal_xy); return std::unique_ptr(new ASearch(initial, goal, gp)); } Node* ASearch::FindSolution() { ApplyFairEvaluator(initial); - open_queue.push(std::shared_ptr(new Node(initial))); + open_queue.push(std::shared_ptr(&initial, [](Node*){})); while(!open_queue.empty()) { std::shared_ptr best_node = open_queue.top(); open_queue.pop(); @@ -47,7 +44,7 @@ Node* ASearch::FindSolution() printf("VALUE: %d\n", best_node->evaluation); #endif if(goal == *best_node) { - open_queue.push(best_node); + close_set.insert(best_node); return best_node.get(); } close_set.insert(best_node); @@ -64,18 +61,16 @@ Node* ASearch::FindSolution() 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& n) { - return *n == *child_node; - }); + auto found_pos = + std::find_if(PQ_cont.begin(), PQ_cont.end(), + [&child_node](const std::shared_ptr& 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)); + PQ_cont.erase(found_pos); /* * reorder priority queue */ @@ -119,36 +114,19 @@ public: : free_moves(fm), empty_box_coord(ebc), cur_state(cs) {} void operator()(const GameParams::coordinates& c) { - if(IsNearEmptyBox(c, empty_box_coord)) { + if(is_next_to_empty_box(empty_box_coord, c)) { 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; + [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(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& parent) const { vect_node free_moves; @@ -156,11 +134,10 @@ vect_node ASearch::ComputeFreeMoves(const std::shared_ptr& parent) const 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& child) { - child->depth = parent->depth + 1; - child->parent_p = parent.get(); - }); + [parent](std::shared_ptr& child) { + child->depth = parent->depth + 1; + child->parent_p = parent.get(); + }); return free_moves; } @@ -171,13 +148,11 @@ void ASearch::ShowSolution(Node *goal) 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& p) { - return p->sequence_number == i; - }); + [i](const std::unique_ptr& p) { + return p->sequence_number == i; + }); (*puzzle_pos)->position(goal->state[i].x, goal->state[i].y); gp->win->redraw(); - Fl::flush(); Fl::check(); usleep(40000); } diff --git a/solution_algorithm.hpp b/solution_algorithm.hpp index f182aa8..792c270 100644 --- a/solution_algorithm.hpp +++ b/solution_algorithm.hpp @@ -28,6 +28,13 @@ public: return first->evaluation > second->evaluation; } }; + struct EqualNode { + bool operator()(const std::shared_ptr& first, + const std::shared_ptr& second) const { + return *first == *second; + } + }; + friend struct std::hash>; friend class ASearch; }; @@ -48,18 +55,11 @@ struct std::hash> { typedef std::vector> vect_node; // using of // ComputeFreeMoves class ASearch { - struct EqualNode { - bool operator()(const std::shared_ptr& first, - const std::shared_ptr& second) const { - return *first == *second; - } - }; - std::priority_queue, vect_node, Node::Comp> open_queue; std::unordered_set, std::hash>, - EqualNode> close_set; + Node::EqualNode> close_set; Node initial; Node goal; GameParams *gp; @@ -70,7 +70,6 @@ public: Node *FindSolution(); void ApplyFairEvaluator(Node &n) const; vect_node ComputeFreeMoves(const std::shared_ptr& n) const; - bool IsNearEmptyBox(const GameParams::coordinates c) const; void ShowSolution(Node *goal); }; -- cgit v1.2.3