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. --- solution_algorithm.cpp | 75 +++++++++++++++++--------------------------------- 1 file changed, 25 insertions(+), 50 deletions(-) (limited to 'solution_algorithm.cpp') 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); } -- cgit v1.2.3