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