WIP quadtree visualization scaffolding

15 files changed, 155 insertions, 27 deletions

diff --git a/Artist.cpp b/Artist.cpp
index c73e695..76e0ca9 100644
--- a/Artist.cpp
+++ b/Artist.cpp
@@ -12,6 +12,7 @@ Artist::Artist(Museum & museum, ArtistData data) : museum(museum) {
 void Artist::update() {
 	this->update_edge_collision();
 	this->update_movement();
+	this->update_color();
 }
 
 void Artist::update_edge_collision() {
@@ -27,6 +28,11 @@ 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;
 
@@ -37,3 +43,22 @@ void Artist::update_movement() {
 	if (abs(int(last_y) - int(this->data.y)) > 0) this->step = true;
 }
 
+void Artist::update_color() {
+	// waiting color
+	if (this->data.waiting > 0) {
+		this->color = {
+			.red = 0xff,
+			.green = 0x00,
+			.blue = 0x00,
+		};
+		return;
+	}
+
+	// default color
+	this->color = {
+		.red = 0x00,
+		.green = 0x00,
+		.blue = 0x00,
+	};
+}
+
diff --git a/Artist.h b/Artist.h
index 49d0393..b880d5e 100644
--- a/Artist.h
+++ b/Artist.h
@@ -15,6 +15,7 @@ public:
 private:
 	void update_movement();
 	void update_edge_collision();
+	void update_color();
 
 public:
 	ArtistData data;
diff --git a/ArtistData.h b/ArtistData.h
index 1c3c88c..ab1e37c 100644
--- a/ArtistData.h
+++ b/ArtistData.h
@@ -5,5 +5,6 @@ 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 b1b39b8..897495e 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -48,6 +48,8 @@ add_executable(main
 	ToggleArtistVisibilityCommand.cpp
 	StepTileCommand.cpp
 	TimeTravelCommand.cpp
+	CollisionContext.cpp
+	QuadTree.cpp
 )
 
 target_link_libraries(main
diff --git a/CollisionContext.cpp b/CollisionContext.cpp
new file mode 100644
index 0000000..648b889
--- /dev/null
+++ b/CollisionContext.cpp
@@ -0,0 +1,23 @@
+#include <memory>
+
+#include "CollisionContext.h"
+#include "Museum.h"
+
+using namespace std;
+
+CollisionContext::CollisionContext(Museum & m) : museum(m) {}
+
+shared_ptr<QuadTree> CollisionContext::get_quadtree() {
+	return this->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),
+	};
+}
+
diff --git a/CollisionContext.h b/CollisionContext.h
new file mode 100644
index 0000000..3cce4d7
--- /dev/null
+++ b/CollisionContext.h
@@ -0,0 +1,22 @@
+#pragma once
+#include <memory>
+
+#include "QuadTree.h"
+
+class Museum;
+
+class CollisionContext {
+public:
+	CollisionContext(Museum &);
+
+	void update();
+
+	std::shared_ptr<QuadTree> get_quadtree();
+
+private:
+	Museum & museum;
+
+private:
+	std::shared_ptr<QuadTree> quadtree = nullptr;
+};
+
diff --git a/Museum.cpp b/Museum.cpp
index f6b8977..fccb0db 100644
--- a/Museum.cpp
+++ b/Museum.cpp
@@ -2,7 +2,7 @@
 
 using namespace std;
 
-Museum::Museum() : people(*this), canvas(*this) {
+Museum::Museum() : people(*this), canvas(*this), collision(*this) {
 	this->worker = new std::thread(&Museum::work, this);
 }
 
@@ -18,6 +18,7 @@ Museum::~Museum() {
 void Museum::update() {
 	this->people.update();
 	this->canvas.update();
+	this->collision.update();
 	this->tick++;
 }
 
diff --git a/Museum.h b/Museum.h
index ae7e71e..09583d9 100644
--- a/Museum.h
+++ b/Museum.h
@@ -7,6 +7,7 @@ using namespace std::chrono_literals;
 
 #include "People.h"
 #include "Canvas.h"
+#include "CollisionContext.h"
 
 class Museum {
 public:
@@ -16,6 +17,7 @@ public:
 public:
 	People people;
 	Canvas canvas;
+	CollisionContext collision;
 
 public:
 	void set_pause(bool paused);
diff --git a/QuadTree.cpp b/QuadTree.cpp
new file mode 100644
index 0000000..54cb0af
--- /dev/null
+++ b/QuadTree.cpp
@@ -0,0 +1,3 @@
+#include "QuadTree.h"
+
+
diff --git a/QuadTree.h b/QuadTree.h
new file mode 100644
index 0000000..6ee7a5a
--- /dev/null
+++ b/QuadTree.h
@@ -0,0 +1,28 @@
+#pragma once
+
+#include <memory>
+#include <forward_list>
+
+#include "Artist.h"
+#include "Rectangle.h"
+
+class QuadTree {
+public:
+	const int capacity = 2;
+
+	std::forward_list<Artist *> artists;
+
+	Rectangle boundary;
+	std::unique_ptr<QuadTree> subtree[4] = {
+		nullptr,
+		nullptr,
+		nullptr,
+		nullptr,
+	};
+
+	void subdivide();
+	void query_range();
+};
+
+
+
diff --git a/Rectangle.h b/Rectangle.h
index a3d0a0d..a8d523b 100644
--- a/Rectangle.h
+++ b/Rectangle.h
@@ -1,9 +1,9 @@
 #pragma once
 
 typedef struct {
-	unsigned int x;
-	unsigned int y;
-	unsigned int width;
-	unsigned int height;
+	float x;
+	float y;
+	float width;
+	float height;
 } Rectangle;
 
diff --git a/View.cpp b/View.cpp
index 05b823c..adf719b 100644
--- a/View.cpp
+++ b/View.cpp
@@ -31,7 +31,6 @@ void View::work() {
 				continue;
 			}
 			if (e.type == SDL_EVENT_KEY_DOWN) {
-				if (e.key.repeat) continue;
 				this->controller.ev_keydown(static_cast<KeyboardCode>(e.key.scancode));
 			}
 			if (e.type == SDL_EVENT_MOUSE_BUTTON_DOWN) {
@@ -93,12 +92,7 @@ void View::draw_end() {
 
 void View::fill_rect(Rectangle r, Color c) {
 	SDL_SetRenderDrawColor(this->renderer, c.red, c.green, c.blue, 255);
-	SDL_FRect rect = {
-		.x = static_cast<float>(r.x),
-		.y = static_cast<float>(r.y),
-		.w = static_cast<float>(r.width),
-		.h = static_cast<float>(r.height),
-	};
+	SDL_FRect rect = { .x = r.x, .y = r.y, .w = r.width, .h = r.height, };
 	SDL_RenderFillRect(this->renderer, &rect);
 }
 
diff --git a/ViewController.cpp b/ViewController.cpp
index d64ec35..d336b9c 100644
--- a/ViewController.cpp
+++ b/ViewController.cpp
@@ -1,4 +1,7 @@
+#include <memory>
+
 #include "ViewController.h"
+#include "QuadTree.h"
 #include "ToggleArtistVisibilityCommand.h"
 #include "Exception.h"
 #include "KeyboardCode.h"
@@ -10,6 +13,8 @@
 #include "View.h"
 #include "Museum.h"
 
+using namespace std;
+
 ViewController::ViewController(Museum & m, View & v) : museum(m), view(v) {
 }
 
@@ -36,10 +41,10 @@ void ViewController::update_tiles() {
 		for (unsigned x = 0; x < this->museum.canvas.data.columns; x++) {
 			Tile & tile = this->museum.canvas.get_tile(x, y);
 			Rectangle rect = {
-				.x = x * scale,
-				.y = y * scale,
-				.width = scale - line_width,
-				.height = scale - line_width,
+				.x = static_cast<float>(x * scale),
+				.y = static_cast<float>(y * scale),
+				.width = static_cast<float>(scale - line_width),
+				.height = static_cast<float>(scale - line_width),
 			};
 			this->view.fill_rect(rect, tile.color);
 		}
@@ -50,10 +55,10 @@ void ViewController::update_artists() {
 	People & people = this->museum.people;
 	for (Artist * artist : people.get_artists()) {
 		Rectangle rect = {
-			.x = static_cast<unsigned int>(artist->data.x * scale),
-			.y = static_cast<unsigned int>(artist->data.y * scale),
-			.width = artist_size,
-			.height = artist_size,
+			.x = static_cast<float>(artist->data.x * scale),
+			.y = static_cast<float>(artist->data.y * scale),
+			.width = static_cast<float>(artist_size),
+			.height = static_cast<float>(artist_size),
 		};
 		this->view.fill_rect(rect, artist->color);
 	}
@@ -62,7 +67,26 @@ void ViewController::update_artists() {
 void ViewController::update_pathfinding() {
 }
 
+void ViewController::update_quadtree_recursive(QuadTree * tree) {
+	if (tree == nullptr) return;
+
+	Rectangle rect = {
+		.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->update_quadtree_recursive(tree->subtree[0].get());
+	this->update_quadtree_recursive(tree->subtree[1].get());
+	this->update_quadtree_recursive(tree->subtree[2].get());
+	this->update_quadtree_recursive(tree->subtree[3].get());
+}
+
 void ViewController::update_quadtree() {
+	shared_ptr<QuadTree> tree = this->museum.collision.get_quadtree();
+	this->update_quadtree_recursive(tree.get());
 }
 
 void ViewController::ev_keydown(KeyboardCode key) {
diff --git a/ViewController.h b/ViewController.h
index bccacd0..fb15fde 100644
--- a/ViewController.h
+++ b/ViewController.h
@@ -8,6 +8,7 @@
 
 class View;
 class Museum;
+class QuadTree;
 
 class ViewController {
 public:
@@ -30,6 +31,7 @@ private:
 	void update_artists();
 	void update_pathfinding();
 	void update_quadtree();
+	void update_quadtree_recursive(QuadTree * tree);
 
 private:
 	Museum & museum;
@@ -38,7 +40,7 @@ private:
 
 	bool draw_artists = true;
 	bool draw_pathfinding = false;
-	bool draw_quadtree = false;
+	bool draw_quadtree = true;
 	
 private:
 	unsigned int scale = 16;
diff --git a/docs/class-diag.puml b/docs/class-diag.puml
index 273e9f1..062cf2a 100644
--- a/docs/class-diag.puml
+++ b/docs/class-diag.puml
@@ -93,11 +93,11 @@ rectangle Group_ParsingDeserialization as "Parsing & deserialization" <<group>>
 }
 
 rectangle Group_Algorithms as "Algorithms" <<group>> {
-	class Pathfinding {
-		+ Pathfinding(Museum &)
+	class PathfindingContext {
+		+ PathfindingContext(Museum &)
 	}
-	class Collision {
-		+ Collision(Museum &)
+	class CollisionContext {
+		+ CollisionContext(Museum &)
 	}
 
 }
@@ -360,8 +360,8 @@ rectangle Group_Commands as "Commands" <<group>> {
 Parser .l> FileReader
 MuseumDeserializer .l> Museum
 
-Museum --> Pathfinding
-Museum --> Collision
+Museum --> PathfindingContext
+Museum --> CollisionContext
 
 ViewController -[norank]> Command