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          * Corner points that indicate the space that is covered by
  28          * the tree. Upper left and lower right points are stored.
  29          */
  30         struct vector corner[2];
  31 };
  32
  33 struct quadtree_ops {
  34         /*
  35          * Calculates required statistical information for a node
  36          */
  37         void (*recalculate_stats)(struct quadtree *node);
  38 };
  39
  40 static inline void init_quadtree(struct quadtree *t)
  41 {
  42         memset(t, 0, sizeof(*t));
  43 }
  44
  45 #define QUADTREE_UPLEFT         0x1
  46 #define QUADTREE_UPRIGHT        0x2
  47 #define QUADTREE_DOWNLEFT       0x4
  48 #define QUADTREE_DOWNRIGHT      0x8
  49 #define QUADTREE_SELF           0x10
  50
  51 struct quadtree_iterator {
  52         struct quadtree *head;
  53         void *ptr;
  54
  55         int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
  56         void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
  57 };
  58
  59 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
  60                               struct quadtree_ops *ops);
  61
  62 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
  63 struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
  64                         struct quadtree_ops *ops);
  65
  66 int walk_quadtree(const struct quadtree_iterator *iterator);
  67
  68
  69 /* quadtree_find_parent - return the highest parent of the node */
  70 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
  71 {
  72         struct quadtree *t = (struct quadtree *)node;
  73         while (t->parent)
  74                 t = t->parent;
  75
  76         return t;
  77 }
  78
  79 #endif