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   assert(wrapper != 0);
  82
  83   const Rectangle& bbox = wrapper->dest;
  84   for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
  85     for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
  86       int gridx = int(x / cell_width);
  87       int gridy = int(y / cell_height);
  88       if(gridx < 0 || gridy < 0
  89           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
  90         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
  91         continue;
  92       }
  93       remove_object_from_gridcell(gridy*cells_x + gridx, object);
  94     }
  95   }
  96
  97   delete wrapper;
  98 }
  99
 100 void
 101 CollisionGrid::move_object(MovingObject* object)
 102 {
 103   const Rectangle& bbox = object->bbox;
 104   for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
 105     for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
 106       int gridx = int(x / cell_width);
 107       int gridy = int(y / cell_height);
 108       if(gridx < 0 || gridy < 0
 109           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
 110         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
 111         continue;
 112       }
 113       // TODO
 114     }
 115   }
 116 }
 117
 118 void
 119 CollisionGrid::check_collisions()
 120 {
 121   CollisionGridIterator iter(*this, Sector::current()->get_active_region());
 122   while(ObjectWrapper* wrapper = iter.next_wrapper()) {
 123     MovingObject* object = wrapper->object;
 124     if(!object->is_valid())
 125       continue;
 126     if(object->get_flags() & GameObject::FLAG_NO_COLLDET) {
 127       object->bbox.move(object->movement);
 128       object->movement = Vector(0, 0);
 129       continue;
 130     }
 131
 132     // hack for now...
 133     Sector::current()->collision_tilemap(object, 0);
 134
 135     collide_object(wrapper);
 136
 137     object->bbox.move(object->get_movement());
 138     object->movement = Vector(0, 0);
 139   }
 140 }
 141
 142 void
 143 CollisionGrid::collide_object(ObjectWrapper* wrapper)
 144 {
 145   iterator_timestamp++;
 146
 147   const Rectangle& bbox = wrapper->object->bbox;
 148   for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
 149     for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
 150       int gridx = int(x / cell_width);
 151       int gridy = int(y / cell_height);
 152       if(gridx < 0 || gridy < 0
 153           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
 154         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
 155         continue;
 156       }
 157
 158       for(GridEntry* entry = grid[gridy*cells_x + gridx]; entry;
 159           entry = entry->next) {
 160         ObjectWrapper* wrapper2 = entry->object_wrapper;
 161         // only check each object once (even if it is in multiple cells)
 162         if(wrapper2->timestamp == iterator_timestamp)
 163           continue;
 164         // don't collide with objects we already collided with
 165         if(wrapper2->id <= wrapper->id)
 166           continue;
 167
 168         wrapper->timestamp = iterator_timestamp;
 169         collide_object_object(wrapper, wrapper2);
 170       }
 171     }
 172   }
 173 }
 174
 175 void
 176 CollisionGrid::collide_object_object(ObjectWrapper* wrapper,
 177     ObjectWrapper* wrapper2)
 178 {
 179   CollisionHit hit;
 180   MovingObject* object1 = wrapper->object;
 181   MovingObject* object2 = wrapper2->object;
 182
 183   Rectangle dest1 = object1->get_bbox();
 184   dest1.move(object1->get_movement());
 185   Rectangle dest2 = object2->get_bbox();
 186   dest2.move(object2->get_movement());
 187
 188   Vector movement = object1->get_movement() - object2->get_movement();
 189   if(Collision::rectangle_rectangle(hit, dest1, movement, dest2)) {
 190     HitResponse response1 = object1->collision(*object2, hit);
 191     hit.normal *= -1;
 192     HitResponse response2 = object2->collision(*object1, hit);
 193
 194     if(response1 != CONTINUE) {
 195       if(response1 == ABORT_MOVE)
 196         object1->movement = Vector(0, 0);
 197       if(response2 == CONTINUE)
 198         object2->movement += hit.normal * (hit.depth + DELTA);
 199     } else if(response2 != CONTINUE) {
 200       if(response2 == ABORT_MOVE)
 201         object2->movement = Vector(0, 0);
 202       if(response1 == CONTINUE)
 203         object1->movement += -hit.normal * (hit.depth + DELTA);
 204     } else {
 205       object1->movement += -hit.normal * (hit.depth/2 + DELTA);
 206       object2->movement += hit.normal * (hit.depth/2 + DELTA);
 207     }
 208   }
 209 }
 210
 211 void
 212 CollisionGrid::remove_object_from_gridcell(int gridcell, MovingObject* object)
 213 {
 214   GridEntry* lastentry = 0;
 215   GridEntry* entry = grid[gridcell];
 216
 217   while(entry) {
 218     if(entry->object_wrapper->object == object) {
 219       if(lastentry == 0) {
 220         grid[gridcell] = entry->next;
 221       } else {
 222         lastentry->next = entry->next;
 223       }
 224       delete entry;
 225       return;
 226     }
 227
 228     lastentry = entry;
 229     entry = entry->next;
 230   };
 231
 232   std::cerr << "Couldn't find object in cell.\n";
 233 }
 234