add stats, incomplete..

diff --git a/main.c b/main.c
index be927c7ae1518cea769236b6f5f93c19fcae4f28..5bf1f4f3f28628c61daaa26978fa8353a4b87b93 100644 (file)
--- a/main.c
+++ b/main.c
@@ -297,10 +297,12 @@ static void loop(SDL_Surface *screen, int num_of_planets, double total_mass,
                        last_fps_time = ticks;
                }
 
-               printf("  \rFrames/s: %.2f, steps/s: %.2f, planets: %d"
-                      ", scale %.2f, zoom %.2f, step %ld, visible %d",
+               printf("  \rfps: %.2f, steps/s: %.2f, planets: %d"
+                      ", scale %.2f, zoom %.2f, step %ld, visible %d,"
+                      " depth %ld, c:%ld",
                       last_fps, last_sps, planets, status.time_scale,
-                      camera.zoom, step_count, visible_planets);
+                      camera.zoom, step_count, visible_planets,
+                      planet_root->tree.depth, planet_root->tree.children);
                fflush(stdout);
 
 

diff --git a/planet.c b/planet.c
index da83d3a1d491762fb1ae8cbe0196bbae10fd9e06..a51d3cb0f2f39b9dda1a2a15b7a1b409eba9e5c8 100644 (file)
--- a/planet.c
+++ b/planet.c
@@ -214,6 +214,7 @@ struct planet *move_planet(struct planet *p, const double time)
 
        vector_scale(&p->speed, time, &tmp);
        vector_add(&p->pos, &tmp, &p->pos);
+       vector_scale(&p->speed, pow(0.99, time), &p->speed);
 
        tree_parent = quadtree_del(&p->tree, planet_spatial_compare);
        quadtree_add(tree_parent, &p->tree, planet_spatial_compare);

diff --git a/quadtree.c b/quadtree.c
index 7d9273c363d5626dc95b7bcf6245506281efd2c0..eb311babf00afe296edbcccddcc9960ec4ec15f1 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -2,6 +2,7 @@
 #include <stdlib.h>
 
 #include "quadtree.h"
+#include "utils.h"
 
 #ifdef DEBUG
 #define debug 1
@@ -18,6 +19,8 @@ static void trap(void )
 static void validate_subtree(const struct quadtree *node)
 {
        int i;
+       long int children;
+       children = 0;
 
        for (i = 0; i < 4; i++) {
                if (!node->child[i])
@@ -29,6 +32,7 @@ static void validate_subtree(const struct quadtree *node)
                               __func__, __LINE__, i, node);
                        trap();
                }
+
                if (node->parent) {
                        if (node->child[i] == node->parent) {
                                printf("%s:%d Fatal! Tree loop detected "
@@ -38,8 +42,51 @@ static void validate_subtree(const struct quadtree *node)
                        }
                }
 
+               children += node->child[i] + 1;
+
                validate_subtree(node->child[i]);
        }
+
+       if (node->children < 0) {
+               printf("%s:%d Tree statistics inconsistency detected! "
+                      "Negative child count: %ld\n",
+                      __func__, __LINE__, node->children);
+       }
+
+       if (node->depth < 0) {
+               printf("%s:%d Tree statistics inconsistency detected! "
+                      "Negative depth: %ld\n",
+                      __func__, __LINE__, node->depth);
+       }
+
+       if (node->children != children) {
+               printf("%s:%d Tree statistics inconsistency detected! "
+                      "child count mismatch. Expected %ld, got %ld\n",
+                      __func__, __LINE__, children, node->children);
+               trap();
+       }
+
+       for (i = 0; i < 4 && node->children; i++) {
+               if (!node->child[i])
+                       continue;
+
+               if (node->depth == node->child[i]->depth + 1)
+                       break;
+
+               if (node->child[i]->depth > node->depth) {
+                       printf("%s:%d Tree statistics inconsistency detected! "
+                              "child depth mismatch %ld > %ld\n",
+                              __func__, __LINE__, node->child[i]->depth,
+                              node->depth);
+               }
+       }
+
+       if (i == 4) {
+               printf("%s:%d Tree statistics inconsistency detected! "
+                      "child depth mismatch.",
+                      __func__, __LINE__);
+               trap();
+       }
 }
 
 static void validate_tree(const struct quadtree *node)
@@ -87,8 +134,14 @@ struct quadtree *quadtree_add(struct quadtree *parent,
                return 0;
        }
 
-       if (parent->child[ret])
-               return quadtree_add(parent->child[ret], new, compare);
+       parent->children++;
+
+       if (parent->child[ret]) {
+               quadtree_add(parent->child[ret], new, compare);
+               parent->depth = MAX(parent->depth,
+                                   parent->child[ret]->depth + 1);
+               return new;
+       }
 
        parent->child[ret] = new;
        new->parent = parent;
@@ -127,6 +180,10 @@ _quadtree_reposition_reqursively(struct quadtree *root,
                node->child[i] = 0;
        }
 
+       /* There are no children left, reset stats */
+       node->depth = 0;
+       node->children = 0;
+
        /* Then remove this node under the new root. */
        quadtree_add(root, node, compare);
 }
@@ -142,7 +199,7 @@ struct quadtree *quadtree_del(struct quadtree *node,
                              int (*compare)(struct quadtree *a,
                                             struct quadtree *b))
 {
-       struct quadtree *parent = 0;
+       struct quadtree *parent = 0, *tmp;
        int i;
 
        /*
@@ -200,9 +257,25 @@ struct quadtree *quadtree_del(struct quadtree *node,
                node->child[i] = 0;
        }
 
+       /* Fix parent stats */
+       tmp = parent;
+       while (tmp) {
+               tmp->children -= node->children;
+               tmp->depth = 0;
+               for (i = 0; i < 4; i++) {
+                       if (tmp->child[i])
+                               tmp->depth = MAX(tmp->depth,
+                                                tmp->child[i]->depth + 1);
+               }
+               tmp = tmp->parent;
+       }
+
        parent = quadtree_find_parent(node);
        node->parent = 0;
 
+       node->children = 0;
+       node->depth = 0;
+
        validate_tree(parent);
        return parent;
 }

diff --git a/quadtree.h b/quadtree.h
index 23b79cebd7595d51875618fadedc42129fd0d5b8..3589b5e1da6a4ab43b3a4f5f3c5c6c6e5d4fcc19 100644 (file)
--- a/quadtree.h
+++ b/quadtree.h
@@ -1,18 +1,20 @@
 #ifndef _QUADTREE_H_
 #define _QUADTREE_H_
 
+#include <string.h>
+
 struct quadtree {
        struct quadtree *child[4];
        struct quadtree *parent;
+
+       /* statistics */
+       long int children;      /* The total number of children */
+       long int depth;         /* The deepest subtree branch */
 };
 
 static inline void init_quadtree(struct quadtree *t)
 {
-       int i;
-
-       for (i = 0; i < 4; i++)
-               t->child[i] = 0;
-       t->parent = 0;
+       memset(t, 0, sizeof(*t));
 }
 
 #define QUADTREE_UPLEFT                0x1