aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--BreadthFirstPathfinder.cpp3
-rw-r--r--CMakeLists.txt1
-rw-r--r--CollisionContext.cpp1
-rw-r--r--CyclePathfindingMethodCommand.cpp9
-rw-r--r--CyclePathfindingMethodCommand.h17
-rw-r--r--DijkstraPathfinder.cpp11
-rw-r--r--PathfindingContext.cpp1
-rw-r--r--QuadTreeCollisionChecker.h2
-rw-r--r--ViewController.cpp60
-rw-r--r--ViewController.h3
-rw-r--r--readme.md4
11 files changed, 86 insertions, 26 deletions
diff --git a/BreadthFirstPathfinder.cpp b/BreadthFirstPathfinder.cpp
index c204387..e3a5430 100644
--- a/BreadthFirstPathfinder.cpp
+++ b/BreadthFirstPathfinder.cpp
@@ -18,9 +18,12 @@ void BreadthFirstPathfinder::find_between(const XY & start, const XY & end) {
vector<Path> trails = { { start } };
this->end = end;
+ int steps = -1;
while (trails.size() > 0) {
+ steps++;
trails = this->find_step(trails);
}
+ printf("BFS: %s (%d steps)\n", this->solution.empty() ? "no solution found" : "solution found", steps);
}
vector<BreadthFirstPathfinder::Path> BreadthFirstPathfinder::find_step(const vector<Path> & to_visit) {
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 710b756..6b221da 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -56,6 +56,7 @@ add_executable(main
Pathfinder.cpp
DijkstraPathfinder.cpp
BreadthFirstPathfinder.cpp
+ CyclePathfindingMethodCommand.cpp
)
target_link_libraries(main
diff --git a/CollisionContext.cpp b/CollisionContext.cpp
index 6df5d3b..743a452 100644
--- a/CollisionContext.cpp
+++ b/CollisionContext.cpp
@@ -35,5 +35,6 @@ void CollisionContext::update() {
void CollisionContext::cycle_method() {
this->checker_index++;
+ this->update();
}
diff --git a/CyclePathfindingMethodCommand.cpp b/CyclePathfindingMethodCommand.cpp
new file mode 100644
index 0000000..562a1ab
--- /dev/null
+++ b/CyclePathfindingMethodCommand.cpp
@@ -0,0 +1,9 @@
+#include "CyclePathfindingMethodCommand.h"
+#include "Museum.h"
+
+CyclePathfindingMethodCommand::CyclePathfindingMethodCommand(Museum & m) : museum(m) { }
+
+void CyclePathfindingMethodCommand::execute() {
+ this->museum.pathfinding.cycle_solver();
+}
+
diff --git a/CyclePathfindingMethodCommand.h b/CyclePathfindingMethodCommand.h
new file mode 100644
index 0000000..6f7366d
--- /dev/null
+++ b/CyclePathfindingMethodCommand.h
@@ -0,0 +1,17 @@
+#pragma once
+
+#include "Command.h"
+
+class Museum;
+
+class CyclePathfindingMethodCommand : public Command {
+public:
+ CyclePathfindingMethodCommand(Museum & m);
+
+public:
+ virtual void execute();
+
+private:
+ Museum & museum;
+};
+
diff --git a/DijkstraPathfinder.cpp b/DijkstraPathfinder.cpp
index 8d86235..8a8e8eb 100644
--- a/DijkstraPathfinder.cpp
+++ b/DijkstraPathfinder.cpp
@@ -23,14 +23,19 @@ void DijkstraPathfinder::find_between(const XY & start, const XY & end) {
this->map_get(start).distance = 0;
this->dijkstra(start);
- // no solution
- if (!this->is_visited(end)) return;
+ if (!this->is_visited(end)) {
+ printf("Dijkstra: no solution found\n");
+ return;
+ }
XY pos = end;
+ int steps = 0;
while (pos != start) {
solution.push_front(pos);
- pos = this->map[pos].parent;
+ pos = this->map_get(pos).parent;
+ steps++;
}
+ printf("Dijkstra: solution found (%d steps, %u time)\n", steps, this->map_get(end).distance);
}
DijkstraPathfinder::Node & DijkstraPathfinder::map_get(const XY & pos) {
diff --git a/PathfindingContext.cpp b/PathfindingContext.cpp
index df2f65b..95ac3b1 100644
--- a/PathfindingContext.cpp
+++ b/PathfindingContext.cpp
@@ -16,6 +16,7 @@ PathfindingContext::PathfindingContext(Museum & m) : museum(m) {
void PathfindingContext::cycle_solver() {
this->solver_index = (this->solver_index + 1) % this->solvers.size();
+ this->update();
}
Pathfinder & PathfindingContext::get_solver() {
diff --git a/QuadTreeCollisionChecker.h b/QuadTreeCollisionChecker.h
index 420e0b7..956befb 100644
--- a/QuadTreeCollisionChecker.h
+++ b/QuadTreeCollisionChecker.h
@@ -24,7 +24,7 @@ public:
private:
QuadTreeCollisionChecker(const QuadTreeCollisionChecker *, const Rectangle & boundary);
- const int capacity = 2;
+ const int capacity = 4;
std::forward_list<Artist *> artists;
size_t artists_size = 0;
diff --git a/ViewController.cpp b/ViewController.cpp
index b1fd795..3238f0f 100644
--- a/ViewController.cpp
+++ b/ViewController.cpp
@@ -4,6 +4,7 @@
#include "CollisionChecker.h"
#include "ControlBooleanCommand.h"
#include "CycleCollisionMethodCommand.h"
+#include "CyclePathfindingMethodCommand.h"
#include "QuadTreeCollisionChecker.h"
#include "Exception.h"
#include "KeyboardCode.h"
@@ -27,9 +28,9 @@ ViewController::~ViewController() {
void ViewController::update() {
this->update_size();
this->update_tiles();
- if (this->draw_artists) this->update_artists();
- if (this->draw_pathfinding) this->update_pathfinding();
- if (this->draw_quadtree) this->update_quadtree();
+ this->update_artists();
+ this->update_pathfinding();
+ this->update_quadtree();
}
void ViewController::update_size() {
@@ -55,6 +56,8 @@ void ViewController::update_tiles() {
}
void ViewController::update_artists() {
+ if (!this->draw_artists) return;
+
People & people = this->museum.people;
for (Artist * artist : people.get_artists()) {
Rectangle rect = {
@@ -80,25 +83,28 @@ void ViewController::update_pathfinding() {
PathfindingContext & ctx = this->museum.pathfinding;
Pathfinder & solver = ctx.get_solver();
- for (int y = 0; y < this->museum.canvas.data.rows; y++) {
- for (int x = 0; x < this->museum.canvas.data.columns; x++) {
- if (!solver.is_visited({ x, y })) continue;
- Rectangle rect = {
- .x = x * scale,
- .y = y * scale,
- .width = scale,
- .height = scale,
- };
- this->view.draw_rect(rect, { 0, 0, 0 }, 2);
+ if (this->draw_visited) {
+ for (int y = 0; y < this->museum.canvas.data.rows; y++) {
+ for (int x = 0; x < this->museum.canvas.data.columns; x++) {
+ if (!solver.is_visited({ x, y })) continue;
+ Rectangle rect = {
+ .x = x * scale,
+ .y = y * scale,
+ .width = scale,
+ .height = scale,
+ };
+ this->view.draw_rect(rect, { 0, 0, 0 }, 2);
+ }
}
}
- const Pathfinder::Path & solution = solver.get_path();
- for (const XY & point : solution) {
- this->draw_pathfinding_dot(point, { 0, 0, 0 });
+ if (this->draw_path) {
+ const Pathfinder::Path & solution = solver.get_path();
+ for (const XY & point : solution) {
+ this->draw_pathfinding_dot(point, { 0, 0, 0 });
+ }
+ this->draw_pathfinding_dot(ctx.get_start(), { 0xff, 0xff, 0xff });
}
-
- this->draw_pathfinding_dot(ctx.get_start(), { 0xff, 0xff, 0xff });
}
void ViewController::update_quadtree_recursive(QuadTreeCollisionChecker * tree) {
@@ -120,6 +126,7 @@ void ViewController::update_quadtree_recursive(QuadTreeCollisionChecker * tree)
}
void ViewController::update_quadtree() {
+ if (!this->draw_quadtree) return;
shared_ptr<CollisionChecker> checker = this->museum.collision.get_checker();
auto tree = dynamic_cast<QuadTreeCollisionChecker*>(checker.get());
if (tree == nullptr) return;
@@ -161,6 +168,22 @@ void ViewController::ev_keydown(KeyboardCode key) {
ControlBooleanCommand(this->draw_quadtree).execute();
break;
}
+ case KEY_P: {
+ ControlBooleanCommand(this->draw_path).execute();
+ break;
+ }
+ case KEY_V: {
+ ControlBooleanCommand(this->draw_visited).execute();
+ break;
+ }
+ case KEY_D: {
+ CyclePathfindingMethodCommand(this->museum).execute();
+ break;
+ }
+ case KEY_W: {
+ // TODO: toggle collision calculation between artist and path
+ break;
+ }
default: break;
}
} catch (Exception & e) {
@@ -172,6 +195,7 @@ void ViewController::ev_mousedown(MouseCode button) {
try {
switch (button) {
case MOUSE_LEFT: {
+ // TODO: call through command
this->museum.pathfinding.set_start(this->mouse_pos);
break;
}
diff --git a/ViewController.h b/ViewController.h
index ce069bd..c74c72a 100644
--- a/ViewController.h
+++ b/ViewController.h
@@ -43,8 +43,9 @@ private:
private:
bool draw_artists = true;
- bool draw_pathfinding = true;
bool draw_quadtree = true;
+ bool draw_path = true;
+ bool draw_visited = true;
private:
float scale = 16;
diff --git a/readme.md b/readme.md
index 12a8bb2..0a8de0b 100644
--- a/readme.md
+++ b/readme.md
@@ -7,7 +7,5 @@ DPA:
ALGA:
- artist-path collision behavior (toggleable)
-- pathfinding start/end selection w/ mouse buttons (left for start, right for end)
-- show {shortest,fastest,no} path toggle
-- vast meer
+- multiple fastest routes with dijkstra???