quadtree: Try to keep the tree in better balance.

[sdl-planets] / quadtree.c

diff --git a/quadtree.c b/quadtree.c
index a3315392f3ae3e9b669401946622cd66c5968e65..61a26997c1555a7ee5c3419633d67164051bee28 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -157,39 +157,72 @@ struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
 }
 
 /*
- * _quadtree_reposition_reqursively - Move everything under and
- * including a given node under the new root node
+ * _qt_optimal_del - Delete nodes from a detached subtree in optimal order
+ *
+ * All nodes are moved under the new parent node
  */
-
-static void
-_quadtree_reposition_reqursively(struct quadtree *root,
-                                struct quadtree *node,
-                                struct quadtree_ops *ops)
+static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
+                      struct quadtree_ops *ops, int parents)
 {
-       int i;
-
-       validate_tree(root);
-
-       /* First remove all children, if any */
+       struct quadtree *child[4] = {0};
+       int i, children = 0, max_c, max_i;
 
        for (i = 0; i < 4; i++) {
-               if (!node->child[i])
+               if (!node->child[i]) {
+                       child[i] = 0;
                        continue;
+               }
 
-               if (node->child[i] == node ||
-                   node->child[i] == node->parent)
-                       trap();
+               child[children] = node->child[i];
+               node->child[i] = NULL;
+               children++;
+       }
+
+       /*
+        * Try to remove the nodes in such order that the node which
+        * has child number one quarter of the parent's child numer
+        * gets deleted first.
+        */
 
-               _quadtree_reposition_reqursively(root, node->child[i], ops);
-               node->child[i] = 0;
+       if (node->children <= parents / 4) {
+               if (debug) {
+                       printf("%d: Moving node %p away from parent %p\n",
+                              __LINE__, node, parent);
+                       fflush(stdout);
+               }
+               validate_tree(parent);
+               quadtree_add(parent, node, ops);
+               node = NULL;
+               parents /= 4;
        }
 
-       /* There are no children left, reset stats */
-       node->depth = 0;
-       node->children = 0;
+       while(children) {
+               max_c = -1;
+               max_i = -1;
+               for (i = 0; i < 4; i++) {
+                       if (!child[i])
+                               continue;
+
+                       if (max_c < child[i]->children) {
+                               max_c = child[i]->children;
+                               max_i = i;
+                       }
+               }
 
-       /* Then remove this node under the new root. */
-       quadtree_add(root, node, ops);
+               _qt_optimal_del(parent, child[max_i], ops, parents / 4);
+               child[max_i] = 0;
+               children--;
+       }
+
+       if (node) {
+               validate_tree(parent);
+               if (debug) {
+                       printf("%d: Moving node %p away from parent %p\n",
+                              __LINE__, node, parent);
+                       fflush(stdout);
+               }
+               quadtree_add(parent, node, ops);
+       }
 }
 
 /*
@@ -225,9 +258,8 @@ struct quadtree *quadtree_del(struct quadtree *node,
                                parent->parent = 0;
                                continue;
                        }
-                       _quadtree_reposition_reqursively(parent,
-                                                        node->child[i],
-                                                        ops);
+                       _qt_optimal_del(parent, node->child[i], ops,
+                                       node->children);
                        node->child[i] = 0;
                }
 
@@ -246,34 +278,28 @@ struct quadtree *quadtree_del(struct quadtree *node,
                        break;
                }
        }
-       if (i == 4) {
-               printf("%s:%d Fatal! Tree inconsistency detected\n",
-                      __func__, __LINE__);
+       if (i == 4)
                trap();
-       }
 
-       /* Fix parent stats */
-       quadtree_recalculate_parent_stats(node->parent, ops);
+       parent = node->parent;
 
        /*
-        * The sub branch is now detached from the main tree. Continue
-        * relocating the detached branch.
+        * The sub branch is now detached from the main tree. Fix the
+        * stats.
         */
+       quadtree_recalculate_parent_stats(node->parent, ops);
 
-       for (i = 0; i < 4; i++) {
-               if (!node->child[i])
-                       continue;
-
-               _quadtree_reposition_reqursively(node->parent, node->child[i],
-                                                ops);
-               node->child[i] = 0;
-       }
+       parent = quadtree_find_parent(parent);
 
-       parent = quadtree_find_parent(node);
-       node->parent = 0;
+       if (node->children) {
+               for (i = 0; i < 4; i++) {
+                       if (!node->child[i])
+                               continue;
 
-       node->children = 0;
-       node->depth = 0;
+                       _qt_optimal_del(parent, node->child[i], ops,
+                                       node->children);
+               }
+       }
 
        validate_tree(parent);
        return parent;