1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
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();
}
}
|
