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                 if (ops->recalculate_stats)
 215                         ops->recalculate_stats(node);
 216
 217                 node = node->parent;
 218         }
 219 }
 220
 221 /**
 222  * quadtree_add - add a node to a quadtree
 223  * @parent: parent node
 224  * @new: the new node to be added
 225  *
 226  * Add a node to a quadtree. The tree is kept in order, the new node
 227  * is placed in the end of appropriate branch.
 228  *
 229  * The case of nodes sharing identical coordinates is not taken into
 230  * account at all.
 231  */
 232
 233 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
 234                               struct quadtree_ops *ops)
 235 {
 236         if (parent == new)
 237                 trap();
 238
 239         validate_tree(parent);
 240
 241         _quadtree_add(parent, new);
 242
 243         if (debug) {
 244                 printf("adding node %p to parent %p\n", new, parent);
 245                 fflush(stdout);
 246         }
 247
 248         quadtree_recalculate_parent_stats(new, ops);
 249
 250         validate_tree(new);
 251
 252         return new;
 253 }
 254
 255 static double max_by_dir(double a, double b, int direction)
 256 {
 257         switch (direction) {
 258         case 0: /* up */
 259         case 3: /* left */
 260                 return MIN(a, b);
 261         case 1: /* right */
 262         case 2: /* down */
 263                 return MAX(a, b);
 264         }
 265
 266         trap();
 267         return 0;
 268 }
 269
 270 static double maxv_by_dir(struct quadtree *a, int direction)
 271 {
 272         switch (direction) {
 273         case 0: /* up */
 274         case 2: /* down */
 275                 return a->pos.y;
 276         case 1: /* right */
 277         case 3: /* left */
 278                 return a->pos.x;
 279         }
 280
 281         trap();
 282         return 0;
 283 }
 284
 285 static double quadtree_get_max_dimension(struct quadtree *node, int direction)
 286 {
 287         struct quadtree *ch1 = NULL, *ch2 = NULL;
 288         double a, b;
 289
 290         switch (direction) {
 291         case 0: /* up */
 292                 ch1 = node->child[0];
 293                 ch2 = node->child[1];
 294                 break;
 295         case 1: /* right */
 296                 ch1 = node->child[1];
 297                 ch2 = node->child[3];
 298                 break;
 299         case 2: /* down */
 300                 ch1 = node->child[2];
 301                 ch2 = node->child[3];
 302                 break;
 303         case 3: /* left */
 304                 ch1 = node->child[0];
 305                 ch2 = node->child[2];
 306                 break;
 307         default:
 308                 trap();
 309         }
 310
 311         if (ch1 && ch2) {
 312                 a = quadtree_get_max_dimension(ch1, direction);
 313                 b = quadtree_get_max_dimension(ch2, direction);
 314                 return max_by_dir(a, b, direction);
 315         }
 316
 317         if (ch1) {
 318                 a = quadtree_get_max_dimension(ch1, direction);
 319                 b = maxv_by_dir(ch1, direction);
 320                 return max_by_dir(a, b, direction);
 321         }
 322         if (ch2) {
 323                 a = quadtree_get_max_dimension(ch2, direction);
 324                 b = maxv_by_dir(ch2, direction);
 325                 return max_by_dir(a, b, direction);
 326         }
 327
 328         return maxv_by_dir(node, direction);
 329 }
 330
 331 /*
 332  * Stores the lower right and upper left corner coordinates to the
 333  * corner vectors
 334  */
 335 static void quadtree_get_tree_dimensions(struct quadtree *node,
 336                                         struct vector *corner)
 337 {
 338         corner[0].y = quadtree_get_max_dimension(node, 2);
 339         corner[0].x = quadtree_get_max_dimension(node, 1);
 340         corner[1].y = quadtree_get_max_dimension(node, 0);
 341         corner[1].x = quadtree_get_max_dimension(node, 3);
 342
 343         if (debug) {
 344                 printf("\nInitial Search rectangle (%f %f) (%f %f), (%f %f)\n",
 345                         corner[0].x, corner[0].y,
 346                         corner[1].x, corner[1].y,
 347                         node->pos.x, node->pos.y);
 348                 fflush(stdout);
 349         }
 350
 351         if ((corner[0].x < corner[1].x) ||
 352             (corner[0].y < corner[1].y))
 353                 trap();
 354 }
 355
 356 static int is_within(struct vector *pos, struct vector *corner)
 357 {
 358         if ((pos->x >= corner[1].x) && (pos->x <= corner[0].x) &&
 359             (pos->y >= corner[1].y) && (pos->y <= corner[0].y))
 360                 return 1;
 361         return 0;
 362 }
 363
 364 static int quadrants_to_search(struct quadtree *node, struct vector *corner)
 365 {
 366         int direction = 0, i;
 367         int up = 0, left = 0, right = 0, down = 0;
 368
 369         for (i = 0; i < 2; i++) {
 370                 if (corner[i].x <= node->pos.x)
 371                         left = 1;
 372                 else if (corner[i].x >= node->pos.x)
 373                         right = 1;
 374                 if (corner[i].y <= node->pos.y)
 375                         up = 1;
 376                 else if (corner[i].y >= node->pos.y)
 377                         down = 1;
 378         }
 379
 380         if (left || up)
 381                 direction |= QUADTREE_UPLEFT;
 382         if (right || up)
 383                 direction |= QUADTREE_UPRIGHT;
 384         if (left || down)
 385                 direction |= QUADTREE_DOWNLEFT;
 386         if (right || down)
 387                 direction |= QUADTREE_DOWNRIGHT;
 388
 389         return direction;
 390 }
 391
 392 static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
 393                                         struct vector *pos,
 394                                         struct vector *corner)
 395 {
 396         struct vector tmp;
 397         struct quadtree *nearest, *node;
 398         double distance = 0, dist;
 399         int i, directions;
 400
 401         if (!is_within(pos, corner)) {
 402                 if (debug) {
 403                         printf("No nearest to be found from (%f %f) (%f %f) "
 404                                 "pos (%f %f)\n",
 405                                 corner[0].x, corner[0].y,
 406                                 corner[1].x, corner[1].y,
 407                                 pos->x, pos->y);
 408                         fflush(stdout);
 409                 }
 410                 return NULL;
 411         }
 412
 413         if (is_within(&tree->pos, corner)) {
 414                 vector_sub(pos, &tree->pos, &tmp);
 415                 distance = vector_abs(&tmp);
 416                 nearest = tree;
 417         } else {
 418                 nearest = NULL;
 419         }
 420
 421         directions = quadrants_to_search(tree, corner);
 422
 423         for (i = 0; i < 4; i++) {
 424                 if (!tree->child[i])
 425                         continue;
 426
 427 /*
 428                 if (!(directions & (1 << i)))
 429                         continue;
 430 */
 431                 node = quadtree_find_nearest(tree->child[i], pos, corner);
 432
 433                 if (!node)
 434                         continue;
 435
 436                 vector_sub(pos, &node->pos, &tmp);
 437                 dist = vector_abs(&tmp);
 438
 439                 if (!nearest || dist < distance) {
 440                         nearest = node;
 441                         distance = dist;
 442
 443                 }
 444         }
 445
 446         if (nearest && !is_within(&nearest->pos, corner)) {
 447                 if (debug)
 448                         printf("Node %p (%f %f) is not within "
 449                                 "search window (%f %f) (%f %f)\n",
 450                                 nearest, nearest->pos.x, nearest->pos.y,
 451                                 corner[0].x, corner[0].y,
 452                                 corner[1].x, corner[1].y);
 453                 return NULL;
 454         }
 455
 456         return nearest;
 457 }
 458
 459 static struct quadtree *quadtree_find_nearest_noparent(struct quadtree *tree,
 460                                                 struct vector *pos,
 461                                                 struct vector *corner)
 462 {
 463         struct quadtree *nearest;
 464         struct vector sub;
 465         struct quadtree *node;
 466         double dist = 0, dist2;
 467         int i;
 468
 469         nearest = quadtree_find_nearest(tree, pos, corner);
 470
 471         if (nearest != tree)
 472                 goto out;
 473
 474         if (debug)
 475                 printf("Avoiding parent or NULL node %p\n", nearest);
 476
 477         /*
 478          * oops, we don't want to pick the parent node, let's choose
 479          * another one
 480          */
 481         nearest = NULL;
 482         for (i = 0; i < 4; i++) {
 483                 if (!tree->child[i])
 484                         continue;
 485
 486                 if (!nearest) {
 487                         nearest = quadtree_find_nearest(tree->child[i], pos,
 488                                                         corner);
 489
 490                         if (nearest == NULL)
 491                                 continue;
 492
 493                         vector_sub(pos, &nearest->pos, &sub);
 494                         dist = vector_abs(&sub);
 495                         continue;
 496                 }
 497                 node = quadtree_find_nearest(tree->child[i],
 498                                         pos, corner);
 499
 500                 if (node == NULL)
 501                         continue;
 502
 503                 vector_sub(pos, &node->pos, &sub);
 504                 dist2 = vector_abs(&sub);
 505
 506                 if (dist2 < dist) {
 507                         nearest = node;
 508                         dist = dist2;
 509                 }
 510         }
 511
 512 out:
 513         return nearest;
 514 }
 515
 516 static void get_middle_point(struct vector *corner, struct vector *middle)
 517 {
 518         middle->x = (corner[0].x + corner[1].x) / (double)2;
 519         middle->y = (corner[0].y + corner[1].y) / (double)2;
 520 }
 521
 522 static int quadtree_split_by_node(struct quadtree *node,
 523                                 struct vector *corner, int dir)
 524 {
 525         if (!is_within(&node->pos, corner)) {
 526                 if (debug)
 527                         printf("Not within search rectangle\n");
 528                 return 0;
 529         }
 530
 531         switch (dir) {
 532         case QUADTREE_UPLEFT:
 533                 corner[0] = node->pos;
 534                 break;
 535         case QUADTREE_UPRIGHT:
 536                 corner[0].y = node->pos.y;
 537                 corner[1].x = node->pos.x;
 538                 break;
 539         case QUADTREE_DOWNRIGHT:
 540                 corner[1] = node->pos;
 541                 break;
 542         case QUADTREE_DOWNLEFT:
 543                 corner[0].x = node->pos.x;
 544                 corner[1].y = node->pos.y;
 545                 break;
 546         default:
 547                 trap();
 548         }
 549
 550         if (debug)
 551                 printf("Search rectangle is now (%f %f) (%f %f), (%f %f)\n",
 552                         corner[0].x, corner[0].y,
 553                         corner[1].x, corner[1].y,
 554                         node->pos.x, node->pos.y);
 555
 556         if ((corner[0].x < corner[1].x) ||
 557             (corner[0].y < corner[1].y))
 558                 trap();
 559
 560         return 1;
 561 }
 562
 563 /*
 564  * Quickly detach a node from a tree. Move all child nodes under
 565  * @parent node.
 566  */
 567 static int _quadtree_del(struct quadtree *node, struct quadtree *parent)
 568 {
 569         struct quadtree *n;
 570         int i;
 571
 572         /* Detach from the tree */
 573         if (node->parent)
 574                 for (i = 0; i < 4; i++) {
 575                         if (node->parent->child[i] == node) {
 576                                 node->parent->child[i] = 0;
 577                                 break;
 578                         }
 579                 }
 580
 581         if (i == 4)
 582                 trap();
 583
 584
 585         for (i = 0; i < 4; i++) {
 586                 if (!node->child[i])
 587                         continue;
 588
 589                 n = node->child[i];
 590                 _quadtree_del(n, parent);
 591                 _quadtree_add(parent, n);
 592         }
 593
 594         return 0;
 595 }
 596
 597 /**
 598  * Move everything under @tree node to @parent node, everything
 599  * else except the @tree node itself
 600  */
 601 static int optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
 602                         struct vector *corner_orig,
 603                         struct quadtree_ops *ops)
 604 {
 605         struct vector corner[2], mid;
 606         struct quadtree *t, *tmp;
 607         int moved = 0;
 608
 609         get_middle_point(corner_orig, &mid);
 610         t = quadtree_find_nearest_noparent(tree, &mid, corner_orig);
 611
 612         if (!t) {
 613                 if (debug)
 614                         printf("Cannot find nearest node\n");
 615
 616                 goto out;
 617         }
 618
 619         /*
 620          * Now we have the t node which contains the object of the
 621          * spatial middle coordinates of the tree.
 622          */
 623
 624         if (debug) {
 625                 printf("Relocating node %p (%f %f) under parent %p\n", t,
 626                         t->pos.x, t->pos.y, parent);
 627                 printf("There are %ld child nodes left\n", tree->children);
 628                 fflush(stdout);
 629         }
 630         _quadtree_del(t, tree);
 631         quadtree_add(parent, t, ops);
 632
 633         moved++;
 634         tree->children--;
 635         if (!tree->children)
 636                 goto out;
 637
 638         /*
 639          * Now split the search rectangle in quadtres and do the same
 640          * with all of the quarters.
 641          */
 642
 643         corner[0] = corner_orig[0];
 644         corner[1] = corner_orig[1];
 645         if (quadtree_split_by_node(t, corner, QUADTREE_UPLEFT))
 646                 moved += optimally_move_tree(tree, parent, corner, ops);
 647
 648         corner[0] = corner_orig[0];
 649         corner[1] = corner_orig[1];
 650         if (quadtree_split_by_node(t, corner, QUADTREE_UPRIGHT))
 651                 moved += optimally_move_tree(tree, parent, corner, ops);
 652
 653         corner[0] = corner_orig[0];
 654         corner[1] = corner_orig[1];
 655         if (quadtree_split_by_node(t, corner, QUADTREE_DOWNLEFT))
 656                 moved += optimally_move_tree(tree, parent, corner, ops);
 657
 658         corner[0] = corner_orig[0];
 659         corner[1] = corner_orig[1];
 660         if (quadtree_split_by_node(t, corner, QUADTREE_DOWNRIGHT))
 661                 moved += optimally_move_tree(tree, parent, corner, ops);
 662
 663         get_middle_point(corner_orig, &mid);
 664         tmp = quadtree_find_nearest(tree, &mid, corner_orig);
 665         if (tmp && tmp != tree)
 666                 trap();
 667
 668 out:
 669         if (debug)
 670                 printf("Now moved %d nodes, %ld left\n", moved, tree->children);
 671
 672         return moved;
 673 }
 674
 675 /*
 676  * quadtree_del - Detach a node from the tree
 677  *
 678  * Return value: The new root node of the tree. If we are detaching
 679  * anything but the root node of the entire tree, the returned root
 680  * value will be the original root of the tree.
 681  */
 682 struct quadtree *quadtree_del(struct quadtree *node,
 683                               struct quadtree_ops *ops)
 684 {
 685         struct quadtree *parent = NULL;
 686         struct vector corner[2];
 687         int i, children = node->children, moved;
 688
 689         validate_tree(node);
 690
 691         if (debug) {
 692                 printf("Deleting node %p under parent %p\n",
 693                                node, node->parent);
 694                 printf("Relocating %ld children\n", node->children);
 695                 fflush(stdout);
 696         }
 697
 698         if (!node->parent) {
 699                 /*
 700                  * We are deleting the root node. This means we have
 701                  * to select a new root node and reconstruct the
 702                  * entire tree under it again.
 703                  */
 704                 if (debug) {
 705                         printf("Deleting root node\n");
 706                         fflush(stdout);
 707                 }
 708                 for (i = 0; i < 4; i++) {
 709                         if (!node->child[i])
 710                                 continue;
 711
 712                         parent = node->child[i];
 713                         _quadtree_del(parent, node);
 714                         parent->parent = 0;
 715                         quadtree_recalculate_parent_stats(parent, ops);
 716                         break;
 717                 }
 718         } else {
 719                 /*
 720                  * The node has a parent. Detach the node from it and
 721                  * relocate the children.
 722                  */
 723
 724                 for (i = 0; i < 4; i++) {
 725                         if (node->parent->child[i] == node) {
 726                                 node->parent->child[i] = 0;
 727                                 break;
 728                         }
 729                 }
 730                 if (i == 4)
 731                         trap();
 732
 733                 parent = node->parent;
 734
 735                 /*
 736                  * The sub branch is now detached from the main
 737                  * tree. Fix the stats.
 738                  */
 739                 quadtree_recalculate_parent_stats(node->parent, ops);
 740         }
 741
 742         validate_tree(parent);
 743
 744         if (!node->children)
 745                 goto out;
 746         /*
 747          * Now we are ready to prepare for relocating the nodes under
 748          * the parent.
 749          */
 750
 751         quadtree_get_tree_dimensions(node, corner);
 752         moved = optimally_move_tree(node, parent, corner, ops);
 753
 754         if (debug) {
 755                 if (moved != children) {
 756                         printf("Got %d children but %d were moved\n",
 757                                 children, moved);
 758                         printf("nearest children left:\n");
 759                         for (i = 0 ; i < 4; i++)
 760                                 if (node->child[i])
 761                                         printf("   node %d %p, (%f %f)\n",
 762                                                 i, node->child[i],
 763                                                 node->child[i]->pos.x,
 764                                                 node->child[i]->pos.y);
 765                         fflush(stdout);
 766                         trap();
 767                 }
 768                 printf("Delete done, returning parent %p\n", parent);
 769                 fflush(stdout);
 770         }
 771
 772 out:
 773         validate_tree(parent);
 774         return quadtree_find_parent(parent);
 775 }
 776
 777 static void check_for_crossed_subnodes(struct quadtree *node,
 778                                 struct vector *limit, struct quadtree_ops *ops)
 779 {
 780         int direction = 0, i;
 781         int up = 0, left = 0, right = 0, down = 0;
 782
 783         for (i = 0; i < 2; i++) {
 784                 if (limit[i].x < node->pos.x)
 785                         left = 1;
 786                 else
 787                         right = 1;
 788                 if (limit[i].y < node->pos.y)
 789                         up = 1;
 790                 else
 791                         down = 1;
 792         }
 793
 794         if (left || up)
 795                 direction |= QUADTREE_UPLEFT;
 796         if (right || up)
 797                 direction |= QUADTREE_UPRIGHT;
 798         if (left || down)
 799                 direction |= QUADTREE_DOWNLEFT;
 800         if (right || down)
 801                 direction |= QUADTREE_DOWNRIGHT;
 802         if ((left && right) || (up && down))
 803                 direction |= QUADTREE_SELF;
 804
 805         if ((direction & QUADTREE_UPLEFT) && node->child[0])
 806                 check_for_crossed_subnodes(node->child[0], limit, ops);
 807
 808         if ((direction & QUADTREE_UPRIGHT) && node->child[1])
 809                 check_for_crossed_subnodes(node->child[0], limit, ops);
 810
 811         if ((direction & QUADTREE_DOWNLEFT) && node->child[2])
 812                 check_for_crossed_subnodes(node->child[0], limit, ops);
 813
 814         if ((direction & QUADTREE_DOWNRIGHT) && node->child[3])
 815                 check_for_crossed_subnodes(node->child[0], limit, ops);
 816
 817         if (direction & QUADTREE_SELF) {
 818                 struct quadtree *parent;
 819
 820                 parent = quadtree_del(node, ops);
 821                 quadtree_add(parent, node, ops);
 822         }
 823 }
 824
 825 struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
 826                         struct quadtree_ops *ops)
 827 {
 828         struct quadtree *parent, *tree_parent;
 829         int modify;
 830
 831         /* Check if we have crossed any of the parents */
 832         parent = node->parent;
 833         while (parent) {
 834                 if (node->pos.x < parent->pos.x && new_pos.x > parent->pos.x)
 835                         modify = 1;
 836                 if (node->pos.x > parent->pos.x && new_pos.x < parent->pos.x)
 837                         modify = 1;
 838                 if (node->pos.y < parent->pos.y && new_pos.y > parent->pos.y)
 839                         modify = 1;
 840                 if (node->pos.y > parent->pos.y && new_pos.y < parent->pos.y)
 841                         modify = 1;
 842
 843                 if (!modify) {
 844                         parent = parent->parent;
 845                         continue;
 846                 }
 847
 848                 /*
 849                  * If the node has crossed the boundaries, remove it
 850                  * from the tree and add it again to it. It is then
 851                  * guaranteed to be in the correct position of the
 852                  * tree.
 853                  */
 854                 tree_parent = quadtree_del(node, ops);
 855                 node->pos = new_pos;
 856                 quadtree_add(tree_parent, node, ops);
 857                 return tree_parent;
 858         }
 859
 860         /* Move the node into its new location */
 861         node->pos = new_pos;
 862
 863         if(node->children) {
 864                 /*
 865                  * Now, search the subtree for any children that are
 866                  * located in wrong place and move them into correct
 867                  * place within the tree.
 868                  */
 869                 struct vector limit[2];
 870
 871                 limit[0] = node->pos;
 872                 limit[1] = new_pos;
 873                 check_for_crossed_subnodes(node, limit, ops);
 874         }
 875
 876         return quadtree_find_parent(node);
 877
 878 }
 879
 880 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
 881 {
 882         int direction, count = 0;
 883
 884         direction = it->direction(head, (struct quadtree_iterator *)it);
 885
 886         if ((direction & QUADTREE_UPLEFT) && head->child[0])
 887                 count += _walk_tree(head->child[0], it);
 888
 889         if ((direction & QUADTREE_UPRIGHT) && head->child[1])
 890                 count += _walk_tree(head->child[1], it);
 891
 892         if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
 893                 count += _walk_tree(head->child[2], it);
 894
 895         if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
 896                 count += _walk_tree(head->child[3], it);
 897
 898         if ((direction & QUADTREE_SELF) && it->callback) {
 899                 it->callback(head, (struct quadtree_iterator *)it);
 900                 count++;
 901         }
 902
 903         return count;
 904 }
 905
 906 int walk_quadtree(const struct quadtree_iterator *it)
 907 {
 908         return _walk_tree(it->head, it);
 909 }