fix quad tree collision checker

1 files changed, 103 insertions, 0 deletions

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 <memory>
+
+#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<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();
+}
+
+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<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
+		.x = this->boundary.x,
+		.y = this->boundary.y,
+		.width = half_width,
+		.height = half_height,
+	}));
+	this->subtree[1] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
+		.x = this->boundary.x + half_width,
+		.y = this->boundary.y,
+		.width = half_width,
+		.height = half_height,
+	}));
+	this->subtree[2] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
+		.x = this->boundary.x,
+		.y = this->boundary.y + half_height,
+		.width = half_width,
+		.height = half_height,
+	}));
+	this->subtree[3] = unique_ptr<QuadTreeCollisionChecker>(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();
+	}
+}
+