A lot of fixes here and there

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

diff --git a/planet.c b/planet.c
index b779baef0b1d7a792953f263b82ac4872922e456..e0b8938fcc8d361d57f02c2e45069fdfc0774a12 100644 (file)
--- a/planet.c
+++ b/planet.c
@@ -7,7 +7,7 @@
 struct quadtree_ops planet_ops;
 int gravitations, optimizations;
 
-static int draw_lines = 0;
+static int draw_lines = 1;
 static int draw_tree_area = 0;
 
 static void putpixel(struct SDL_Surface *screen, const int x, const int y,
@@ -277,8 +277,8 @@ static void _merge_planets(struct planet *a, struct planet *b)
        vector_add(&pa, &pb, &p);
        mass = a->mass + b->mass;
 
-       if (a->mass < b->mass)
-               a->tree.pos = b->tree.pos;
+       //if (a->mass < b->mass)
+       //a->tree.pos = b->tree.pos;
 
        a->r = (a->r * a->mass + b->r * b->mass) / mass;
        a->g = (a->g * a->mass + b->g * b->mass) / mass;
@@ -392,12 +392,15 @@ static int planet_search_when_moving(struct quadtree *node,
 void planet_move_iterator(struct quadtree *node, struct quadtree_iterator *it)
 {
        struct quadtree *parent;
-
+       struct planet_search_iterator *itr = qt_itr_to_planet_itr(it);
        if (node == it->head)
                return;
 
+/*
        parent = quadtree_del(node, &planet_ops);
        quadtree_add(parent, node, &planet_ops);
+*/
+       itr->modify++;
 }
 
 struct planet *move_planet(struct planet *p, const double time)
@@ -408,6 +411,7 @@ struct planet *move_planet(struct planet *p, const double time)
        struct planet_search_iterator it;
 
        int modify = 0;
+       it.modify = 0;
 
        vector_scale(&p->speed, time, &tmp);
        vector_add(&p->tree.pos, &tmp, &new_pos);
@@ -430,6 +434,8 @@ struct planet *move_planet(struct planet *p, const double time)
                        continue;
                }
 
+               printf("\nMove node %p\n", &p->tree);
+
                tree_parent = quadtree_del(&p->tree, &planet_ops);
                p->tree.pos = new_pos;
                quadtree_add(tree_parent, &p->tree, &planet_ops);
@@ -448,9 +454,19 @@ struct planet *move_planet(struct planet *p, const double time)
                it.qt_iterator.callback = planet_move_iterator;
                walk_quadtree(&it.qt_iterator);
        }
-       p->tree.pos = new_pos;
 
-       return tree_to_planet(quadtree_find_parent(&p->tree));
+       if (it.modify) {  
+               tree_parent = quadtree_del(&p->tree, &planet_ops);
+               p->tree.pos = new_pos;
+               quadtree_add(tree_parent, &p->tree, &planet_ops);
+               goto out;
+       }
+
+       p->tree.pos = new_pos;
+       tree_parent = tree_to_planet(quadtree_find_parent(&p->tree));
+out:
+       quadtree_validate_tree(&p->tree);
+       return tree_parent;
 }
 
 struct planet *prune_planet_tree(struct planet *p)
@@ -484,6 +500,7 @@ struct planet *prune_planet_tree(struct planet *p)
 
        if (p->to_be_deleted) {
                list_del(&p->list);
+               printf("Permanently removing node %p\n", &p->tree);
                tree_parent = quadtree_del(&p->tree, &planet_ops);
                free(p);
                return tree_to_planet(tree_parent);

diff --git a/planet.h b/planet.h
index 9ca44083a8a6b644662038ff38debe51bb1dde9d..85ed98e20c06ad3800bc4637515fa0d26349283d 100644 (file)
--- a/planet.h
+++ b/planet.h
@@ -28,6 +28,7 @@ struct planet_search_iterator {
        struct vector limit[2];
        struct camera *cam;
        SDL_Surface *screen;
+       int modify;
 };
 
 extern int gravitations, optimizations;

diff --git a/quadtree.c b/quadtree.c
index d1d9c8a481811b1c896c6a18c7623fa552cc91ff..721435dbc3a0fb65732aef63eff22970f38b28b4 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -3,23 +3,40 @@
 
 #include "quadtree.h"
 
-#ifdef DEBUG
-#define debug 1
-#else
-#define debug 0
-#endif
-
 static void trap(void)
 {
        if (debug) {
                printf("Trapped, use debugger to get backtrace\n");
+               fflush(stdout);
                exit(1);
        }
 }
 
+static int quadtree_compare_coord(const struct vector *a,
+                               const struct vector *b)
+{
+       int up, left;
+
+       up = b->y < a->y;
+       left = b->x < a->x;
+
+       if (up && left)
+               return 0;
+       if (up && !left)
+               return 1;
+       if (left)
+               return 2;
+       return 3;
+}
+
+static int quadtree_compare(const struct quadtree *a, const struct quadtree *b)
+{
+       return quadtree_compare_coord(&a->pos, &b->pos);
+}
+
 static void validate_subtree(const struct quadtree *node)
 {
-       int i;
+       int i, dir;
        long int children;
        children = 0;
 
@@ -52,6 +69,22 @@ static void validate_subtree(const struct quadtree *node)
                        }
                }
 
