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>

diff --git a/Makefile b/Makefile
index 5b89e4f375832a789449d6fb6518bb17a34d08fe..35a581d64a31f57d5f17723b328d90ad3da4e5eb 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 f72b1b0087a523fe76e0f10979fe5cd8d842d7de..bdbde37dc3f587d3b4e6048e166c1eeb4c61a689 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);
 }
 
 /**
@@ -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 4b6d3f42e4d87ec3c1f1ad08578b54dcd425b1e8..22bfd070cb91f699ae8ff24ce1509594b4caaa11 100644 (file)
--- 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