1 /*
2 XBubble - path_init.c
3
4 Copyright (C) 2002 Ivan Djelic <ivan@savannah.gnu.org>
5 Copyright (C) 2003 Martin Quinson <mquinson@savannah.gnu.org>
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21
22 #include <stdio.h>
23
24 #include <string.h>
25 #include <math.h>
26 #include <assert.h>
27
28 #include "utils.h"
29 #include "setting.h"
30 #include "bubble.h"
31 #include "cell.h"
32
33 static int debug=1; /* To control the verbosity of the cache creation stuff */
34
35 /* xbubble_path_cache is what this program builds.
36 Fake definition here to break dependency loop, to compile cell.c
37 (which we need to load to get low level stuff, and which loads the result
38 of this program by declaring 'extern int xbubble_path_cache') */
39 int xbubble_path_cache[2][ROWS][NB_ANGLES][2][TRAJ_MAX_LENGTH];
40
41
42 /* We use a cache to compute quickly were a launched ball will land */
43 typedef struct {
44 Vector neighbor;
45 Vector position;
46 } LaunchPath;
47
48
cellXY(CellArray ca,double x,double y)49 static int cellXY( CellArray ca, double x, double y ) {
50 double rx, ry;
51 int column, row, rest, a, b, c, e;
52 e = ca->parity;
53 rx = (x-(e+1.0)/4);
54 ry = 2*ROW_HEIGHT*(y-0.5) + 1;
55 a = (int) floor(rx+ry);
56 b = (int) floor(ry-rx);
57 c = (int) floor(2*x + (1-e)/2);
58 row = (a+b)/3;
59 rest = e*(row%2);
60 column = (c+rest)>>1;
61 return cellCL( ca, row, column );
62 }
63
64 /* Algorithm for the target cell finding:
65 (applied for each possible angle in target_cell_init() to fill the cache in)
66
67 While the bubble did not reach the top:
68 Compute the next segment the ball will cover, ie the position on which it will either
69 stick on the ceiling (and end of the algorithm) or bump against a wall (before
70 covering yet another segment
71
72 Clip the searched area for colliding balls for efficiency
73
74 For each ball in the covered area:
75 if the trajectory of the ball touches the ball,
76 store where, and after which distance on the segment
77
78 Sort the array of reached position by lenght of the covered area
79
80 Put it in the cache of paths.
81
82 */
83 typedef struct {
84 int neighbor; /* pos of the neighbor */
85 int position; /* where to go if neighbor is there */
86 double dist; /* Y distance covered on the segment to get there */
87 } possible_target_t;
88
89 /**
90 * possible_target_cmp:
91 *
92 * Helping function of cell_path_init() to qsort() between the different possible
93 * target and get the closer one (which will be kept)
94 */
possible_target_cmp(const void * a,const void * b)95 int possible_target_cmp(const void *a, const void *b) { /* used to qsort */
96 return ((possible_target_t*)a)->dist < ((possible_target_t*)b)->dist ? -1 :
97 (((possible_target_t*)a)->dist > ((possible_target_t*)b)->dist ? 1 : 0);
98 }
99
100
101
102
103 /**
104 * compute_one_traj:
105 *
106 * FIXME: TODO
107 * Compute one of the trajectories
108
109 void compute_one_traj(int parity, int ceiling, int angle) {
110 }
111 */
112
113 /**
114 * path_init:
115 *
116 * Computes the caches of trajectories path
117 */
path_init(void)118 void path_init( void ) {
119 int angle, i, ceiling,parity;
120 double cdist= COLLISION_DIST*COLLISION_DIST; /* square of the collision distance */
121 CellArray ca;
122 Vector neighbor, position;
123
124 /* malloc the tables */
125
126 neighbor = vector_new(25);
127 position = vector_new(25);
128 ca=cell_array_new(1);
129
130 /* for each parity */
131 for (parity=0;parity<2;parity++){
132 ca->parity *= -1; /* parity=0 => ca->parity=-1; p=1 => ca->p=1 */
133 printf(" /* parity=%d */ {\n", parity);
134
135 for (ceiling=0; ceiling<ROWS ; ceiling++) {
136 ca->first_row=ceiling;
137 printf(" /* ceiling=%d */ {\n",ceiling);
138 for (angle=0; angle<NB_ANGLES; angle++) {
139 double vx,vy; /* speed (ie, direction) of the bubble */
140 double v2; /* square bubble velocity */
141 double xt,yt; /* position of the target */
142 double xb,yb; /* position of segment begin */
143 double xe,ye; /* position of segment end */
144 double xc; /* temp for x position. */
145
146 double half_range; /* horizontal cross-section of bubble sweeping area */
147 int min_col, max_col, min_row, max_row; /* area searched for colision */
148 int col,row; /* position of currently searched */
149 int cell,first_col; /* position of the corner of the searched area */
150 double xa,ya; /* pos of the ball with which we may collide */
151 double dp; /* dot product: used to check if we approach or leave the considered ball */
152 double seg_len; /* length of this segment */
153 int ceiling_pos=OUT_OF_BOUNDS; /* position to get when sticked to the ceiling */
154
155 int bouncing; /* set to 0 when stick to the top */
156
157 if (debug) fprintf(stderr,"PARITY=%d(%c); CEILING=%d; ANGLE=%d:",parity,parity==0?'-':'+',ceiling,angle);
158 printf(" /* angle=%d */ {\n",angle);
159
160 vector_empty(neighbor);
161 vector_empty(position);
162
163 vx = LAUNCHING_SPEED * sin( (angle-CANON_ANGLE_MAX)*ANGLE_STEP );
164 vy = LAUNCHING_SPEED * - cos( (angle-CANON_ANGLE_MAX)*ANGLE_STEP );
165
166 half_range = sqrt( 1 + vx*vx/vy/vy );
167 bouncing=1;
168 xb=CANON_X;
169 yb=CANON_Y;
170 v2 = vx*vx + vy*vy;
171
172 while (bouncing) {
173 possible_target_t targets[NB_CELLS];
174 int target_count=0;
175
176 /* Where would be the ball at the level of the ceiling when going that direction? */
177 xc = xb + ( ceiling_y(ca) - yb )*vx/vy;
178 if ( xc < 0.5 ) { /* Too left: hits the wall before */
179 xe = 0.5;
180 ye = yb + ( xe - xb )*vy/vx;
181 } else if ( xc > COLS - 0.5 ) { /* Too right: hits wall */
182 // xe = 2*COLS - 1.0 - xc; /* always stay inside board cells */
183 xe = COLS - 0.5; /* always stay inside board cells */
184 ye = yb + ( xe - xb )*vy/vx;
185 } else { /* bubble hits ceiling: this segment is the last one */
186 bouncing = 0;
187 xe = xc;
188 ye = (0.5 + ceiling*ROW_HEIGHT);
189 ceiling_pos=cellXY( ca, xe, ye );
190 }
191 if (debug>1) fprintf(stderr,"[%.1f;%.1f -> %.1f;%.1f;vx=%f;vy=%f]\n",xb,yb,xe,ye,vx,vy);
192 seg_len = ( ye - yb )/vy; /* segment length */
193
194 /* now scan cells and look for any colliding bubble */
195
196 /* try to minimize row range */
197 max_row = clip( (int) floor( yb / ROW_HEIGHT ) + 1, 0, ROWS-1 );
198 min_row = clip( (int) floor( ye / ROW_HEIGHT ) - 1, 0, ROWS-1 );
199 if (debug>1) fprintf(stderr,"Rows=%d-%d\n",min_row,max_row);
200 /* scan from bottom to top */
201 for ( row = max_row; row >= min_row; row-- ) {
202 cell = COLS*row;
203 /* column range */
204 first_col = row_start( ca, row); /* 0 when parity=1; 1 when parity=-1 */
205 /* xc = intersection between row and bubble trajectory */
206 xc = xb + ( row*ROW_HEIGHT + 0.5 - yb )*vx/vy - ( 1.0 - first_col )/2;
207 /* restrict cell scan to a small horizontal range : */
208 min_col = clip( (int) floor( xc - half_range +1 ), first_col, COLS-1 );
209 max_col = clip( (int) floor( xc + half_range ), first_col, COLS-1 );
210 if (debug>1)
211 fprintf(stderr,"Row=%d; first_col=%d; half_range=%.1f;xc=%.1f Cols=%d-%d\n",
212 row, first_col, half_range,xc,min_col,max_col);
213
214 for ( col = min_col; col <= max_col; col++ ) {
215 /* We have a potential collider in cell[col+cell], let's call it 'A'.
216 We now check if A will intersect our bubble (let's call it 'M').
217
218 let's compute ( xa, ya ) = location of bubble A */
219 cell_center( ca, col + cell, &xa, &ya );
220 if (debug>1) fprintf(stderr,"%d (%.1f;%.1f)=>",col+cell,xa,ya);
221
222 /* dot product: used to check if bubble M is approaching
223 or leaving bubble A (hence the ( dp > 0 ) test ) */
224 dp = vx*( xa - xb ) + vy*( ya - yb );
225
226 if ( dp > 0 ) {
227 /* Let v be the velocity vector of bubble M.
228 Let theta = angle(v,MA).
229 Then, let H be the
230 orthogonal projection of A on (M,v):
231
232 A
233 +
234 /|
235 / |
236 / |
237 / |
238 / |
239 / |_
240 M +->..|.|..........
241 v H
242
243 There will be a collision if AH <= 1.
244 Thus, we compute AH using a vector product :
245
246 vp = | v /\ MA | = |v.MA.sin(theta)|
247
248 Since v and MA are in the same plane we have:
249
250 vp = | vy*( xa - xb ) - vx*( ya - yb ) |
251
252 AH = |MA.sin(theta)| = vp/v
253
254 But instead of computing v = sqrt(v2), we compute
255 vp2 = vp.vp = v2.AH.AH, such that :
256
257 AH = sqrt( vp2 / v2 )
258
259 Now the test AH <= 1 becomes vp2 <= v2.
260 */
261 double vp, vp2;
262
263 vp = vy*( xa - xb ) - vx*( ya - yb );
264 vp2 = vp*vp;
265
266 /*
267 Strictly speaking, if AH <= 1 then bubbles will intersect.
268 But we relax this condition for easier aiming:
269 AH <= COLLISION_DIST
270 */
271 if ( vp2 <= cdist*v2 ) {
272 double dist;
273 /*
274 We have a collision. But where will M be when it
275 touches A ? In point T = M + dist.v :
276 ( T is on (M,v), between M and H and such that
277 TA = COLLISION_DIST )
278 */
279 dist = ( dp - sqrt( v2*cdist - vp2 ) )/v2;
280 if (debug>1) fprintf(stderr,"(d=%f) ",dist);
281 if (dist >= 0 && dist <= seg_len) {
282 xt = xb + vx*dist;
283 yt = yb + vy*dist;
284
285 // if (xt < 0.5) xt=1-xt;
286 // if (xt > COLS - 0.5001) xt = 2*COLS - 1.0002 - xt;
287 targets[target_count].neighbor=col+cell;
288 targets[target_count].position=cellXY( ca, xt, yt );
289 targets[target_count].dist=dist;
290 if (targets[target_count].position == -1) {
291 if (debug>1) {
292 fprintf(stderr,"Pos (%.1f;%.1f) => -1 because of %d\n",xt,yt,col+cell);
293 }
294 if (debug>2) abort();
295 } else {
296 target_count++;
297 }
298 if (debug>1) fprintf(stderr,"%d\n",targets[target_count-1].position);
299 } else {if (debug>1) fprintf (stderr,"dist=%.1f<0;\n",dist); }
300 } else {if (debug>1) fprintf (stderr,"too far;\n");}
301 } else { if (debug>1) fprintf (stderr,"dp=%.1f<0;{vx=%.1f,xa-xb=%.1f;vy=%.1f,ya-yb=%.1f}\n",dp,vx,xa-xb,vy,ya-yb); }
302 }
303 }
304 /* sort out the targets found on this segment, and push them to the cache */
305 qsort(targets,target_count, sizeof(possible_target_t),&possible_target_cmp);
306 for (i=0; i<target_count; i++) {
307 vector_push(neighbor, targets[i].neighbor);
308 vector_push(position, targets[i].position);
309
310 // printf(" ,%d,%d",targets[i].neighbor,targets[i].position);
311 // printf(" vector_push(path[%d][%d][% 3d].neighbor, %d);\t",
312 // parity%2,ceiling,angle, targets[i].neighbor);
313 // printf("vector_push(path[%d][%d][% 3d].position, %d);\n",
314 // parity%2,ceiling,angle, targets[i].position);
315 if (debug) fprintf (stderr, " (%d,%d)", targets[i].neighbor, targets[i].position);
316 }
317
318 /* prepare for next segment */
319 if (bouncing) {
320 vx *= -1;
321 xb = xe;
322 yb = ye;
323 } else {
324
325 // vector_push(neighbor, OUT_OF_BOUNDS);
326 // vector_push(position, ceiling_pos);
327
328 // printf(" ,%d,%d);\n",OUT_OF_BOUNDS,ceiling_pos);
329
330 // printf(" vector_push(path[%d][%d][% 3d].neighbor, %d);\t",
331 // parity%2,ceiling,angle, OUT_OF_BOUNDS);
332 // printf("vector_push(path[%d][%d][% 3d].position, %d);\n\n",
333 // parity%2,ceiling,angle, ceiling_pos);
334
335 // vector_push(path[parity%2][ceiling][angle].neighbor, OUT_OF_BOUNDS);
336 // vector_push(path[parity%2][ceiling][angle].position, ceiling_pos);
337 if (debug) fprintf (stderr, " (###,%d)\n", ceiling_pos);
338 }
339 }
340 /* There is no new segment: Output the traj. */
341
342 if (neighbor->size >= TRAJ_MAX_LENGTH)
343 fail("the constant TRAJ_MAX_LENGTH is too small (%d=<%d). Please edit setting.h",
344 TRAJ_MAX_LENGTH,neighbor->size);
345
346 printf(" /* neighbor */ {");
347 for (i=0;i<TRAJ_MAX_LENGTH; i++){
348 printf(" %-2d%c",
349 (i<neighbor->size ? neighbor->element[i] :
350 (i==neighbor->size ? OUT_OF_BOUNDS : 0 )),
351 (i<TRAJ_MAX_LENGTH-1?',':' '));
352 }
353 printf("},\n");
354
355 printf(" /* position */ {");
356 for (i=0;i<TRAJ_MAX_LENGTH; i++){
357 printf(" %-2d%c",
358 (i<position->size ? position->element[i] :
359 (i==position->size ? ceiling_pos : 0 )),
360 (i<TRAJ_MAX_LENGTH-1?',':' '));
361 }
362 printf("}\n");
363
364 printf(" }%c /* angle=%d */%c\n",
365 angle < NB_ANGLES-1 ? ',' : ' ',
366 angle,
367 angle < NB_ANGLES-1 ? '\n' : ' ');
368 }
369 printf(" }%c /* ceiling=%d */%c\n",
370 ceiling < ROWS-1 ? ',' : ' ',
371 ceiling,
372 ceiling < ROWS-1 ? '\n' : ' ');
373 }
374 printf(" }%c /* parity=%d */\n", (parity == 0 ? ',' : ' '), parity);
375 }
376
377
378 cell_array_free(ca);
379 vector_free(neighbor);
380 vector_free(position);
381 }
382
main()383 int main() {
384 printf("/* This file is generated. Do not edit */\n");
385 printf("/* Here are the trajectories as computed at compilation time */\n\n");
386
387 printf("/* parity x ceiling x angle x { neighbor; position } x { several positions } */\n\n");
388 printf("int xbubble_path_cache[2][%d][%d][2][%d] = {\n",ROWS,NB_ANGLES,TRAJ_MAX_LENGTH);
389 path_init();
390 printf("}; /* path */\n");
391 return 0;
392 }
393
394