+               dir = quadtree_compare(node, node->child[i]);
+
+               if (dir != i) {
+                       printf("%s:%d Fatal! Spatial inconsistency detected "
+                               "at child %d in node %p\n"
+                               "parent: (%f %f), child (%f %f), "
+                               "dir %d != %d\n",
+                               __func__, __LINE__, i, node,
+                               node->pos.x, node->pos.y,
+                               node->child[i]->pos.x, node->child[i]->pos.y,
+                               dir, i);
+                       fflush(stdout);
+                       trap();
+               }
+                      
+
                children += node->child[i]->children + 1;
 
                validate_subtree(node->child[i]);
@@ -110,8 +143,9 @@ static void validate_tree(const struct quadtree *node)
                        break;
 
        if (i == 4) {
-               printf("%s:%d Tree inconsistency detected! Wrong parent\n",
-                      __func__, __LINE__);
+               printf("%s:%d Tree inconsistency detected! "
+                       "Wrong parent %p for node %p\n",
+                       __func__, __LINE__, node->parent, node);
                fflush(stdout);
                trap();
        }
@@ -119,25 +153,9 @@ static void validate_tree(const struct quadtree *node)
        validate_tree(node->parent);
 }
 
-static int quadtree_compare_coord(struct vector *a, struct vector *b)
-{
-       int up, left;
-
-       up = b->y < a->y;
-       left = b->x < a->x;
-
-       if (up && left)
-               return 0;
-       if (up && !left)
-               return 1;
-       if (left)
-               return 2;
-       return 3;
-}
-
-static int quadtree_compare(struct quadtree *a, struct quadtree *b)
+void _quadtree_validate_tree(const struct quadtree *node)
 {
-       return quadtree_compare_coord(&a->pos, &b->pos);
+       validate_tree(node);
 }
 
 static struct quadtree *_quadtree_add(struct quadtree *parent,
@@ -259,16 +277,22 @@ static double quadtree_get_max_dimension(struct quadtree *node, int direction)
                return max_by_dir(a, b, direction);
        }
 
-       if (ch1)
-               return quadtree_get_max_dimension(ch1, direction);
-       if (ch2)
-               return quadtree_get_max_dimension(ch2, direction);
+       if (ch1) {
+               a = quadtree_get_max_dimension(ch1, direction);
+               b = maxv_by_dir(ch1, direction);
+               return max_by_dir(a, b, direction);
+       }
+       if (ch2) {
+               a = quadtree_get_max_dimension(ch2, direction);
+               b = maxv_by_dir(ch2, direction);
+               return max_by_dir(a, b, direction);
+       }
 
        return maxv_by_dir(node, direction);
 }
 
 /*
- * Stores the upper right and lower left corner coordinates to the
+ * Stores the lower right and upper left corner coordinates to the
  * corner vectors
  */
 static void quadtree_get_tree_dimensions(struct quadtree *node,
@@ -278,6 +302,18 @@ static void quadtree_get_tree_dimensions(struct quadtree *node,
        corner[0].x = quadtree_get_max_dimension(node, 1);
        corner[1].y = quadtree_get_max_dimension(node, 0);
        corner[1].x = quadtree_get_max_dimension(node, 3);
+
+       if (debug) {
+               printf("Initial Search rectangle (%f %f) (%f %f), (%f %f)\n",
+                       corner[0].x, corner[0].y,
+                       corner[1].x, corner[1].y,
+                       node->pos.x, node->pos.y);
+               fflush(stdout);
+       }
+
+       if ((corner[0].x < corner[1].x) ||
+           (corner[0].y < corner[1].y))
+               trap();
 }
 
 static int is_within(struct vector *pos, struct vector *corner)
@@ -294,8 +330,17 @@ static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
 {
        int ret;
 
-       if (!is_within(pos, corner))
+       if (!is_within(pos, corner)) {
+               if (debug) {
+                       printf("No nearest to be found from (%f %f) (%f %f) "
+                               "pos (%f %f)\n",
+                               corner[0].x, corner[0].y,
+                               corner[1].x, corner[1].y,
+                               pos->x, pos->y);
+                       fflush(stdout);
+               }
                return NULL;
+       }
 
        while (1) {
                ret = quadtree_compare_coord(&tree->pos, pos);
@@ -304,8 +349,17 @@ static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
                        tree = tree->child[ret];
                        continue;
                }
+               if (is_within(&tree->pos, corner))
+                       return tree;
 
-               return tree;
+               if (debug)
+                       printf("Node %p (%f %f) is not within "
+                               "search window (%f %f) (%f %f)\n",
+                               tree, tree->pos.x, tree->pos.y,
+                               corner[0].x, corner[0].y,
+                               corner[1].x, corner[1].y);
+
+               return 0;
        }
 }
 
