quadtree: quadtree_move(): Avoid excess rebalancing

[sdl-planets] / quadtree.c

diff --git a/quadtree.c b/quadtree.c
index 3f621f12c19f5e9794b6dc381c101c4a1d9ffdb6..9d5c56d6a6039c778c4aec6557c627eb2fd7b68d 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -760,11 +760,13 @@ out:
        return quadtree_find_parent(parent);
 }
 
-static void check_for_crossed_subnodes(struct quadtree *node,
+static int check_for_crossed_subnodes(struct quadtree *node,
+                               struct quadtree *skip,
                                struct vector *limit, struct quadtree_ops *ops)
 {
        int direction = 0, i;
        int up = 0, left = 0, right = 0, down = 0;
+       int cross = 0;
 
        for (i = 0; i < 2; i++) {
                if (limit[i].x < node->pos.x)
@@ -788,65 +790,114 @@ static void check_for_crossed_subnodes(struct quadtree *node,
        if ((left && right) || (up && down))
                direction |= QUADTREE_SELF;
 
-       if ((direction & QUADTREE_UPLEFT) && node->child[0])
-               check_for_crossed_subnodes(node->child[0], limit, ops);
-
-       if ((direction & QUADTREE_UPRIGHT) && node->child[1])
-               check_for_crossed_subnodes(node->child[0], limit, ops);
 
-       if ((direction & QUADTREE_DOWNLEFT) && node->child[2])
-               check_for_crossed_subnodes(node->child[0], limit, ops);
-
-       if ((direction & QUADTREE_DOWNRIGHT) && node->child[3])
-               check_for_crossed_subnodes(node->child[0], limit, ops);
+       /*
+        * We need to skip the topmost node (the one that was actually
+        * moved), otherwise we would trigger rebalance every time
+        */
+       if (node == skip)
+               goto child_check;
 
        if (direction & QUADTREE_SELF) {
                struct quadtree *parent;
 
+               if (debug)
+                       printf("Rebalanced because crossed child %p: "
+                               "node (%f %f) limits (%f %f) (%f %f)\n",
+                               node,
+                               node->pos.x, node->pos.y,
+                               limit[0].x, limit[0].y,
+                               limit[1].x, limit[1].y);
+               return 1;
                parent = quadtree_del(node, ops);
                quadtree_add(parent, node, ops);
        }
+
+child_check:
+       if ((direction & QUADTREE_UPLEFT) && node->child[0])
+               cross += check_for_crossed_subnodes(node->child[0], skip,
+                                               limit, ops);
+
+       if (cross)
+               goto out;
+
+       if ((direction & QUADTREE_UPRIGHT) && node->child[1])
+               cross += check_for_crossed_subnodes(node->child[1], skip,
+                                               limit, ops);
+
+       if (cross)
+               goto out;
+
+       if ((direction & QUADTREE_DOWNLEFT) && node->child[2])
+               cross += check_for_crossed_subnodes(node->child[2], skip,
+                                               limit, ops);
+
+       if (cross)
+               goto out;
+
+       if ((direction & QUADTREE_DOWNRIGHT) && node->child[3])
+               cross += check_for_crossed_subnodes(node->child[3], skip,
+                                               limit, ops);
+out:
+       return cross;
 }
 
 struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
                        struct quadtree_ops *ops)
 {
        struct quadtree *parent, *tree_parent;
-       int modify;
+       int modify = 0;
+       int parents = 0, all_parents = 0;
+
+       if (debug) {
+               parent = node->parent;
+               while (parent) {
+                       parent = parent->parent;
+                       all_parents++;
+               }
+       }
 
        /* Check if we have crossed any of the parents */
        parent = node->parent;
        while (parent) {
+               parents++;
                if (node->pos.x < parent->pos.x && new_pos.x > parent->pos.x)
-                       modify = 1;
+                       modify |= 1;
                if (node->pos.x > parent->pos.x && new_pos.x < parent->pos.x)
-                       modify = 1;
+                       modify |= 2;
                if (node->pos.y < parent->pos.y && new_pos.y > parent->pos.y)
-                       modify = 1;
+                       modify |= 4;
                if (node->pos.y > parent->pos.y && new_pos.y < parent->pos.y)
-                       modify = 1;
+                       modify |= 8;
 
                if (!modify) {
                        parent = parent->parent;
                        continue;
                }
 
+               if (debug)
+                       printf("Rebalanced because crossed parent: node %p, "
+                               "%d/%d %x "
+                               "old (%f %f) new (%f %f) parent (%f %f)\n",
+                               node, parents, all_parents, modify,
+                               node->pos.x, node->pos.y,
+                               new_pos.x, new_pos.y,
+                               parent->pos.x, parent->pos.y);
                /*
                 * If the node has crossed the boundaries, remove it
                 * from the tree and add it again to it. It is then
                 * guaranteed to be in the correct position of the
                 * tree.
                 */
+               validate_tree(node);
                tree_parent = quadtree_del(node, ops);
                node->pos = new_pos;
                quadtree_add(tree_parent, node, ops);
+               validate_tree(node);
+
                return tree_parent;
        }
 
-       /* Move the node into its new location */
-       node->pos = new_pos;
-       recalculate_parent_area_stats(node);
-
        if (node->children) {
                /*
                 * Now, search the subtree for any children that are
@@ -857,9 +908,20 @@ struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
 
                limit[0] = node->pos;
                limit[1] = new_pos;
-               check_for_crossed_subnodes(node, limit, ops);
+               modify = check_for_crossed_subnodes(node, node, limit, ops);
        }
 
+       /* Move the node into its new location */
+
+       validate_tree(node);
+       if (modify)
+               tree_parent = quadtree_del(node, ops);
+       node->pos = new_pos;
+       if (!modify)
+               recalculate_parent_area_stats(node);
+       if (modify)
+               quadtree_add(tree_parent, node, ops);
+       validate_tree(node);
        return quadtree_find_parent(node);
 
 }