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
24 #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 std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
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 std::cerr << "Tried to remove nonexistant object!\n";
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 std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
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 std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
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 std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
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;
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_flags() & GameObject::FLAG_NO_COLLDET) {
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);
196 for(std::vector<ObjectWrapper*>::iterator i = moved_objects.begin();
197 i != moved_objects.end(); ++i) {
203 CollisionGrid::collide_object(ObjectWrapper* wrapper)
205 iterator_timestamp++;
207 const Rect& 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";
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)
224 // don't collide with objects we already collided with
225 if(wrapper2->id <= wrapper->id)
228 wrapper->timestamp = iterator_timestamp;
229 collide_object_object(wrapper, wrapper2);
236 CollisionGrid::collide_object_object(ObjectWrapper* wrapper,
237 ObjectWrapper* wrapper2)
240 MovingObject* object1 = wrapper->object;
241 MovingObject* object2 = wrapper2->object;
243 Rect dest1 = object1->get_bbox();
244 dest1.move(object1->get_movement());
245 Rect dest2 = object2->get_bbox();
246 dest2.move(object2->get_movement());
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);
252 HitResponse response2 = object2->collision(*object1, hit);
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);
265 object1->movement += -hit.normal * (hit.depth/2 + DELTA);
266 object2->movement += hit.normal * (hit.depth/2 + DELTA);
272 CollisionGrid::remove_object_from_gridcell(int gridcell, ObjectWrapper* wrapper)
274 GridEntry* lastentry = 0;
275 GridEntry* entry = grid[gridcell];
278 if(entry->object_wrapper == wrapper) {
280 grid[gridcell] = entry->next;
282 lastentry->next = entry->next;
292 std::cerr << "Couldn't find object in cell.\n";