back to scratko.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorscratko <m@scratko.xyz>2025-07-25 17:04:21 +0300
committerscratko <m@scratko.xyz>2025-07-25 17:46:22 +0300
commit90bd5ca05bea4dbeaaeff5cbe13b5671da420c82 (patch)
tree05757ed9b9ea0c007f4b4e86cfd8402fea4c6a5d
parentac9a06b04144023e87d1a504cfe5598e7cf3d7b4 (diff)
downloadpicture-puzzle-master.tar.gz
picture-puzzle-master.tar.bz2
picture-puzzle-master.zip
July updateHEADmaster
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.
-rw-r--r--README.md13
-rw-r--r--gameplay.cpp6
-rw-r--r--gameplay.hpp2
-rw-r--r--image_converter/converter.c1
-rw-r--r--img_handler.cpp8
-rw-r--r--main.cpp7
-rw-r--r--menu_callbacks.cpp10
-rw-r--r--puzzle.cpp4
-rw-r--r--puzzle.hpp25
-rw-r--r--puzzle.pngbin114081 -> 101050 bytes
-rw-r--r--solution_algorithm.cpp75
-rw-r--r--solution_algorithm.hpp17
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 <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)
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<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);
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<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;
diff --git a/puzzle.png b/puzzle.png
index 30dd62b..8d6de56 100644
--- a/puzzle.png
+++ b/puzzle.png
Binary files 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> 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);
};