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