1 /*
2 * SDL Graphics Extension
3 * Collision routines
4 *
5 * Started 000625
6 *
7 * License: LGPL v2+ (see the file LICENSE)
8 * (c)1999-2003 Anders Lindstr�m
9 */
10
11 /*********************************************************************
12 * This library is free software; you can redistribute it and/or *
13 * modify it under the terms of the GNU Library General Public *
14 * License as published by the Free Software Foundation; either *
15 * version 2 of the License, or (at your option) any later version. *
16 *********************************************************************/
17
18 #include "SDL.h"
19 #include <stdio.h>
20 #include <string.h>
21 #include <new>
22 #include "sge_collision.h"
23 #include "sge_surface.h"
24 #include "sge_shape.h"
25
26 using namespace std;
27
28 Uint8 sge_mask[8]={SGE_FLAG1,SGE_FLAG2,SGE_FLAG3,SGE_FLAG4,SGE_FLAG5,SGE_FLAG6,SGE_FLAG7,SGE_FLAG8};
29 SDL_Rect _ua;
30 Sint16 _cx=0,_cy=0;
31
32 int memand(Uint8 *s1, Uint8 *s2, int shift1, int shift2, int N);
33
34 //==================================================================================
35 // Makes a new collision map from img. Set colorkey first!
36 //==================================================================================
sge_make_cmap(SDL_Surface * img)37 sge_cdata *sge_make_cmap(SDL_Surface *img)
38 {
39 sge_cdata *cdata;
40 Uint8 *map;
41 Sint16 x,y;
42 Sint32 offs;
43 int i;
44
45 cdata=new(nothrow) sge_cdata;
46 if(!cdata){SDL_SetError("SGE - Out of memory");return NULL;}
47 cdata->w=img->w; cdata->h=img->h;
48 offs=(img->w*img->h)/8;
49 cdata->map=new(nothrow) Uint8[offs+2];
50 if(!cdata->map){SDL_SetError("SGE - Out of memory");return NULL;}
51 memset(cdata->map,0x00,offs+2);
52
53 map=cdata->map;
54
55 i=0;
56 for(y=0; y < img->h; y++){
57 for(x=0; x < img->w; x++){
58 if(i>7){i=0;map++;}
59 if(sge_GetPixel(img, Sint16(x),Sint16(y))!=img->format->colorkey){
60 *map=*map|sge_mask[i];
61 }
62 i++;
63 }
64 }
65 return cdata;
66 }
67
68 //==================================================================================
69 // Checks bounding boxes for collision: 0-no collision 1-collision
70 //==================================================================================
sge_bbcheck(sge_cdata * cd1,Sint16 x1,Sint16 y1,sge_cdata * cd2,Sint16 x2,Sint16 y2)71 int sge_bbcheck(sge_cdata *cd1,Sint16 x1,Sint16 y1, sge_cdata *cd2,Sint16 x2,Sint16 y2)
72 {
73 Sint16 w1=cd1->w;
74 Sint16 h1=cd1->h;
75 Sint16 w2=cd2->w;
76 Sint16 h2=cd2->h;
77
78 if(x1 < x2){
79 if(x1+w1 > x2){
80 if(y1 < y2){
81 if(y1+h1 > y2){
82 _ua.x=x2;
83 _ua.y=y2;
84 return 1;
85 }
86 }
87 else{
88 if(y2+h2 > y1){
89 _ua.x=x2;
90 _ua.y=y1;
91 return 1;
92 }
93 }
94 }
95 }
96 else{
97 if(x2+w2 > x1){
98 if(y2 < y1){
99 if(y2+h2 > y1){
100 _ua.x=x1;
101 _ua.y=y1;
102 return 1;
103 }
104 }
105 else{
106 if(y1+h1 > y2){
107 _ua.x=x1;
108 _ua.y=y2;
109 return 1;
110 }
111 }
112 }
113 }
114
115
116 return 0;
117 }
118
119 //==================================================================================
120 // Checks bounding boxes for collision: 0-no collision 1-collision
121 //==================================================================================
_sge_bbcheck(Sint16 x1,Sint16 y1,Sint16 w1,Sint16 h1,Sint16 x2,Sint16 y2,Sint16 w2,Sint16 h2)122 int _sge_bbcheck(Sint16 x1,Sint16 y1,Sint16 w1,Sint16 h1, Sint16 x2,Sint16 y2,Sint16 w2,Sint16 h2)
123 {
124 if(x1 < x2){
125 if(x1+w1 > x2){
126 if(y1 < y2){
127 if(y1+h1 > y2){
128 _ua.x=x2;
129 _ua.y=y2;
130 return 1;
131 }
132 }
133 else{
134 if(y2+h2 > y1){
135 _ua.x=x2;
136 _ua.y=y1;
137 return 1;
138 }
139 }
140 }
141 }
142 else{
143 if(x2+w2 > x1){
144 if(y2 < y1){
145 if(y2+h2 > y1){
146 _ua.x=x1;
147 _ua.y=y1;
148 return 1;
149 }
150 }
151 else{
152 if(y1+h1 > y2){
153 _ua.x=x1;
154 _ua.y=y2;
155 return 1;
156 }
157 }
158 }
159 }
160
161
162 return 0;
163 }
164
165 //==================================================================================
166 // AND N bits of s1 and s2
167 // Returns the number of the bit (or zero)
168 //==================================================================================
memand(Uint8 * s1,Uint8 * s2,int shift1,int shift2,int N)169 int memand(Uint8 *s1, Uint8 *s2, int shift1, int shift2, int N)
170 {
171 int b,i1=shift1,i2=shift2;
172
173 for(b=0; b<N; b++){
174 if(i1>7){i1=0;s1++;}
175 if(i2>7){i2=0;s2++;}
176 if( (*s1&sge_mask[i1]) && (*s2&sge_mask[i2]) ) return b+1;
177 i1++; i2++;
178 }
179 return 0;
180 }
181
182 //==================================================================================
183 // Checks for pixel perfect collision: 0-no collision 1-collision
184 // sge_bbcheck MUST be called first!!!
185 //==================================================================================
_sge_cmcheck(sge_cdata * cd1,Sint16 x1,Sint16 y1,sge_cdata * cd2,Sint16 x2,Sint16 y2)186 int _sge_cmcheck(sge_cdata *cd1,Sint16 x1,Sint16 y1, sge_cdata *cd2,Sint16 x2,Sint16 y2)
187 {
188 if(cd1->map==NULL || cd2->map==NULL)
189 return 0;
190
191 Sint16 w1=cd1->w;
192 Sint16 h1=cd1->h;
193 Sint16 w2=cd2->w;
194 Sint16 h2=cd2->h;
195
196 //masks
197
198 Sint32 x1o=0,x2o=0,y1o=0,y2o=0,offs; //offsets
199 int i1=0,i2=0;
200
201 Uint8 *map1=cd1->map;
202 Uint8 *map2=cd2->map;
203
204 //Calculate correct starting point
205 if(_ua.x==x2 && _ua.y==y2){
206 x1o=x2-x1;
207 y1o=y2-y1;
208
209 offs=w1*y1o+x1o;
210 map1+=offs/8;
211 i1=offs%8;
212 }
213 else if(_ua.x==x2 && _ua.y==y1){
214 x1o=x2-x1;
215 y2o=y1-y2;
216
217 map1+=x1o/8;
218 i1=x1o%8;
219
220 offs=w2*y2o;
221 map2+=offs/8;
222 i2=offs%8;
223 }
224 else if(_ua.x==x1 && _ua.y==y1){
225 x2o=x1-x2;
226 y2o=y1-y2;
227
228 offs=w2*y2o+x2o;
229 map2+=offs/8;
230 i2=offs%8;
231 }
232 else if(_ua.x==x1 && _ua.y==y2){
233 x2o=x1-x2;
234 y1o=y2-y1;
235
236 offs=w1*y1o;
237 map1+=offs/8;
238 i1=offs%8;
239
240 map2+=x2o/8;
241 i2=x2o%8;
242 }
243 else
244 return 0;
245
246 Sint16 y;
247
248 Sint16 lenght;
249
250 if(x1+w1 < x2+w2)
251 lenght=w1-x1o;
252 else
253 lenght=w2-x2o;
254
255 //AND(map1,map2)
256 for(y=_ua.y; y<=y1+h1 && y<=y2+h2; y++){
257
258 offs=memand(map1,map2,i1,i2,lenght);
259 if(offs){
260 _cx=_ua.x+offs-1; _cy=y;
261 return 1;
262 }
263
264 //goto the new line
265 offs=(y-y1)*w1+x1o;
266 map1=cd1->map; //reset pointer
267 map1+=offs/8;
268 i1=offs%8;
269
270 offs=(y-y2)*w2+x2o;
271 map2=cd2->map; //reset pointer
272 map2+=offs/8;
273 i2=offs%8;
274 }
275
276
277 return 0;
278 }
279
280 //==================================================================================
281 // Checks pixel perfect collision: 0-no collision 1-collision
282 // calls sge_bbcheck automaticly
283 //==================================================================================
sge_cmcheck(sge_cdata * cd1,Sint16 x1,Sint16 y1,sge_cdata * cd2,Sint16 x2,Sint16 y2)284 int sge_cmcheck(sge_cdata *cd1,Sint16 x1,Sint16 y1, sge_cdata *cd2,Sint16 x2,Sint16 y2)
285 {
286 if(!sge_bbcheck(cd1,x1,y1, cd2,x2,y2))
287 return 0;
288
289 if(cd1->map==NULL || cd2->map==NULL)
290 return 1;
291
292 return _sge_cmcheck(cd1,x1,y1, cd2,x2,y2);
293 }
294
295
296 //==================================================================================
297 // Get the position of the last collision
298 //==================================================================================
sge_get_cx(void)299 Sint16 sge_get_cx(void)
300 {
301 return _cx;
302 }
sge_get_cy(void)303 Sint16 sge_get_cy(void)
304 {
305 return _cy;
306 }
307
308
309 //==================================================================================
310 // Removes collision map from memory
311 //==================================================================================
sge_destroy_cmap(sge_cdata * cd)312 void sge_destroy_cmap(sge_cdata *cd)
313 {
314 if(cd->map!=NULL)
315 delete [] cd->map;
316
317 delete cd;
318 }
319
320
321 //==================================================================================
322 // Checks bounding boxes for collision: 0-no collision 1-collision
323 // (sprites)
324 //==================================================================================
325 #ifndef _SGE_NO_CLASSES
sge_bbcheck_shape(sge_shape * shape1,sge_shape * shape2)326 int sge_bbcheck_shape(sge_shape *shape1, sge_shape *shape2)
327 {
328 return _sge_bbcheck(shape1->get_xpos(), shape1->get_ypos(), shape1->get_w(), shape1->get_h(), shape2->get_xpos(), shape2->get_ypos(), shape2->get_w(), shape2->get_h());
329 }
330 #endif
331
332
333 //==================================================================================
334 // Clears an area in a cmap
335 //==================================================================================
sge_unset_cdata(sge_cdata * cd,Sint16 x,Sint16 y,Sint16 w,Sint16 h)336 void sge_unset_cdata(sge_cdata *cd, Sint16 x, Sint16 y, Sint16 w, Sint16 h)
337 {
338 Uint8 *map=cd->map;
339 Sint16 offs,len;
340 int i,n=0;
341
342 offs=y*cd->w + x;
343 map+=offs/8;
344 i=offs%8;
345
346 while(h--){
347 len=w;
348 while(len--){
349 if(i>7){i=0;map++;}
350 *map&=~sge_mask[i];
351 i++;
352 }
353 n++;
354 map=cd->map;
355 offs=(y+n)*cd->w + x;
356 map+=offs/8;
357 i=offs%8;
358 }
359 }
360
361
362 //==================================================================================
363 // Fills an area in a cmap
364 //==================================================================================
sge_set_cdata(sge_cdata * cd,Sint16 x,Sint16 y,Sint16 w,Sint16 h)365 void sge_set_cdata(sge_cdata *cd, Sint16 x, Sint16 y, Sint16 w, Sint16 h)
366 {
367 Uint8 *map=cd->map;
368 Sint16 offs,len;
369 int i,n=0;
370
371 offs=y*cd->w + x;
372 map+=offs/8;
373 i=offs%8;
374
375 while(h--){
376 len=w;
377 while(len--){
378 if(i>7){i=0;map++;}
379 *map|=sge_mask[i];
380 i++;
381 }
382 n++;
383 map=cd->map;
384 offs=(y+n)*cd->w + x;
385 map+=offs/8;
386 i=offs%8;
387 }
388 }
389