planets: Add quadtrees in use

[sdl-planets] / planet.c

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;
+}