aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--problem.cpp143
-rw-r--r--problem.hpp18
-rw-r--r--ui.cpp11
-rw-r--r--ui.hpp1
4 files changed, 170 insertions, 3 deletions
diff --git a/problem.cpp b/problem.cpp
index e56b0b3..3169751 100644
--- a/problem.cpp
+++ b/problem.cpp
@@ -1,5 +1,8 @@
+#include <deque>
+
#include "problem.hpp"
+
using namespace std;
// ===================================== //
@@ -42,16 +45,150 @@ solution solution::direct_sol(const hilare_a &pos_a, const hilare_a &pos_b) {
return solution(sol);
}
+bool solution::intersects(const problem &p) const {
+ for (auto& x: movement) {
+ if (x.intersects(p)) return true;
+ }
+ return false;
+}
+
// =============================== //
// IMPLEMENTATION FOR CLASS SOLVER //
// =============================== //
-solver::solver() {
- // nothing ?
+solver::solver() : _worker(&solver::run, this) {
+ _running = false;
+ _done = false;
+ _please_stop = false;
+}
+
+void solver::start(const problem &p) {
+ _p = p;
+
+ if (_running) {
+ _please_stop = true;
+ _worker.wait();
+ }
+
+ _please_stop = false;
+ _done = false;
+ _running = true;
+ _worker.launch();
+}
+
+void solver::run() {
+ problem p = _p; // copy problem
+
+ solver_internal d;
+ d.initialize(p);
+ {
+ sf::Lock l(_d_lock);
+ _d = d;
+ }
+
+ while (!_please_stop) {
+ solution s = d.try_find_solution();
+ if (s.movement.size() > 0) {
+ _s = s;
+ _done = true;
+ break;
+ }
+
+ if (!_please_stop) break;
+
+ d.step(p);
+
+ // Write local results to guys outside
+ {
+ sf::Lock l(_d_lock);
+ _d = d;
+ }
+ }
+ _running = false;
+}
+
+bool solver::finished() {
+ return _done;
+}
+
+solution solver::get_solution() {
+ if (_done) return _s;
+ return solution();
}
solver_internal solver::peek_internal() {
- return _d;
+ solver_internal x;
+ {
+ sf::Lock l(_d_lock);
+ x = _d;
+ }
+ return x;
+}
+
+void solver_internal::initialize(const problem &p) {
+ paths.clear();
+ pts.clear();
+
+ pts.push_back(p.begin_pos);
+ pts.push_back(p.end_pos);
+
+ solution ts = solution::direct_sol(p.begin_pos, p.end_pos);
+ if (!ts.intersects(p)) {
+ paths[0][1] = ts;
+ }
+}
+
+solution solver_internal::try_find_solution() {
+ // Simple graph search algorithm
+
+ vector<int> par(pts.size(), -1);
+ deque<int> q;
+
+ par[0] = 0;
+ q.push_back(0);
+ while (!q.empty()) {
+ int x = q.front();
+ q.pop_front();
+
+ if (paths.find(x) != paths.end()) {
+ auto pp = paths.find(x)->second;
+
+ for (auto& kv: pp) {
+ int y = kv.first;
+ if (par[y] == -1) {
+ par[y] = x;
+ q.push_back(y);
+ }
+ }
+ }
+ }
+
+ if (par[1] != -1) {
+ vector<hilare_a_mvt> sol;
+
+ int b = 1;
+ while (b != 0) {
+ int a = par[b];
+
+ auto& x = paths[a][b];
+
+ sol.insert(sol.begin(), x.movement.begin(), x.movement.end());
+
+ b = a;
+ }
+
+ return solution(sol);
+ }
+
+ return solution(); // not found
+}
+
+void solver_internal::step(const problem &p) {
+ // take new random point
+ // try to connect to all existing points
+
+ // TODO
+ sf::sleep(sf::milliseconds(10)); // no CPU hog
}
/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/problem.hpp b/problem.hpp
index 685e1df..8851fa2 100644
--- a/problem.hpp
+++ b/problem.hpp
@@ -2,6 +2,7 @@
#include <vector>
#include <map>
+#include <SFML/System.hpp>
#include "geom.hpp"
@@ -87,18 +88,35 @@ struct solver_internal {
// represents a graph of randomly chosen positions and simple solutions between them
std::vector<hilare_a> pts;
std::map<int, std::map<int, solution> > paths;
+
+ void initialize(const problem &p);
+ solution try_find_solution();
+ void step(const problem &p);
};
class solver {
// mutex-protected asynchronous structure
private:
+
+ sf::Mutex _d_lock;
solver_internal _d;
+ problem _p;
+
+ bool _please_stop;
+ bool _running;
+ bool _done;
+ solution _s;
+
+ sf::Thread _worker;
public:
solver();
void start(const problem &p);
+
+ void run(); // worker thread
+
bool finished();
solution get_solution();
diff --git a/ui.cpp b/ui.cpp
index 1f61f03..a2ec620 100644
--- a/ui.cpp
+++ b/ui.cpp
@@ -11,6 +11,7 @@
- e : select end pos
- a : add obstacle
- d : delete obstacle under mouse pointer
+ - g : start solving
Select modes : no other keys
*/
@@ -25,6 +26,8 @@ UI::UI(hilare_a_param *p) : _sel_obs(vec(0,0), 0) {
_view.zoom = 1;
_mode = M_NORMAL;
+
+ _got_sol = true;
}
void UI::run() {
@@ -55,6 +58,9 @@ void UI::run() {
_view.zoom *= 1.1;
} else if (k == 'o') {
_view.zoom /= 1.1;
+ } else if (k == 'g') {
+ _solver.start(_p);
+ _got_sol = false;
}
}
@@ -63,6 +69,11 @@ void UI::run() {
if (_mode == M_SEL_BEGIN || _mode == M_SEL_END) handle_sel_pos(ev);
}
+ if (!_got_sol && _solver.finished()) {
+ _s = _solver.get_solution();
+ _got_sol = true;
+ }
+
_win.clear(sf::Color::Black);
render_internal();
diff --git a/ui.hpp b/ui.hpp
index 8496b58..07383fd 100644
--- a/ui.hpp
+++ b/ui.hpp
@@ -28,6 +28,7 @@ class UI {
problem _p;
solution _s;
solver _solver;
+ bool _got_sol;
struct {
double x0, y0, zoom;