src/collision_grid.cpp

   1 #include <config.h>
   2
   3 #include <iostream>
   4 #include "collision_grid.h"
   5 #include "special/collision.h"
   6 #include "sector.h"
   7 #include "collision_grid_iterator.h"
   8
   9 static const float DELTA = .001;
  10
  11 CollisionGrid::CollisionGrid(float newwidth, float newheight)
  12   : width(newwidth), height(newheight), cell_width(128), cell_height(128),
  13     iterator_timestamp(0)
  14 {
  15   cells_x = size_t(width / cell_width) + 1;
  16   cells_y = size_t(height / cell_height) + 1;
  17   grid.resize(cells_x * cells_y);
  18 }
  19
  20 CollisionGrid::~CollisionGrid()
  21 {
  22   for(GridEntries::iterator i = grid.begin(); i != grid.end(); ++i) {
  23     GridEntry* entry = *i;
  24     while(entry) {
  25       GridEntry* nextentry = entry->next;
  26       delete entry;
  27       entry = nextentry;
  28     }
  29   }
  30 }
  31
  32 void
  33 CollisionGrid::add_object(MovingObject* object)
  34 {
  35 #ifdef DEBUG
  36   // make sure the object isn't already in the grid
  37   for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) {
  38     ObjectWrapper* wrapper = *i;
  39     if(wrapper->object == object)
  40       assert(false);
  41   }
  42   assert(object != 0);
  43 #endif
  44
  45   ObjectWrapper* wrapper = new ObjectWrapper;
  46   wrapper->object = object;
  47   wrapper->timestamp = 0;
  48   wrapper->dest = object->bbox;
  49   objects.push_back(wrapper);
  50   wrapper->id = objects.size()-1;
  51
  52   const Rectangle& bbox = object->bbox;
  53   for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
  54     for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
  55       int gridx = int(x / cell_width);
  56       int gridy = int(y / cell_height);
  57       if(gridx < 0 || gridy < 0
  58           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
  59         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
  60         continue;
  61       }
  62       GridEntry* entry = new GridEntry;
  63       entry->object_wrapper = wrapper;
  64       entry->next = grid[gridy*cells_x + gridx];
  65       grid[gridy*cells_x + gridx] = entry;
  66     }
  67   }
  68 }
  69
  70 void
  71 CollisionGrid::remove_object(MovingObject* object)
  72 {
  73   ObjectWrapper* wrapper = 0;
  74   for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) {
  75     if((*i)->object == object) {
  76       wrapper = *i;
  77       objects.erase(i);
  78       break;
  79     }
  80   }
  81 #ifdef DEBUG
  82   assert(wrapper != 0);
  83 #else
  84   if(wrapper == 0) {
  85         std::cerr << "Tried to remove nonexistant object!\n";
  86         return;
  87   }
  88 #endif
  89
  90   const Rectangle& bbox = wrapper->dest;
  91   for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
  92     for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
  93       int gridx = int(x / cell_width);
  94       int gridy = int(y / cell_height);
  95       if(gridx < 0 || gridy < 0
  96           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
  97         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
  98         continue;
  99       }
 100       remove_object_from_gridcell(gridy*cells_x + gridx, wrapper);
 101     }
 102   }
 103
 104   delete wrapper;
 105 }
 106
 107 void
 108 CollisionGrid::move_object(ObjectWrapper* wrapper)
 109 {
 110   // FIXME not optimal yet... should leave the gridcells untouched that don't
 111   // need to be changed.
 112   const Rectangle& obbox = wrapper->dest;
 113   for(float y = obbox.p1.y; y < obbox.p2.y; y += cell_height) {
 114     for(float x = obbox.p1.x; x < obbox.p2.x; x += cell_width) {
 115       int gridx = int(x / cell_width);
 116       int gridy = int(y / cell_height);
 117       if(gridx < 0 || gridy < 0
 118           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
 119         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
 120         continue;
 121       }
 122       remove_object_from_gridcell(gridy*cells_x + gridx, wrapper);
 123     }
 124   }
 125
 126   const Rectangle& nbbox = wrapper->object->bbox;
 127   for(float y = nbbox.p1.y; y < nbbox.p2.y; y += cell_height) {
 128     for(float x = nbbox.p1.x; x < nbbox.p2.x; x += cell_width) {
 129       int gridx = int(x / cell_width);
 130       int gridy = int(y / cell_height);
 131       if(gridx < 0 || gridy < 0
 132           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
 133         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
 134         continue;
 135       }
 136
 137       GridEntry* entry = new GridEntry;
 138       entry->object_wrapper = wrapper;
 139       entry->next = grid[gridy*cells_x + gridx];
 140       grid[gridy*cells_x + gridx] = entry;
 141     }
 142   }
 143
 144   wrapper->dest = nbbox;
 145 }
 146
 147 void
 148 CollisionGrid::check_collisions()
 149 {
 150   std::vector<ObjectWrapper*> moved_objects;
 151
 152   CollisionGridIterator iter(*this, Sector::current()->get_active_region());
 153   while(ObjectWrapper* wrapper = iter.next_wrapper()) {
 154     MovingObject* object = wrapper->object;
 155     if(!object->is_valid())
 156       continue;
 157     if(object->get_flags() & GameObject::FLAG_NO_COLLDET) {
 158       object->bbox.move(object->movement);
 159       object->movement = Vector(0, 0);
 160       moved_objects.push_back(wrapper);
 161       continue;
 162     }
 163
 164     // hack for now...
 165     Sector::current()->collision_tilemap(object, 0);
 166
 167     collide_object(wrapper);
 168
 169     if(object->movement != Vector(0, 0)) {
 170       object->bbox.move(object->movement);
 171       object->movement = Vector(0, 0);
 172       moved_objects.push_back(wrapper);
 173     }
 174   }
 175
 176   for(std::vector<ObjectWrapper*>::iterator i = moved_objects.begin();
 177       i != moved_objects.end(); ++i) {
 178     move_object(*i);
 179   }
 180 }
 181
 182 void
 183 CollisionGrid::collide_object(ObjectWrapper* wrapper)
 184 {
 185   iterator_timestamp++;
 186
 187   const Rectangle& bbox = wrapper->object->bbox;
 188   for(float y = bbox.p1.y - cell_height; y < bbox.p2.y + cell_height; y += cell_height) {
 189     for(float x = bbox.p1.x - cell_width; x < bbox.p2.x + cell_width; x += cell_width) {
 190       int gridx = int(x / cell_width);
 191       int gridy = int(y / cell_height);
 192       if(gridx < 0 || gridy < 0
 193           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
 194         //std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
 195         continue;
 196       }
 197
 198       for(GridEntry* entry = grid[gridy*cells_x + gridx]; entry;
 199           entry = entry->next) {
 200         ObjectWrapper* wrapper2 = entry->object_wrapper;
 201         // only check each object once (even if it is in multiple cells)
 202         if(wrapper2->timestamp == iterator_timestamp)
 203           continue;
 204         // don't collide with objects we already collided with
 205         if(wrapper2->id <= wrapper->id)
 206           continue;
 207
 208         wrapper->timestamp = iterator_timestamp;
 209         collide_object_object(wrapper, wrapper2);
 210       }
 211     }
 212   }
 213 }
 214
 215 void
 216 CollisionGrid::collide_object_object(ObjectWrapper* wrapper,
 217     ObjectWrapper* wrapper2)
 218 {
 219   CollisionHit hit;
 220   MovingObject* object1 = wrapper->object;
 221   MovingObject* object2 = wrapper2->object;
 222
 223   Rectangle dest1 = object1->get_bbox();
 224   dest1.move(object1->get_movement());
 225   Rectangle dest2 = object2->get_bbox();
 226   dest2.move(object2->get_movement());
 227
 228   Vector movement = object1->get_movement() - object2->get_movement();
 229   if(Collision::rectangle_rectangle(hit, dest1, movement, dest2)) {
 230     HitResponse response1 = object1->collision(*object2, hit);
 231     hit.normal *= -1;
 232     HitResponse response2 = object2->collision(*object1, hit);
 233
 234     if(response1 != CONTINUE) {
 235       if(response1 == ABORT_MOVE)
 236         object1->movement = Vector(0, 0);
 237       if(response2 == CONTINUE)
 238         object2->movement += hit.normal * (hit.depth + DELTA);
 239     } else if(response2 != CONTINUE) {
 240       if(response2 == ABORT_MOVE)
 241         object2->movement = Vector(0, 0);
 242       if(response1 == CONTINUE)
 243         object1->movement += -hit.normal * (hit.depth + DELTA);
 244     } else {
 245       object1->movement += -hit.normal * (hit.depth/2 + DELTA);
 246       object2->movement += hit.normal * (hit.depth/2 + DELTA);
 247     }
 248   }
 249 }
 250
 251 void
 252 CollisionGrid::remove_object_from_gridcell(int gridcell, ObjectWrapper* wrapper)
 253 {
 254   GridEntry* lastentry = 0;
 255   GridEntry* entry = grid[gridcell];
 256
 257   while(entry) {
 258     if(entry->object_wrapper == wrapper) {
 259       if(lastentry == 0) {
 260         grid[gridcell] = entry->next;
 261       } else {
 262         lastentry->next = entry->next;
 263       }
 264       delete entry;
 265       return;
 266     }
 267
 268     lastentry = entry;
 269     entry = entry->next;
 270   };
 271
 272   std::cerr << "Couldn't find object in cell.\n";
 273 }
 274