diff options
| -rw-r--r-- | README.md | 82 | ||||
| -rw-r--r-- | gameplay.cpp | 6 | ||||
| -rw-r--r-- | gameplay.hpp | 2 | ||||
| -rw-r--r-- | image_converter/converter.c | 1 | ||||
| -rw-r--r-- | img_handler.cpp | 8 | ||||
| -rw-r--r-- | main.cpp | 7 | ||||
| -rw-r--r-- | menu_callbacks.cpp | 10 | ||||
| -rw-r--r-- | puzzle.cpp | 4 | ||||
| -rw-r--r-- | puzzle.hpp | 25 | ||||
| -rw-r--r-- | puzzle.png | bin | 114081 -> 101050 bytes | |||
| -rw-r--r-- | solution_algorithm.cpp | 75 | ||||
| -rw-r--r-- | solution_algorithm.hpp | 17 |
12 files changed, 133 insertions, 104 deletions
@@ -1,35 +1,74 @@ -# Picture puzzle +# Picture Puzzle <img src="puzzle.png" /> -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. +A desktop sliding puzzle game similar to the standard widget in Windows 7. +Written in modern **C++17** with **FLTK** for the graphical interface, it +provides a lightweight, cross-platform experience with fast compilation and +responsive UI. -The essence of the game should be clear: to collect the image in its original -form, moving one puzzle per move. +The goal is simple: rearrange the tiles to restore the original image, moving +one piece at a time. -The application has the following features: +--- -- *upload your image in any format and resolution. The program itself will - resize, cut into puzzles, create the appropriate directory and save them in - it.* +## Features -- *showing the complete solution of the puzzle using the optimization algorithm - A\*.* +### Image Handling +- Upload an image in **any format and resolution** — the program will: + - Resize it to fit the puzzle grid (`300x300`). + - Slice it into `3x3` tiles. + - Save tiles into a dedicated `resources/` subdirectory. +- Uses **stb_image**, **stb_image_resize**, and **stb_image_write** for image +loading, resizing, and saving. -- *the game is distributed in a single executable file by embedding the original - standard image (toucan image) in the executable file. The image data is stored - in an array in an object file (resources.o)* +### Built-in Embedded Image +- **Both Linux and Windows builds include a fully embedded image** (Toucan) directly inside the executable. +- The embedded image is stored in `resources.o` as a static **byte array**. +- A C-language **image converter** tool is included, which: + - Takes a PNG image. + - Generates a `resources.cpp` file containing the image bytes. +- This allows shipping the game as a **single executable** without requiring external image files. +- The embedded Toucan image serves as the default puzzle; users can still load their own images. -- *support for \*unix and Windows platforms* +### Puzzle Gameplay +- Standard 3×3 sliding puzzle with one empty tile. +- Random shuffling with **solvability check** to ensure the puzzle can be +completed. +- Option to load: + - Built-in embedded image. + - External images from `resources/` folder or user upload. + +### Automatic Puzzle Solver +- **A\*** search algorithm implementation. +- Uses **Manhattan distance** as the heuristic (`g(n) + W(n)`). +- Shows a **step-by-step animation** of the optimal solution. + +### Cross-Platform +- Works on **Linux** and **Windows**. +- On both platforms, distributed as a single executable with embedded resources. + +--- + +## Technologies Used +- **C++17 STL** — `std::unique_ptr`, `std::shared_ptr`, `priority_queue`, +`unordered_set`, `filesystem`, `algorithm`. +- **FLTK** — lightweight GUI library. +- **stb_image** / **stb_image_resize** / **stb_image_write** — image processing. +- **A\*** algorithm for optimal pathfinding. +- Custom hashing and equality comparison for puzzle states. +- **Custom C-based resource generator** for embedding binary image data into the executable. + +--- ## Building -For \*nix platform, you need to install FLTK library and then do the following: +### Linux -``` +Install FLTK development package: + +```bash +sudo apt install fltk1.3-dev git clone https://git.scratko.xyz/picture-puzzle cd picture-puzzle make @@ -38,6 +77,7 @@ make ## For Windows platform -The built executable file (under x86_64) is available at the link: <a -href="https://scratko.xyz/games/puzzle.exe" target="_blank">Download Windows +- Requires FLTK for Windows. +- Prebuilt x86_64 executable available here: +<a href="https://scratko.xyz/games/puzzle.exe" target="_blank">Download Windows version</a> diff --git a/gameplay.cpp b/gameplay.cpp index d6bf59f..0fcb39c 100644 --- a/gameplay.cpp +++ b/gameplay.cpp @@ -7,8 +7,8 @@ #include <memory> #include <vector> -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<Puzzle>& next_puzzle) { + auto lambda = [gp, &is_match](const std::unique_ptr<Puzzle>& 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) @@ -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<GameParams*>(gp)); + if(!reinterpret_cast<GameParams*>(gp)->GetAStarActive()) + PuzzleGame::StartGame(reinterpret_cast<GameParams*>(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<GameParams*>(gp); + if(game->GetAStarActive()) + return; + game->SetAStarActive(); std::unique_ptr<ASearch> 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); @@ -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; @@ -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<std::unique_ptr<Puzzle>> 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<Puzzle>& 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; Binary files differdiff --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> 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<Puzzle>& p) { - init_xy[p->sequence_number] = - {p->x(), p->y()}; - }); + [&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); + 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<ASearch>(new ASearch(initial, goal, gp)); } Node* ASearch::FindSolution() { ApplyFairEvaluator(initial); - open_queue.push(std::shared_ptr<Node>(new Node(initial))); + open_queue.push(std::shared_ptr<Node>(&initial, [](Node*){})); while(!open_queue.empty()) { std::shared_ptr<Node> 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<Node>& n) { - return *n == *child_node; - }); + 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)); + 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<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; @@ -156,11 +134,10 @@ vect_node ASearch::ComputeFreeMoves(const std::shared_ptr<Node>& 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<Node>& child) { - child->depth = parent->depth + 1; - child->parent_p = parent.get(); - }); + [parent](std::shared_ptr<Node>& 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<Puzzle>& p) { - return p->sequence_number == i; - }); + [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(); - 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<Node>& first, + const std::shared_ptr<Node>& second) const { + return *first == *second; + } + }; + friend struct std::hash<std::shared_ptr<Node>>; friend class ASearch; }; @@ -48,18 +55,11 @@ struct std::hash<std::shared_ptr<Node>> { 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::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<Node>& n) const; - bool IsNearEmptyBox(const GameParams::coordinates c) const; void ShowSolution(Node *goal); }; |
