From 90652f512e9621e0dfac497439c7c80bf113d9d5 Mon Sep 17 00:00:00 2001 From: Loek Le Blansch Date: Mon, 21 Oct 2024 17:41:38 +0200 Subject: implement quadtree paritioning --- CollisionContext.cpp | 8 +---- QuadTree.cpp | 80 +++++++++++++++++++++++++++++++++++++++++++++ QuadTree.h | 18 ++++++---- SetNeighborTileBehavior.cpp | 2 ++ ViewController.cpp | 11 ++++--- 5 files changed, 101 insertions(+), 18 deletions(-) diff --git a/CollisionContext.cpp b/CollisionContext.cpp index 648b889..e7550e5 100644 --- a/CollisionContext.cpp +++ b/CollisionContext.cpp @@ -12,12 +12,6 @@ shared_ptr CollisionContext::get_quadtree() { } void CollisionContext::update() { - this->quadtree = std::make_shared(); - this->quadtree->boundary = { - .x = 0.0, - .y = 0.0, - .width = static_cast(this->museum.canvas.data.columns), - .height = static_cast(this->museum.canvas.data.rows), - }; + this->quadtree = std::make_shared(this->museum); } diff --git a/QuadTree.cpp b/QuadTree.cpp index 54cb0af..3850e2c 100644 --- a/QuadTree.cpp +++ b/QuadTree.cpp @@ -1,3 +1,83 @@ +#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 index 6ee7a5a..5a371d4 100644 --- a/QuadTree.h +++ b/QuadTree.h @@ -8,11 +8,9 @@ class QuadTree { public: - const int capacity = 2; - - std::forward_list artists; - - Rectangle boundary; + QuadTree(Museum &); + QuadTree(const QuadTree *, const Rectangle & boundary); + const Rectangle & get_boundary() { return this->boundary; } std::unique_ptr subtree[4] = { nullptr, nullptr, @@ -20,8 +18,16 @@ public: nullptr, }; +private: + const int capacity = 2; + + std::forward_list artists; + size_t artists_size = 0; + + Rectangle boundary; + void subdivide(); - void query_range(); + void cull(); }; diff --git a/SetNeighborTileBehavior.cpp b/SetNeighborTileBehavior.cpp index d56fa0b..7b7ede7 100644 --- a/SetNeighborTileBehavior.cpp +++ b/SetNeighborTileBehavior.cpp @@ -1,6 +1,7 @@ #include "SetNeighborTileBehavior.h" #include "CreateArtistTileBehavior.h" #include "Artist.h" +#include "DeleteArtistTileBehavior.h" #include "Tile.h" using namespace std; @@ -21,6 +22,7 @@ static void update_neighbor(Tile & here, int dx, int dy) { if (neighbor == nullptr) return; neighbor->set_type(SetNeighborTileBehavior::type); + // neighbor->set_type(DeleteArtistTileBehavior::type); } void SetNeighborTileBehavior::update(Tile & tile) { diff --git a/ViewController.cpp b/ViewController.cpp index d336b9c..3b298db 100644 --- a/ViewController.cpp +++ b/ViewController.cpp @@ -70,13 +70,14 @@ void ViewController::update_pathfinding() { void ViewController::update_quadtree_recursive(QuadTree * tree) { if (tree == nullptr) return; + const Rectangle & tree_boundary = tree->get_boundary(); Rectangle rect = { - .x = tree->boundary.x * scale, - .y = tree->boundary.y * scale, - .width = tree->boundary.width * scale, - .height = tree->boundary.height * scale, + .x = tree_boundary.x * scale, + .y = tree_boundary.y * scale, + .width = tree_boundary.width * scale, + .height = tree_boundary.height * scale, }; - this->view.draw_rect(rect, { .red = 0xff, .green = 0x00, .blue = 0xff, }, 2); + this->view.draw_rect(rect, { .red = 0xff, .green = 0x00, .blue = 0xff, }, 1); this->update_quadtree_recursive(tree->subtree[0].get()); this->update_quadtree_recursive(tree->subtree[1].get()); -- cgit v1.2.3