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