fix quad tree collision checker

18 files changed, 164 insertions, 55 deletions

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<QuadTree> CollisionContext::get_quadtree() {
-	return this->quadtree;
+shared_ptr<CollisionChecker> CollisionContext::get_checker() {
+	return this->checker;
 }
 
 void CollisionContext::update() {
-	this->quadtree = std::make_shared<QuadTree>(this->museum);
+	this->checker = std::make_shared<QuadTreeCollisionChecker>(this->museum);
+	// this->checker = std::make_shared<NaiveCollisionChecker>(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 <memory>
 
-#include "QuadTree.h"
+#include "CollisionChecker.h"
 
 class Museum;
 
@@ -11,12 +11,12 @@ public:
 
 	void update();
 
-	std::shared_ptr<QuadTree> get_quadtree();
+	std::shared_ptr<CollisionChecker> get_checker();
 
 private:
 	Museum & museum;
 
 private:
-	std::shared_ptr<QuadTree> quadtree = nullptr;
+	std::shared_ptr<CollisionChecker> 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/QuadTreeCollisionChecker.cpp
index 3850e2c..0d211c0 100644
--- a/QuadTree.cpp
+++ b/QuadTreeCollisionChecker.cpp
@@ -1,11 +1,11 @@
 #include <memory>
 
-#include "QuadTree.h"
+#include "QuadTreeCollisionChecker.h"
 #include "Museum.h"
 
 using namespace std;
 
-QuadTree::QuadTree(Museum & museum) {
+QuadTreeCollisionChecker::QuadTreeCollisionChecker(Museum & museum) : CollisionChecker(museum) {
 	this->boundary = {
 		.x = 0.0,
 		.y = 0.0,
@@ -20,7 +20,7 @@ QuadTree::QuadTree(Museum & museum) {
 		this->subdivide();
 }
 
-QuadTree::QuadTree(const QuadTree * parent, const Rectangle & boundary) {
+QuadTreeCollisionChecker::QuadTreeCollisionChecker(const QuadTreeCollisionChecker * parent, const Rectangle & boundary) : CollisionChecker(parent->museum) {
 	this->boundary = boundary;
 
 	this->artists = parent->artists;
@@ -32,7 +32,7 @@ QuadTree::QuadTree(const QuadTree * parent, const Rectangle & boundary) {
 		this->subdivide();
 }
 
-void QuadTree::subdivide() {
+void QuadTreeCollisionChecker::subdivide() {
 	float half_width = this->boundary.width / 2;
 	float half_height = this->boundary.height / 2;
 
@@ -40,25 +40,25 @@ void QuadTree::subdivide() {
 	if (half_width <= 0.5) return;
 	if (half_height <= 0.5) return;
 
-	this->subtree[0] = unique_ptr<QuadTree>(new QuadTree(this, {
+	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<QuadTree>(new QuadTree(this, {
+	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<QuadTree>(new QuadTree(this, {
+	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<QuadTree>(new QuadTree(this, {
+	this->subtree[3] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
 		.x = this->boundary.x + half_width,
 		.y = this->boundary.y + half_height,
 		.width = half_width,
@@ -68,9 +68,10 @@ void QuadTree::subdivide() {
 	// 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 QuadTree::cull() {
+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;
@@ -81,3 +82,22 @@ void QuadTree::cull() {
 	});
 }
 
+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/QuadTree.h b/QuadTreeCollisionChecker.h
index 5a371d4..420e0b7 100644
--- a/QuadTree.h
+++ b/QuadTreeCollisionChecker.h
@@ -4,14 +4,17 @@
 #include <forward_list>
 
 #include "Artist.h"
+#include "CollisionChecker.h"
 #include "Rectangle.h"
 
-class QuadTree {
+class QuadTreeCollisionChecker : public CollisionChecker {
+public:
+	QuadTreeCollisionChecker(Museum &);
+	virtual void check();
+
 public:
-	QuadTree(Museum &);
-	QuadTree(const QuadTree *, const Rectangle & boundary);
 	const Rectangle & get_boundary() { return this->boundary; }
-	std::unique_ptr<QuadTree> subtree[4] = {
+	std::unique_ptr<QuadTreeCollisionChecker> subtree[4] = {
 		nullptr,
 		nullptr,
 		nullptr,
@@ -19,6 +22,8 @@ public:
 	};
 
 private:
+	QuadTreeCollisionChecker(const QuadTreeCollisionChecker *, const Rectangle & boundary);
+
 	const int capacity = 2;
 
 	std::forward_list<Artist *> artists;
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 <memory>
 
 #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<QuadTree> tree = this->museum.collision.get_quadtree();
-	this->update_quadtree_recursive(tree.get());
+	shared_ptr<CollisionChecker> checker = this->museum.collision.get_checker();
+	auto tree = dynamic_cast<QuadTreeCollisionChecker*>(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" <<group>> {
 	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" <<group>> {
 	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