4 // Copyright (C) 2006 Matthias Braun <matze@braunis.de>
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.
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.
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
23 #include "collision_grid.hpp"
25 #include "collision.hpp"
27 #include "collision_grid_iterator.hpp"
29 static const float DELTA = .001;
31 CollisionGrid::CollisionGrid(float newwidth, float newheight)
32 : width(newwidth), height(newheight), cell_width(128), cell_height(128),
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);
40 CollisionGrid::~CollisionGrid()
42 for(GridEntries::iterator i = grid.begin(); i != grid.end(); ++i) {
43 GridEntry* entry = *i;
45 GridEntry* nextentry = entry->next;
53 CollisionGrid::add_object(MovingObject* object)
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)
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;
72 const Rect& 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 log_warning << "Object out of range: " << gridx << ", " << gridy << std::endl;
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;
91 CollisionGrid::remove_object(MovingObject* object)
93 ObjectWrapper* wrapper = 0;
94 for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) {
95 if((*i)->object == object) {
102 assert(wrapper != 0);
105 log_warning << "Tried to remove nonexistant object" << std::endl;
110 const Rect& 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 log_warning << "Object out of range: " << gridx << ", " << gridy << std::endl;
120 remove_object_from_gridcell(gridy*cells_x + gridx, wrapper);
128 CollisionGrid::move_object(ObjectWrapper* wrapper)
130 // FIXME not optimal yet... should leave the gridcells untouched that don't
131 // need to be changed.
132 const Rect& 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 log_warning << "Object out of range: " << gridx << ", " << gridy << std::endl;
142 remove_object_from_gridcell(gridy*cells_x + gridx, wrapper);
146 const Rect& 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 log_warning << "Object out of range: " << gridx << ", " << gridy << std::endl;
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;
164 wrapper->dest = nbbox;
168 CollisionGrid::check_collisions()
170 std::vector<ObjectWrapper*> moved_objects;
173 CollisionGridIterator iter(*this, Sector::current()->get_active_region());
174 while(ObjectWrapper* wrapper = iter.next_wrapper()) {
175 MovingObject* object = wrapper->object;
176 if(!object->is_valid())
178 if(object->get_group() == COLGROUP_DISABLED) {
179 object->bbox.move(object->movement);
180 object->movement = Vector(0, 0);
181 moved_objects.push_back(wrapper);
186 Sector::current()->collision_tilemap(object, 0);
188 collide_object(wrapper);
190 if(object->movement != Vector(0, 0)) {
191 object->bbox.move(object->movement);
192 object->movement = Vector(0, 0);
193 moved_objects.push_back(wrapper);
198 for(std::vector<ObjectWrapper*>::iterator i = moved_objects.begin();
199 i != moved_objects.end(); ++i) {
205 CollisionGrid::collide_object(ObjectWrapper* wrapper)
207 iterator_timestamp++;
209 const Rect& bbox = wrapper->object->bbox;
210 for(float y = bbox.p1.y - cell_height; y < bbox.p2.y + cell_height; y += cell_height) {
211 for(float x = bbox.p1.x - cell_width; x < bbox.p2.x + cell_width; x += cell_width) {
212 int gridx = int(x / cell_width);
213 int gridy = int(y / cell_height);
214 if(gridx < 0 || gridy < 0
215 || gridx >= int(cells_x) || gridy >= int(cells_y)) {
216 //log_warning << "Object out of range: " << gridx << ", " << gridy << std::endl;
220 for(GridEntry* entry = grid[gridy*cells_x + gridx]; entry;
221 entry = entry->next) {
222 ObjectWrapper* wrapper2 = entry->object_wrapper;
223 // only check each object once (even if it is in multiple cells)
224 if(wrapper2->timestamp == iterator_timestamp)
226 // don't collide with objects we already collided with
227 if(wrapper2->id <= wrapper->id)
230 wrapper->timestamp = iterator_timestamp;
231 collide_object_object(wrapper, wrapper2);
238 CollisionGrid::collide_object_object(ObjectWrapper* wrapper,
239 ObjectWrapper* wrapper2)
242 MovingObject* object1 = wrapper->object;
243 MovingObject* object2 = wrapper2->object;
245 Rect dest1 = object1->get_bbox();
246 dest1.move(object1->get_movement());
247 Rect dest2 = object2->get_bbox();
248 dest2.move(object2->get_movement());
250 Vector movement = object1->get_movement() - object2->get_movement();
251 if(Collision::rectangle_rectangle(hit, dest1, movement, dest2)) {
252 HitResponse response1 = object1->collision(*object2, hit);
254 HitResponse response2 = object2->collision(*object1, hit);
256 if(response1 != CONTINUE) {
257 if(response1 == ABORT_MOVE)
258 object1->movement = Vector(0, 0);
259 if(response2 == CONTINUE)
260 object2->movement += hit.normal * (hit.depth + DELTA);
261 } else if(response2 != CONTINUE) {
262 if(response2 == ABORT_MOVE)
263 object2->movement = Vector(0, 0);
264 if(response1 == CONTINUE)
265 object1->movement += -hit.normal * (hit.depth + DELTA);
267 object1->movement += -hit.normal * (hit.depth/2 + DELTA);
268 object2->movement += hit.normal * (hit.depth/2 + DELTA);
274 CollisionGrid::remove_object_from_gridcell(int gridcell, ObjectWrapper* wrapper)
276 GridEntry* lastentry = 0;
277 GridEntry* entry = grid[gridcell];
280 if(entry->object_wrapper == wrapper) {
282 grid[gridcell] = entry->next;
284 lastentry->next = entry->next;
294 log_warning << "Couldn't find object in cell" << std::endl;