Merge branch 'master' into HEAD

Conflicts:
	main.c
	planet.c

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

diff --cc main.c
index dfec1a1a33eb7e4896576a587f631fed7dd584e5,b42f2345d5404ae0e54cc579d6ae4bc39a006f6c..afb9d86ee7f2a6904ce7c1f3ed4e347dfca5334a
--- 1/main.c
--- 2/main.c
+++ b/main.c
@@@ -220,18 -221,26 +221,17 @@@ static void loop(SDL_Surface *screen, i
        ticks = SDL_GetTicks();
        while (1) {
                planets = 0;
 +              gravitations = 0;
 +              optimizations = 0;
  
 -              if (status.time_scale > 0) {
 -                      list_for_each_entry(pl1, &planet->list, list) {
 -                              pl2 = list_to_planet(pl1->list.next);
 -                              list_for_each_entry_from(pl2, &planet->list,
 -                                                       list) {
 -                                      struct planet *ptmp;
 -                                      if (!gravitize_planets(pl1, pl2,
 -                                                             step_time))
 -                                              continue;
 -
 -                                      ptmp = list_to_planet(pl2->list.prev);
 -                                      merge_planets(pl1, pl2);
 -                                      pl2 = ptmp;
 -                              }
 -
 -                              planet_root = move_planet(pl1, step_time);
 -                              planets++;
 -                      }
 +              gravitize_planet_tree(planet_root, step_time);
 +
 +              planet_root = prune_planet_tree(planet_root);
 +
 +              list_for_each_entry(pl1, &planet_root->list, list) {
 +                      planet_root = move_planet(pl1, step_time);
 +                      planets++;
                }
- 
                move_camera(&camera, true_time);
  
                if (poll_events(&status, true_time))

diff --cc planet.c
index 5b227c0f62e7a11b8ca44b2a4b24c5d855c2bd0c,24b2d21da259f90d280ee6fd76bfb475d23221ee..b779baef0b1d7a792953f263b82ac4872922e456
--- 1/planet.c
--- 2/planet.c
+++ b/planet.c
@@@ -211,12 -204,7 +211,12 @@@ int gravitize_planet_with_planet(struc
        struct vector distance, sum;
        double dist, f, acc;
  
-       vector_sub(&a->pos, &b->pos, &distance);
 +      if (a->to_be_deleted || b->to_be_deleted)
 +              return 0;
 +
 +      gravitations++;
 +
+       vector_sub(&a->tree.pos, &b->tree.pos, &distance);
  
        dist = vector_abs(&distance);
  
@@@ -229,31 -216,9 +229,31 @@@
  
        f = a->mass * b->mass / (dist * dist) * time;
  
 -      acc = f / b->mass;
 +      acc = f / a->mass;
        vector_scale(&distance, acc, &sum);
 -      vector_add(&b->speed, &sum, &b->speed);
 +      vector_sub(&a->speed, &sum, &a->speed);
 +
 +      return 0;
 +}
 +
 +int gravitize_planet_with_tree(struct planet *a, struct planet *b,
 +                             const double time)
 +{
 +      struct vector distance, sum;
 +      double dist, f, acc;
 +
 +      if (a->to_be_deleted || b->to_be_deleted)
 +              return 0;
 +
 +      gravitations++;
 +
-       vector_sub(&a->pos, &b->pos, &distance);
++      vector_sub(&a->tree.pos, &b->tree.pos, &distance);
 +
 +      dist = vector_abs(&distance);
 +
 +      vector_div(&distance, dist, &distance);
 +
 +      f = a->mass * b->tree_mass / (dist * dist) * time;
  
        acc = f / a->mass;
        vector_scale(&distance, acc, &sum);
@@@ -301,55 -271,6 +307,55 @@@ struct planet *merge_planets(struct pla
        return a;
  }
  
-       vector_sub(&p->pos, &pt->pos, &vect);
 +static void gravitize_planet(struct planet *p, struct planet *pt, double time)
 +{
 +      struct vector vect;
 +      float dist;
 +      int i;
 +
++      vector_sub(&p->tree.pos, &pt->tree.pos, &vect);
 +      dist = vector_abs(&vect);
 +
 +      if (p != pt)
 +              gravitize_planet_with_planet(p, pt, time);
 +
 +      if (dist > pt->tree_area * 2) {
 +              /*
 +               * OK, the node is far enough. We can approximate the
 +               * entire tree as a single entity.
 +               */
 +              optimizations += pt->tree.children;
 +              gravitize_planet_with_tree(p, pt, time);
 +              return;
 +      }
 +
 +      /* Otherwise, gravitize with each of the child */
 +      for (i = 0; i < 4; i++) {
 +              if (!pt->tree.child[i])
 +                      continue;
 +
 +              gravitize_planet(p, tree_to_planet(pt->tree.child[i]),
 +                               time);
 +      }
 +}
 +
 +void gravitize_planet_tree(struct planet *p, double time)
 +{
 +      int i;
 +
 +      for (i = 0; i < 4; i++) {
 +              if (!p->tree.child[i])
 +                      continue;
 +
 +              gravitize_planet_tree(tree_to_planet(p->tree.child[i]),
 +                                    time);
 +      }
 +
 +      gravitize_planet(p,
 +                       tree_to_planet(quadtree_find_parent(&p->tree)),
 +                       time);
 +}
 +
  static int planet_search_when_moving(struct quadtree *node,
                                     struct quadtree_iterator *itr)
  {

diff --cc planet.h
Simple merge

diff --cc quadtree.c
Simple merge

diff --cc quadtree.h
index 30cfd1461c6f700b7e30bb1c172e0a239c04e2c5,619a67574fc045f69ed3f7ea959f42d2e1046e7a..b5922dbd3bfc8acbd8a199f087dfcd3eeaf12711
--- 1/quadtree.h
--- 2/quadtree.h
+++ b/quadtree.h
@@@ -3,28 -3,20 +3,24 @@@
  
  #include <string.h>
  
 +#include "list.h"
  #include "utils.h"
+ #include "vector.h"
  
  struct quadtree {
+       struct vector pos;
        struct quadtree *child[4];
        struct quadtree *parent;
 +      struct list_head list;  /* This list is used when balancing the tree */
  
        /* statistics */
        long int children;      /* The total number of children */
        long int depth;         /* The deepest subtree branch */
  };
  
 +#define list_to_tree(list_head) container_of((list_head), struct quadtree, list)
 +
  struct quadtree_ops {
-       /*
-        * Comparison function that is needed to find out the correct
-        * location for a node in the tree
-        */
-       int (*compare)(struct quadtree *a, struct quadtree *b);
- 
        /*
         * Calculates required statistical information for a node
         */