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

   1 #ifndef _QUADTREE_H_
   2 #define _QUADTREE_H_
   3
   4 #include <string.h>
   5
   6 #include "utils.h"
   7 #include "vector.h"
   8
   9 struct quadtree {
  10         struct vector pos;
  11
  12         /*
  13          * Each node divide the sub-tree in following quadtrants:
  14          *
  15          *       up left (0)  |  up right (1)
  16          *      -----------------------------
  17          *      down left (2) | down right (3)
  18          */
  19         struct quadtree *child[4];
  20         struct quadtree *parent;
  21
  22         /* statistics */
  23         long int children;      /* The total number of children */
  24         long int depth;         /* The deepest subtree branch */
  25 };
  26
  27 struct quadtree_ops {
  28         /*
  29          * Calculates required statistical information for a node
  30          */
  31         void (*recalculate_stats)(struct quadtree *node);
  32 };
  33
  34 static inline void init_quadtree(struct quadtree *t)
  35 {
  36         memset(t, 0, sizeof(*t));
  37 }
  38
  39 #define QUADTREE_UPLEFT         0x1
  40 #define QUADTREE_UPRIGHT        0x2
  41 #define QUADTREE_DOWNLEFT       0x4
  42 #define QUADTREE_DOWNRIGHT      0x8
  43 #define QUADTREE_SELF           0x10
  44
  45 struct quadtree_iterator {
  46         struct quadtree *head;
  47         void *ptr;
  48
  49         int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
  50         void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
  51 };
  52
  53 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
  54                               struct quadtree_ops *ops);
  55
  56 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
  57 struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
  58                         struct quadtree_ops *ops);
  59
  60 int walk_quadtree(const struct quadtree_iterator *iterator);
  61
  62
  63 /* quadtree_find_parent - return the highest parent of the node */
  64 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
  65 {
  66         struct quadtree *t = (struct quadtree *)node;
  67         while (t->parent)
  68                 t = t->parent;
  69
  70         return t;
  71 }
  72
  73 /*
  74  * Recursively walk through the tree and propagate changes made to the
  75  * given node up until the highest parent.
  76  */
  77 static inline void quadtree_recalculate_parent_stats(struct quadtree *node,
  78                                                      struct quadtree_ops *ops)
  79 {
  80         int i;
  81
  82         while (node) {
  83                 node->depth = 0;
  84                 node->children = 0;
  85
  86                 for (i = 0; i < 4; i++) {
  87                         if (!node->child[i])
  88                                 continue;
  89
  90                         node->depth = MAX(node->depth,
  91                                           node->child[i]->depth + 1);
  92                         node->children += node->child[i]->children + 1;
  93                 }
  94
  95                 if (ops->recalculate_stats)
  96                         ops->recalculate_stats(node);
  97
  98                 node = node->parent;
  99         }
 100 }
 101
 102 #endif