src/collision_grid.cpp

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