-Incorporated Marcin Ko��cielnicki patch that reintroduces the flying
[supertux.git] / src / collision_grid.cpp
1 #include <config.h>
2
3 #include <iostream>
4 #include "collision_grid.h"
5 #include "special/collision.h"
6 #include "sector.h"
7 #include "collision_grid_iterator.h"
8
9 static const float DELTA = .001;
10
11 CollisionGrid::CollisionGrid(float newwidth, float newheight)
12   : width(newwidth), height(newheight), cell_width(128), cell_height(128),
13     iterator_timestamp(0)
14 {
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);
18 }
19
20 CollisionGrid::~CollisionGrid()
21 {
22   for(GridEntries::iterator i = grid.begin(); i != grid.end(); ++i) {
23     GridEntry* entry = *i;
24     while(entry) {
25       GridEntry* nextentry = entry->next;
26       delete entry;
27       entry = nextentry;
28     }
29   }
30 }
31
32 void
33 CollisionGrid::add_object(MovingObject* object)
34 {
35 #ifdef DEBUG
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)
40       assert(false);
41   }
42   assert(object != 0);
43 #endif
44   
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;
51   
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";
60         continue;
61       }
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;
66     }
67   }
68 }
69
70 void
71 CollisionGrid::remove_object(MovingObject* object)
72 {
73   ObjectWrapper* wrapper = 0;
74   for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) {
75     if((*i)->object == object) {
76       wrapper = *i;
77       objects.erase(i);
78       break;
79     }
80   }
81   assert(wrapper != 0);
82   
83   const Rectangle& bbox = wrapper->dest;
84   for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
85     for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
86       int gridx = int(x / cell_width);
87       int gridy = int(y / cell_height);
88       if(gridx < 0 || gridy < 0 
89           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
90         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
91         continue;
92       }
93       remove_object_from_gridcell(gridy*cells_x + gridx, object);
94     }
95   }
96
97   delete wrapper;
98 }
99
100 void
101 CollisionGrid::move_object(MovingObject* object)
102 {
103   const Rectangle& bbox = object->bbox;
104   for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
105     for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
106       int gridx = int(x / cell_width);
107       int gridy = int(y / cell_height);
108       if(gridx < 0 || gridy < 0 
109           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
110         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
111         continue;
112       }
113       // TODO
114     }
115   }
116 }
117
118 void
119 CollisionGrid::check_collisions()
120 {
121   CollisionGridIterator iter(*this, Sector::current()->get_active_region());
122   while(ObjectWrapper* wrapper = iter.next_wrapper()) {
123     MovingObject* object = wrapper->object;
124     if(!object->is_valid())
125       continue;
126     if(object->get_flags() & GameObject::FLAG_NO_COLLDET) {
127       object->bbox.move(object->movement);
128       object->movement = Vector(0, 0);
129       continue;
130     }
131
132     // hack for now...
133     Sector::current()->collision_tilemap(object, 0);
134     
135     collide_object(wrapper);
136
137     object->bbox.move(object->get_movement());
138     object->movement = Vector(0, 0);
139   }
140 }
141
142 void
143 CollisionGrid::collide_object(ObjectWrapper* wrapper)
144 {
145   iterator_timestamp++;
146
147   const Rectangle& bbox = wrapper->object->bbox;
148   for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) {
149     for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) {
150       int gridx = int(x / cell_width);
151       int gridy = int(y / cell_height);
152       if(gridx < 0 || gridy < 0 
153           || gridx >= int(cells_x) || gridy >= int(cells_y)) {
154         std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n";
155         continue;
156       }
157   
158       for(GridEntry* entry = grid[gridy*cells_x + gridx]; entry;
159           entry = entry->next) {
160         ObjectWrapper* wrapper2 = entry->object_wrapper;
161         // only check each object once (even if it is in multiple cells)
162         if(wrapper2->timestamp == iterator_timestamp)
163           continue;
164         // don't collide with objects we already collided with
165         if(wrapper2->id <= wrapper->id)
166           continue;
167
168         wrapper->timestamp = iterator_timestamp;
169         collide_object_object(wrapper, wrapper2);
170       }
171     }
172   }
173 }
174
175 void
176 CollisionGrid::collide_object_object(ObjectWrapper* wrapper,
177     ObjectWrapper* wrapper2)
178 {
179   CollisionHit hit;
180   MovingObject* object1 = wrapper->object;
181   MovingObject* object2 = wrapper2->object;
182   
183   Rectangle dest1 = object1->get_bbox();
184   dest1.move(object1->get_movement());
185   Rectangle dest2 = object2->get_bbox();
186   dest2.move(object2->get_movement());
187
188   Vector movement = object1->get_movement() - object2->get_movement();
189   if(Collision::rectangle_rectangle(hit, dest1, movement, dest2)) {
190     HitResponse response1 = object1->collision(*object2, hit);
191     hit.normal *= -1;
192     HitResponse response2 = object2->collision(*object1, hit);
193
194     if(response1 != CONTINUE) {
195       if(response1 == ABORT_MOVE)
196         object1->movement = Vector(0, 0);
197       if(response2 == CONTINUE)
198         object2->movement += hit.normal * (hit.depth + DELTA);
199     } else if(response2 != CONTINUE) {
200       if(response2 == ABORT_MOVE)
201         object2->movement = Vector(0, 0);
202       if(response1 == CONTINUE)
203         object1->movement += -hit.normal * (hit.depth + DELTA);
204     } else {
205       object1->movement += -hit.normal * (hit.depth/2 + DELTA);
206       object2->movement += hit.normal * (hit.depth/2 + DELTA);
207     }
208   }
209 }
210
211 void
212 CollisionGrid::remove_object_from_gridcell(int gridcell, MovingObject* object)
213 {
214   GridEntry* lastentry = 0;
215   GridEntry* entry = grid[gridcell];
216
217   while(entry) {
218     if(entry->object_wrapper->object == object) {
219       if(lastentry == 0) {
220         grid[gridcell] = entry->next;
221       } else {
222         lastentry->next = entry->next;
223       }
224       delete entry;
225       return;
226     }
227
228     lastentry = entry;
229     entry = entry->next;
230   };
231
232   std::cerr << "Couldn't find object in cell.\n";
233 }
234