From da669db4f083194bc78358041c5d9929e103ac9f Mon Sep 17 00:00:00 2001 From: Loek Le Blansch Date: Thu, 24 Oct 2024 21:14:14 +0200 Subject: add more todos, shortcut keys and logging --- BreadthFirstPathfinder.cpp | 3 ++ CMakeLists.txt | 1 + CollisionContext.cpp | 1 + CyclePathfindingMethodCommand.cpp | 9 ++++++ CyclePathfindingMethodCommand.h | 17 +++++++++++ DijkstraPathfinder.cpp | 11 +++++-- PathfindingContext.cpp | 1 + QuadTreeCollisionChecker.h | 2 +- ViewController.cpp | 60 +++++++++++++++++++++++++++------------ ViewController.h | 3 +- readme.md | 4 +-- 11 files changed, 86 insertions(+), 26 deletions(-) create mode 100644 CyclePathfindingMethodCommand.cpp create mode 100644 CyclePathfindingMethodCommand.h 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 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::find_step(const vector & 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 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 checker = this->museum.collision.get_checker(); auto tree = dynamic_cast(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??? -- cgit v1.2.3