1 /* sdlx - c++ wrapper for libSDL
2 * Copyright (C) 2005-2007 Vladimir Menshakov
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18
19
20 #include "c_map.h"
21 #include "surface.h"
22
23 #include "mrt/logger.h"
24 #include "mrt/file.h"
25
26 #include "math/binary.h"
27 #include "math/matrix.h"
28
29 #if defined(__GNUC__)
30 #define restrict __restrict__
31 #elif !defined(restrict)
32 # define restrict
33 #endif
34
35 using namespace sdlx;
36
CollisionMap()37 CollisionMap::CollisionMap() : _empty(true), _full(false), _w(0), _h(0), _data() {}
38
39
40 //DO NOT USE THIS FUNCTION FOR SIGNED TYPES! :(
41 template <typename T>
type_collide(T * & ptr1,const int shift1,T * & ptr2,const int shift2,const T mask=~(T)0)42 static inline const bool type_collide(T* &ptr1, const int shift1, T* &ptr2, const int shift2, const T mask = ~(T)0) {
43 const T a = (shift1 != 0)?((*ptr1++ << shift1) | (*ptr1 >> (sizeof(T) * 8 - shift1))):*ptr1++;
44 const T b = (shift2 != 0)?((*ptr2++ << shift2) | (*ptr2 >> (sizeof(T) * 8 - shift2))):*ptr2++;
45 return (mask & a & b) != 0;
46 }
47
bitline_collide(const unsigned char * base1,const int size1,const int x1,const unsigned char * base2,const int size2,const int x2,int line_size)48 static inline const bool bitline_collide(
49 const unsigned char *base1, const int size1, const int x1,
50 const unsigned char *base2, const int size2, const int x2,
51 int line_size) {
52 if (size1 <= 0 || size2 <= 0 || line_size <= 0)
53 return false;
54
55 const int shift1 = x1 % 8, pos1 = x1 / 8;
56 const int shift2 = x2 % 8, pos2 = x2 / 8;
57
58 assert((line_size - 1) / 8 + 1 <= size1);
59 assert((line_size - 1) / 8 + 1 <= size2);
60
61 unsigned int *iptr1 = (unsigned int *) (base1 + pos1);
62 unsigned int *iptr2 = (unsigned int *) (base2 + pos2);
63
64 for(; line_size >= 8 * (int)sizeof(int); line_size -= 8 * (int)sizeof(int)) {
65 if (type_collide(iptr1, shift1, iptr2, shift2))
66 return true;
67 }
68
69 Uint8 *ptr1 = (Uint8 *) iptr1;
70 Uint8 *ptr2 = (Uint8 *) iptr2;
71
72 for(; line_size >= 8 * (int)sizeof(Uint8); line_size -= 8 * (int)sizeof(Uint8)) {
73 if (type_collide(ptr1, shift1, ptr2, shift2))
74 return true;
75 }
76
77 if (line_size == 0)
78 return false; //no collision, line_size aligned by 8 bits.
79
80 const Uint8 mask = ~((1 << (8 - line_size)) - 1);
81 //LOG_DEBUG(("a: 0x%x, b: 0x%x, line_size: %d, mask: 0x%x", a, b, line_size, mask));
82 return type_collide(ptr1, shift1, ptr2, shift2, mask);
83 }
84
collides(const sdlx::Rect & src,const CollisionMap * other,const sdlx::Rect & other_src,const int bx,const int by,const bool hidden_by_other) const85 const bool CollisionMap::collides(const sdlx::Rect &src, const CollisionMap *other, const sdlx::Rect &other_src, const int bx, const int by, const bool hidden_by_other) const {
86 if (_empty || other->_empty)
87 return false;
88
89 int aw = (src.w > 0)?src.w:(_w * 8);
90 int ah = (src.h > 0)?src.h:_h;
91
92 int bw = (other_src.w > 0)?other_src.w:(other->_w * 8);
93 int bh = (other_src.h > 0)?other_src.h:other->_h;
94
95 int ax1 = 0 + aw - 1;
96 int ay1 = 0 + ah - 1;
97
98 /*b - bottom right co-ordinates*/
99 int bx1 = bx + bw - 1;
100 int by1 = by + bh - 1;
101
102 int inter_x0, inter_x1, inter_y0, inter_y1;
103
104 /*check if bounding boxes intersect*/
105 if((bx1 < 0) || (ax1 < bx) || (by1 < 0) || (ay1 < by))
106 return false;
107
108 if (_full && other->_full)
109 return true;
110
111
112 inter_x0 = math::max(0, bx);
113 inter_x1 = math::min(ax1, bx1);
114
115 inter_y0 = math::max(0, by);
116 inter_y1 = math::min(ay1, by1);
117
118 //LOG_DEBUG(("%p->collide(%p, src:(%d, %d, %d, %d), osrc:(%d, %d, %d, %d), [%d, %d, %d, %d])", this, other, src.x, src.y, aw, ah, other_src.x, other_src.y, bw, bh, inter_x0, inter_y0, inter_y0, inter_y1));
119
120 unsigned char * restrict ptr1 = (unsigned char *) _data.get_ptr();
121 unsigned char * restrict ptr2 = (unsigned char *) other->_data.get_ptr();
122
123 int size1 = _data.get_size();
124 int size2 = other->_data.get_size();
125
126
127 //you can play with it, but 8 seems optimal for me.
128 #define INTERLACE_STEP 8
129
130 #if INTERLACE_STEP == 16
131 int steps_pos[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
132 #elif INTERLACE_STEP == 8
133 int steps_pos[] = {0, 4, 2, 6, 3, 7, 1, 5};
134 #elif INTERLACE_STEP == 4
135 int steps_pos[] = {0, 2, 1, 3};
136 #elif INTERLACE_STEP == 2
137 int steps_pos[] = {0, 1};
138 #elif INTERLACE_STEP == 1
139 int steps_pos[] = {0};
140 #endif
141
142 /* int steps = 0;
143 int steps_total = (inter_y1 - inter_y0 + 1) * (inter_x1 - inter_x0 + 1);
144 */
145 #define NEW_COLLIDES
146 #ifndef NEW_COLLIDES
147 for(int sy = 0; sy < INTERLACE_STEP; ++sy)
148 for(int sx = 0; sx < INTERLACE_STEP; ++sx)
149 for(int y = inter_y0 + steps_pos[sy]; y <= inter_y1 ; y += INTERLACE_STEP) {
150 const int ybase1 = (src.y + y) * _w;
151 const int ybase2 = (other_src.y + y - by) * other->_w;
152 for(int x = inter_x0 + steps_pos[sx]; x <= inter_x1 ; x += INTERLACE_STEP) {
153 const int pos1 = (src.x + x) / 8 + ybase1;
154 const int pos2 = (other_src.x + x - bx) / 8 + ybase2;
155
156 /*
157 assert(pos1 >= 0 && pos1 < size1);
158 assert(pos2 >= 0 && pos2 < size2);
159 */ //collision detection code works in 99% cases.
160 //this asserts above can be triggered by malicious objects (invalid rectangle returned by get_render_rect)
161 //so skip it. :)
162 if (pos1 < 0 || pos2 < 0)
163 continue;
164
165 if (pos1 >= size1 || pos2 >= size2)
166 break;
167
168 const unsigned char bit1 = 1<<(7 - ((x + src.x) & 7));
169 const unsigned char bit2 = 1<<(7 - ((other_src.x + x - bx) & 7));
170
171 if ( (ptr1[pos1]&bit1) != 0 && (ptr2[pos2]&bit2) != 0) {
172 //LOG_DEBUG(("collision detected: %d of %d : %g%", steps, steps_total, 100.0 * steps / steps_total));
173 return true;
174 }
175 //++steps;
176 }
177 }
178 #else
179 for(int sy = 0; sy < INTERLACE_STEP; ++sy)
180 for(int y = inter_y0 + steps_pos[sy]; y <= inter_y1 ; y += INTERLACE_STEP) {
181 const int ybase1 = (src.y + y) * _w;
182 const int ybase2 = (other_src.y + y - by) * other->_w;
183 if (::bitline_collide(
184 ptr1 + ybase1, size1 - ybase1, src.x + inter_x0,
185 ptr2 + ybase2, size2 - ybase2, other_src.x + inter_x0 - bx ,
186 inter_x1 - inter_x0 + 1
187 ))
188 return true;
189 }
190 #endif
191
192 //LOG_DEBUG(("no collision : %d steps", steps));
193 return false;
194 }
195
196
test_pixel(const sdlx::Surface * surface,const unsigned x,const unsigned y,const CollisionMap::Type type)197 static inline const bool test_pixel(const sdlx::Surface * surface, const unsigned x, const unsigned y, const CollisionMap::Type type) {
198 Uint32 pixelcolor = surface->get_pixel(x, y);
199
200 switch(type) {
201 case CollisionMap::OnlyOpaque:
202 if ((surface->getFlags() & SDL_SRCALPHA) == SDL_SRCALPHA) {
203 Uint8 r, g, b, a;
204 surface->get_rgba(pixelcolor, r, g, b, a);
205 return a == 255;
206 }
207 return (pixelcolor != surface->get_pixel_format()->colorkey);
208
209 case CollisionMap::AnyVisible:
210 if ((surface->getFlags() & SDL_SRCALPHA) == SDL_SRCALPHA) {
211 Uint8 r, g, b, a;
212 surface->get_rgba(pixelcolor, r, g, b, a);
213 return a >= 250;
214 }
215 return (pixelcolor != surface->get_pixel_format()->colorkey);
216 }
217
218 return false;
219 }
220
create(const unsigned int w,const unsigned int h,const bool bit)221 void CollisionMap::create(const unsigned int w, const unsigned int h, const bool bit) {
222 _empty = !bit;
223 _full = bit;
224
225 _w = (w - 1) / 8 + 1;
226 _h = h;
227
228
229 _data.set_size(_w * _h);
230 _data.fill(bit?~0:0);
231 }
232
load(unsigned int w,unsigned int h,const mrt::Chunk & data)233 bool CollisionMap::load(unsigned int w, unsigned int h, const mrt::Chunk &data) {
234 unsigned size = ((w - 1) / 8 + 1) * h;
235 if (size != data.get_size()) {
236 LOG_WARN(("collision data size mismatch. %ux%u = %u, got %u", w, h, size, (unsigned)data.get_size()));
237 return false;
238 }
239
240 _data = data;
241 _w = (w - 1) / 8 + 1;
242 _h = h;
243
244 _empty = _full = true;
245 bool e_set = false, f_set = false;
246 unsigned char * pdata = (unsigned char *)_data.get_ptr();
247 for(unsigned y = 0; y < h; ++y) {
248 unsigned x;
249 for(x = 0; x < w / 8; ++x) {
250 unsigned char b = pdata[y * _w + x];
251 if (b != 0) {
252 _empty = false;
253 e_set = true;
254 } else if (b != 0xff) {
255 _full = false;
256 f_set = true;
257 }
258 if (e_set && f_set)
259 return true;
260 }
261 unsigned w2 = w % 8;
262 if (w2 != 0) {
263 unsigned mask = ~((1 << (7 - w2)) - 1);
264 unsigned char b = pdata[y * _w + x] & mask;
265 if (b != 0) {
266 _empty = false;
267 e_set = true;
268 } else if (b != mask) {
269 _full = false;
270 f_set = true;
271 }
272
273 if (e_set && f_set)
274 return true;
275 }
276 }
277
278 return true;
279 }
280
init(const sdlx::Surface * surface,const Type type)281 void CollisionMap::init(const sdlx::Surface * surface, const Type type) {
282 _empty = true;
283 _full = true;
284 assert(surface->get_width() != 0 && surface->get_height() != 0);
285 _w = (surface->get_width() - 1) / 8 + 1;
286 _h = surface->get_height();
287 _data.set_size(_w * _h);
288 //LOG_DEBUG(("got surface %d %d -> %d %d, allocated: %u bytes", surface->get_width(), surface->get_height(), _w, _h, (unsigned)_data.get_size()));
289 _data.fill(0);
290
291 surface->lock();
292 unsigned char * data = (unsigned char *)_data.get_ptr();
293 for(int y = 0; y < surface->get_height(); ++y) {
294 for(int x = 0; x < surface->get_width(); ++x) {
295 unsigned int b = 7-(x&7);
296 unsigned int pos = y * _w + x / 8;
297 assert(pos < _data.get_size());
298
299 if (test_pixel(surface, x, y, type)) {
300 data[pos] |= (1 << b);
301 _empty = false;
302 } else _full = false;
303 }
304 }
305 surface->unlock();
306 //LOG_DEBUG(("built collision map (size: %u): %s", (unsigned)_data.get_size(), _data.dump().c_str()));
307 //if (_empty)
308 // LOG_DEBUG(("this collision map is empty"));
309 }
310
save(const std::string & fname) const311 void CollisionMap::save(const std::string &fname) const {
312 mrt::File f;
313 f.open(fname, "wb");
314 f.write_all(_data);
315 f.close();
316 }
317
318
project(Matrix<bool> & result,const unsigned w,const unsigned h) const319 void CollisionMap::project(Matrix<bool> &result, const unsigned w, const unsigned h) const {
320 unsigned xs = _w / w, ys = _h / h;
321 if (xs * w != _w || ys * h != _h)
322 throw_ex(("cannot project collision map %dx%d (square size: %dx%d)", _w, _h, xs, ys));
323 result.set_size(h, w, false);
324 unsigned char *ptr = (unsigned char *)_data.get_ptr();
325 unsigned int size = _data.get_size();
326 for(unsigned int y = 0; y < _h; ++y)
327 for(unsigned int x = 0; x < _w; ++x) {
328 assert(x + _w * y < size);
329 if (ptr[x + _w * y])
330 result.set(y / ys, x / xs, true);
331 }
332 }
333