planets: Firt quadtree adoption

At this moment we only add planets also in the quadtree. Nothing else
is done with the quadtree.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/Makefile b/Makefile
index 86498238846db220ad623486f042f47fe5741c8a..2c708bced0f123da01b904b2b57ae895aadc89ec 100644 (file)
--- 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 2b5c7f09217c6726b6c99c98e63fea26e7d288e7..75674f4cb1e5e16ab80ed11f9137516711ff43ab 100644 (file)
--- 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);
 }
 
 /**
@@ -76,7 +77,11 @@ 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);
+               quadtree_add(&new_planet->tree, &p->tree,
+                            planet_spatial_compare);
+
                setup_planet(new_planet,
                             total_mass / num * 2 * get_random_double(),
                             total_mass,
@@ -206,3 +211,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 4b6d3f42e4d87ec3c1f1ad08578b54dcd425b1e8..0ab556bf067badea4e80e89bf3950dacfc0b8ed3 100644 (file)
--- a/planet.h
+++ b/planet.h
@@ -7,17 +7,20 @@
 #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;
 };
 
 #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,
@@ -28,4 +31,6 @@ struct planet *merge_planets(struct planet *a, struct planet *b);
 void 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