From 8f24d6f4d85fb9deb6faa29c2f0c4b710d73262d Mon Sep 17 00:00:00 2001
From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Thu, 8 Apr 2010 19:43:01 +0300
Subject: [PATCH] planets: Add quadtrees in use

The tree is used and kept sorted, but it is not used for anything
useful yet.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
---
 Makefile |  2 +-
 planet.c | 35 ++++++++++++++++++++++++++++++++++-
 planet.h |  7 ++++++-
 3 files changed, 41 insertions(+), 3 deletions(-)

diff --git a/Makefile b/Makefile
index 5b89e4f..35a581d 100644
--- a/Makefile
+++ b/Makefile
@@ -8,7 +8,7 @@ CC=gcc
 SPARSE=sparse
 CHECKPATCH=/usr/src/linux/scripts/checkpatch.pl
 
-PLANET_OBJS=main.o random.o vector.o planet.o camera.o
+PLANET_OBJS=main.o random.o vector.o planet.o camera.o quadtree.o
 PLANET_DEBUG_OBJS= $(patsubst %.o,%-debug.o,$(PLANET_OBJS))
 
 sdl-planet: $(PLANET_OBJS)
diff --git a/planet.c b/planet.c
index f72b1b0..bdbde37 100644
--- a/planet.c
+++ b/planet.c
@@ -34,6 +34,7 @@ void init_planet(struct planet *p)
 	p->b = get_random() % 256;
 
 	INIT_LIST_HEAD(&p->list);
+	init_quadtree(&p->tree);
 }
 
 /**
@@ -81,12 +82,17 @@ void create_planets(struct planet *p, int num, double total_mass, double radius)
 	for (i = 0; i < num; i++) {
 		new_planet = malloc(sizeof(*new_planet));
 		init_planet(new_planet);
+
 		list_add(&new_planet->list, &p->list);
+
 		setup_planet(new_planet,
 			     total_mass / num * 2 * get_random_double(),
 			     total_mass,
 			     radius);
 
+		quadtree_add(&p->tree, &new_planet->tree,
+			     planet_spatial_compare);
+
 		sum += new_planet->mass;
 	}
 }
@@ -195,15 +201,23 @@ struct planet *merge_planets(struct planet *a, struct planet *b)
 	_merge_planets(a, b);
 
 	list_del(&b->list);
+	quadtree_del(&b->tree, planet_spatial_compare);
+
 	free(b);
 	return a;
 }
 
-void move_planet(struct planet *p, const double time)
+struct planet *move_planet(struct planet *p, const double time)
 {
 	struct vector tmp;
+	struct quadtree *tree_parent;
+
 	vector_scale(&p->speed, time, &tmp);
 	vector_add(&p->pos, &tmp, &p->pos);
+
+	tree_parent = quadtree_del(&p->tree, planet_spatial_compare);
+	quadtree_add(tree_parent, &p->tree, planet_spatial_compare);
+	return tree_to_planet(tree_parent);
 }
 
 void print_planet(const struct planet *p)
@@ -211,3 +225,22 @@ void print_planet(const struct planet *p)
 	printf("pos: (%f,%f), speed: (%f,%f), mass: %f, radius %f\n",
 	       p->pos.x, p->pos.y, p->speed.x, p->speed.y, p->mass, p->radius);
 }
+
+int planet_spatial_compare(struct quadtree *ta, struct quadtree *tb)
+{
+	struct planet *a, *b;
+	int up, left;
+	a = tree_to_planet(ta);
+	b = tree_to_planet(tb);
+
+	up = b->pos.y < a->pos.y;
+	left = b->pos.x < a->pos.x;
+
+	if (up && left)
+		return 0;
+	if (up && !left)
+		return 1;
+	if (left)
+		return 2;
+	return 3;
+}
diff --git a/planet.h b/planet.h
index 4b6d3f4..22bfd07 100644
--- a/planet.h
+++ b/planet.h
@@ -7,11 +7,13 @@
 #include "list.h"
 #include "utils.h"
 #include "camera.h"
+#include "quadtree.h"
 
 struct planet {
 	struct vector speed;
 	struct vector pos;
 	struct list_head list;
+	struct quadtree tree;
 	double mass;
 	float radius;
 	unsigned char r, g, b;
@@ -19,13 +21,16 @@ struct planet {
 
 #define list_to_planet(list_head) container_of((list_head), struct planet, list)
 
+#define tree_to_planet(qt) container_of((qt), struct planet, tree)
+
 void init_planet(struct planet *p);
 void create_planets(struct planet *p, int num, double total_mass,
 		    double radius);
 void draw_planet(SDL_Surface *screen, struct planet *p, const struct camera *);
 int gravitize_planets(struct planet *a, struct planet *b, const double time);
 struct planet *merge_planets(struct planet *a, struct planet *b);
-void move_planet(struct planet *p, const double time);
+struct planet *move_planet(struct planet *p, const double time);
 void print_planet(const struct planet *p);
 
+int planet_spatial_compare(struct quadtree *a, struct quadtree *b);
 #endif
-- 
2.45.0