git.itanic.dy.fi Git - sdl-planets/blob - quadtree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #include "quadtree.h"
   5
   6 #ifdef DEBUG
   7 #define debug 1
   8 #else
   9 #define debug 0
  10 #endif
  11
  12 static void _trap(int line)
  13 {
  14         if (debug) {
  15                 printf("Trapped from line %d, use debugger to get backtrace\n",
  16                         line);
  17                 fflush(stdout);
  18                 exit(1);
  19         }
  20 }
  21
  22 #define trap() _trap(__LINE__)
  23
  24 static int quadtree_compare_coord(const struct vector *a,
  25                                 const struct vector *b)
  26 {
  27         int up, left;
  28
  29         up = b->y < a->y;
  30         left = b->x < a->x;
  31
  32         if (up && left)
  33                 return 0;
  34         if (up && !left)
  35                 return 1;
  36         if (left)
  37                 return 2;
  38         return 3;
  39 }
  40
  41 static int quadtree_compare(const struct quadtree *a, const struct quadtree *b)
  42 {
  43         return quadtree_compare_coord(&a->pos, &b->pos);
  44 }
  45
  46 static void validate_subtree(const struct quadtree *node)
  47 {
  48         int i, dir;
  49         long int children;
  50         children = 0;
  51
  52         if (!node) {
  53                 printf("Attempted to validate a null pointer\n");
  54                 fflush(stdout);
  55                 trap();
  56         }
  57
  58         for (i = 0; i < 4; i++) {
  59                 if (!node->child[i])
  60                         continue;
  61
  62                 if (node->child[i]->parent != node) {
  63                         printf("%s:%d Fatal! Tree inconsistency detected at "
  64                                "child %d %p in node %p, incorrent parent %p\n",
  65                                __func__, __LINE__, i, node->child[i], node,
  66                                node->child[i]->parent);
  67                         fflush(stdout);
  68                         trap();
  69                 }
  70
  71                 if (node->parent) {
  72                         if (node->child[i] == node->parent) {
  73                                 printf("%s:%d Fatal! Tree loop detected "
  74                                        "at child %d in node %p\n",
  75                                        __func__, __LINE__, i, node);
  76                                 fflush(stdout);
  77                                 trap();
  78                         }
  79                 }
  80
  81                 dir = quadtree_compare(node, node->child[i]);
  82
  83                 if (dir != i) {
  84                         printf("%s:%d Fatal! Spatial inconsistency detected "
  85                                 "at child %d in node %p\n"
  86                                 "parent: (%f %f), child (%f %f), "
  87                                 "dir %d != %d\n",
  88                                 __func__, __LINE__, i, node,
  89                                 node->pos.x, node->pos.y,
  90                                 node->child[i]->pos.x, node->child[i]->pos.y,
  91                                 dir, i);
  92                         fflush(stdout);
  93                         trap();
  94                 }
  95
  96                 children += node->child[i]->children + 1;
  97
  98                 validate_subtree(node->child[i]);
  99         }
 100
 101         if (node->depth < 0) {
 102                 printf("%s:%d Tree statistics inconsistency detected! "
 103                        "Negative depth: %ld\n",
 104                        __func__, __LINE__, node->depth);
 105         }
 106
 107         if (node->children != children) {
 108                 printf("%s:%d Tree statistics inconsistency detected! "
 109                        "child count mismatch. Expected %ld, got %ld\n",
 110                        __func__, __LINE__, children, node->children);
 111                 fflush(stdout);
 112                 trap();
 113         }
 114
 115         for (i = 0; i < 4 && node->children; i++) {
 116                 if (!node->child[i])
 117                         continue;
 118
 119                 if (node->depth == node->child[i]->depth + 1)
 120                         break;
 121
 122                 if (node->child[i]->depth > node->depth) {
 123                         printf("%s:%d Tree statistics inconsistency detected! "
 124                                "child depth mismatch %ld > %ld\n",
 125                                __func__, __LINE__, node->child[i]->depth,
 126                                node->depth);
 127                 }
 128         }
 129
 130         if (i == 4) {
 131                 printf("%s:%d Tree statistics inconsistency detected! "
 132                        "child depth mismatch.",
 133                        __func__, __LINE__);
 134                 fflush(stdout);
 135                 trap();
 136         }
 137 }
 138
 139 static void validate_tree(const struct quadtree *node)
 140 {
 141         int i;
 142
 143         if (!debug)
 144                 return;
 145
 146         if (!node->parent)
 147                 return validate_subtree(node);
 148
 149         for (i = 0; i < 4; i++)
 150                 if (node->parent->child[i] == node)
 151                         break;
 152
 153         if (i == 4) {
 154                 printf("%s:%d Tree inconsistency detected! "
 155                         "Wrong parent %p for node %p\n",
 156                         __func__, __LINE__, node->parent, node);
 157                 fflush(stdout);
 158                 trap();
 159         }
 160
 161         validate_tree(node->parent);
 162 }
 163
 164 void _quadtree_validate_tree(const struct quadtree *node)
 165 {
 166         validate_tree(node);
 167 }
 168
 169 static struct quadtree *_quadtree_add(struct quadtree *parent,
 170                                 struct quadtree *new)
 171 {
 172         int ret, i;
 173
 174         ret = quadtree_compare(parent, new);
 175
 176         if (ret < 0 || ret >= 4) {
 177                 printf("Invalid comparison result of %d\n", ret);
 178                 return 0;
 179         }
 180
 181         if (parent->child[ret])
 182                 return _quadtree_add(parent->child[ret], new);
 183
 184         parent->child[ret] = new;
 185         new->parent = parent;
 186         for (i = 0; i < 4; i++)
 187                 new->child[i] = 0;
 188
 189         return new;
 190 }
 191
 192 /*
 193  * Recursively walk through the tree and propagate changes made to the
 194  * given node up until the highest parent.
 195  */
 196 static void quadtree_recalculate_parent_stats(struct quadtree *node,
 197                                                      struct quadtree_ops *ops)
 198 {
 199         int i;
 200
 201         while (node) {
 202                 node->depth = 0;
 203                 node->children = 0;
 204
 205                 for (i = 0; i < 4; i++) {
 206                         if (!node->child[i])
 207                                 continue;
 208
 209                         node->depth = MAX(node->depth,
 210                                           node->child[i]->depth + 1);
 211                         node->children += node->child[i]->children + 1;
 212                 }
 213
 214                 /* The space covered by the parent node's corner
 215                  * points needs be as wide as its widest child node's
 216                  * corners.
 217                  */
 218 #define CHILD_CORNER_SAFE(node, ch_idx, cor_idx, axis)               \
 219                 (node)->child[ch_idx] ?                              \
 220                         (node)->child[ch_idx]->corner[cor_idx].axis : \
 221                         (node)->pos.axis
 222
 223                 node->corner[0].x = MIN(CHILD_CORNER_SAFE(node, 0, 0, x),
 224                                         CHILD_CORNER_SAFE(node, 2, 0, x));
 225                 node->corner[0].y = MIN(CHILD_CORNER_SAFE(node, 0, 0, y),
 226                                         CHILD_CORNER_SAFE(node, 1, 0, y));
 227                 node->corner[1].x = MAX(CHILD_CORNER_SAFE(node, 1, 1, x),
 228                                         CHILD_CORNER_SAFE(node, 3, 1, x));
 229                 node->corner[1].y = MAX(CHILD_CORNER_SAFE(node, 2, 1, y),
 230                                         CHILD_CORNER_SAFE(node, 3, 1, y));
 231 #undef CHILD_CORNER_SAFE
 232
 233                 if (ops->recalculate_stats)
 234                         ops->recalculate_stats(node);
 235
 236                 node = node->parent;
 237         }
 238 }
 239
 240 /**
 241  * quadtree_add - add a node to a quadtree
 242  * @parent: parent node
 243  * @new: the new node to be added
 244  *
 245  * Add a node to a quadtree. The tree is kept in order, the new node
 246  * is placed in the end of appropriate branch.
 247  *
 248  * The case of nodes sharing identical coordinates is not taken into
 249  * account at all.
 250  */
 251
 252 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
 253                               struct quadtree_ops *ops)
 254 {
 255         if (parent == new)
 256                 trap();
 257
 258         validate_tree(parent);
 259
 260         _quadtree_add(parent, new);
 261
 262         if (debug) {
 263                 printf("adding node %p to parent %p\n", new, parent);
 264                 fflush(stdout);
 265         }
 266
 267         quadtree_recalculate_parent_stats(new, ops);
 268
 269         validate_tree(new);
 270
 271         return new;
 272 }
 273
 274 static int is_within(struct vector *pos, struct vector *corner)
 275 {
 276         if ((pos->x >= corner[1].x) && (pos->x <= corner[0].x) &&
 277             (pos->y >= corner[1].y) && (pos->y <= corner[0].y))
 278                 return 1;
 279         return 0;
 280 }
 281
 282 static int quadrants_to_search(struct quadtree *node, struct vector *corner)
 283 {
 284         int direction = 0, i;
 285         int up = 0, left = 0, right = 0, down = 0;
 286
 287         for (i = 0; i < 2; i++) {
 288                 if (corner[i].x <= node->pos.x)
 289                         left = 1;
 290                 else if (corner[i].x >= node->pos.x)
 291                         right = 1;
 292                 if (corner[i].y <= node->pos.y)
 293                         up = 1;
 294                 else if (corner[i].y >= node->pos.y)
 295                         down = 1;
 296         }
 297
 298         if (left || up)
 299                 direction |= QUADTREE_UPLEFT;
 300         if (right || up)
 301                 direction |= QUADTREE_UPRIGHT;
 302         if (left || down)
 303                 direction |= QUADTREE_DOWNLEFT;
 304         if (right || down)
 305                 direction |= QUADTREE_DOWNRIGHT;
 306
 307         return direction;
 308 }
 309
 310 static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
 311                                         struct vector *pos,
 312                                         struct vector *corner)
 313 {
 314         struct vector tmp;
 315         struct quadtree *nearest, *node;
 316         double distance = 0, dist;
 317         int i, directions;
 318
 319         if (!is_within(pos, corner)) {
 320                 if (debug) {
 321                         printf("No nearest to be found from (%f %f) (%f %f) "
 322                                 "pos (%f %f)\n",
 323                                 corner[0].x, corner[0].y,
 324                                 corner[1].x, corner[1].y,
 325                                 pos->x, pos->y);
 326                         fflush(stdout);
 327                 }
 328                 return NULL;
 329         }
 330
 331         if (is_within(&tree->pos, corner)) {
 332                 vector_sub(pos, &tree->pos, &tmp);
 333                 distance = vector_abs(&tmp);
 334                 nearest = tree;
 335         } else {
 336                 nearest = NULL;
 337         }
 338
 339         directions = quadrants_to_search(tree, corner);
 340
 341         for (i = 0; i < 4; i++) {
 342                 if (!tree->child[i])
 343                         continue;
 344
 345 /*
 346                 if (!(directions & (1 << i)))
 347                         continue;
 348 */
 349                 node = quadtree_find_nearest(tree->child[i], pos, corner);
 350
 351                 if (!node)
 352                         continue;
 353
 354                 vector_sub(pos, &node->pos, &tmp);
 355                 dist = vector_abs(&tmp);
 356
 357                 if (!nearest || dist < distance) {
 358                         nearest = node;
 359                         distance = dist;
 360
 361                 }
 362         }
 363
 364         if (nearest && !is_within(&nearest->pos, corner)) {
 365                 if (debug)
 366                         printf("Node %p (%f %f) is not within "
 367                                 "search window (%f %f) (%f %f)\n",
 368                                 nearest, nearest->pos.x, nearest->pos.y,
 369                                 corner[0].x, corner[0].y,
 370                                 corner[1].x, corner[1].y);
 371                 return NULL;
 372         }
 373
 374         return nearest;
 375 }
 376
 377 static struct quadtree *quadtree_find_nearest_noparent(struct quadtree *tree,
 378                                                 struct vector *pos,
 379                                                 struct vector *corner)
 380 {
 381         struct quadtree *nearest;
 382         struct vector sub;
 383         struct quadtree *node;
 384         double dist = 0, dist2;
 385         int i;
 386
 387         nearest = quadtree_find_nearest(tree, pos, corner);
 388
 389         if (nearest != tree)
 390                 goto out;
 391
 392         if (debug)
 393                 printf("Avoiding parent or NULL node %p\n", nearest);
 394
 395         /*
 396          * oops, we don't want to pick the parent node, let's choose
 397          * another one
 398          */
 399         nearest = NULL;
 400         for (i = 0; i < 4; i++) {
 401                 if (!tree->child[i])
 402                         continue;
 403
 404                 if (!nearest) {
 405                         nearest = quadtree_find_nearest(tree->child[i], pos,
 406                                                         corner);
 407
 408                         if (nearest == NULL)
 409                                 continue;
 410
 411                         vector_sub(pos, &nearest->pos, &sub);
 412                         dist = vector_abs(&sub);
 413                         continue;
 414                 }
 415                 node = quadtree_find_nearest(tree->child[i],
 416                                         pos, corner);
 417
 418                 if (node == NULL)
 419                         continue;
 420
 421                 vector_sub(pos, &node->pos, &sub);
 422                 dist2 = vector_abs(&sub);
 423
 424                 if (dist2 < dist) {
 425                         nearest = node;
 426                         dist = dist2;
 427                 }
 428         }
 429
 430 out:
 431         return nearest;
 432 }
 433
 434 static void get_middle_point(struct vector *corner, struct vector *middle)
 435 {
 436         middle->x = (corner[0].x + corner[1].x) / (double)2;
 437         middle->y = (corner[0].y + corner[1].y) / (double)2;
 438 }
 439
 440 static int quadtree_split_by_node(struct quadtree *node,
 441                                 struct vector *corner, int dir)
 442 {
 443         if (!is_within(&node->pos, corner)) {
 444                 if (debug)
 445                         printf("Not within search rectangle\n");
 446                 return 0;
 447         }
 448
 449         switch (dir) {
 450         case QUADTREE_UPLEFT:
 451                 corner[0] = node->pos;
 452                 break;
 453         case QUADTREE_UPRIGHT:
 454                 corner[0].y = node->pos.y;
 455                 corner[1].x = node->pos.x;
 456                 break;
 457         case QUADTREE_DOWNRIGHT:
 458                 corner[1] = node->pos;
 459                 break;
 460         case QUADTREE_DOWNLEFT:
 461                 corner[0].x = node->pos.x;
 462                 corner[1].y = node->pos.y;
 463                 break;
 464         default:
 465                 trap();
 466         }
 467
 468         if (debug)
 469                 printf("Search rectangle is now (%f %f) (%f %f), (%f %f)\n",
 470                         corner[0].x, corner[0].y,
 471                         corner[1].x, corner[1].y,
 472                         node->pos.x, node->pos.y);
 473
 474         if ((corner[0].x < corner[1].x) ||
 475             (corner[0].y < corner[1].y))
 476                 trap();
 477
 478         return 1;
 479 }
 480
 481 /*
 482  * Quickly detach a node from a tree. Move all child nodes under
 483  * @parent node.
 484  */
 485 static int _quadtree_del(struct quadtree *node, struct quadtree *parent)
 486 {
 487         struct quadtree *n;
 488         int i;
 489
 490         /* Detach from the tree */
 491         if (node->parent)
 492                 for (i = 0; i < 4; i++) {
 493                         if (node->parent->child[i] == node) {
 494                                 node->parent->child[i] = 0;
 495                                 break;
 496                         }
 497                 }
 498
 499         if (i == 4)
 500                 trap();
 501
 502
 503         for (i = 0; i < 4; i++) {
 504                 if (!node->child[i])
 505                         continue;
 506
 507                 n = node->child[i];
 508                 _quadtree_del(n, parent);
 509                 _quadtree_add(parent, n);
 510         }
 511
 512         return 0;
 513 }
 514
 515 /**
 516  * Move everything under @tree node to @parent node, everything
 517  * else except the @tree node itself
 518  */
 519 static int optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
 520                         struct vector *corner_orig,
 521                         struct quadtree_ops *ops)
 522 {
 523         struct vector corner[2], mid;
 524         struct quadtree *t, *tmp;
 525         int moved = 0;
 526
 527         get_middle_point(corner_orig, &mid);
 528         t = quadtree_find_nearest_noparent(tree, &mid, corner_orig);
 529
 530         if (!t) {
 531                 if (debug)
 532                         printf("Cannot find nearest node\n");
 533
 534                 goto out;
 535         }
 536
 537         /*
 538          * Now we have the t node which contains the object of the
 539          * spatial middle coordinates of the tree.
 540          */
 541
 542         if (debug) {
 543                 printf("Relocating node %p (%f %f) under parent %p\n", t,
 544                         t->pos.x, t->pos.y, parent);
 545                 printf("There are %ld child nodes left\n", tree->children);
 546                 fflush(stdout);
 547         }
 548         _quadtree_del(t, tree);
 549         quadtree_add(parent, t, ops);
 550
 551         moved++;
 552         tree->children--;
 553         if (!tree->children)
 554                 goto out;
 555
 556         /*
 557          * Now split the search rectangle in quadtres and do the same
 558          * with all of the quarters.
 559          */
 560
 561         corner[0] = corner_orig[0];
 562         corner[1] = corner_orig[1];
 563         if (quadtree_split_by_node(t, corner, QUADTREE_UPLEFT))
 564                 moved += optimally_move_tree(tree, parent, corner, ops);
 565
 566         corner[0] = corner_orig[0];
 567         corner[1] = corner_orig[1];
 568         if (quadtree_split_by_node(t, corner, QUADTREE_UPRIGHT))
 569                 moved += optimally_move_tree(tree, parent, corner, ops);
 570
 571         corner[0] = corner_orig[0];
 572         corner[1] = corner_orig[1];
 573         if (quadtree_split_by_node(t, corner, QUADTREE_DOWNLEFT))
 574                 moved += optimally_move_tree(tree, parent, corner, ops);
 575
 576         corner[0] = corner_orig[0];
 577         corner[1] = corner_orig[1];
 578         if (quadtree_split_by_node(t, corner, QUADTREE_DOWNRIGHT))
 579                 moved += optimally_move_tree(tree, parent, corner, ops);
 580
 581         get_middle_point(corner_orig, &mid);
 582         tmp = quadtree_find_nearest(tree, &mid, corner_orig);
 583         if (tmp && tmp != tree)
 584                 trap();
 585
 586 out:
 587         if (debug)
 588                 printf("Now moved %d nodes, %ld left\n", moved, tree->children);
 589
 590         return moved;
 591 }
 592
 593 /*
 594  * quadtree_del - Detach a node from the tree
 595  *
 596  * Return value: The new root node of the tree. If we are detaching
 597  * anything but the root node of the entire tree, the returned root
 598  * value will be the original root of the tree.
 599  */
 600 struct quadtree *quadtree_del(struct quadtree *node,
 601                               struct quadtree_ops *ops)
 602 {
 603         struct quadtree *parent = NULL;
 604         struct vector corner[2];
 605         int i, children = node->children, moved;
 606
 607         validate_tree(node);
 608
 609         if (debug) {
 610                 printf("Deleting node %p under parent %p\n",
 611                                node, node->parent);
 612                 printf("Relocating %ld children\n", node->children);
 613                 fflush(stdout);
 614         }
 615
 616         if (!node->parent) {
 617                 /*
 618                  * We are deleting the root node. This means we have
 619                  * to select a new root node and reconstruct the
 620                  * entire tree under it again.
 621                  */
 622                 if (debug) {
 623                         printf("Deleting root node\n");
 624                         fflush(stdout);
 625                 }
 626                 for (i = 0; i < 4; i++) {
 627                         if (!node->child[i])
 628                                 continue;
 629
 630                         parent = node->child[i];
 631                         _quadtree_del(parent, node);
 632                         parent->parent = 0;
 633                         quadtree_recalculate_parent_stats(parent, ops);
 634                         break;
 635                 }
 636         } else {
 637                 /*
 638                  * The node has a parent. Detach the node from it and
 639                  * relocate the children.
 640                  */
 641
 642                 for (i = 0; i < 4; i++) {
 643                         if (node->parent->child[i] == node) {
 644                                 node->parent->child[i] = 0;
 645                                 break;
 646                         }
 647                 }
 648                 if (i == 4)
 649                         trap();
 650
 651                 parent = node->parent;
 652
 653                 /*
 654                  * The sub branch is now detached from the main
 655                  * tree. Fix the stats.
 656                  */
 657                 quadtree_recalculate_parent_stats(node->parent, ops);
 658         }
 659
 660         validate_tree(parent);
 661
 662         if (!node->children)
 663                 goto out;
 664         /*
 665          * Now we are ready to prepare for relocating the nodes under
 666          * the parent.
 667          */
 668
 669         corner[0] = node->corner[1];
 670         corner[1] = node->corner[0];
 671         moved = optimally_move_tree(node, parent, corner, ops);
 672
 673         if (debug) {
 674                 if (moved != children) {
 675                         printf("Got %d children but %d were moved\n",
 676                                 children, moved);
 677                         printf("nearest children left:\n");
 678                         for (i = 0 ; i < 4; i++)
 679                                 if (node->child[i])
 680                                         printf("   node %d %p, (%f %f)\n",
 681                                                 i, node->child[i],
 682                                                 node->child[i]->pos.x,
 683                                                 node->child[i]->pos.y);
 684                         fflush(stdout);
 685                         trap();
 686                 }
 687                 printf("Delete done, returning parent %p\n", parent);
 688                 fflush(stdout);
 689         }
 690
 691 out:
 692         validate_tree(parent);
 693         return quadtree_find_parent(parent);
 694 }
 695
 696 static void check_for_crossed_subnodes(struct quadtree *node,
 697                                 struct vector *limit, struct quadtree_ops *ops)
 698 {
 699         int direction = 0, i;
 700         int up = 0, left = 0, right = 0, down = 0;
 701
 702         for (i = 0; i < 2; i++) {
 703                 if (limit[i].x < node->pos.x)
 704                         left = 1;
 705                 else
 706                         right = 1;
 707                 if (limit[i].y < node->pos.y)
 708                         up = 1;
 709                 else
 710                         down = 1;
 711         }
 712
 713         if (left || up)
 714                 direction |= QUADTREE_UPLEFT;
 715         if (right || up)
 716                 direction |= QUADTREE_UPRIGHT;
 717         if (left || down)
 718                 direction |= QUADTREE_DOWNLEFT;
 719         if (right || down)
 720                 direction |= QUADTREE_DOWNRIGHT;
 721         if ((left && right) || (up && down))
 722                 direction |= QUADTREE_SELF;
 723
 724         if ((direction & QUADTREE_UPLEFT) && node->child[0])
 725                 check_for_crossed_subnodes(node->child[0], limit, ops);
 726
 727         if ((direction & QUADTREE_UPRIGHT) && node->child[1])
 728                 check_for_crossed_subnodes(node->child[0], limit, ops);
 729
 730         if ((direction & QUADTREE_DOWNLEFT) && node->child[2])
 731                 check_for_crossed_subnodes(node->child[0], limit, ops);
 732
 733         if ((direction & QUADTREE_DOWNRIGHT) && node->child[3])
 734                 check_for_crossed_subnodes(node->child[0], limit, ops);
 735
 736         if (direction & QUADTREE_SELF) {
 737                 struct quadtree *parent;
 738
 739                 parent = quadtree_del(node, ops);
 740                 quadtree_add(parent, node, ops);
 741         }
 742 }
 743
 744 struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
 745                         struct quadtree_ops *ops)
 746 {
 747         struct quadtree *parent, *tree_parent;
 748         int modify;
 749
 750         /* Check if we have crossed any of the parents */
 751         parent = node->parent;
 752         while (parent) {
 753                 if (node->pos.x < parent->pos.x && new_pos.x > parent->pos.x)
 754                         modify = 1;
 755                 if (node->pos.x > parent->pos.x && new_pos.x < parent->pos.x)
 756                         modify = 1;
 757                 if (node->pos.y < parent->pos.y && new_pos.y > parent->pos.y)
 758                         modify = 1;
 759                 if (node->pos.y > parent->pos.y && new_pos.y < parent->pos.y)
 760                         modify = 1;
 761
 762                 if (!modify) {
 763                         parent = parent->parent;
 764                         continue;
 765                 }
 766
 767                 /*
 768                  * If the node has crossed the boundaries, remove it
 769                  * from the tree and add it again to it. It is then
 770                  * guaranteed to be in the correct position of the
 771                  * tree.
 772                  */
 773                 tree_parent = quadtree_del(node, ops);
 774                 node->pos = new_pos;
 775                 quadtree_add(tree_parent, node, ops);
 776                 quadtree_recalculate_parent_stats(node, ops);
 777                 return tree_parent;
 778         }
 779
 780         /* Move the node into its new location */
 781         node->pos = new_pos;
 782
 783         if(node->children) {
 784                 /*
 785                  * Now, search the subtree for any children that are
 786                  * located in wrong place and move them into correct
 787                  * place within the tree.
 788                  */
 789                 struct vector limit[2];
 790
 791                 limit[0] = node->pos;
 792                 limit[1] = new_pos;
 793                 check_for_crossed_subnodes(node, limit, ops);
 794         }
 795
 796         quadtree_recalculate_parent_stats(node, ops);
 797         return quadtree_find_parent(node);
 798
 799 }
 800
 801 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
 802 {
 803         int direction, count = 0;
 804
 805         direction = it->direction(head, (struct quadtree_iterator *)it);
 806
 807         if ((direction & QUADTREE_UPLEFT) && head->child[0])
 808                 count += _walk_tree(head->child[0], it);
 809
 810         if ((direction & QUADTREE_UPRIGHT) && head->child[1])
 811                 count += _walk_tree(head->child[1], it);
 812
 813         if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
 814                 count += _walk_tree(head->child[2], it);
 815
 816         if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
 817                 count += _walk_tree(head->child[3], it);
 818
 819         if ((direction & QUADTREE_SELF) && it->callback) {
 820                 it->callback(head, (struct quadtree_iterator *)it);
 821                 count++;
 822         }
 823
 824         return count;
 825 }
 826
 827 int walk_quadtree(const struct quadtree_iterator *it)
 828 {
 829         return _walk_tree(it->head, it);
 830 }