planets: Add support for spatial search from quadtree

This can be used to for example draw only visible planets on the
screen.

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

diff --git a/planet.c b/planet.c
index bdbde37dc3f587d3b4e6048e166c1eeb4c61a689..da83d3a1d491762fb1ae8cbe0196bbae10fd9e06 100644 (file)
--- a/planet.c
+++ b/planet.c
@@ -244,3 +244,45 @@ int planet_spatial_compare(struct quadtree *ta, struct quadtree *tb)
                return 2;
        return 3;
 }
                return 2;
        return 3;
 }

+
+int planet_search_rectangular(struct quadtree *node,
+                             struct quadtree_iterator *itr)
+{
+       struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
+       struct planet *p = tree_to_planet(node);
+       int direction = 0, i;
+       int up = 0, left = 0, right = 0, down = 0;
+
+       for (i = 0; i < 2; i++) {
+               if (it->limit[i].x < p->pos.x)
+                       left = 1;
+               else
+                       right = 1;
+               if (it->limit[i].y < p->pos.y)
+                       up = 1;
+               else
+                       down = 1;
+       }
+
+       if (left && up)
+               direction |= QUADTREE_UPLEFT;
+       if (right && up)
+               direction |= QUADTREE_UPRIGHT;
+       if (left && down)
+               direction |= QUADTREE_DOWNLEFT;
+       if (right && down)
+               direction |= QUADTREE_DOWNRIGHT;
+       if (direction == (QUADTREE_UPLEFT | QUADTREE_UPRIGHT |
+                         QUADTREE_DOWNLEFT | QUADTREE_DOWNRIGHT))
+               direction |= QUADTREE_SELF;
+
+       return direction;
+}
+
+void planet_draw_iterator(struct quadtree *node, struct quadtree_iterator *it)
+{
+       struct planet *p = tree_to_planet(node);
+       struct planet_search_iterator *i = qt_itr_to_planet_itr(it);
+
+       draw_planet(i->screen, p, i->cam);
+}

diff --git a/planet.h b/planet.h
index 22bfd070cb91f699ae8ff24ce1509594b4caaa11..0673c87bb6267ec84c39db7573835e95c18a60bc 100644 (file)
--- a/planet.h
+++ b/planet.h
@@ -19,10 +19,20 @@ struct planet {
        unsigned char r, g, b;
 };
 
        unsigned char r, g, b;
 };
 

+struct planet_search_iterator {
+       struct quadtree_iterator qt_iterator;
+       struct vector limit[2];
+       struct camera *cam;
+       SDL_Surface *screen;
+};
+

 #define list_to_planet(list_head) container_of((list_head), struct planet, list)
 
 #define tree_to_planet(qt) container_of((qt), struct planet, tree)
 
 #define list_to_planet(list_head) container_of((list_head), struct planet, list)
 
 #define tree_to_planet(qt) container_of((qt), struct planet, tree)
 

+#define qt_itr_to_planet_itr(qt)                                       \
+       container_of((qt), struct planet_search_iterator, qt_iterator)
+

 void init_planet(struct planet *p);
 void create_planets(struct planet *p, int num, double total_mass,
                    double radius);
 void init_planet(struct planet *p);
 void create_planets(struct planet *p, int num, double total_mass,
                    double radius);


@@ -33,4 +43,8 @@ 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);
 void print_planet(const struct planet *p);
 
 int planet_spatial_compare(struct quadtree *a, struct quadtree *b);

+int planet_search_rectangular(struct quadtree *node,
+                             struct quadtree_iterator *itr);
+void planet_draw_iterator(struct quadtree *node, struct quadtree_iterator *it);
+

 #endif
 #endif