glants_mech/linux/src/octree.c

   1 //
   2 // bsp.cpp
   3 // This may border on octree but they are similar
   4 //
   5 // the goal is to use this code with the pheremones
   6 // when they are dropped by the ants
   7 // if an ant drops 100 pheremones on the way to the nest
   8 // 100 * 500, it would be silly to have to test all of these
   9 // so some algorithm is needed to save cpu time
  10 //
  11 // - the octree is an array of pointers to seperate lists
  12 // - the lists contains the position of the pheremone
  13 // - whenever a pheremone is created, it is added to the list
  14 // - whenever a pheremone is deleted, is is removed from the list
  15 // - whenever the bot moves, he searches the list
  16 // - better than brute force, of course
  17 // - since we are using a hash function, possibly O(1)
  18 //
  19
  20 #include <stdlib.h>
  21 #include <stdio.h>
  22
  23 #include <GL/gl.h>                      // Header File For The OpenGL32 Library
  24 #include <GL/glu.h>                     // Header File For The GLu32 Library
  25
  26
  27 #include "objects.h"
  28 #include "bot.h"
  29 #include "tree.h"
  30 #include "gldrawlib.h"
  31 #include "plist.h"
  32 #include "octree.h"
  33
  34 Octree **pheromone_tree;
  35 Octree **GenerateOctree(void);
  36
  37 //
  38 // CreateOctree
  39 //
  40 Octree *CreateOctree(void)
  41 {
  42         Octree *ptr;
  43         ptr = (Octree *)malloc(sizeof(Octree));
  44
  45         return ptr;
  46
  47 } // end of the function
  48
  49 //
  50 // DeleteOctree
  51 //
  52 void DeleteOctree(Octree **tree_ptr)
  53 {
  54         // delete the lists on the tree
  55         int i;
  56         int max;
  57         max = tree_ptr[0]->max_elements;
  58
  59         for (i = 0; i < max; i++)
  60         {
  61                 DestroyPtrList(tree_ptr[i]->list);
  62
  63         } // end of the for
  64
  65         // have to delete every node individually
  66         for (i = 0; i < max; i++)
  67         {
  68                 free(tree_ptr[i]);
  69         } // end of the for
  70
  71         free(tree_ptr);
  72
  73 } // end of the function
  74
  75 //
  76 // GenerateOctree
  77 //  - struct has xmin,xmax,ymin, ymax
  78 // and a pointer to a list
  79 //
  80 Octree **GenerateOctree(void)
  81 {
  82
  83         float i,j;
  84         float width = 7.5f;
  85         float height = width;   // square grid
  86         float x_min,x_max, y_min, y_max;
  87         int hash_key = 0;
  88         int count = 0;
  89         int z = 0;
  90         int index = 0;
  91         Octree **tree_ptr;
  92
  93         for (i = -30.0f; i < 30.0f; i+= height)
  94                 for (j = -30.0f; j < 30.0f; j+= width)
  95                 {
  96                         count++;
  97                 } // end of the for
  98
  99         // First we have to create an array of pointers
 100         tree_ptr = (Octree **)malloc(count * sizeof(Octree *));
 101
 102         // Create each node
 103         for (index = 0; index < count; index++)
 104                 tree_ptr[index] = CreateOctree();
 105
 106
 107         z = 0;          // reset counter
 108
 109         // populate the tree with data
 110         for (i = -30.0f; i < 30.0f; i+= height)
 111         {
 112                 for (j = -30.0f; j < 30.0f; j+= width)
 113                 {
 114                         x_min = j;
 115                         y_min = i;
 116                         x_max = j + width;
 117                         y_max = i + width;
 118
 119                         tree_ptr[z]->list = CreatePtrList();
 120                         tree_ptr[z]->x_max= x_max;
 121                         tree_ptr[z]->x_min= x_min;
 122                         tree_ptr[z]->y_max = y_max;
 123                         tree_ptr[z]->y_min = y_min;
 124                         tree_ptr[z]->max_elements = count;
 125
 126                         z++;
 127                 } // end of the for
 128
 129         } // end of the for
 130
 131         return tree_ptr;
 132
 133 } // end of the function
 134
 135
 136 //
 137 // InsertOctree
 138 // - insert a pheremone into the tree
 139 //
 140 void InsertOctree(Octree **tree_ptr, StaticBotPtr bot)
 141 {
 142         int i;
 143         float x_min,y_min, x_max, y_max;
 144         int max = tree_ptr[0]->max_elements;
 145
 146         for (i = 0; i < max; i++)
 147         {
 148                 x_min = tree_ptr[i]->x_min;
 149                 x_max = tree_ptr[i]->x_max;
 150                 y_min = tree_ptr[i]->y_min;
 151                 y_max = tree_ptr[i]->y_max;
 152
 153                 if ((bot->position[0] > x_min) &&
 154                         (bot->position[0] < x_max) &&
 155                         (bot->position[2] > y_min) &&
 156                         (bot->position[2] < y_max))
 157                 {
 158                         // in the area add to list
 159                         InsertFront(tree_ptr[i]->list, (StaticBotPtr)bot);
 160                         return;
 161                 } // end of the if
 162
 163         } // end of the for
 164
 165 } // end of the function
 166
 167
 168 //
 169 // SearchListBot
 170 // - search the list for a static bot
 171 //
 172 StaticBotPtr SearchListBot(PtrList *list, DriverBotPtr bot)
 173 {
 174  PtrNode *current_ptr;
 175  StaticBotPtr x;
 176  float x_min, x_max, y_min, y_max;
 177
 178  //if (isempty(list))
 179  //     return NULL;
 180  if (list->head == NULL)
 181    return NULL;
 182
 183  current_ptr = list->head;
 184
 185  while(current_ptr != NULL)
 186  {
 187         // interesting
 188         x = (StaticBotPtr)current_ptr->ptr;
 189
 190         x_min = x->position[0] - (x->size[0]/2.0f);
 191         x_max = x->position[0] + (x->size[0]/2.0f);
 192         y_min = x->position[2] - (x->size[0]/2.0f);
 193         y_max = x->position[2] + (x->size[0]/2.0f);
 194
 195         if ((bot->x > x_min) && (bot->x < x_max) &&
 196                 (bot->y > y_min) && (bot->y < y_max))
 197         {
 198                         return x;
 199         } // end of the if
 200
 201         current_ptr = current_ptr->next;
 202
 203  } // end of while
 204
 205  return NULL;
 206
 207 } // end of the function
 208
 209 //
 210 // SearchOctree
 211 // - check if we are in the region
 212 //
 213 StaticBotPtr SearchOctree(Octree **tree_ptr, DriverBotPtr bot)
 214 {
 215         // find out which bin to search
 216         int i;
 217         float x_min,y_min, x_max, y_max;
 218         int max = tree_ptr[0]->max_elements;
 219
 220         StaticBotPtr res = NULL;
 221
 222         for (i = 0; i < max; i++)
 223         {
 224                 x_min = tree_ptr[i]->x_min;
 225                 x_max = tree_ptr[i]->x_max;
 226                 y_min = tree_ptr[i]->y_min;
 227                 y_max = tree_ptr[i]->y_max;
 228
 229                 if ((bot->x > x_min) &&
 230                         (bot->x < x_max) &&
 231                         (bot->y > y_min) &&
 232                         (bot->y < y_max))
 233                 {
 234                         // in the area add to list
 235                         res = SearchListBot(tree_ptr[i]->list, bot);
 236
 237                         // Search the list in this region
 238                         return res;
 239                 } // end of the if
 240
 241
 242         } // end of the for
 243
 244         return NULL;
 245
 246 } // end of the function
 247
 248 //
 249 // DeleteOctree
 250 // - delete a node from the tree
 251 //
 252 void DeleteOctreeNode(Octree **tree_ptr, StaticBotPtr bot)
 253 {
 254         // find out which bin to search
 255         int i;
 256         float x_min,y_min, x_max, y_max;
 257         int max = tree_ptr[0]->max_elements;
 258
 259         for (i = 0; i < max; i++)
 260         {
 261                 x_min = tree_ptr[i]->x_min;
 262                 x_max = tree_ptr[i]->x_max;
 263                 y_min = tree_ptr[i]->y_min;
 264                 y_max = tree_ptr[i]->y_max;
 265
 266                 if ((bot->position[0] > x_min) &&
 267                         (bot->position[0] < x_max) &&
 268                         (bot->position[2] > y_min) &&
 269                         (bot->position[2] < y_max))
 270                 {
 271
 272                         // delete the node
 273                         DeletePtrNode(tree_ptr[i]->list, bot);
 274
 275                 } // end of the if
 276
 277
 278         } // end of the for
 279
 280 } // end of the function
 281
 282
 283 //
 284 // Wrapper Functions
 285 // - you should probably only have to deal
 286 // with these functions unless you want more
 287 // trees
 288 void pheromoneBuild(void)
 289 {
 290         pheromone_tree = GenerateOctree();
 291 } // end of the function
 292
 293 //
 294 // octreeDestroy
 295 // - make sure this called
 296 //
 297 void pheromoneDestroy(void)
 298 {
 299          DeleteOctree(pheromone_tree);
 300 } // end of the function
 301
 302 //
 303 // pheromoneInsert(StaticBotPtr bot)
 304 //
 305 void pheromoneInsert(StaticBotPtr bot)
 306 {
 307         InsertOctree(pheromone_tree, bot);
 308 }// end of the function
 309
 310 //
 311 // pheromoneSearch
 312 //
 313 StaticBotPtr pheromoneSearch(DriverBotPtr bot)
 314 {
 315         StaticBotPtr ptr;
 316         ptr = SearchOctree(pheromone_tree, bot);
 317
 318         return ptr;
 319 } // end of the function
 320
 321 //
 322 // pheromoneDelete
 323 // - delete a pheromone
 324 //
 325 void pheromoneDelete(StaticBotPtr bot)
 326 {
 327
 328         DeleteOctreeNode(pheromone_tree, bot);
 329
 330 } // end of the function
 331