1 /*
2 * position.c
3 * Copyright (C) 2009-2020 Joachim de Groot <jdegroot@web.de>
4 *
5 * NLarn is free software: you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * NLarn is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
13 * See the GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License along
16 * with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <glib.h>
20 #include <stdlib.h>
21
22 #include "cJSON.h"
23 #include "display.h"
24 #include "map.h"
25 #include "extdefs.h"
26 #include "position.h"
27
28 #define POS_MAX_XY (1<<10)
29 #define POS_MAX_Z (1<<6)
30
31 static void area_flood_worker(area *flood, area *obstacles, int x, int y);
32
33 const position pos_invalid = { { POS_MAX_XY, POS_MAX_XY, POS_MAX_Z } };
34
pos_move(position pos,direction dir)35 position pos_move(position pos, direction dir)
36 {
37 /* return given position if direction is not implemented */
38 position npos = pos;
39
40 g_assert(dir > GD_NONE && dir < GD_MAX);
41
42 switch (dir)
43 {
44 case GD_WEST:
45 if (X(pos) > 0)
46 X(npos) -= 1;
47 else
48 npos = pos_invalid;
49
50 break;
51
52 case GD_NW:
53 if ((X(pos) > 0) && (Y(pos) > 0))
54 {
55 X(npos) -= 1;
56 Y(npos) -= 1;
57 }
58 else
59 npos = pos_invalid;
60
61 break;
62
63 case GD_NORTH:
64 if (Y(pos) > 0)
65 Y(npos) -= 1;
66 else
67 npos = pos_invalid;
68
69 break;
70
71 case GD_NE:
72 if ((X(pos) < MAP_MAX_X - 1) && (Y(pos) > 0))
73 {
74 X(npos) += 1;
75 Y(npos) -= 1;
76 }
77 else
78 npos = pos_invalid;
79
80 break;
81
82 case GD_EAST:
83 if (X(pos) < MAP_MAX_X - 1)
84 X(npos) += 1;
85 else
86 npos = pos_invalid;
87
88 break;
89
90 case GD_SE:
91 if ((X(pos) < MAP_MAX_X - 1) && (Y(pos) < MAP_MAX_Y - 1))
92 {
93 X(npos) += 1;
94 Y(npos) += 1;
95 }
96 else
97 npos = pos_invalid;
98
99 break;
100
101 case GD_SOUTH:
102 if (Y(pos) < MAP_MAX_Y - 1)
103 Y(npos) += 1;
104 else
105 npos = pos_invalid;
106
107 break;
108
109 case GD_SW:
110 if ((X(pos) > 0) && (Y(pos) < MAP_MAX_Y - 1))
111 {
112 X(npos) -= 1;
113 Y(npos) += 1;
114 }
115 else
116 npos = pos_invalid;
117
118 break;
119
120 default:
121 npos = pos;
122
123 }
124
125 return npos;
126 }
127
pos_distance(position first,position second)128 gint pos_distance(position first, position second)
129 {
130 if (Z(first) != Z(second))
131 return INT_MAX;
132
133 return (abs(X(first) - X(second)) + 1) + (abs(Y(first) - Y(second)) + 1);
134 }
135
pos_identical(position pos1,position pos2)136 int pos_identical(position pos1, position pos2)
137 {
138 return (pos1.val == pos2.val);
139 }
140
pos_adjacent(position first,position second)141 int pos_adjacent(position first, position second)
142 {
143 guint dist_x, dist_y;
144
145 if (Z(first) != Z(second))
146 return FALSE;
147
148 dist_x = abs(X(first) - X(second));
149 dist_y = abs(Y(first) - Y(second));
150
151 return ((dist_x < 2) && (dist_y < 2));
152 }
153
pos_valid(position pos)154 int pos_valid(position pos)
155 {
156 return (X(pos) < MAP_MAX_X)
157 && (Y(pos) < MAP_MAX_Y)
158 && (Z(pos) < MAP_MAX);
159 }
160
pos_dir(position origin,position target)161 direction pos_dir(position origin, position target)
162 {
163 g_assert (pos_valid(origin) && pos_valid(target));
164
165 if ((X(origin) > X(target)) && (Y(origin) < Y(target))) return GD_SW;
166 if ((X(origin) == X(target)) && (Y(origin) < Y(target))) return GD_SOUTH;
167 if ((X(origin) < X(target)) && (Y(origin) < Y(target))) return GD_SE;
168 if ((X(origin) > X(target)) && (Y(origin) == Y(target))) return GD_WEST;
169 if ((X(origin) == X(target)) && (Y(origin) == Y(target))) return GD_CURR;
170 if ((X(origin) < X(target)) && (Y(origin) == Y(target))) return GD_EAST;
171 if ((X(origin) > X(target)) && (Y(origin) > Y(target))) return GD_NW;
172 if ((X(origin) == X(target)) && (Y(origin) > Y(target))) return GD_NORTH;
173 if ((X(origin) < X(target)) && (Y(origin) > Y(target))) return GD_NE;
174
175 /* impossible! */
176 return GD_NONE;
177 }
178
rect_new(int x1,int y1,int x2,int y2)179 rectangle rect_new(int x1, int y1, int x2, int y2)
180 {
181 rectangle rect;
182
183 rect.x1 = (x1 < 0) ? 0 : x1;
184 rect.y1 = (y1 < 0) ? 0 : y1;
185 rect.x2 = (x2 > MAP_MAX_X) ? MAP_MAX_X : x2;
186 rect.y2 = (y2 > MAP_MAX_Y) ? MAP_MAX_Y : y2;
187
188 return(rect);
189 }
190
rect_new_sized(position center,int size)191 rectangle rect_new_sized(position center, int size)
192 {
193 return rect_new(X(center) - size,
194 Y(center) - size,
195 X(center) + size,
196 Y(center) + size);
197 }
198
pos_in_rect(position pos,rectangle rect)199 int pos_in_rect(position pos, rectangle rect)
200 {
201 if ((X(pos) >= rect.x1)
202 && (X(pos) <= rect.x2)
203 && (Y(pos) >= rect.y1)
204 && (Y(pos) <= rect.y2))
205 {
206 return TRUE;
207 }
208 else
209 return FALSE;
210 }
211
area_new(int start_x,int start_y,int size_x,int size_y)212 area *area_new(int start_x, int start_y, int size_x, int size_y)
213 {
214 area *a = g_malloc0(sizeof(area));
215
216 a->start_x = start_x;
217 a->start_y = start_y;
218 a->size_x = size_x;
219 a->size_y = size_y;
220
221 a->area = g_malloc0(size_y * sizeof(int *));
222
223 for (int y = 0; y < size_y; y++)
224 a->area[y] = g_malloc0(size_x * sizeof(int));
225
226 return a;
227 }
228
area_new_circle(position center,guint radius,gboolean hollow)229 area *area_new_circle(position center, guint radius, gboolean hollow)
230 {
231 area *circle;
232
233 int f = 1 - radius;
234 int ddF_x = 1;
235 int ddF_y = -2 * radius;
236 int x = 0;
237 int y = radius;
238
239 if (!pos_valid(center))
240 return NULL;
241
242 circle = area_new(X(center) - radius,
243 Y(center) - radius,
244 2 * radius + 1,
245 2 * radius + 1);
246
247 /* reposition the center to relative values */
248 X(center) = radius;
249 Y(center) = radius;
250
251 area_point_set(circle, X(center), Y(center) + radius);
252 area_point_set(circle, X(center), Y(center) - radius);
253 area_point_set(circle, X(center) + radius, Y(center));
254 area_point_set(circle, X(center) - radius, Y(center));
255
256 while (x < y)
257 {
258 g_assert(ddF_x == 2 * x + 1);
259 g_assert(ddF_y == -2 * y);
260 g_assert(f == x * x + y * y - (int)radius * (int)radius + 2 * x - y + 1);
261
262 if (f >= 0)
263 {
264 y--;
265 ddF_y += 2;
266 f += ddF_y;
267 }
268
269 x++;
270 ddF_x += 2;
271 f += ddF_x;
272
273 area_point_set(circle, X(center) + x, Y(center) + y);
274 area_point_set(circle, X(center) - x, Y(center) + y);
275 area_point_set(circle, X(center) + x, Y(center) - y);
276 area_point_set(circle, X(center) - x, Y(center) - y);
277 area_point_set(circle, X(center) + y, Y(center) + x);
278 area_point_set(circle, X(center) - y, Y(center) + x);
279 area_point_set(circle, X(center) + y, Y(center) - x);
280 area_point_set(circle, X(center) - y, Y(center) - x);
281 }
282
283 if (hollow)
284 return circle;
285
286 /* fill the circle
287 * - set fill to TRUE when spotting the left border
288 * - set position if (fill == TRUE)
289 * - set fill = FALSE when spotting the right border
290 *
291 * do not need to fill the first and last row
292 */
293
294 for (y = 1; y < circle->size_y - 1; y++)
295 {
296 gboolean fill = FALSE;
297
298 for (x = 0; x < circle->size_x; x++)
299 {
300 /* there are double dots at the beginning and the end of the square */
301 if (area_point_get(circle, x, y) && (!area_point_get(circle, x + 1, y)))
302 {
303 fill = !fill;
304 continue;
305 }
306
307 if (fill)
308 {
309 area_point_set(circle, x, y);
310 }
311 }
312 }
313
314 return circle;
315 }
316
area_new_circle_flooded(position center,guint radius,area * obstacles)317 area *area_new_circle_flooded(position center, guint radius, area *obstacles)
318 {
319 area *narea;
320 int start_x, start_y;
321
322 g_assert(radius > 0 && obstacles != NULL);
323
324 if (!pos_valid(center))
325 return NULL;
326
327 /* add circle boundary to obstacle map */
328 obstacles = area_add(obstacles, area_new_circle(center, radius, TRUE));
329
330 /* translate absolute center position to area */
331 start_x = X(center) - obstacles->start_x;
332 start_y = Y(center) - obstacles->start_y;
333
334 /* fill narea */
335 narea = area_flood(obstacles, start_x, start_y);
336
337 return narea;
338 }
339
area_blast(position center,guint radius,const damage_originator * damo,area_hit_sth pos_hitfun,gpointer data1,gpointer data2,char glyph,int colour)340 gboolean area_blast(position center, guint radius,
341 const damage_originator *damo,
342 area_hit_sth pos_hitfun,
343 gpointer data1, gpointer data2,
344 char glyph, int colour)
345 {
346 map *cmap = game_map(nlarn, Z(center));
347 position cursor = center;
348 gboolean retval = FALSE;
349 area *ball, *obsmap;
350
351 obsmap = map_get_obstacles(cmap, center, radius, TRUE);
352 ball = area_new_circle_flooded(center, radius, obsmap);
353
354 attron(colour);
355
356 for (Y(cursor) = ball->start_y; Y(cursor) < ball->start_y + ball->size_y; Y(cursor)++)
357 {
358 for (X(cursor) = ball->start_x; X(cursor) < ball->start_x + ball->size_x; X(cursor)++)
359 {
360 monster *m = NULL;
361
362 /* skip this position if it is not affected by the blast */
363 if (!area_pos_get(ball, cursor))
364 continue;
365
366 /* move the cursor to the position */
367 move(Y(cursor), X(cursor));
368
369 if (map_sobject_at(cmap, cursor))
370 {
371 /* The blast hit a stationary object. */
372 addch(so_get_glyph(map_sobject_at(cmap, cursor)));
373 }
374 else if ((m = map_get_monster_at(cmap, cursor)))
375 {
376 /* The blast hit a monster */
377 if (monster_in_sight(m))
378 addch(monster_glyph(m));
379 else
380 addch(glyph);
381 }
382 else if (pos_identical(nlarn->p->pos, cursor))
383 {
384 /* The blast hit the player */
385 addch('@');
386 }
387 else
388 {
389 /* The blast hit nothing */
390 addch(glyph);
391 }
392
393 /* keep track if the blast hit something */
394 if (pos_hitfun(cursor, damo, data1, data2))
395 retval = TRUE;
396 }
397 }
398
399 area_destroy(ball);
400 attroff(colour);
401
402 /* make sure the blast shows up */
403 display_draw();
404
405 /* sleep a 3/4 second */
406 napms(750);
407
408 return retval;
409 }
410
area_destroy(area * a)411 void area_destroy(area *a)
412 {
413 g_assert(a != NULL);
414
415 for (int y = 0; y < a->size_y; y++)
416 g_free(a->area[y]);
417
418 g_free(a->area);
419
420 g_free(a);
421 }
422
area_add(area * a,area * b)423 area *area_add(area *a, area *b)
424 {
425 g_assert (a != NULL && b != NULL);
426 g_assert (a->size_x == b->size_x && a->size_y == b->size_y);
427
428 for (int y = 0; y < a->size_y; y++)
429 {
430 for (int x = 0; x < a->size_x; x++)
431 {
432 if (area_point_get(b, x, y))
433 {
434 area_point_set(a, x, y);
435 }
436 }
437 }
438
439 area_destroy(b);
440
441 return a;
442 }
443
area_flood(area * obstacles,int start_x,int start_y)444 area *area_flood(area *obstacles, int start_x, int start_y)
445 {
446 g_assert (obstacles != NULL && area_point_valid(obstacles, start_x, start_y));
447
448 area *flood = area_new(obstacles->start_x, obstacles->start_y,
449 obstacles->size_x, obstacles->size_y);
450
451 area_flood_worker(flood, obstacles, start_x, start_y);
452
453 area_destroy(obstacles);
454
455 return flood;
456 }
457
area_point_set(area * a,int x,int y)458 void area_point_set(area *a, int x, int y)
459 {
460 g_assert(a != NULL);
461 g_assert(area_point_valid(a, x, y));
462 a->area[y][x] = TRUE;
463 }
464
area_point_get(area * a,int x,int y)465 int area_point_get(area *a, int x, int y)
466 {
467 g_assert (a != NULL);
468
469 if (!area_point_valid(a, x, y))
470 return FALSE;
471
472 return a->area[y][x];
473 }
474
area_point_valid(area * a,int x,int y)475 int area_point_valid(area *a, int x, int y)
476 {
477 g_assert (a != NULL);
478 return ((x < a->size_x) && (x >= 0)) && ((y < a->size_y) && (y >= 0));
479 }
480
area_pos_get(area * a,position pos)481 int area_pos_get(area *a, position pos)
482 {
483 int x, y;
484
485 g_assert (a != NULL);
486
487 x = X(pos) - a->start_x;
488 y = Y(pos) - a->start_y;
489
490 return area_point_get(a, x, y);
491 }
492
area_flood_worker(area * flood,area * obstacles,int x,int y)493 static void area_flood_worker(area *flood, area *obstacles, int x, int y)
494 {
495 /* stepped out of area */
496 if (!area_point_valid(flood, x, y))
497 return;
498
499 /* can't flood this */
500 if (area_point_get(obstacles, x, y))
501 return;
502
503 /* been here before */
504 if (area_point_get(flood, x, y))
505 return;
506
507 area_point_set(flood, x, y);
508
509 area_flood_worker(flood, obstacles, x + 1, y);
510 area_flood_worker(flood, obstacles, x - 1, y);
511 area_flood_worker(flood, obstacles, x, y + 1);
512 area_flood_worker(flood, obstacles, x, y - 1);
513 }
514