4 #include "collision_grid.h"
5 #include "special/collision.h"
7 #include "collision_grid_iterator.h"
9 static const float DELTA = .001;
11 CollisionGrid::CollisionGrid(float newwidth, float newheight)
12 : width(newwidth), height(newheight), cell_width(128), cell_height(128),
15 cells_x = size_t(width / cell_width) + 1;
16 cells_y = size_t(height / cell_height) + 1;
17 grid.resize(cells_x * cells_y);
20 CollisionGrid::~CollisionGrid()
22 for(GridEntries::iterator i = grid.begin(); i != grid.end(); ++i) {
23 GridEntry* entry = *i;
25 GridEntry* nextentry = entry->next;
33 CollisionGrid::add_object(MovingObject* object)
36 // make sure the object isn't already in the grid
37 for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) {
38 ObjectWrapper* wrapper = *i;
39 if(wrapper->object == object)
45 ObjectWrapper* wrapper = new ObjectWrapper;
46 wrapper->object = object;
47 wrapper->timestamp = 0;
48 wrapper->dest = object->bbox;
49 objects.push_back(wrapper);
50 wrapper->id = objects.size()-1;
52 const Rectangle& bbox = object->bbox;
53 for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
54 for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
55 int gridx = int(x / cell_width);
56 int gridy = int(y / cell_height);
57 if(gridx < 0 || gridy < 0
58 || gridx >= int(cells_x) || gridy >= int(cells_y)) {
59 std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
62 GridEntry* entry = new GridEntry;
63 entry->object_wrapper = wrapper;
64 entry->next = grid[gridy*cells_x + gridx];
65 grid[gridy*cells_x + gridx] = entry;
71 CollisionGrid::remove_object(MovingObject* object)
73 ObjectWrapper* wrapper = 0;
74 for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) {
75 if((*i)->object == object) {
85 std::cerr << "Tried to remove nonexistant object!\n";
90 const Rectangle& bbox = wrapper->dest;
91 for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
92 for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
93 int gridx = int(x / cell_width);
94 int gridy = int(y / cell_height);
95 if(gridx < 0 || gridy < 0
96 || gridx >= int(cells_x) || gridy >= int(cells_y)) {
97 std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
100 remove_object_from_gridcell(gridy*cells_x + gridx, wrapper);
108 CollisionGrid::move_object(ObjectWrapper* wrapper)
110 // FIXME not optimal yet... should leave the gridcells untouched that don't
111 // need to be changed.
112 const Rectangle& obbox = wrapper->dest;
113 for(float y = obbox.p1.y; y < obbox.p2.y; y += cell_height) {
114 for(float x = obbox.p1.x; x < obbox.p2.x; x += cell_width) {
115 int gridx = int(x / cell_width);
116 int gridy = int(y / cell_height);
117 if(gridx < 0 || gridy < 0
118 || gridx >= int(cells_x) || gridy >= int(cells_y)) {
119 std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
122 remove_object_from_gridcell(gridy*cells_x + gridx, wrapper);
126 const Rectangle& nbbox = wrapper->object->bbox;
127 for(float y = nbbox.p1.y; y < nbbox.p2.y; y += cell_height) {
128 for(float x = nbbox.p1.x; x < nbbox.p2.x; x += cell_width) {
129 int gridx = int(x / cell_width);
130 int gridy = int(y / cell_height);
131 if(gridx < 0 || gridy < 0
132 || gridx >= int(cells_x) || gridy >= int(cells_y)) {
133 std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
137 GridEntry* entry = new GridEntry;
138 entry->object_wrapper = wrapper;
139 entry->next = grid[gridy*cells_x + gridx];
140 grid[gridy*cells_x + gridx] = entry;
144 wrapper->dest = nbbox;
148 CollisionGrid::check_collisions()
150 std::vector<ObjectWrapper*> moved_objects;
152 CollisionGridIterator iter(*this, Sector::current()->get_active_region());
153 while(ObjectWrapper* wrapper = iter.next_wrapper()) {
154 MovingObject* object = wrapper->object;
155 if(!object->is_valid())
157 if(object->get_flags() & GameObject::FLAG_NO_COLLDET) {
158 object->bbox.move(object->movement);
159 object->movement = Vector(0, 0);
160 moved_objects.push_back(wrapper);
165 Sector::current()->collision_tilemap(object, 0);
167 collide_object(wrapper);
169 if(object->movement != Vector(0, 0)) {
170 object->bbox.move(object->movement);
171 object->movement = Vector(0, 0);
172 moved_objects.push_back(wrapper);
176 for(std::vector<ObjectWrapper*>::iterator i = moved_objects.begin();
177 i != moved_objects.end(); ++i) {
183 CollisionGrid::collide_object(ObjectWrapper* wrapper)
185 iterator_timestamp++;
187 const Rectangle& bbox = wrapper->object->bbox;
188 for(float y = bbox.p1.y - cell_height; y < bbox.p2.y + cell_height; y += cell_height) {
189 for(float x = bbox.p1.x - cell_width; x < bbox.p2.x + cell_width; x += cell_width) {
190 int gridx = int(x / cell_width);
191 int gridy = int(y / cell_height);
192 if(gridx < 0 || gridy < 0
193 || gridx >= int(cells_x) || gridy >= int(cells_y)) {
194 //std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
198 for(GridEntry* entry = grid[gridy*cells_x + gridx]; entry;
199 entry = entry->next) {
200 ObjectWrapper* wrapper2 = entry->object_wrapper;
201 // only check each object once (even if it is in multiple cells)
202 if(wrapper2->timestamp == iterator_timestamp)
204 // don't collide with objects we already collided with
205 if(wrapper2->id <= wrapper->id)
208 wrapper->timestamp = iterator_timestamp;
209 collide_object_object(wrapper, wrapper2);
216 CollisionGrid::collide_object_object(ObjectWrapper* wrapper,
217 ObjectWrapper* wrapper2)
220 MovingObject* object1 = wrapper->object;
221 MovingObject* object2 = wrapper2->object;
223 Rectangle dest1 = object1->get_bbox();
224 dest1.move(object1->get_movement());
225 Rectangle dest2 = object2->get_bbox();
226 dest2.move(object2->get_movement());
228 Vector movement = object1->get_movement() - object2->get_movement();
229 if(Collision::rectangle_rectangle(hit, dest1, movement, dest2)) {
230 HitResponse response1 = object1->collision(*object2, hit);
232 HitResponse response2 = object2->collision(*object1, hit);
234 if(response1 != CONTINUE) {
235 if(response1 == ABORT_MOVE)
236 object1->movement = Vector(0, 0);
237 if(response2 == CONTINUE)
238 object2->movement += hit.normal * (hit.depth + DELTA);
239 } else if(response2 != CONTINUE) {
240 if(response2 == ABORT_MOVE)
241 object2->movement = Vector(0, 0);
242 if(response1 == CONTINUE)
243 object1->movement += -hit.normal * (hit.depth + DELTA);
245 object1->movement += -hit.normal * (hit.depth/2 + DELTA);
246 object2->movement += hit.normal * (hit.depth/2 + DELTA);
252 CollisionGrid::remove_object_from_gridcell(int gridcell, ObjectWrapper* wrapper)
254 GridEntry* lastentry = 0;
255 GridEntry* entry = grid[gridcell];
258 if(entry->object_wrapper == wrapper) {
260 grid[gridcell] = entry->next;
262 lastentry->next = entry->next;
272 std::cerr << "Couldn't find object in cell.\n";