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