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