1 /*
2 *
3 * Copyright (c) 1994, 2002, 2003 Johannes Prix
4 * Copyright (c) 1994, 2002 Reinhard Prix
5 * Copyright (c) 2004-2010 Arthur Huillet
6 *
7 *
8 * This file is part of Freedroid
9 *
10 * Freedroid is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; either version 2 of the License, or
13 * (at your option) any later version.
14 *
15 * Freedroid is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with Freedroid; see the file COPYING. If not, write to the
22 * Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
23 * MA 02111-1307 USA
24 *
25 */
26
27 /**
28 * This file contains all the functions managing the lighting inside
29 * the FreedroidRPG game window, i.e. the 'light radius' of the Tux and
30 * of other light emanating objects.
31 */
32
33 #define _light_c
34
35 #include "struct.h"
36 #include "global.h"
37 #include "proto.h"
38
39 /* Position and strength of a light source */
40 struct light_source {
41 gps pos;
42 gps vpos;
43 int strength;
44 };
45
46 static struct dynarray light_sources;
47
48 light_radius_config LightRadiusConfig = { -1, -1, -1, -1, 0.0 };
49
50 int *light_strength_buffer = NULL;
51 #define LIGHT_RADIUS_TEXTURE_DIVISOR 10 // Default number of screen pixels per cell
52 #define LIGHT_RADIUS_TEXTURE_MAX_SIZE 64 // texture max size is 64x64
53 #define LIGHT_STRENGTH_CELL(x,y) *(int*)(light_strength_buffer + (y)*LightRadiusConfig.cells_w + (x))
54
55 #define UNIVERSAL_TUX_HEIGHT 100.0 // Empirical Tux height, in the universal coordinate system
56
57 /*
58 * ------------------------------------------------
59 * Foreword to the 'light interpolation' algorithm
60 * ------------------------------------------------
61 *
62 * Some data (such as minimum_light_value) used to create the 'darkness map'
63 * are level dependants. If several levels are displayed (i.e. when Tux is
64 * near a level's border), we want to avoid abrupt light changes at level
65 * boundaries. The call to soften_light_distribution() is not enough to smooth
66 * those changes in a correct way. A better method is to interpolate the level
67 * dependent values near the level boundaries.
68 *
69 * For each tile of the darkness map there are several cases :
70 * 1) the darkness tile is near a boundary's corner, which can be connected to
71 * 0, 1, 2 or 3 neighbors, needing no interpolation or an interpolation
72 * between up to 4 values (barycentric interpolation).
73 * 2) the tile is near a boundary's line, with 0 or 1 neighbor, needing no
74 * no interpolation or an interpolation between 2 values.
75 * 3) the tile is far from any level boundary, so no interpolation is needed.
76 *
77 * Those different cases thus depend on where the darkness tile is, relatively
78 * to the levels boundaries, but they also depend on the levels neighborhood.
79 * Many darkness tiles thus share some properties and interpolation parameters.
80 * The idea is to prepare and store as much knowledge as possible, so that
81 * for each darkness tile we will use a simple switch with 3 cases :
82 * - no interpolation
83 * - interpolation between 2 pre-computed values
84 * - interpolation between 4 pre-computed values
85 *
86 * ==================
87 * Interpolation Mesh
88 * ==================
89 *
90 * We thus have a given DATA (such as 'minimum_light_value'), which has a
91 * specific VALUE on each level. Let's use the following diagram, showing
92 * the 8 potential neighbors around the current level (denoted 'C'):
93 *
94 * +----+----+----+ We call 'c_val', the VALUE of the DATA on the Current level.
95 * | NW | N | NE | We call 'nw_val', the VALUE of the DATA on the North-West
96 * +----+----+----+ neighbor. And so on...
97 * | W | C | E |
98 * +----+----+----+ Conceptually, this defines a "quad-mesh", with a VALUE for
99 * | SW | S | SE | each quad. Our aim is to interpolate those VALUES on the
100 * +----+----+----+ quad-mesh, to have a smooth variation of the DATA.
101 *
102 * However, given the semantic of the DATAs, we only want to interpolate on a
103 * small area near the levels' boundaries. So, we refine *each* quad into a
104 * set of quads (that we will call AREAs):
105 *
106 * | (vc) |(vd)
107 * --+--+------+--+--
108 * | | | | In the central AREA there will be no interpolation.
109 * +--+------+--+
110 * | | (va)| |(vb) In the side AREAs, there will be an interpolation with
111 * | | | | the corresponding direct neighbor.
112 * | | | |
113 * | | (ve)| |(vf) In the corner AREAs, there will be an interpolation
114 * +--+------+--+ with all the surrounding neighbors.
115 * | | | |
116 * --+--+------+--+--
117 * | |
118 *
119 * We now need to define the VALUE of the DATA at each vertex of the AREAs.
120 *
121 * Let's take the north-east corner AREA and the east side AREA as an example.
122 * We call 'A', the VALUE at vertex 'va'.
123 * We call 'B', the VALUE at vertex 'vb', and so on.
124 *
125 * The vertex 'va' is at the boundary of the central AREA. So we have:
126 * A = c_val
127 *
128 * The vertex 'vb' is at a level boundary, that is at *the middle* of the current
129 * level and the eastern neighbor. The VALUE at 'vb' is thus the *middle* of
130 * the VALUE at current level (c_val) and the VALUE at eastern neighbor (e_val).
131 * So we have:
132 * B = 1/2 * (c_val + e_val)
133 *
134 * In the same way, we have:
135 * C = 1/2 * (c_val + n_val)
136 *
137 * The vertex 'vd' is at *the center* of 4 levels, so at the *center* of the
138 * VALUEs of the DATA in those 4 levels. So we have:
139 * D = 1/4 * (c_val + n_val + ne_val + e_val)
140 *
141 * The vertices 've' and 'vf' are equivalent to 'va' and 'vb', so:
142 * E = A = c_val
143 * F = B = 1/2 * (c_val + e_val)
144 *
145 * =============================
146 * Application to "darkness map"
147 * =============================
148 *
149 * To compute the VALUE of the DATA on a specific darkness tile, we need to find
150 * in which AREA the tile is lying. If the tile is:
151 *
152 * - in the central AREA, no interpolation is needed,
153 *
154 * - in a side AREA, we can easily see that we only need an interpolation along
155 * one axis between 2 values (in our east side AREA example, the interpolation
156 * is between the 'A' and 'B' VALUES),
157 *
158 * - in a corner AREA, a 4-values interpolation is needed (in our north-east
159 * corner AREA example, the interpolation is between 'A', 'B', 'C' and 'D').
160 *
161 * As a result, a given level can thus be defined by a 3x3 matrix of data
162 * structures (one per AREA), and for each AREA we have to store the kind of
163 * interpolation to apply, and the VALUEs needed to compute this interpolation.
164 * This data structure is called "Interpolation Data Storage".
165 *
166 * ================================
167 * Interpolation Data Storage (IDS)
168 * ================================
169 *
170 * If we look at our example (east side AREA and north-east corner AREA),
171 * we easily see that the 'B' value is in common to the two AREAs.
172 * In the same way, the 'C' value is in common to the north side AREA and the
173 * north-east corner AREA. And so on...
174 *
175 * The 'A' VALUE (this is the value inside the current level) is common to
176 * every AREA, and will be stored in the central IDS (that is the IDS
177 * associated to the central AREA).
178 *
179 * If we store 'B' in the eastern IDS, and 'C' in the northern IDS, then
180 * only the 'D' VALUE (that is the 'diagonal' value) has to be stored in the
181 * north-eastern IDS. Other values can be retrieved from the other IDSs.
182 *
183 * As a conclusion, for each of the 9 AREAs, we only need to store one VALUE
184 * along with the kind of interpolation to apply.
185 *
186 * Hence the following definitions:
187 *
188 */
189
190 /* Interpolation type: Defines the axis along which an interpolation is needed */
191 enum interpolation_methods {
192 NO_INTERP = 0, // No interpolation is needed
193 ALONG_X = 1, // Interpolation with the neighbor along X axis is needed
194 ALONG_Y = 2, // Interpolation with the neighbor along Y axis is needed
195 ALONG_XY = 3, // ALONG_X | ALONG_Y
196 };
197
198 /* Definition of the Interpolation Data Storage for an interpolation area */
199 struct interpolation_data_cell
200 {
201 /* Interpolation values */
202 float minimum_light_value;
203 float light_bonus;
204
205 /* Interpolation type */
206 enum interpolation_methods interpolation_method;
207
208 /* prepare_light_interpolation() Internal use */
209 float sum;
210 };
211
212 /* Interpolation Data Storage for all interpolation areas */
213 /* (neighbors are defined by "N/C/S" and "W/C/E" indices) */
214 static struct interpolation_data_cell interpolation_data[MAX_LEVELS][3][3];
215
216 /*
217 * This function adds interpolation values to some interpolation
218 * areas.
219 */
add_interpolation_values(int curr_id,int ngb_id,int starty,int endy,int startx,int endx,enum interpolation_methods method)220 static void add_interpolation_values(int curr_id, int ngb_id,
221 int starty, int endy, int startx, int endx, enum interpolation_methods method)
222 {
223 level *ngb_lvl;
224 int x, y;
225
226 if (ngb_id != -1) {
227 ngb_lvl = curShip.AllLevels[ngb_id];
228 for (y=starty; y<=endy; y++) {
229 for (x=startx; x<=endx; x++) {
230 interpolation_data[curr_id][y][x].light_bonus += ngb_lvl->light_bonus;
231 interpolation_data[curr_id][y][x].minimum_light_value += ngb_lvl->minimum_light_value;
232 interpolation_data[curr_id][y][x].sum += 1;
233 interpolation_data[curr_id][y][x].interpolation_method |= method;
234 }
235 }
236 }
237 }
238
239 /*
240 * This function prepares some data structures used later to accelerate the
241 * creation of the 'darkness map'.
242 * This function is called only once per frame.
243 */
prepare_light_interpolation()244 static void prepare_light_interpolation()
245 {
246 int x, y;
247 level *curr_lvl;
248 int curr_id;
249
250 struct visible_level *visible_lvl, *next_lvl;
251
252 // We only care of the visible levels
253
254 BROWSE_VISIBLE_LEVELS(visible_lvl, next_lvl) {
255
256 curr_lvl = visible_lvl->lvl_pointer;
257 curr_id = curr_lvl->levelnum;
258
259 // Step 1
260 // Initialize all interpolation areas with the 'c_val'
261 //
262 for (y = 0; y < 3; y++) {
263 for (x = 0; x < 3; x++) {
264 interpolation_data[curr_id][y][x].light_bonus = curr_lvl->light_bonus;
265 interpolation_data[curr_id][y][x].minimum_light_value = curr_lvl->minimum_light_value;
266 interpolation_data[curr_id][y][x].sum = 1;
267 interpolation_data[curr_id][y][x].interpolation_method = NO_INTERP;
268 }
269 }
270
271 // Step 2
272 // For each existing neighbor, add its data to the related areas
273 //
274 add_interpolation_values(curr_id, NEIGHBOR_ID_N(curr_id), 0, 0, 0, 2, ALONG_Y);
275 add_interpolation_values(curr_id, NEIGHBOR_ID_S(curr_id), 2, 2, 0, 2, ALONG_Y);
276 add_interpolation_values(curr_id, NEIGHBOR_ID_W(curr_id), 0, 2, 0, 0, ALONG_X);
277 add_interpolation_values(curr_id, NEIGHBOR_ID_E(curr_id), 0, 2, 2, 2, ALONG_X);
278 add_interpolation_values(curr_id, NEIGHBOR_ID_NW(curr_id), 0, 0, 0, 0, ALONG_XY);
279 add_interpolation_values(curr_id, NEIGHBOR_ID_NE(curr_id), 0, 0, 2, 2, ALONG_XY);
280 add_interpolation_values(curr_id, NEIGHBOR_ID_SW(curr_id), 2, 2, 0, 0, ALONG_XY);
281 add_interpolation_values(curr_id, NEIGHBOR_ID_SE(curr_id), 2, 2, 2, 2, ALONG_XY);
282
283 // Step 3
284 // Compute the mean of each value
285 //
286 for (y = 0; y < 3; y++) {
287 for (x = 0; x < 3; x++) {
288 interpolation_data[curr_id][y][x].light_bonus /= interpolation_data[curr_id][y][x].sum;
289 interpolation_data[curr_id][y][x].minimum_light_value /= interpolation_data[curr_id][y][x].sum;
290 interpolation_data[curr_id][y][x].sum = 1;
291 }
292 }
293 }
294 } // void prepare_light_interpolation()
295
296 /*
297 * This functions compute the interpolation of the level dependent light values,
298 * at a given gps position.
299 * (for a global comment on light interpolation see 'Foreword to light interpolation
300 * algorithm')
301 *
302 * Some Notes:
303 * 1) The interpolation is computed in an area inside the level's boundaries.
304 * The width of this area is INTERP_WIDTH. If the current point is inside such
305 * an area, an interpolation factor is computed.
306 * The interpolation factor is defined as :
307 * distance_to_level_boundary / INTERP_WIDTH.
308 * The range of this factor is thus [0, 1] ('O' if the point is at the level
309 * boundary).
310 * 2) We assume that the level's size, along one given axis, is always greater
311 * than 2*INTER_WIDTH. We thus never have to interpolate the current level
312 * together with its eastern *and* western neighbors, for example.
313 */
314
interpolate_light_data(gps * pos,struct interpolation_data_cell * data)315 static void interpolate_light_data(gps *pos, struct interpolation_data_cell *data)
316 {
317 # define INTERP_WIDTH 3.0
318 # define INTERP_FACTOR(x) ((x)/INTERP_WIDTH)
319
320 float X = pos->x;
321 float Y = pos->y;
322 int lvl_id = pos->z;
323 level *lvl = curShip.AllLevels[pos->z];
324
325 // Interpolation macros
326
327 # define INTERP_2_VALUES(dir, field) \
328 ( \
329 interp_factor_##dir * center_area->field + \
330 (1.0-interp_factor_##dir) * curr_area->field \
331 )
332
333 # define INTERP_4_VALUES(field) \
334 ( \
335 interp_factor_x * interp_factor_y * center_area->field + \
336 (1.0-interp_factor_x) * interp_factor_y * xborder_area->field + \
337 interp_factor_x * (1.0-interp_factor_y) * yborder_area->field + \
338 (1.0-interp_factor_x) * (1.0-interp_factor_y) * curr_area->field \
339 )
340
341 // Compute the 'N/C/S' and 'W/C/E' indices of the area containing
342 // the current position, compute the interpolation factors,
343 // and get the associated interpolation data cell.
344
345 int area_x = 1; // default value : center
346 int area_y = 1; // default value : center
347 float interp_factor_x = 1.0; // Interpolation factor along X axis
348 float interp_factor_y = 1.0; // Interpolation factor along Y axis
349 struct interpolation_data_cell *curr_area;
350
351 if (X < INTERP_WIDTH) {
352 area_x = 0;
353 interp_factor_x = INTERP_FACTOR(X);
354 } else if (X > (lvl->xlen - INTERP_WIDTH)) {
355 area_x = 2;
356 interp_factor_x = INTERP_FACTOR(lvl->xlen - X);
357 }
358
359 if (Y < INTERP_WIDTH) {
360 area_y = 0;
361 interp_factor_y = INTERP_FACTOR(Y);
362 } else if (Y > (lvl->ylen - INTERP_WIDTH)) {
363 area_y = 2;
364 interp_factor_y = INTERP_FACTOR(lvl->ylen - Y);
365 }
366
367 curr_area = &interpolation_data[lvl_id][area_y][area_x];
368
369 // And now, the interpolation
370
371 switch (curr_area->interpolation_method) {
372 case NO_INTERP:
373 data->minimum_light_value = curr_area->minimum_light_value;
374 data->light_bonus = curr_area->light_bonus;
375 break;
376 case ALONG_X:
377 {
378 struct interpolation_data_cell *center_area = &interpolation_data[lvl_id][1][1];
379 data->minimum_light_value = INTERP_2_VALUES(x, minimum_light_value);
380 data->light_bonus = INTERP_2_VALUES(x, light_bonus);
381 }
382 break;
383 case ALONG_Y:
384 {
385 struct interpolation_data_cell *center_area = &interpolation_data[lvl_id][1][1];
386 data->minimum_light_value = INTERP_2_VALUES(y, minimum_light_value);
387 data->light_bonus = INTERP_2_VALUES(y, light_bonus);
388 }
389 break;
390 default:
391 { // In any other case, a 4-values interpolation was prepared
392 struct interpolation_data_cell *center_area = &interpolation_data[lvl_id][1][1];
393 struct interpolation_data_cell *xborder_area = &interpolation_data[lvl_id][1][area_x];
394 struct interpolation_data_cell *yborder_area = &interpolation_data[lvl_id][area_y][1];
395 data->minimum_light_value = INTERP_4_VALUES(minimum_light_value);
396 data->light_bonus = INTERP_4_VALUES(light_bonus);
397 }
398 break;
399 }
400
401 # undef INTERP_2_VALUES
402 # undef INTERP_4_VALUES
403 # undef INTERP_FACTOR
404 # undef INTERP_WIDTH
405
406 } // static void interpolate_light_data(...)
407
408 /**
409 * Compute the light_radius texture size, and allocate it
410 */
LightRadiusInit()411 void LightRadiusInit()
412 {
413 // Divide to screen dimensions by default divisor, to compute the default
414 // number of cells in the light_radius texture
415 LightRadiusConfig.cells_w = round((float)GameConfig.screen_width / (float)LIGHT_RADIUS_TEXTURE_DIVISOR);
416 LightRadiusConfig.cells_h = round((float)GameConfig.screen_height / (float)LIGHT_RADIUS_TEXTURE_DIVISOR);
417
418 // This will prevent a SIGFPE from happening below
419 if(LightRadiusConfig.cells_w <= 1) LightRadiusConfig.cells_w = 2;
420 if(LightRadiusConfig.cells_h <= 1) LightRadiusConfig.cells_h = 2;
421
422 // Find the the nearest power-of-two greater than of equal to the number of cells
423 // and limit the texture's size
424 int pot_w = pot_gte(LightRadiusConfig.cells_w);
425 if (pot_w > LIGHT_RADIUS_TEXTURE_MAX_SIZE)
426 pot_w = LIGHT_RADIUS_TEXTURE_MAX_SIZE;
427 int pot_h = pot_gte(LightRadiusConfig.cells_h);
428 if (pot_h > LIGHT_RADIUS_TEXTURE_MAX_SIZE)
429 pot_h = LIGHT_RADIUS_TEXTURE_MAX_SIZE;
430
431 if (GameConfig.screen_width >= GameConfig.screen_height) {
432 // Use the whole texture width
433 LightRadiusConfig.cells_w = pot_w;
434 LightRadiusConfig.texture_w = pot_w;
435 // Compute the actual scale factor when using the whole texture width
436 // Note : The flicker-free code will translate the darkness texture.
437 // The translation can be up to one whole cell, so the scale factor
438 // is computed to be one cell wider than needed.
439 LightRadiusConfig.scale_factor = (float)GameConfig.screen_width / (float)(LightRadiusConfig.cells_w - 1);
440 // Since we have an homogeneous scale factor in X and Y,
441 // compute the new number of cells in Y.
442 // Note : Here again, we take into account the translation applied by the
443 // flicker-free code, by adding one more cell.
444 LightRadiusConfig.cells_h = (int)ceilf((float)GameConfig.screen_height / LightRadiusConfig.scale_factor) + 1;
445 // Check if the texture's height is now big enough. If not, take the next power-of-two
446 if (LightRadiusConfig.cells_h <= pot_h)
447 LightRadiusConfig.texture_h = pot_h;
448 else
449 LightRadiusConfig.texture_h = pot_h << 1;
450 } else {
451 // Same thing, if screen's height > screen's width
452 // Is it ever a used screen ratio ? Well, when fdrpg will run on smartphones,
453 // it could be :-)
454 LightRadiusConfig.cells_h = pot_h;
455 LightRadiusConfig.texture_h = pot_h;
456 LightRadiusConfig.scale_factor = (float)GameConfig.screen_height / (float)(LightRadiusConfig.cells_h - 1);
457 LightRadiusConfig.cells_w = (int)ceilf((float)GameConfig.screen_width / LightRadiusConfig.scale_factor) + 1;
458 if (LightRadiusConfig.cells_w <= pot_w)
459 LightRadiusConfig.texture_w = pot_w;
460 else
461 LightRadiusConfig.texture_w = pot_w << 1;
462 }
463
464 // The scale factor has to be an integer (due to a modulo operation in the
465 // flicker-free code).
466 LightRadiusConfig.scale_factor = ceilf(LightRadiusConfig.scale_factor);
467
468 // The center of the light_radius texture will be translated along the Y axe,
469 // to simulate a light coming from bot/tux heads, instead of their feet.
470
471 // First: convert a universal unit into a screen height.
472 // But because the UNIVERSAL_COORD macros currently works only for 4:3 screen,
473 // we take the real screen ration into account
474 //
475 // We should use UNIVERSAL_COORD_H( (GameConfig.screen_width/GameConfig.screen_height) / (4.0/3.0) ),
476 // however it returns 0 instead of 1 for a 640x480 resolution, due to floating point approximations.
477 float unit_screen_height =
478 (((float)GameConfig.screen_width / (float)GameConfig.screen_height) / (4.0 / 3.0)) * ((float)(GameConfig.screen_height) /
479 480.0);
480
481 // Second : transform Tux universal height into screen height
482 LightRadiusConfig.translate_y = (int)(UNIVERSAL_TUX_HEIGHT / unit_screen_height);
483
484 // Allocate the light_radius buffer
485 light_strength_buffer = MyMalloc(LightRadiusConfig.cells_w * LightRadiusConfig.cells_h * sizeof(int));
486
487 } // void LightRadiusInit();
488
489 /**
490 * Clean and deallocate light_radius texture
491 */
LightRadiusClean()492 void LightRadiusClean()
493 {
494 if (light_strength_buffer) {
495 free(light_strength_buffer);
496 light_strength_buffer = NULL;
497 }
498 }
499
add_light_source(gps pos,gps vpos,int strength)500 static void add_light_source(gps pos, gps vpos, int strength)
501 {
502 struct light_source src;
503
504 src.pos = pos;
505 src.vpos = vpos;
506 src.strength = strength;
507
508 dynarray_add(&light_sources, &src, sizeof(src));
509 }
510
511 /**
512 * There might be some obstacles that emit some light. Yet, we can't
513 * go through all the obstacle list of a level every frame at sufficiently
514 * low cost. Therefore we create a reduced list of light emitters for
515 * usage in the light computation code.
516 */
update_light_list()517 void update_light_list()
518 {
519 Level light_level = curShip.AllLevels[Me.pos.z];
520 struct visible_level *visible_lvl, *next_lvl;
521 level *curr_lvl;
522 int curr_id;
523 int glue_index;
524 int light_strength;
525 int obs_index;
526 int map_x, map_y;
527 obstacle *emitter;
528 int blast_idx;
529 gps me_vpos;
530
531 dynarray_init(&light_sources, 10, sizeof(struct light_source));
532
533 // Now we fill in the Tux position as the very first light source, that will
534 // always be present.
535 //
536 light_strength = light_level->light_bonus + Me.light_bonus_from_tux;
537
538 // We must not in any case tear a hole into the beginning of the list though...
539 if (light_strength <= 0)
540 light_strength = 1;
541
542 add_light_source(Me.pos, Me.pos, light_strength);
543
544 // Now we can fill in any explosions, that are currently going on.
545 // These will typically emanate a lot of light.
546 //
547 for (blast_idx = 0; blast_idx < MAXBLASTS; blast_idx++) {
548 if (!(AllBlasts[blast_idx].type == DROIDBLAST))
549 continue;
550
551 // We add some light strength according to the phase of the blast
552 //
553 int light_strength = 10 + AllBlasts[blast_idx].phase / 2;
554 if (light_strength < 0) continue;
555
556 gps vpos;
557 update_virtual_position(&vpos, &AllBlasts[blast_idx].pos, Me.pos.z);
558 if (vpos.x == -1)
559 continue;
560
561 add_light_source(AllBlasts[blast_idx].pos, vpos, light_strength);
562 }
563
564 // Now we can fill in the remaining light sources of this level.
565 // First we scan all the obstacles around Tux
566 //
567
568 // Scanned area
569 gps area_start = { Me.pos.x - 1.5 * FLOOR_TILES_VISIBLE_AROUND_TUX,
570 Me.pos.y - 1.5 * FLOOR_TILES_VISIBLE_AROUND_TUX,
571 Me.pos.z
572 };
573 gps area_end = { Me.pos.x + 1.5 * FLOOR_TILES_VISIBLE_AROUND_TUX,
574 Me.pos.y + 1.5 * FLOOR_TILES_VISIBLE_AROUND_TUX,
575 Me.pos.z
576 };
577 gps intersection_start, intersection_end;
578
579 // For each visible level, compute the intersection between the scanned area
580 // and the level's limits, and search light emitting obstacles inside this
581 // intersection
582 BROWSE_VISIBLE_LEVELS(visible_lvl, next_lvl) {
583 curr_lvl = visible_lvl->lvl_pointer;
584 curr_id = curr_lvl->levelnum;
585
586 // transform area gps relatively to current level
587 update_virtual_position(&intersection_start, &area_start, curr_id);
588 update_virtual_position(&intersection_end, &area_end, curr_id);
589
590 // intersect with level's limits
591 intersection_start.x = max(intersection_start.x, 0);
592 intersection_start.y = max(intersection_start.y, 0);
593 intersection_end.x = min(intersection_end.x, curr_lvl->xlen - 1);
594 intersection_end.y = min(intersection_end.y, curr_lvl->ylen - 1);
595
596 // scan all obstacles inside the intersected area
597 int tstamp = next_glue_timestamp();
598 for (map_y = intersection_start.y; map_y < intersection_end.y; map_y++) {
599 for (map_x = intersection_start.x; map_x < intersection_end.x; map_x++) {
600 for (glue_index = 0; glue_index < curr_lvl->map[map_y][map_x].glued_obstacles.size; glue_index++) {
601
602 obs_index = ((int *)(curr_lvl->map[map_y][map_x].glued_obstacles.arr))[glue_index];
603 emitter = &(curr_lvl->obstacle_list[obs_index]);
604
605 if (emitter->timestamp == tstamp)
606 continue;
607
608 emitter->timestamp = tstamp;
609
610 struct dynarray *animated_light_strengths = &(get_obstacle_spec(emitter->type)->emitted_light_strength);
611 int emitted_light_strength = *(int *)dynarray_member(animated_light_strengths, emitter->frame_index % animated_light_strengths->size, sizeof(int));
612 if (!emitted_light_strength)
613 continue;
614
615 gps vpos;
616 update_virtual_position(&vpos, &emitter->pos, Me.pos.z);
617 if (vpos.x == -1)
618 continue;
619
620 add_light_source(emitter->pos, vpos, emitted_light_strength);
621 }
622 }
623 }
624 }
625
626 // Second, we add the potentially visible bots
627 //
628 enemy *erot;
629
630 BROWSE_VISIBLE_LEVELS(visible_lvl, next_lvl) {
631 curr_lvl = visible_lvl->lvl_pointer;
632 curr_id = curr_lvl->levelnum;
633 update_virtual_position(&me_vpos, &Me.pos, curr_id);
634
635 BROWSE_LEVEL_BOTS(erot, curr_id) {
636 if (fabsf(me_vpos.x - erot->pos.x) >= FLOOR_TILES_VISIBLE_AROUND_TUX)
637 continue;
638
639 if (fabsf(me_vpos.y - erot->pos.y) >= FLOOR_TILES_VISIBLE_AROUND_TUX)
640 continue;
641
642 gps vpos;
643 update_virtual_position(&vpos, &erot->pos, Me.pos.z);
644 if (vpos.x == -1)
645 continue;
646
647 add_light_source(erot->pos, vpos, 5);
648 }
649 }
650 } // void update_light_list ( )
651
652 /**
653 * This function is used to find the light intensity at any given point
654 * on the map.
655 */
calculate_light_strength(gps * cell_vpos)656 static int calculate_light_strength(gps *cell_vpos)
657 {
658 int i;
659 float xdist;
660 float ydist;
661 float squared_dist;
662 gps cell_rpos;
663 struct interpolation_data_cell ilights;
664 struct light_source *lights = light_sources.arr;
665
666 // 1. Light interpolation
667 //
668 if (!resolve_virtual_position(&cell_rpos, cell_vpos))
669 return 0;
670
671 interpolate_light_data(&cell_rpos, &ilights);
672
673 // Interpolated ambient light
674 // Full dark: final_light_strength = 0
675 // Max bright: final_light_strength = minimum light value
676 int final_light_strength = max(0, ilights.minimum_light_value);
677
678 // Interpolated light emitted from Tux
679 lights[0].strength = ilights.light_bonus + Me.light_bonus_from_tux;
680
681 // 2. Compute the light strength value at "cell_vpos"
682 // Nota: the following code being quite obscure, some explanations are quite
683 // mandatory
684 //
685 // 1) The light_strength value of a light source is a relative value, to
686 // be added to the level's ambient light strength. We thus define:
687 // Absolute_intensity = level_ambient + source_strength
688 // Moreover, the light emitted from a light source decreases linearly
689 // with the distance. So, at a given target position, the perceived
690 // intensity of a light is:
691 // I = Absolute_intensity - 4.0 * distance(Light_pos, Cell_vpos)
692 //
693 // Note on the 4.0 factor :
694 // This factor is used to reduce the size of the radius of the "light
695 // circle" around the light source.
696 //
697 // 2) The code loops on each light source, and keeps the maximum light
698 // strength. It does not accumulate light intensity.
699 //
700 // So the initial code is :
701 //
702 // 1: foreach this_light in (set of lights) {
703 // 2: if (this_light is visible from the target) {
704 // 3: this_light_strength = Absolute_intensity - 4.0 * distance(this_light.pos, cell.pos);
705 // 4: if (this_ligh_strength > final_strength) final_strength = this_light_strength;
706 // 5: }
707 // 6: }
708 //
709 // However, this function is time-critical, simply because it is called many
710 // times at every frame. Therefore we want to avoid the sqrt() needed to compute
711 // a distance, if the test fails, and instead use squared values as much as
712 // possible.
713 //
714 // So, lines 3 and 4 are transformed into:
715 // if (Abs_intensity - 4.0 * distance > final_strength) final_strength = Abs_intensity - 4.0 * distance;
716 // which are then transformed into:
717 // if (4.0 * distance < Abs_intensity - final_strength) final_strength = Abs_intensity - 4.0 * distance;
718 // and finally, in order to remove sqrt(), into:
719 // if ((4.0 * distance)^2 < (Abs_intensity - final_strength)^2) final_strength = Abs_intensity - 4.0 * distance;
720 // (note: we will ensure that (Abs_intensity - final_strength) > 0, so there is no problem
721 // with the sign of the inequality. see optimization 1 in the code)
722 //
723 // Visibility test (line 2) being far more costly than the light strength test, we revert the 2 tests :
724 //
725 // 1: foreach this_light in (set of lights) {
726 // 2: if ((4.0 * distance)^2 < (Abs_intensity - final_strength)^2) {
727 // 3: if (this_light is visible from the target)
728 // 4: final_strength = Abs_intensity - 4.0 * distance;
729 // 5: }
730 // 6: }
731
732 // Now, here is the final algorithm
733 //
734 for (i = 0; i < light_sources.size; i++) {
735 float absolute_intensity = ilights.minimum_light_value + lights[i].strength;
736
737 // Optimization 1:
738 // If absolute_intensity is lower than current intensity, we do not take
739 // the light source into account. It means that we do not accumulate
740 // light sources.
741 if ( absolute_intensity - final_light_strength < 0 )
742 continue;
743
744 // Some pre-computations
745 // First transform light source's position into virtual position, related to Tux's current level
746 xdist = lights[i].vpos.x - cell_vpos->x;
747 ydist = lights[i].vpos.y - cell_vpos->y;
748 squared_dist = xdist * xdist + ydist * ydist;
749
750 // Comparison between current light strength and the light source's strength (line 2 of the pseudo-code)
751 if ((squared_dist * 4.0 * 4.0) >=
752 (absolute_intensity - final_light_strength) * (absolute_intensity - final_light_strength))
753 continue;
754
755 // Visibility check (line 3 of pseudo_code)
756 // with a small optimization : no visibility check if the target is very closed to the light
757 if (squared_dist > (0.5*0.5)) {
758 if (!DirectLineColldet(lights[i].vpos.x, lights[i].vpos.y, cell_vpos->x, cell_vpos->y, cell_vpos->z, &VisiblePassFilter))
759 continue;
760 }
761
762 // New final_light_strength
763 final_light_strength = absolute_intensity - 4.0 * sqrt(squared_dist);
764
765 // Full bright, no need to test any other light source
766 if (final_light_strength >= (NUMBER_OF_SHADOW_IMAGES - 1))
767 return (NUMBER_OF_SHADOW_IMAGES - 1);
768 }
769
770 return (final_light_strength);
771
772 } // int calculate_light_strength(gps *cell_vpos)
773
774 /**
775 * When the light radius (i.e. the shadow values for the floor) has been
776 * set up, the shadows usually are very 'hard' in the sense that extreme
777 * darkness can be right next to very bright light. This does not look
778 * very real. Therefore we 'soften' the shadow a bit, by allowing only
779 * a limited step size from one shadow square to the next. Of course
780 * these changes have to be propagated, so we run through the whole
781 * shadow grid twice and propagate in 'both' directions.
782 * The hardness of the shadow can be controlled in the definition of
783 * MAX_LIGHT_STEP. Higher values will lead to harder shadows, while
784 * lower values will give very smooth and fluorescent shadows propagating
785 * even a bit under walls (which doesn't look too good). 3 seems like
786 * a reasonable setting.
787 */
soften_light_distribution(void)788 static void soften_light_distribution(void)
789 {
790 #define MAX_LIGHT_STEP 3
791 uint32_t x, y;
792
793 // Now that the light buffer has been set up properly, we can start to
794 // smooth it out a bit. We do so in the direction of more light.
795 // Propagate from top-left to bottom-right
796 //
797 for (y = 0; y < (LightRadiusConfig.cells_h - 1); y++) {
798 for (x = 0; x < (LightRadiusConfig.cells_w - 1); x++) {
799 if (LIGHT_STRENGTH_CELL(x + 1, y) < LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP)
800 LIGHT_STRENGTH_CELL(x + 1, y) = LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP;
801 if (LIGHT_STRENGTH_CELL(x, y + 1) < LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP)
802 LIGHT_STRENGTH_CELL(x, y + 1) = LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP;
803 if (LIGHT_STRENGTH_CELL(x + 1, y + 1) < LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP)
804 LIGHT_STRENGTH_CELL(x + 1, y + 1) = LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP;
805 }
806 }
807 // now the same again, this time from bottom-right to top-left
808 for (y = (LightRadiusConfig.cells_h - 1); y > 0; y--) {
809 for (x = (LightRadiusConfig.cells_w - 1); x > 0; x--) {
810 if (LIGHT_STRENGTH_CELL(x - 1, y) < LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP)
811 LIGHT_STRENGTH_CELL(x - 1, y) = LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP;
812 if (LIGHT_STRENGTH_CELL(x, y - 1) < LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP)
813 LIGHT_STRENGTH_CELL(x, y - 1) = LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP;
814 if (LIGHT_STRENGTH_CELL(x - 1, y - 1) < LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP)
815 LIGHT_STRENGTH_CELL(x - 1, y - 1) = LIGHT_STRENGTH_CELL(x, y) - MAX_LIGHT_STEP;
816 }
817 }
818
819 } // void soften_light_distribution ( void )
820
821 /**
822 * This function is used to find the light intensity at any given point
823 * on the map.
824 */
set_up_light_strength_buffer(int * decay_x,int * decay_y)825 void set_up_light_strength_buffer(int *decay_x, int *decay_y)
826 {
827 uint32_t x;
828 uint32_t y;
829 gps cell_vpos;
830 int screen_x;
831 int screen_y;
832
833 // Flicker-free code :
834 //
835 // To avoid flickering, the darkness map is 'stuck' to the floor, that is :
836 // when Tux moves, the darkness's textured rectangle is translated in the
837 // opposite direction, to follow the apparent move of the floor.
838 // The same translation has thus to be applied when generating the light
839 // strength buffer.
840 //
841 // However, the darkness's textured rectangle does only cover the screen,
842 // we will thus apply a modulo to the translation. The value of the modulo
843 // is "scale_factor", that is the width (and height) of a darkness cell.
844 // This ensures that a given point on the floor is always inside the "same"
845 // (relative) darkness cell.
846 //
847 // Finally, we only keep negative translations, so that the darkness's
848 // textured rectangle top-left corner is always outside the screen.
849 // (note: the bottom-right corner is also always outside of the screen, due
850 // to the large enough value of scale_factor (see: LightRadiusInit())
851 //
852 *decay_x = - (ceilf(Me.pos.x * iso_floor_tile_width*0.5) - ceilf(Me.pos.y * iso_floor_tile_width*0.5));
853 *decay_x = *decay_x % (int)LightRadiusConfig.scale_factor;
854 if (*decay_x > 0) *decay_x -= (int)LightRadiusConfig.scale_factor;
855
856 *decay_y = - (ceilf(Me.pos.x * iso_floor_tile_height*0.5) + ceilf(Me.pos.y * iso_floor_tile_height*0.5));
857 *decay_y = *decay_y % (int)LightRadiusConfig.scale_factor;
858 if (*decay_y > 0) *decay_y -= (int)LightRadiusConfig.scale_factor;
859
860 prepare_light_interpolation();
861
862 for (y = 0; y < LightRadiusConfig.cells_h; y++) {
863 for (x = 0; x < LightRadiusConfig.cells_w; x++) {
864 screen_x = (int)(x * LightRadiusConfig.scale_factor) - UserCenter_x + *decay_x;
865 // Apply a translation to Y coordinate, to simulate a light coming from bot/tux heads, instead
866 // of their feet.
867 screen_y = (int)(y * LightRadiusConfig.scale_factor) - UserCenter_y + LightRadiusConfig.translate_y + *decay_y;
868
869 // Transform the screen coordinates into a virtual point on the map, relatively to
870 // Tux's current level.
871 cell_vpos.x = translate_pixel_to_map_location(screen_x, screen_y, TRUE);
872 cell_vpos.y = translate_pixel_to_map_location(screen_x, screen_y, FALSE);
873 cell_vpos.z = Me.pos.z;
874
875 LIGHT_STRENGTH_CELL(x,y) = calculate_light_strength(&cell_vpos);
876 }
877 }
878
879 soften_light_distribution();
880
881 } // void set_up_light_strength_buffer ( void )
882
883 /**
884 * This function is used to find the light intensity at any given point
885 * on the screen.
886 */
get_light_strength_cell(uint32_t x,uint32_t y)887 int get_light_strength_cell(uint32_t x, uint32_t y)
888 {
889 return LIGHT_STRENGTH_CELL(x, y);
890 }
891
892 /**
893 * This function is used to find the light intensity at any given point
894 * on the screen.
895 */
get_light_strength_screen(int x,int y)896 int get_light_strength_screen(int x, int y)
897 {
898 x = x / LightRadiusConfig.scale_factor;
899 y = y / LightRadiusConfig.scale_factor;
900
901 if ((x >= 0) && (x < LightRadiusConfig.cells_w) && (y >= 0) && (y < LightRadiusConfig.cells_h)) {
902 return (LIGHT_STRENGTH_CELL(x, y));
903 } else {
904 // If a request reaches outside the prepared buffer, we use the
905 // nearest point, if we can get it easily, otherwise we'll use
906 // blackness by default.
907
908 if ((x >= 0) && (x < LightRadiusConfig.cells_w)) {
909 if (y >= LightRadiusConfig.cells_h)
910 return (LIGHT_STRENGTH_CELL(x, LightRadiusConfig.cells_h - 1));
911 else if (y < 0)
912 return (LIGHT_STRENGTH_CELL(x, 0));
913 } else if ((y >= 0) && (y < LightRadiusConfig.cells_h)) {
914 if (x >= LightRadiusConfig.cells_w)
915 return (LIGHT_STRENGTH_CELL(LightRadiusConfig.cells_w - 1, y));
916 else if (x < 0)
917 return (LIGHT_STRENGTH_CELL(0, y));
918 }
919
920 return (NUMBER_OF_SHADOW_IMAGES - 1);
921 }
922
923 } // int get_light_screen_strength ( moderately_finepoint target_pos )
924
925 /**
926 * This function should blit the shadows on the floor, that are used to
927 * generate the impression of a 'light radius' around the players
928 * character.
929 *
930 * decay_x and decay_y does translate the textured rectangle to avoid
931 * darkness flickering. See flicker-free code's note in set_up_light_strength_buffer()
932 *
933 * Note : the flicker-free light_strength_buffer is not really compatible with this function.
934 * The light_strength_buffer is indeed based on an orthogonal grid, but in SDL mode the darkness
935 * map does use an isometric grid.
936 * However the use of the flicker-free light_strength_buffer does reduce flickering even in
937 * SDL mode. So, we use it.
938 */
blit_classic_SDL_light_radius(int decay_x,int decay_y)939 void blit_classic_SDL_light_radius(int decay_x, int decay_y)
940 {
941 // Number of tiles along X and Y
942 static int lrc_nb_columns = 0;
943 static int lrc_nb_lines = 0;
944
945 /* The screen is covered with small light_radius_chunks images, placed on a regular orthogonal grid.
946 *
947 * Each line is composed of two half-lines :
948 * /\/\/\ First half of first line
949 * \/\/\/\
950 * \/\/\/ Second half of first line
951 *
952 * The ligth_strength value to apply is computed at the center of each tile.
953 */
954
955 // Width and height of the tiles
956 # define LRC_ISO_WIDTH 26
957 # define LRC_ISO_HEIGHT 14
958 // The design of the tiles implies a 2 pixels gap along X, to avoid tiles overlapping
959 # define LRC_ISO_GAP_X 2
960
961 // Load of light_radius_chunk images, and initializes some variables, during the first call
962 //
963 static int first_call = TRUE;
964
965 if (first_call) {
966 first_call = FALSE;
967
968 int i;
969 char constructed_file_name[2000];
970
971 for (i = 0; i < NUMBER_OF_SHADOW_IMAGES; i++) {
972 sprintf(constructed_file_name, "light_radius_chunks/iso_light_radius_darkness_%04d.png", i);
973 load_image(&light_radius_chunk[i], constructed_file_name, NO_MOD);
974 }
975
976 lrc_nb_columns = (int)ceilf((float)GameConfig.screen_width / (float)(LRC_ISO_WIDTH + LRC_ISO_GAP_X)) + 1;
977 lrc_nb_lines = (int)ceilf((float)GameConfig.screen_height / (float)(LRC_ISO_HEIGHT)) + 1;
978 }
979 // Fill the screen with the tiles
980 //
981
982 int l, c;
983 int center_x, center_y; // Position of the center of the tile
984 SDL_Rect target_rectangle; // Used to store the position of the blitted tile, centered on (center_x,center_y)
985 // Note : target_rectangle is modified by the SDL_BlitSurface call,
986 // so it has to be reinitialized after each call
987
988 // First line
989 center_y = 0;
990 target_rectangle.y = center_y - (LRC_ISO_HEIGHT) / 2 + decay_y;
991
992 for (l = 0; l < lrc_nb_lines; ++l) {
993 // First column of the first half-line
994 center_x = 0;
995 target_rectangle.x = center_x - (LRC_ISO_WIDTH + LRC_ISO_GAP_X) / 2 + decay_x;
996
997 for (c = 0; c <= lrc_nb_columns; ++c) {
998 int light_strength;
999 light_strength = get_light_strength_screen((uint32_t) center_x, (uint32_t) center_y);
1000 if (light_strength < (NUMBER_OF_SHADOW_IMAGES-1))
1001 SDL_BlitSurface(light_radius_chunk[light_strength].surface, NULL, Screen, &target_rectangle);
1002
1003 // Next tile along X
1004 center_x += (LRC_ISO_WIDTH + LRC_ISO_GAP_X);
1005 target_rectangle.x = center_x - (LRC_ISO_WIDTH + LRC_ISO_GAP_X) / 2 + decay_x;
1006 target_rectangle.y = center_y - (LRC_ISO_HEIGHT) / 2 + decay_y;
1007 }
1008
1009 // Second half-line, translated by a tile's half-height
1010 center_y += (LRC_ISO_HEIGHT) / 2;
1011 target_rectangle.y = center_y - (LRC_ISO_HEIGHT) / 2 + decay_y;
1012
1013 // First column of the second half-line, translated by a tile's half-width
1014 center_x = (LRC_ISO_WIDTH + LRC_ISO_GAP_X) / 2;
1015 target_rectangle.x = center_x - (LRC_ISO_WIDTH + LRC_ISO_GAP_X) / 2 + decay_x;
1016
1017 for (c = 0; c <= lrc_nb_columns; ++c) {
1018 int light_strength;
1019 light_strength = get_light_strength_screen((uint32_t) center_x, (uint32_t) center_y);
1020 if (light_strength < (NUMBER_OF_SHADOW_IMAGES-1))
1021 SDL_BlitSurface(light_radius_chunk[light_strength].surface, NULL, Screen, &target_rectangle);
1022
1023 // Next tile along X
1024 center_x += LRC_ISO_WIDTH + LRC_ISO_GAP_X;
1025 target_rectangle.x = center_x - (LRC_ISO_WIDTH + LRC_ISO_GAP_X) / 2 + decay_x;
1026 target_rectangle.y = center_y - (LRC_ISO_HEIGHT) / 2 + decay_y;
1027 }
1028
1029 // Next line
1030 center_y += (LRC_ISO_HEIGHT) / 2;
1031 target_rectangle.y = center_y - (LRC_ISO_HEIGHT) / 2 +decay_y;
1032 }
1033 } // void blit_classic_SDL_light_radius( void )
1034
1035 /**
1036 * FreedroidRPG does some light/shadow computations and then draws some
1037 * shadows/light on the floor. There is a certain amount of light around
1038 * the Tux. This light is called the 'light radius'.
1039 *
1040 * This function is supposed to compute all light/shadow values for the
1041 * the floor and then draw the light radius on the floor. Note, that
1042 * this is something completely different from the prerendered shadows
1043 * that are to be blitted for obstacles, when they are exposed to
1044 * daylight.
1045 */
blit_light_radius(void)1046 void blit_light_radius(void)
1047 {
1048 int decay_x, decay_y;
1049
1050 // Before making any reference to the light, it's best to
1051 // first calculate the values in the light buffer, because
1052 // those will be used when drawing the light radius.
1053 //
1054 set_up_light_strength_buffer(&decay_x, &decay_y);
1055
1056 if (use_open_gl) {
1057 // blit_open_gl_light_radius ();
1058 // blit_open_gl_cheap_light_radius ();
1059 blit_open_gl_stretched_texture_light_radius(decay_x, decay_y);
1060 } else {
1061 blit_classic_SDL_light_radius(decay_x, decay_y);
1062 }
1063
1064 dynarray_free(&light_sources);
1065 } // void blit_light_radius ( void )
1066
1067 #undef _light_c
1068