1 #include <math.h> /* pow() */
2 #include <stddef.h> /* NULL */
3 #include <stdint.h> /* ?(u)int(8|16|32)_t, ?(U)INT8_(MIN|MAX) */
4 #include <stdlib.h> /* free, malloc */
5 #include <string.h> /* memset */
7 /* Number of degrees a circle is divided into. The greater it is, the greater
8 * the angle precision. But make it one whole zero larger and bizarre FOV bugs
9 * appear on large maps, probably due to value overflows (TODO: more research!).
11 #define CIRCLE 3600000
13 /* Angle of a shadow. */
16 struct shadow_angle * next;
21 /* To be used as temporary storage for world map array. */
22 static char * worldmap = NULL;
24 /* Coordinate for maps of max. 256x256 cells. */
31 /* Storage for map_length, set by set_maplength(). */
32 static uint16_t maplength = 0;
33 extern void set_maplength(uint16_t maplength_input)
35 maplength = maplength_input;
38 /* Pseudo-randomness seed for rrand(), set by seed_rrand(). */
39 static uint32_t seed = 0;
41 /* Helper to mv_yx_in_dir_legal(). Move "yx" into hex direction "d". */
42 static void mv_yx_in_dir(char d, struct yx_uint8 * yx)
46 yx->x = yx->x + (yx->y % 2);
55 yx->x = yx->x + (yx->y % 2);
60 yx->x = yx->x - !(yx->y % 2);
69 yx->x = yx->x - !(yx->y % 2);
74 /* Move "yx" into hex direction "dir". Available hex directions are: 'e'
75 * (north-east), 'd' (east), 'c' (south-east), 'x' (south-west), 's' (west), 'w'
76 * (north-west). Returns 1 if the move was legal, 0 if not, and -1 when internal
77 * wrapping limits were exceeded.
79 * A move is legal if "yx" ends up within the the map and the original wrap
80 * space. The latter is left to a neighbor wrap space if "yx" moves beyond the
81 * minimal (0) or maximal (UINT8_MAX) column or row of possible map space – in
82 * which case "yx".y or "yx".x will snap to the respective opposite side. The
83 * current wrapping state is kept between successive calls until a "yx" of NULL
84 * is passed, in which case the function does nothing but zero the wrap state.
85 * Successive wrapping may move "yx" several wrap spaces into either direction,
86 * or return it into the original wrap space.
88 static int8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx)
90 static int8_t wrap_west_east = 0;
91 static int8_t wrap_north_south = 0;
94 wrap_west_east = wrap_north_south = 0;
97 if ( INT8_MIN == wrap_west_east || INT8_MIN == wrap_north_south
98 || INT8_MAX == wrap_west_east || INT8_MAX == wrap_north_south)
102 struct yx_uint8 original = *yx;
103 mv_yx_in_dir(dir, yx);
104 if (('e' == dir || 'd' == dir || 'c' == dir) && yx->x < original.x)
108 else if (('x' == dir || 's' == dir || 'w' == dir) && yx->x > original.x)
112 if (('w' == dir || 'e' == dir) && yx->y > original.y)
116 else if (('x' == dir || 'c' == dir) && yx->y < original.y)
120 if ( !wrap_west_east && !wrap_north_south
121 && yx->x < maplength && yx->y < maplength)
128 /* Wrapper around mv_yx_in_dir_legal() that stores new coordinate in res_y/x,
129 * (return with result_y/x()), and immediately resets the wrapping.
131 static uint8_t res_y = 0;
132 static uint8_t res_x = 0;
133 extern uint8_t mv_yx_in_dir_legal_wrap(char dir, uint8_t y, uint8_t x)
138 uint8_t result = mv_yx_in_dir_legal(dir, &yx);
139 mv_yx_in_dir_legal(0, NULL);
144 extern uint8_t result_y()
148 extern uint8_t result_x()
153 /* With set_seed set, set seed global to seed_input. In any case, return it. */
154 extern uint32_t seed_rrand(uint8_t set_seed, uint32_t seed_input)
163 /* Return 16-bit number pseudo-randomly generated via Linear Congruential
164 * Generator algorithm with some proven constants. Use instead of any rand() to
165 * ensure portability of the same pseudo-randomness across systems.
167 extern uint16_t rrand()
168 { /* Constants as recommended by POSIX.1-2001 (see man page rand(3)). */
169 seed = ((seed * 1103515245) + 12345) % 4294967296;
170 return (seed >> 16); /* Ignore less random least significant bits. */
173 /* Free shadow angles list "angles". */
174 static void free_angles(struct shadow_angle * angles)
178 free_angles(angles->next);
183 /* Recalculate angle < 0 or > CIRCLE to a value between these two limits. */
184 static uint32_t correct_angle(int32_t angle)
188 angle = angle + CIRCLE;
190 while (angle > CIRCLE)
192 angle = angle - CIRCLE;
197 /* Try merging the angle between "left_angle" and "right_angle" to "shadow" if
198 * it meets the shadow from the right or the left. Returns 1 on success, else 0.
200 static uint8_t try_merge(struct shadow_angle * shadow,
201 uint32_t left_angle, uint32_t right_angle)
203 if ( shadow->right_angle <= left_angle + 1
204 && shadow->right_angle >= right_angle)
206 shadow->right_angle = right_angle;
208 else if ( shadow->left_angle + 1 >= right_angle
209 && shadow->left_angle <= left_angle)
211 shadow->left_angle = left_angle;
220 /* Try merging the shadow angle between "left_angle" and "right_angle" into an
221 * existing shadow angle in "shadows". On success, see if this leads to any
222 * additional shadow angle overlaps and merge these accordingly. Return 1 on
225 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
226 struct shadow_angle ** shadows)
228 uint8_t angle_merge = 0;
229 struct shadow_angle * shadow;
230 for (shadow = *shadows; shadow; shadow = shadow->next)
232 if (try_merge(shadow, left_angle, right_angle))
239 struct shadow_angle * shadow1;
240 for (shadow1 = *shadows; shadow1; shadow1 = shadow1->next)
242 struct shadow_angle * last_shadow = NULL;
243 struct shadow_angle * shadow2;
244 for (shadow2 = *shadows; shadow2; shadow2 = shadow2->next)
246 if ( shadow1 != shadow2
247 && try_merge(shadow1, shadow2->left_angle,
248 shadow2->right_angle))
250 struct shadow_angle * to_free = shadow2;
253 last_shadow->next = shadow2->next;
254 shadow2 = last_shadow;
258 *shadows = shadow2->next;
263 last_shadow = shadow2;
270 /* To "shadows", add shadow defined by "left_angle" and "right_angle", either as
271 * new entry or as part of an existing shadow (swallowed whole or extending it).
272 * Return 1 on malloc error, else 0.
274 static uint8_t set_shadow(uint32_t left_angle, uint32_t right_angle,
275 struct shadow_angle ** shadows)
277 struct shadow_angle * shadow_i;
278 if (!try_merging_angles(left_angle, right_angle, shadows))
280 struct shadow_angle * shadow;
281 shadow = malloc(sizeof(struct shadow_angle));
286 shadow->left_angle = left_angle;
287 shadow->right_angle = right_angle;
291 for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
295 shadow_i->next = shadow;
305 /* Test whether angle between "left_angle" and "right_angle", or at least
306 * "middle_angle", is captured inside one of the shadow angles in "shadows". If
307 * so, set hex in "fov_map" indexed by "pos_in_map" to 'H'. If the whole angle
308 * and not just "middle_angle" is captured, return 1. Any other case: 0.
310 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
311 uint32_t middle_angle, struct shadow_angle ** shadows,
312 uint16_t pos_in_map, char * fov_map)
314 struct shadow_angle * shadow_i;
315 if (fov_map[pos_in_map] == 'v')
317 for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
319 if ( left_angle <= shadow_i->left_angle
320 && right_angle >= shadow_i->right_angle)
322 fov_map[pos_in_map] = 'H';
325 if ( middle_angle < shadow_i->left_angle
326 && middle_angle > shadow_i->right_angle)
328 fov_map[pos_in_map] = 'H';
335 /* Evaluate map position "test_pos" in distance "dist" to the view origin, and
336 * on the circle of that distance to the origin on hex "hex_i" (as counted from
337 * the circle's rightmost point), for setting shaded hexes in "fov_map" and
338 * potentially adding a new shadow to linked shadow angle list "shadows".
339 * Return 1 on malloc error, else 0.
341 static uint8_t eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
342 struct yx_uint8 * test_pos,
343 struct shadow_angle ** shadows,
344 const char * symbols_obstacle)
346 int32_t left_angle_uncorrected = ((CIRCLE / 12) / dist)
347 - (hex_i * (CIRCLE / 6) / dist);
348 int32_t right_angle_uncorrected = left_angle_uncorrected
349 - (CIRCLE / (6 * dist));
350 uint32_t left_angle = correct_angle(left_angle_uncorrected);
351 uint32_t right_angle = correct_angle(right_angle_uncorrected);
352 uint32_t right_angle_1st = right_angle > left_angle ? 0 : right_angle;
353 uint32_t middle_angle = 0;
356 middle_angle = right_angle + ((left_angle - right_angle) / 2);
358 uint16_t pos_in_map = test_pos->y * maplength + test_pos->x;
359 uint8_t all_shaded = shade_hex(left_angle, right_angle_1st, middle_angle,
360 shadows, pos_in_map, fov_map);
361 if (!all_shaded && NULL != strchr(symbols_obstacle, worldmap[pos_in_map]))
363 if (set_shadow(left_angle, right_angle_1st, shadows))
367 if (right_angle_1st != right_angle)
370 if (set_shadow(left_angle, right_angle, shadows))
379 /* Update field of view in "fovmap" of "worldmap_input" as seen from "y"/"x".
380 * Return 1 on malloc error, else 0.
382 extern uint8_t build_fov_map(uint8_t y, uint8_t x, char * fovmap,
383 char * worldmap_input,
384 const char * symbols_obstacle)
386 worldmap = worldmap_input;
387 struct shadow_angle * shadows = NULL;
388 struct yx_uint8 test_pos;
391 char * circledirs_string = "xswedc";
393 uint8_t circle_is_on_map;
394 for (circle_i = 1, circle_is_on_map = 1; circle_is_on_map; circle_i++)
396 circle_is_on_map = 0;
397 if (1 < circle_i) /* All circles but the 1st are */
398 { /* moved into starting from a */
399 mv_yx_in_dir_legal('c', &test_pos);/* previous circle's last hex, */
400 } /* i.e. from the upper left. */
401 char dir_char = 'd'; /* Circle's 1st hex is entered by rightward move.*/
402 uint8_t dir_char_pos_in_circledirs_string = UINT8_MAX;
403 uint16_t dist_i, hex_i;
404 for (hex_i=0, dist_i=circle_i; hex_i < 6 * circle_i; dist_i++, hex_i++)
406 if (circle_i < dist_i)
409 dir_char=circledirs_string[++dir_char_pos_in_circledirs_string];
411 if (mv_yx_in_dir_legal(dir_char, &test_pos))
413 if (eval_position(circle_i, hex_i, fovmap, &test_pos, &shadows,
418 circle_is_on_map = 1;
422 mv_yx_in_dir_legal(0, NULL);
423 free_angles(shadows);
427 static uint16_t * score_map = NULL;
428 static uint16_t neighbor_scores[6];
430 /* Init AI score map. Return 1 on failure, else 0. */
431 extern uint8_t init_score_map()
433 uint32_t map_size = maplength * maplength;
434 score_map = malloc(map_size * sizeof(uint16_t));
440 for (; i < map_size; i++)
442 score_map[i] = UINT16_MAX;
447 /* Set score_map[pos] to score. Return 1 on failure, else 0. */
448 extern uint8_t set_map_score(uint16_t pos, uint16_t score)
454 score_map[pos] = score;
458 /* Get score_map[pos]. Return uint16_t value on success, -1 on failure. */
459 extern int32_t get_map_score(uint16_t pos)
465 return score_map[pos];
468 /* Free score_map. */
469 extern void free_score_map()
475 /* Write into "neighbors" scores of the immediate neighbors of the score_map
476 * cell at pos_i (array index), as found in the directions north-east, east,
477 * south-east etc. (clockwise order). Use kill_score for illegal neighborhoods
478 * (i.e. if direction would lead beyond the map's border).
480 static void get_neighbor_scores(uint16_t pos_i, uint16_t kill_score,
481 uint16_t * neighbors)
483 uint32_t map_size = maplength * maplength;
484 uint8_t open_north = pos_i >= maplength;
485 uint8_t open_east = pos_i + 1 % maplength;
486 uint8_t open_south = pos_i + maplength < map_size;
487 uint8_t open_west = pos_i % maplength;
488 uint8_t is_indented = (pos_i / maplength) % 2;
489 uint8_t open_diag_west = is_indented || open_west;
490 uint8_t open_diag_east = !is_indented || open_east;
491 neighbors[0] = !(open_north && open_diag_east) ? kill_score :
492 score_map[pos_i - maplength + is_indented];
493 neighbors[1] = !(open_east) ? kill_score : score_map[pos_i + 1];
494 neighbors[2] = !(open_south && open_diag_east) ? kill_score :
495 score_map[pos_i + maplength + is_indented];
496 neighbors[3] = !(open_south && open_diag_west) ? kill_score :
497 score_map[pos_i + maplength - !is_indented];
498 neighbors[4] = !(open_west) ? kill_score : score_map[pos_i - 1];
499 neighbors[5] = !(open_north && open_diag_west) ? kill_score :
500 score_map[pos_i - maplength - !is_indented];
503 /* Call get_neighbor_scores() on neighbor_scores buffer. Return 1 on error. */
504 extern uint8_t ready_neighbor_scores(uint16_t pos)
510 get_neighbor_scores(pos, UINT16_MAX, neighbor_scores);
514 /* Return i-th position from neighbor_scores buffer.*/
515 extern uint16_t get_neighbor_score(uint8_t i)
517 return neighbor_scores[i];
520 /* Iterate over scored cells in score_map geometry. Compare each cell's score
521 * against the score of its immediate neighbors in 6 directions. If any
522 * neighbor's score is at least two points lower than the current cell's score,
523 * re-set it to 1 point higher than its lowest-scored neighbor. Repeat this
524 * whole process until all cells have settled on their final score. Ignore cells
525 * whose score is greater than UINT16_MAX - 1 (treat those as unreachable). Also
526 * ignore cells whose score is smaller or equal the number of past iterations.
527 * Return 1 on error, else 0.
529 extern uint8_t dijkstra_map()
535 uint16_t max_score = UINT16_MAX - 1;
536 uint32_t map_size = maplength * maplength;
538 uint16_t i_scans, neighbors[6], min_neighbor;
539 uint8_t scores_still_changing = 1;
541 for (i_scans = 0; scores_still_changing; i_scans++)
543 scores_still_changing = 0;
544 for (pos = 0; pos < map_size; pos++)
546 uint16_t score = score_map[pos];
547 if (score <= max_score && score > i_scans)
549 get_neighbor_scores(pos, max_score, neighbors);
550 min_neighbor = max_score;
551 for (i_dirs = 0; i_dirs < 6; i_dirs++)
553 if (min_neighbor > neighbors[i_dirs])
555 min_neighbor = neighbors[i_dirs];
558 if (score_map[pos] > min_neighbor + 1)
560 score_map[pos] = min_neighbor + 1;
561 scores_still_changing = 1;
570 /* 7DRL/TCE addition: Init AI score map to all-eatable unknown fields. */
571 extern uint8_t TCE_init_score_map()
573 uint32_t map_size = maplength * maplength;
574 score_map = malloc(map_size * sizeof(uint16_t));
580 for (; i < map_size; i++)
582 score_map[i] = UINT16_MAX - 1;
587 /* 7DRL/TCE addition: movement cost map setting. */
588 static uint8_t * TCE_move_cost_map = NULL;
589 extern uint8_t TCE_set_movement_cost_map(char * mem_map)
591 uint32_t map_size = maplength * maplength;
592 free(TCE_move_cost_map);
593 TCE_move_cost_map = malloc(map_size * sizeof(uint8_t));
595 for (; pos < map_size; pos++)
597 TCE_move_cost_map[pos] = 0;
599 if (!TCE_move_cost_map)
603 for (pos = 0; pos < map_size; pos++)
605 switch(mem_map[pos]) {
607 TCE_move_cost_map[pos] = 1;
610 TCE_move_cost_map[pos] = 2;
613 TCE_move_cost_map[pos] = 4;
616 TCE_move_cost_map[pos] = 3;
619 TCE_move_cost_map[pos] = 6;
627 /* 7DRL/TCE addition: Like dijkstra_map(), but with movement costs applied. */
628 extern uint8_t TCE_dijkstra_map_with_movement_cost()
630 if (!score_map || !TCE_move_cost_map)
634 uint16_t max_score = UINT16_MAX - 1;
635 uint32_t map_size = maplength * maplength;
637 uint16_t i_scans, neighbors[6], min_neighbor;
638 uint8_t scores_still_changing = 1;
640 for (i_scans = 0; scores_still_changing; i_scans++)
642 scores_still_changing = 0;
643 for (pos = 0; pos < map_size; pos++)
645 uint16_t score = score_map[pos];
646 uint8_t mov_cost = TCE_move_cost_map[pos];
647 if (score <= max_score && mov_cost > 0 && score > i_scans)
649 get_neighbor_scores(pos, max_score, neighbors);
650 min_neighbor = max_score;
651 for (i_dirs = 0; i_dirs < 6; i_dirs++)
653 if (min_neighbor > neighbors[i_dirs])
655 min_neighbor = neighbors[i_dirs];
658 if (score_map[pos] > min_neighbor + mov_cost)
660 score_map[pos] = min_neighbor + mov_cost;
661 scores_still_changing = 1;
670 extern uint8_t zero_score_map_where_char_on_memdepthmap(char c,
677 uint32_t map_size = maplength * maplength;
679 for (pos = 0; pos < map_size; pos++)
681 if (c == memdepthmap[pos])
689 extern void age_some_memdepthmap_on_nonfov_cells(char * memdepthmap,
692 uint32_t map_size = maplength * maplength;
694 for (pos = 0; pos < map_size; pos++)
696 if ('v' != fovmap[pos])
698 char c = memdepthmap[pos];
699 if( '0' <= c && '9' > c && !(rrand() % (uint16_t) pow(2, c - 48)))
707 extern uint8_t set_cells_passable_on_memmap_to_65534_on_scoremap(char * mem_map,
708 const char * symbols_passable)
714 uint32_t map_size = maplength * maplength;
716 for (pos = 0; pos < map_size; pos++)
718 if (NULL != strchr(symbols_passable, mem_map[pos]))
720 score_map[pos] = 65534;
727 extern void update_mem_and_memdepthmap_via_fovmap(char * map, char * fovmap,
731 uint32_t map_size = maplength * maplength;
733 for (pos = 0; pos < map_size; pos++)
735 if ('v' == fovmap[pos])
737 memdepthmap[pos] = '0';
738 memmap[pos] = map[pos];
743 /* USEFUL FOR DEBUGGING
745 extern void write_score_map()
747 FILE *f = fopen("score_map", "a");
749 fprintf(f, "\n---------------------------------------------------------\n");
751 for (y = 0; y < maplength; y++)
753 for (x = 0; x < maplength; x++)
755 uint32_t pos = y * maplength + x;
756 uint16_t val = score_map[pos];
757 if (val == UINT16_MAX)
760 } else if (val == UINT16_MAX - 1) {
763 fprintf(f, "%2X", score_map[pos] % 256);