implement quadtree paritioning

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<QuadTree> CollisionContext::get_quadtree() {
 }
 
 void CollisionContext::update() {
-	this->quadtree = std::make_shared<QuadTree>();
-	this->quadtree->boundary = {
-		.x = 0.0,
-		.y = 0.0,
-		.width = static_cast<float>(this->museum.canvas.data.columns),
-		.height = static_cast<float>(this->museum.canvas.data.rows),
-	};
+	this->quadtree = std::make_shared<QuadTree>(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 <memory>
+
 #include "QuadTree.h"
+#include "Museum.h"
+
+using namespace std;
+
+QuadTree::QuadTree(Museum & museum) {
+	this->boundary = {
+		.x = 0.0,
+		.y = 0.0,
+		.width = static_cast<float>(museum.canvas.data.columns),
+		.height = static_cast<float>(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<QuadTree>(new QuadTree(this, {
+		.x = this->boundary.x,
+		.y = this->boundary.y,
+		.width = half_width,
+		.height = half_height,
+	}));
+	this->subtree[1] = unique_ptr<QuadTree>(new QuadTree(this, {
+		.x = this->boundary.x + half_width,
+		.y = this->boundary.y,
+		.width = half_width,
+		.height = half_height,
+	}));
+	this->subtree[2] = unique_ptr<QuadTree>(new QuadTree(this, {
+		.x = this->boundary.x,
+		.y = this->boundary.y + half_height,
+		.width = half_width,
+		.height = half_height,
+	}));
+	this->subtree[3] = unique_ptr<QuadTree>(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<Artist *> artists;
-
-	Rectangle boundary;
+	QuadTree(Museum &);
+	QuadTree(const QuadTree *, const Rectangle & boundary);
+	const Rectangle & get_boundary() { return this->boundary; }
 	std::unique_ptr<QuadTree> subtree[4] = {
 		nullptr,
 		nullptr,
@@ -20,8 +18,16 @@ public:
 		nullptr,
 	};
 
+private:
+	const int capacity = 2;
+
+	std::forward_list<Artist *> 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());