@@ -315,16 +369,22 @@ static void get_middle_point(struct vector *corner, struct vector *middle)
        middle->y = (corner[0].y + corner[1].y) / 2;
 }
 
-static void quadtree_split_by_node(struct quadtree *node,
+static int quadtree_split_by_node(struct quadtree *node,
                                struct vector *corner, int dir)
 {
+       if (!is_within(&node->pos, corner)) {
+               if (debug)
+                       printf("Not within search rectangle\n");
+               return 0;
+       }
+
        switch (dir) {
        case QUADTREE_UPLEFT:
                corner[0] = node->pos;
                break;
        case QUADTREE_UPRIGHT:
-               corner[0].x = node->pos.x;
-               corner[1].y = node->pos.y;
+               corner[0].y = node->pos.y;
+               corner[1].x = node->pos.x;
                break;
        case QUADTREE_DOWNRIGHT:
                corner[1] = node->pos;
@@ -336,6 +396,18 @@ static void quadtree_split_by_node(struct quadtree *node,
        default:
                trap();
        }
+
+       if (debug)
+               printf("Search rectangle is now (%f %f) (%f %f), (%f %f)\n",
+                       corner[0].x, corner[0].y,
+                       corner[1].x, corner[1].y,
+                       node->pos.x, node->pos.y);
+
+       if ((corner[0].x < corner[1].x) ||
+           (corner[0].y < corner[1].y))
+               trap();
+
+       return 1;
 }
 
 /*
@@ -373,22 +445,26 @@ static int _quadtree_del(struct quadtree *node, struct quadtree *parent)
 }
 
 /**
- * Move everything under @tree node under @parent node, everything
+ * Move everything under @tree node to @parent node, everything
  * else except the @tree node itself
  */
-static void optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
-                               struct vector *corner_orig,
-                               struct quadtree_ops *ops)
+static int optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
+                       struct vector *corner_orig,
+                       struct quadtree_ops *ops)
 {
        struct vector corner[2], mid;
-       struct quadtree *t;
-       int ret;
+       struct quadtree *t, *tmp;
+       int ret, moved = 0;
 
        get_middle_point(corner_orig, &mid);
        t = quadtree_find_nearest(tree, &mid, corner_orig);
 
-       if (!t)
-               return;
+       if (!t) {
+               if (debug)
+                       printf("Cannot find nearest node\n");
+
+               goto out;
+       }
 
        /* oops, we don't want to remove this node, let's pick another
         * one
@@ -418,11 +494,19 @@ static void optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
                                        t = quadtree_find_nearest(
                                                tree->child[i], &mid,
                                                corner_orig);
+
+                                       if (t == NULL)
+                                               continue;
+
                                        vector_sub(&mid, &t->pos, &sub);
                                        dist = vector_abs(&sub);
                                }
                                node = quadtree_find_nearest(tree->child[i],
                                                        &mid, corner_orig);
+
+                               if (node == NULL)
+                                       continue;
+
                                vector_sub(&mid, &node->pos, &sub);
                                dist2 = vector_abs(&sub);
 
@@ -433,7 +517,7 @@ static void optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
                        }
 
                        if (t == NULL)
-                               return;
+                               goto out;
                }
        }
 
@@ -450,9 +534,10 @@ static void optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
        _quadtree_del(t, tree);
        quadtree_add(parent, t, ops);
 
+       moved++;
        tree->children--;
        if (!tree->children)
-               return;
+               goto out;
 
        /*
         * Now split the search rectangle in quadtres and do the same
@@ -461,23 +546,53 @@ static void optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
 
        corner[0] = corner_orig[0];
        corner[1] = corner_orig[1];
-       quadtree_split_by_node(t, corner, QUADTREE_UPLEFT);
-       optimally_move_tree(tree, parent, corner, ops);
+       if (quadtree_split_by_node(t, corner, QUADTREE_UPLEFT)) {
+               moved += optimally_move_tree(tree, parent, corner, ops);
+
+               tmp = quadtree_find_nearest(tree, &t->pos, corner);
+               if (tmp && tmp != t)
+                       trap();
+
+       }
 
        corner[0] = corner_orig[0];
        corner[1] = corner_orig[1];
-       quadtree_split_by_node(t, corner, QUADTREE_UPRIGHT);
-       optimally_move_tree(tree, parent, corner, ops);
+       if (quadtree_split_by_node(t, corner, QUADTREE_UPRIGHT)) {
+               moved += optimally_move_tree(tree, parent, corner, ops);
+
+               tmp = quadtree_find_nearest(tree, &t->pos, corner);
+               if (tmp && tmp != t)
+                       trap();
+
+       }
 
        corner[0] = corner_orig[0];
        corner[1] = corner_orig[1];
-       quadtree_split_by_node(t, corner, QUADTREE_DOWNLEFT);
-       optimally_move_tree(tree, parent, corner, ops);
+       if (quadtree_split_by_node(t, corner, QUADTREE_DOWNLEFT)) {
+               moved += optimally_move_tree(tree, parent, corner, ops);
+
+               tmp = quadtree_find_nearest(tree, &t->pos, corner);
+               if (tmp && tmp != t)
+                       trap();
+
+       }
 
        corner[0] = corner_orig[0];
        corner[1] = corner_orig[1];
-       quadtree_split_by_node(t, corner, QUADTREE_DOWNRIGHT);
-       optimally_move_tree(tree, parent, corner, ops);
+       if (quadtree_split_by_node(t, corner, QUADTREE_DOWNRIGHT)) {
+               moved += optimally_move_tree(tree, parent, corner, ops);
+
+               tmp = quadtree_find_nearest(tree, &t->pos, corner);
+               if (tmp && tmp != t)
+                       trap();
+
+       }
+
+out:
+       if (debug)
+               printf("Now moved %d nodes, %d left\n", moved, tree->children);
+
+       return moved;
 }
 
 /*
@@ -492,7 +607,7 @@ struct quadtree *quadtree_del(struct quadtree *node,
 {
        struct quadtree *parent = NULL;
        struct vector corner[2];
-       int i;
+       int i, children = node->children, moved;
 
        validate_tree(node);
 
@@ -525,9 +640,8 @@ struct quadtree *quadtree_del(struct quadtree *node,
                }
        } else {
                /*
-                * We are not deleting the parent. Detach the node
-                * from the parent abd relocate the children. The node
-                * will be then detached from the tree.
+                * The node has a parent. Detach the node from it and
+                * relocate the children.
                 */
 
                for (i = 0; i < 4; i++) {
@@ -558,9 +672,14 @@ struct quadtree *quadtree_del(struct quadtree *node,
         */
 
        quadtree_get_tree_dimensions(node, corner);
-       optimally_move_tree(node, parent, corner, ops);
+       moved = optimally_move_tree(node, parent, corner, ops);
 
        if (debug) {
+               if (moved != children) {
+                       printf("Got %d children but %d were moved\n",
+                               children, moved);
+                       trap();
+               }
                printf("Delete done, returning parent %p\n", parent);
                fflush(stdout);
        }

diff --git a/quadtree.h b/quadtree.h
index b5922dbd3bfc8acbd8a199f087dfcd3eeaf12711..69643fee34894bb7596853104280f5c49732fd41 100644 (file)
--- a/quadtree.h
+++ b/quadtree.h
@@ -93,4 +93,12 @@ static inline void quadtree_recalculate_parent_stats(struct quadtree *node,
        }
 }
 
+void _quadtree_validate_tree(const struct quadtree *node);
+
+static inline void quadtree_validate_tree(struct quadtree *node)
+{
+       if (debug)
+               _quadtree_validate_tree(node);
+}
+
 #endif

diff --git a/utils.h b/utils.h
index 6c9a272a6b37ff85c4c2e0e70e22e0e7ed18d2a1..a25957e98290b2340a8923f18f9180f3817dffff 100644 (file)
--- a/utils.h
+++ b/utils.h
@@ -3,6 +3,12 @@
 
 #include <stddef.h>
 
+#ifdef DEBUG
+#define debug 1
+#else
+#define debug 0
+#endif
+
 #define MAX(a,b) ((a) > (b) ? (a) : (b))
 #define MIN(a,b) ((a) < (b) ? (a) : (b))