From fab0fccc0aaa18e915bcd08e81e5a04177e435cd Mon Sep 17 00:00:00 2001 From: Loek Le Blansch Date: Mon, 21 Oct 2024 19:06:58 +0200 Subject: fix quad tree collision checker --- Artist.cpp | 8 +-- Artist.h | 1 + ArtistData.h | 1 - CMakeLists.txt | 5 +- CollisionChecker.cpp | 14 ++++++ CollisionChecker.h | 17 +++++++ CollisionContext.cpp | 10 ++-- CollisionContext.h | 6 +-- KeyboardCode.h | 6 +++ NaiveCollisionChecker.cpp | 19 +++++++ NaiveCollisionChecker.h | 14 ++++++ QuadTree.cpp | 83 ------------------------------ QuadTree.h | 34 ------------- QuadTreeCollisionChecker.cpp | 103 ++++++++++++++++++++++++++++++++++++++ QuadTreeCollisionChecker.h | 39 +++++++++++++++ ToggleArtistVisibilityCommand.cpp | 5 -- ToggleArtistVisibilityCommand.h | 11 ---- ViewController.cpp | 23 ++++++--- ViewController.h | 6 +-- docs/class-diag.puml | 22 +++++++- 20 files changed, 268 insertions(+), 159 deletions(-) create mode 100644 CollisionChecker.cpp create mode 100644 CollisionChecker.h create mode 100644 NaiveCollisionChecker.cpp create mode 100644 NaiveCollisionChecker.h delete mode 100644 QuadTree.cpp delete mode 100644 QuadTree.h create mode 100644 QuadTreeCollisionChecker.cpp create mode 100644 QuadTreeCollisionChecker.h delete mode 100644 ToggleArtistVisibilityCommand.cpp delete mode 100644 ToggleArtistVisibilityCommand.h diff --git a/Artist.cpp b/Artist.cpp index 76e0ca9..6d95542 100644 --- a/Artist.cpp +++ b/Artist.cpp @@ -28,11 +28,6 @@ void Artist::update_edge_collision() { } void Artist::update_movement() { - if (this->data.waiting > 0) { - this->data.waiting--; - return; - } - float last_x = this->data.x; float last_y = this->data.y; @@ -44,8 +39,7 @@ void Artist::update_movement() { } void Artist::update_color() { - // waiting color - if (this->data.waiting > 0) { + if (this->colliding) { this->color = { .red = 0xff, .green = 0x00, diff --git a/Artist.h b/Artist.h index b880d5e..81ae7b0 100644 --- a/Artist.h +++ b/Artist.h @@ -22,6 +22,7 @@ public: Color color; bool step = false; + bool colliding = false; private: Museum & museum; diff --git a/ArtistData.h b/ArtistData.h index ab1e37c..1c3c88c 100644 --- a/ArtistData.h +++ b/ArtistData.h @@ -5,6 +5,5 @@ struct ArtistData { float y = 0.0; float vx = 0.0; float vy = 0.0; - unsigned int waiting = 0; }; diff --git a/CMakeLists.txt b/CMakeLists.txt index 9f45d76..15f889b 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -45,12 +45,13 @@ add_executable(main OpenFileGUICommand.cpp LoadFilesCommand.cpp ToggleMuseumPauseCommand.cpp - ToggleArtistVisibilityCommand.cpp StepTileCommand.cpp TimeTravelCommand.cpp CollisionContext.cpp - QuadTree.cpp + QuadTreeCollisionChecker.cpp ControlBooleanCommand.cpp + CollisionChecker.cpp + NaiveCollisionChecker.cpp ) target_link_libraries(main diff --git a/CollisionChecker.cpp b/CollisionChecker.cpp new file mode 100644 index 0000000..b8bcbd5 --- /dev/null +++ b/CollisionChecker.cpp @@ -0,0 +1,14 @@ +#include "CollisionChecker.h" +#include "Museum.h" + +CollisionChecker::CollisionChecker(Museum & m) : museum(m) { } + +void CollisionChecker::compare(Artist & a, Artist & b) { + if (a.data.x + 0.5 < b.data.x) return; + if (a.data.y + 0.5 < b.data.y) return; + if (a.data.x > b.data.x + 0.5) return; + if (a.data.y > b.data.y + 0.5) return; + + a.colliding = b.colliding = true; +} + diff --git a/CollisionChecker.h b/CollisionChecker.h new file mode 100644 index 0000000..646aa42 --- /dev/null +++ b/CollisionChecker.h @@ -0,0 +1,17 @@ +#pragma once + +class Museum; +class Artist; + +class CollisionChecker { +public: + CollisionChecker(Museum &); + void compare(Artist & a, Artist & b); + + virtual void check() = 0; + +protected: + Museum & museum; + +}; + diff --git a/CollisionContext.cpp b/CollisionContext.cpp index e7550e5..ec608b5 100644 --- a/CollisionContext.cpp +++ b/CollisionContext.cpp @@ -2,16 +2,20 @@ #include "CollisionContext.h" #include "Museum.h" +#include "NaiveCollisionChecker.h" +#include "QuadTreeCollisionChecker.h" using namespace std; CollisionContext::CollisionContext(Museum & m) : museum(m) {} -shared_ptr CollisionContext::get_quadtree() { - return this->quadtree; +shared_ptr CollisionContext::get_checker() { + return this->checker; } void CollisionContext::update() { - this->quadtree = std::make_shared(this->museum); + this->checker = std::make_shared(this->museum); + // this->checker = std::make_shared(this->museum); + this->checker->check(); } diff --git a/CollisionContext.h b/CollisionContext.h index 3cce4d7..e35c373 100644 --- a/CollisionContext.h +++ b/CollisionContext.h @@ -1,7 +1,7 @@ #pragma once #include -#include "QuadTree.h" +#include "CollisionChecker.h" class Museum; @@ -11,12 +11,12 @@ public: void update(); - std::shared_ptr get_quadtree(); + std::shared_ptr get_checker(); private: Museum & museum; private: - std::shared_ptr quadtree = nullptr; + std::shared_ptr checker = nullptr; }; diff --git a/KeyboardCode.h b/KeyboardCode.h index a7232ba..345c7eb 100644 --- a/KeyboardCode.h +++ b/KeyboardCode.h @@ -7,5 +7,11 @@ typedef enum { KEY_A = 4, KEY_LEFT = 80, KEY_RIGHT = 79, + KEY_Q = 20, + KEY_W = 26, + KEY_V = 25, + KEY_D = 7, + KEY_P = 19, + KEY_C = 6, } KeyboardCode; diff --git a/NaiveCollisionChecker.cpp b/NaiveCollisionChecker.cpp new file mode 100644 index 0000000..db277ab --- /dev/null +++ b/NaiveCollisionChecker.cpp @@ -0,0 +1,19 @@ +#include "NaiveCollisionChecker.h" +#include "Museum.h" +#include "People.h" +#include "Artist.h" + +void NaiveCollisionChecker::check() { + auto artists = this->museum.people.get_artists(); + for (Artist * artist : artists) artist->colliding = false; + auto begin = artists.begin(); + auto end = artists.end(); + for (auto it1 = begin; it1 != end; ++it1) { + auto it2 = it1; + ++it2; + for (; it2 != end; ++it2) { + this->compare(**it1, **it2); + } + } +} + diff --git a/NaiveCollisionChecker.h b/NaiveCollisionChecker.h new file mode 100644 index 0000000..31a2d62 --- /dev/null +++ b/NaiveCollisionChecker.h @@ -0,0 +1,14 @@ +#pragma once + +#include "CollisionChecker.h" + +class NaiveCollisionChecker : public CollisionChecker { + using CollisionChecker::CollisionChecker; + +public: + virtual void check(); + +}; + + + diff --git a/QuadTree.cpp b/QuadTree.cpp deleted file mode 100644 index 3850e2c..0000000 --- a/QuadTree.cpp +++ /dev/null @@ -1,83 +0,0 @@ -#include - -#include "QuadTree.h" -#include "Museum.h" - -using namespace std; - -QuadTree::QuadTree(Museum & museum) { - this->boundary = { - .x = 0.0, - .y = 0.0, - .width = static_cast(museum.canvas.data.columns), - .height = static_cast(museum.canvas.data.rows), - }; - - this->artists = museum.people.get_artists(); - for (auto & _ : this->artists) this->artists_size++; - - if (this->artists_size > this->capacity) - this->subdivide(); -} - -QuadTree::QuadTree(const QuadTree * parent, const Rectangle & boundary) { - this->boundary = boundary; - - this->artists = parent->artists; - this->artists_size = parent->artists_size; - - this->cull(); - - if (this->artists_size > this->capacity) - this->subdivide(); -} - -void QuadTree::subdivide() { - float half_width = this->boundary.width / 2; - float half_height = this->boundary.height / 2; - - // squares smaller than artists will subdivide infinitely - if (half_width <= 0.5) return; - if (half_height <= 0.5) return; - - this->subtree[0] = unique_ptr(new QuadTree(this, { - .x = this->boundary.x, - .y = this->boundary.y, - .width = half_width, - .height = half_height, - })); - this->subtree[1] = unique_ptr(new QuadTree(this, { - .x = this->boundary.x + half_width, - .y = this->boundary.y, - .width = half_width, - .height = half_height, - })); - this->subtree[2] = unique_ptr(new QuadTree(this, { - .x = this->boundary.x, - .y = this->boundary.y + half_height, - .width = half_width, - .height = half_height, - })); - this->subtree[3] = unique_ptr(new QuadTree(this, { - .x = this->boundary.x + half_width, - .y = this->boundary.y + half_height, - .width = half_width, - .height = half_height, - })); - - // now all artists are stored in subtrees, so they no longer have to be - // stored in this quad - this->artists.clear(); -} - -void QuadTree::cull() { - // remove artists that are *completely* outside the boundary - this->artists_size -= this->artists.remove_if([this](const Artist * artist) -> bool { - if (artist->data.x + 0.5 < this->boundary.x) return true; - if (artist->data.y + 0.5 < this->boundary.y) return true; - if (artist->data.x > this->boundary.x + this->boundary.width) return true; - if (artist->data.y > this->boundary.y + this->boundary.height) return true; - return false; - }); -} - diff --git a/QuadTree.h b/QuadTree.h deleted file mode 100644 index 5a371d4..0000000 --- a/QuadTree.h +++ /dev/null @@ -1,34 +0,0 @@ -#pragma once - -#include -#include - -#include "Artist.h" -#include "Rectangle.h" - -class QuadTree { -public: - QuadTree(Museum &); - QuadTree(const QuadTree *, const Rectangle & boundary); - const Rectangle & get_boundary() { return this->boundary; } - std::unique_ptr subtree[4] = { - nullptr, - nullptr, - nullptr, - nullptr, - }; - -private: - const int capacity = 2; - - std::forward_list artists; - size_t artists_size = 0; - - Rectangle boundary; - - void subdivide(); - void cull(); -}; - - - diff --git a/QuadTreeCollisionChecker.cpp b/QuadTreeCollisionChecker.cpp new file mode 100644 index 0000000..0d211c0 --- /dev/null +++ b/QuadTreeCollisionChecker.cpp @@ -0,0 +1,103 @@ +#include + +#include "QuadTreeCollisionChecker.h" +#include "Museum.h" + +using namespace std; + +QuadTreeCollisionChecker::QuadTreeCollisionChecker(Museum & museum) : CollisionChecker(museum) { + this->boundary = { + .x = 0.0, + .y = 0.0, + .width = static_cast(museum.canvas.data.columns), + .height = static_cast(museum.canvas.data.rows), + }; + + this->artists = museum.people.get_artists(); + for (auto & _ : this->artists) this->artists_size++; + + if (this->artists_size > this->capacity) + this->subdivide(); +} + +QuadTreeCollisionChecker::QuadTreeCollisionChecker(const QuadTreeCollisionChecker * parent, const Rectangle & boundary) : CollisionChecker(parent->museum) { + this->boundary = boundary; + + this->artists = parent->artists; + this->artists_size = parent->artists_size; + + this->cull(); + + if (this->artists_size > this->capacity) + this->subdivide(); +} + +void QuadTreeCollisionChecker::subdivide() { + float half_width = this->boundary.width / 2; + float half_height = this->boundary.height / 2; + + // squares smaller than artists will subdivide infinitely + if (half_width <= 0.5) return; + if (half_height <= 0.5) return; + + this->subtree[0] = unique_ptr(new QuadTreeCollisionChecker(this, { + .x = this->boundary.x, + .y = this->boundary.y, + .width = half_width, + .height = half_height, + })); + this->subtree[1] = unique_ptr(new QuadTreeCollisionChecker(this, { + .x = this->boundary.x + half_width, + .y = this->boundary.y, + .width = half_width, + .height = half_height, + })); + this->subtree[2] = unique_ptr(new QuadTreeCollisionChecker(this, { + .x = this->boundary.x, + .y = this->boundary.y + half_height, + .width = half_width, + .height = half_height, + })); + this->subtree[3] = unique_ptr(new QuadTreeCollisionChecker(this, { + .x = this->boundary.x + half_width, + .y = this->boundary.y + half_height, + .width = half_width, + .height = half_height, + })); + + // now all artists are stored in subtrees, so they no longer have to be + // stored in this quad + this->artists.clear(); + this->artists_size = 0; +} + +void QuadTreeCollisionChecker::cull() { + // remove artists that are *completely* outside the boundary + this->artists_size -= this->artists.remove_if([this](const Artist * artist) -> bool { + if (artist->data.x + 0.5 < this->boundary.x) return true; + if (artist->data.y + 0.5 < this->boundary.y) return true; + if (artist->data.x > this->boundary.x + this->boundary.width) return true; + if (artist->data.y > this->boundary.y + this->boundary.height) return true; + return false; + }); +} + +void QuadTreeCollisionChecker::check() { + if (this->artists_size > 0) { + auto begin = this->artists.begin(); + auto end = this->artists.end(); + for (Artist * artist : this->artists) artist->colliding = false; + for (auto it1 = begin; it1 != end; ++it1) { + auto it2 = it1; + ++it2; + for (; it2 != end; ++it2) { + this->compare(**it1, **it2); + } + } + } + for (size_t i = 0; i < 4; i++) { + if (this->subtree[i] == nullptr) continue; + this->subtree[i]->check(); + } +} + diff --git a/QuadTreeCollisionChecker.h b/QuadTreeCollisionChecker.h new file mode 100644 index 0000000..420e0b7 --- /dev/null +++ b/QuadTreeCollisionChecker.h @@ -0,0 +1,39 @@ +#pragma once + +#include +#include + +#include "Artist.h" +#include "CollisionChecker.h" +#include "Rectangle.h" + +class QuadTreeCollisionChecker : public CollisionChecker { +public: + QuadTreeCollisionChecker(Museum &); + virtual void check(); + +public: + const Rectangle & get_boundary() { return this->boundary; } + std::unique_ptr subtree[4] = { + nullptr, + nullptr, + nullptr, + nullptr, + }; + +private: + QuadTreeCollisionChecker(const QuadTreeCollisionChecker *, const Rectangle & boundary); + + const int capacity = 2; + + std::forward_list artists; + size_t artists_size = 0; + + Rectangle boundary; + + void subdivide(); + void cull(); +}; + + + diff --git a/ToggleArtistVisibilityCommand.cpp b/ToggleArtistVisibilityCommand.cpp deleted file mode 100644 index 3c5d08b..0000000 --- a/ToggleArtistVisibilityCommand.cpp +++ /dev/null @@ -1,5 +0,0 @@ -#include "ToggleArtistVisibilityCommand.h" -#include "ViewController.h" - -ToggleArtistVisibilityCommand::ToggleArtistVisibilityCommand(ViewController & c) : ControlBooleanCommand(c.draw_artists) { } - diff --git a/ToggleArtistVisibilityCommand.h b/ToggleArtistVisibilityCommand.h deleted file mode 100644 index 62df654..0000000 --- a/ToggleArtistVisibilityCommand.h +++ /dev/null @@ -1,11 +0,0 @@ -#pragma once - -#include "ControlBooleanCommand.h" - -class ViewController; - -class ToggleArtistVisibilityCommand : public ControlBooleanCommand { -public: - ToggleArtistVisibilityCommand(ViewController & c); -}; - diff --git a/ViewController.cpp b/ViewController.cpp index 3b298db..7f3fdfc 100644 --- a/ViewController.cpp +++ b/ViewController.cpp @@ -1,8 +1,9 @@ #include #include "ViewController.h" -#include "QuadTree.h" -#include "ToggleArtistVisibilityCommand.h" +#include "CollisionChecker.h" +#include "ControlBooleanCommand.h" +#include "QuadTreeCollisionChecker.h" #include "Exception.h" #include "KeyboardCode.h" #include "MouseCode.h" @@ -67,7 +68,7 @@ void ViewController::update_artists() { void ViewController::update_pathfinding() { } -void ViewController::update_quadtree_recursive(QuadTree * tree) { +void ViewController::update_quadtree_recursive(QuadTreeCollisionChecker * tree) { if (tree == nullptr) return; const Rectangle & tree_boundary = tree->get_boundary(); @@ -86,8 +87,10 @@ void ViewController::update_quadtree_recursive(QuadTree * tree) { } void ViewController::update_quadtree() { - shared_ptr tree = this->museum.collision.get_quadtree(); - this->update_quadtree_recursive(tree.get()); + shared_ptr checker = this->museum.collision.get_checker(); + auto tree = dynamic_cast(checker.get()); + if (tree == nullptr) return; + this->update_quadtree_recursive(tree); } void ViewController::ev_keydown(KeyboardCode key) { @@ -106,7 +109,7 @@ void ViewController::ev_keydown(KeyboardCode key) { break; } case KEY_A: { - ToggleArtistVisibilityCommand(*this).execute(); + ControlBooleanCommand(this->draw_artists).execute(); break; } case KEY_LEFT: { @@ -117,6 +120,14 @@ void ViewController::ev_keydown(KeyboardCode key) { TimeTravelCommand(this->museum, true).execute(); break; } + case KEY_C: { + // CycleCollisionMethodCommand(this->museum).execute(); + break; + } + case KEY_Q: { + ControlBooleanCommand(this->draw_quadtree).execute(); + break; + } default: break; } } catch (Exception & e) { diff --git a/ViewController.h b/ViewController.h index 708079b..162ae19 100644 --- a/ViewController.h +++ b/ViewController.h @@ -8,7 +8,7 @@ class View; class Museum; -class QuadTree; +class QuadTreeCollisionChecker; class ViewController { public: @@ -27,14 +27,14 @@ private: void update_artists(); void update_pathfinding(); void update_quadtree(); - void update_quadtree_recursive(QuadTree * tree); + void update_quadtree_recursive(QuadTreeCollisionChecker * tree); private: Museum & museum; View & view; const Command * cmd_base = nullptr; -public: +private: bool draw_artists = true; bool draw_pathfinding = false; bool draw_quadtree = true; diff --git a/docs/class-diag.puml b/docs/class-diag.puml index 062cf2a..8058e0a 100644 --- a/docs/class-diag.puml +++ b/docs/class-diag.puml @@ -96,19 +96,39 @@ rectangle Group_Algorithms as "Algorithms" <> { class PathfindingContext { + PathfindingContext(Museum &) } + together { class CollisionContext { + CollisionContext(Museum &) } + class CollisionChecker { + + CollisionChecker(Museum &) + + check(Artist & a, Artist & b) + } + class QuadTreeCollisionChecker { + + QuadTree(Museum &) + + QuadTree(parent : QuadTree *, boundary : Rectangle &) + } + class NaiveCollisionChecker { + } + + CollisionChecker <|-- QuadTreeCollisionChecker + CollisionChecker <|-- NaiveCollisionChecker + CollisionContext -> CollisionChecker + } } rectangle Group_Model as "Model" <> { class Museum { + people : People + canvas : Canvas + + collision : CollisionContext + + pathfinding : PathfindingContext -- + + paused : bool + update() + + skip_forward() + + skip_backward() -- - - paused : bool <<+get>> <<+set>> - jump : unsigned long -- - working : bool -- cgit v1.2.3