4 // Copyright (C) 2005 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"
24 #include "collision.hpp"
26 #include "collision_grid_iterator.hpp"
28 static const float DELTA = .001;
30 CollisionGrid::CollisionGrid(float newwidth, float newheight)
31 : width(newwidth), height(newheight), cell_width(128), cell_height(128),
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);
39 CollisionGrid::~CollisionGrid()
41 for(GridEntries::iterator i = grid.begin(); i != grid.end(); ++i) {
42 GridEntry* entry = *i;
44 GridEntry* nextentry = entry->next;
52 CollisionGrid::add_object(MovingObject* object)
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)
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;
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";
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;
90 CollisionGrid::remove_object(MovingObject* object)
92 ObjectWrapper* wrapper = 0;
93 for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) {
94 if((*i)->object == object) {
101 assert(wrapper != 0);
104 std::cerr << "Tried to remove nonexistant object!\n";
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";
119 remove_object_from_gridcell(gridy*cells_x + gridx, wrapper);
127 CollisionGrid::move_object(ObjectWrapper* wrapper)
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";
141 remove_object_from_gridcell(gridy*cells_x + gridx, wrapper);
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";
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;
163 wrapper->dest = nbbox;
167 CollisionGrid::check_collisions()
169 std::vector<ObjectWrapper*> moved_objects;
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())
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);
185 Sector::current()->collision_tilemap(object, 0);
187 collide_object(wrapper);
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);
197 for(std::vector<ObjectWrapper*>::iterator i = moved_objects.begin();
198 i != moved_objects.end(); ++i) {
204 CollisionGrid::collide_object(ObjectWrapper* wrapper)
206 iterator_timestamp++;
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";
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)
225 // don't collide with objects we already collided with
226 if(wrapper2->id <= wrapper->id)
229 wrapper->timestamp = iterator_timestamp;
230 collide_object_object(wrapper, wrapper2);
237 CollisionGrid::collide_object_object(ObjectWrapper* wrapper,
238 ObjectWrapper* wrapper2)
241 MovingObject* object1 = wrapper->object;
242 MovingObject* object2 = wrapper2->object;
244 Rect dest1 = object1->get_bbox();
245 dest1.move(object1->get_movement());
246 Rect dest2 = object2->get_bbox();
247 dest2.move(object2->get_movement());
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);
253 HitResponse response2 = object2->collision(*object1, hit);
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);
266 object1->movement += -hit.normal * (hit.depth/2 + DELTA);
267 object2->movement += hit.normal * (hit.depth/2 + DELTA);
273 CollisionGrid::remove_object_from_gridcell(int gridcell, ObjectWrapper* wrapper)
275 GridEntry* lastentry = 0;
276 GridEntry* entry = grid[gridcell];
279 if(entry->object_wrapper == wrapper) {
281 grid[gridcell] = entry->next;
283 lastentry->next = entry->next;
293 std::cerr << "Couldn't find object in cell.\n";