home · contact · privacy
Server/py: Add movable AI.
[plomrogue] / libplomrogue.c
1 #include <stddef.h> /* NULL */
2 #include <stdint.h> /* ?(u)int(8|16|32)_t, ?(U)INT8_(MIN|MAX) */
3 #include <stdlib.h> /* free, malloc */
4 #include <string.h> /* memset */
5
6 /* Number of degrees a circle is divided into. The greater it is, the greater
7  * the angle precision. But make it one whole zero larger and bizarre FOV bugs
8  * appear on large maps, probably due to value overflows (TODO: more research!).
9  */
10 #define CIRCLE 3600000
11
12 /* Angle of a shadow. */
13 struct shadow_angle
14 {
15     struct shadow_angle * next;
16     uint32_t left_angle;
17     uint32_t right_angle;
18 };
19
20 /* To be used as temporary storage for world map array. */
21 static char * worldmap = NULL;
22
23 /* Coordinate for maps of max. 256x256 cells. */
24 struct yx_uint8
25 {
26     uint8_t y;
27     uint8_t x;
28 };
29
30 /* Storage for map_length, set by set_maplength(). */
31 static uint16_t maplength = 0;
32 extern void set_maplength(uint16_t maplength_input)
33 {
34     maplength = maplength_input;
35 }
36
37 /* Pseudo-randomness seed for rrand(), set by seed_rrand(). */
38 static uint32_t seed = 0;
39
40 /* Helper to mv_yx_in_dir_legal(). Move "yx" into hex direction "d". */
41 static void mv_yx_in_dir(char d, struct yx_uint8 * yx)
42 {
43     if      (d == 'e')
44     {
45         yx->x = yx->x + (yx->y % 2);
46         yx->y--;
47     }
48     else if (d == 'd')
49     {
50         yx->x++;
51     }
52     else if (d == 'c')
53     {
54         yx->x = yx->x + (yx->y % 2);
55         yx->y++;
56     }
57     else if (d == 'x')
58     {
59         yx->x = yx->x - !(yx->y % 2);
60         yx->y++;
61     }
62     else if (d == 's')
63     {
64         yx->x--;
65     }
66     else if (d == 'w')
67     {
68         yx->x = yx->x - !(yx->y % 2);
69         yx->y--;
70     }
71 }
72
73 /* Move "yx" into hex direction "dir". Available hex directions are: 'e'
74  * (north-east), 'd' (east), 'c' (south-east), 'x' (south-west), 's' (west), 'w'
75  * (north-west). Returns 1 if the move was legal, 0 if not, and -1 when internal
76  * wrapping limits were exceeded.
77  *
78  * A move is legal if "yx" ends up within the the map and the original wrap
79  * space. The latter is left to a neighbor wrap space if "yx" moves beyond the
80  * minimal (0) or maximal (UINT8_MAX) column or row of possible map space – in
81  * which case "yx".y or "yx".x will snap to the respective opposite side. The
82  * current wrapping state is kept between successive calls until a "yx" of NULL
83  * is passed, in which case the function does nothing but zero the wrap state.
84  * Successive wrapping may move "yx" several wrap spaces into either direction,
85  * or return it into the original wrap space.
86  */
87 static int8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx)
88 {
89     static int8_t wrap_west_east   = 0;
90     static int8_t wrap_north_south = 0;
91     if (!yx)
92     {
93         wrap_west_east = wrap_north_south = 0;
94         return 0;
95     }
96     if (   INT8_MIN == wrap_west_east || INT8_MIN == wrap_north_south
97         || INT8_MAX == wrap_west_east || INT8_MAX == wrap_north_south)
98     {
99         return -1;
100     }
101     struct yx_uint8 original = *yx;
102     mv_yx_in_dir(dir, yx);
103     if      (('e' == dir || 'd' == dir || 'c' == dir) && yx->x < original.x)
104     {
105         wrap_west_east++;
106     }
107     else if (('x' == dir || 's' == dir || 'w' == dir) && yx->x > original.x)
108     {
109         wrap_west_east--;
110     }
111     if      (('w' == dir || 'e' == dir)               && yx->y > original.y)
112     {
113         wrap_north_south--;
114     }
115     else if (('x' == dir || 'c' == dir)               && yx->y < original.y)
116     {
117         wrap_north_south++;
118     }
119     if (   !wrap_west_east && !wrap_north_south
120         && yx->x < maplength && yx->y < maplength)
121     {
122         return 1;
123     }
124     return 0;
125 }
126
127 /* Wrapper around mv_yx_in_dir_legal() that stores new coordinate in res_y/x,
128  * (return with result_y/x()), and immediately resets the wrapping.
129  */
130 static uint8_t res_y = 0;
131 static uint8_t res_x = 0;
132 extern uint8_t mv_yx_in_dir_legal_wrap(char dir, uint8_t y, uint8_t x)
133 {
134     struct yx_uint8 yx;
135     yx.y = y;
136     yx.x = x;
137     uint8_t result = mv_yx_in_dir_legal(dir, &yx);
138     mv_yx_in_dir_legal(0, NULL);
139     res_y = yx.y;
140     res_x = yx.x;
141     return result;
142 }
143 extern uint8_t result_y()
144 {
145     return res_y;
146 }
147 extern uint8_t result_x()
148 {
149     return res_x;
150 }
151
152 /* With set_seed set, set seed global to seed_input. In any case, return it. */
153 extern uint32_t seed_rrand(uint8_t set_seed, uint32_t seed_input)
154 {
155     if (set_seed)
156     {
157         seed = seed_input;
158     }
159     return seed;
160 }
161
162 /* Return 16-bit number pseudo-randomly generated via Linear Congruential
163  * Generator algorithm with some proven constants. Use instead of any rand() to
164   * ensure portability of the same pseudo-randomness across systems.
165  */
166 extern uint16_t rrand()
167 {   /* Constants as recommended by POSIX.1-2001 (see man page rand(3)). */
168     seed = ((seed * 1103515245) + 12345) % 4294967296;
169     return (seed >> 16); /* Ignore less random least significant bits. */
170 }
171
172 /* Free shadow angles list "angles". */
173 static void free_angles(struct shadow_angle * angles)
174 {
175     if (angles->next)
176     {
177         free_angles(angles->next);
178     }
179     free(angles);
180 }
181
182 /* Recalculate angle < 0 or > CIRCLE to a value between these two limits. */
183 static uint32_t correct_angle(int32_t angle)
184 {
185     while (angle < 0)
186     {
187         angle = angle + CIRCLE;
188     }
189     while (angle > CIRCLE)
190     {
191         angle = angle - CIRCLE;
192     }
193     return angle;
194 }
195
196 /* Try merging the angle between "left_angle" and "right_angle" to "shadow" if
197  * it meets the shadow from the right or the left. Returns 1 on success, else 0.
198  */
199 static uint8_t try_merge(struct shadow_angle * shadow,
200                          uint32_t left_angle, uint32_t right_angle)
201 {
202     if      (   shadow->right_angle <= left_angle + 1
203              && shadow->right_angle >= right_angle)
204     {
205         shadow->right_angle = right_angle;
206     }
207     else if (   shadow->left_angle + 1 >= right_angle
208              && shadow->left_angle     <= left_angle)
209     {
210         shadow->left_angle = left_angle;
211     }
212     else
213     {
214         return 0;
215     }
216     return 1;
217 }
218
219 /* Try merging the shadow angle between "left_angle" and "right_angle" into an
220  * existing shadow angle in "shadows". On success, see if this leads to any
221  * additional shadow angle overlaps and merge these accordingly. Return 1 on
222  * success, else 0.
223  */
224 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
225                                   struct shadow_angle ** shadows)
226 {
227     uint8_t angle_merge = 0;
228     struct shadow_angle * shadow;
229     for (shadow = *shadows; shadow; shadow = shadow->next)
230     {
231         if (try_merge(shadow, left_angle, right_angle))
232         {
233             angle_merge = 1;
234         }
235     }
236     if (angle_merge)
237     {
238         struct shadow_angle * shadow1;
239         for (shadow1 = *shadows; shadow1; shadow1 = shadow1->next)
240         {
241             struct shadow_angle * last_shadow = NULL;
242             struct shadow_angle * shadow2;
243             for (shadow2 = *shadows; shadow2; shadow2 = shadow2->next)
244             {
245                 if (   shadow1 != shadow2
246                     && try_merge(shadow1, shadow2->left_angle,
247                                           shadow2->right_angle))
248                 {
249                     struct shadow_angle * to_free = shadow2;
250                     if (last_shadow)
251                     {
252                         last_shadow->next = shadow2->next;
253                         shadow2 = last_shadow;
254                     }
255                     else
256                     {
257                         *shadows = shadow2->next;
258                         shadow2 = *shadows;
259                     }
260                     free(to_free);
261                 }
262                 last_shadow = shadow2;
263             }
264         }
265     }
266     return angle_merge;
267 }
268
269 /* To "shadows", add shadow defined by "left_angle" and "right_angle", either as
270  * new entry or as part of an existing shadow (swallowed whole or extending it).
271  * Return 1 on malloc error, else 0.
272  */
273 static uint8_t set_shadow(uint32_t left_angle, uint32_t right_angle,
274                           struct shadow_angle ** shadows)
275 {
276     struct shadow_angle * shadow_i;
277     if (!try_merging_angles(left_angle, right_angle, shadows))
278     {
279         struct shadow_angle * shadow;
280         shadow = malloc(sizeof(struct shadow_angle));
281         if (!shadow)
282         {
283             return 1;
284         }
285         shadow->left_angle  = left_angle;
286         shadow->right_angle = right_angle;
287         shadow->next = NULL;
288         if (*shadows)
289         {
290             for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
291             {
292                 if (!shadow_i->next)
293                 {
294                     shadow_i->next = shadow;
295                     return 0;
296                 }
297             }
298         }
299         *shadows = shadow;
300     }
301     return 0;
302 }
303
304 /* Test whether angle between "left_angle" and "right_angle", or at least
305  * "middle_angle", is captured inside one of the shadow angles in "shadows". If
306  * so, set hex in "fov_map" indexed by "pos_in_map" to 'H'. If the whole angle
307  * and not just "middle_angle" is captured, return 1. Any other case: 0.
308  */
309 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
310                          uint32_t middle_angle, struct shadow_angle ** shadows,
311                          uint16_t pos_in_map, char * fov_map)
312 {
313     struct shadow_angle * shadow_i;
314     if (fov_map[pos_in_map] == 'v')
315     {
316         for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
317         {
318             if (   left_angle <=  shadow_i->left_angle
319                 && right_angle >= shadow_i->right_angle)
320             {
321                 fov_map[pos_in_map] = 'H';
322                 return 1;
323             }
324             if (   middle_angle < shadow_i->left_angle
325                 && middle_angle > shadow_i->right_angle)
326             {
327                 fov_map[pos_in_map] = 'H';
328             }
329         }
330     }
331     return 0;
332 }
333
334 /* Evaluate map position "test_pos" in distance "dist" to the view origin, and
335  * on the circle of that distance to the origin on hex "hex_i" (as counted from
336  * the circle's rightmost point), for setting shaded hexes in "fov_map" and
337  * potentially adding a new shadow to linked shadow angle list "shadows".
338  * Return 1 on malloc error, else 0.
339  */
340 static uint8_t eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
341                              struct yx_uint8 * test_pos,
342                              struct shadow_angle ** shadows)
343 {
344     int32_t left_angle_uncorrected =   ((CIRCLE / 12) / dist)
345                                      - (hex_i * (CIRCLE / 6) / dist);
346     int32_t right_angle_uncorrected =   left_angle_uncorrected
347                                       - (CIRCLE / (6 * dist));
348     uint32_t left_angle  = correct_angle(left_angle_uncorrected);
349     uint32_t right_angle = correct_angle(right_angle_uncorrected);
350     uint32_t right_angle_1st = right_angle > left_angle ? 0 : right_angle;
351     uint32_t middle_angle = 0;
352     if (right_angle_1st)
353     {
354         middle_angle = right_angle + ((left_angle - right_angle) / 2);
355     }
356     uint16_t pos_in_map = test_pos->y * maplength + test_pos->x;
357     uint8_t all_shaded = shade_hex(left_angle, right_angle_1st, middle_angle,
358                                    shadows, pos_in_map, fov_map);
359     if (!all_shaded && 'X' == worldmap[pos_in_map])
360     {
361         if (set_shadow(left_angle, right_angle_1st, shadows))
362         {
363             return 1;
364         }
365         if (right_angle_1st != right_angle)
366         {
367             left_angle = CIRCLE;
368             if (set_shadow(left_angle, right_angle, shadows))
369             {
370                 return 1;
371             }
372         }
373     }
374     return 0;
375 }
376
377 /* Update field of view in "fovmap" of "worldmap_input" as seen from "y"/"x".
378  * Return 1 on malloc error, else 0.
379  */
380 extern uint8_t build_fov_map(uint8_t y, uint8_t x,
381                              char * fovmap, char * worldmap_input)
382 {
383     worldmap = worldmap_input;
384     struct shadow_angle * shadows = NULL;
385     struct yx_uint8 test_pos;
386     test_pos.y = y;
387     test_pos.x = x;
388     char * circledirs_string = "xswedc";
389     uint16_t circle_i;
390     uint8_t circle_is_on_map;
391     for (circle_i = 1, circle_is_on_map = 1; circle_is_on_map; circle_i++)
392     {
393         circle_is_on_map = 0;
394         if (1 < circle_i)                      /* All circles but the 1st are */
395         {                                      /* moved into starting from a  */
396             mv_yx_in_dir_legal('c', &test_pos);/* previous circle's last hex, */
397         }                                      /* i.e. from the upper left.   */
398         char dir_char = 'd'; /* Circle's 1st hex is entered by rightward move.*/
399         uint8_t dir_char_pos_in_circledirs_string = UINT8_MAX;
400         uint16_t dist_i, hex_i;
401         for (hex_i=0, dist_i=circle_i; hex_i < 6 * circle_i; dist_i++, hex_i++)
402         {
403             if (circle_i < dist_i)
404             {
405                 dist_i = 1;
406                 dir_char=circledirs_string[++dir_char_pos_in_circledirs_string];
407             }
408             if (mv_yx_in_dir_legal(dir_char, &test_pos))
409             {
410                 if (eval_position(circle_i, hex_i, fovmap, &test_pos, &shadows))
411                 {
412                     return 1;
413                 }
414                 circle_is_on_map = 1;
415             }
416         }
417     }
418     mv_yx_in_dir_legal(0, NULL);
419     free_angles(shadows);
420     return 0;
421 }
422
423 static uint16_t * score_map = NULL;
424 static uint16_t neighbor_scores[6];
425
426 /* Init AI score map. Return 1 on failure, else 0. */
427 extern uint8_t init_score_map()
428 {
429     uint32_t map_size = maplength * maplength;
430     score_map = malloc(map_size * sizeof(uint16_t));
431     if (!score_map)
432     {
433         return 1;
434     }
435     uint32_t i = 0;
436     for (; i < map_size; i++)
437     {
438         score_map[i] = UINT16_MAX;
439     }
440     return 0;
441 }
442
443 /* Set score_map[pos] to score. Return 1 on failure, else 0. */
444 extern uint8_t set_map_score(uint16_t pos, uint16_t score)
445 {
446     if (!score_map)
447     {
448         return 1;
449     }
450     score_map[pos] = score;
451 /*
452     uint32_t mup_size = maplength * maplength;
453     uint32_t pus;
454     FILE * file = fopen("test_set", "w");
455     for (pus = 0; pus < mup_size; pus++)
456     {
457         fprintf(file, "%d ", score_map[pus]);
458         if (0 == pus % maplength)
459         {
460             fprintf(file, "\n");
461         }
462     }
463     fclose(file);
464 */
465     return 0;
466 }
467
468 /* Get score_map[pos]. Return uint16_t value on success, -1 on failure. */
469 extern int32_t get_map_score(uint16_t pos)
470 {
471     if (!score_map)
472     {
473         return -1;
474     }
475     return score_map[pos];
476 }
477
478 /* Free score_map. */
479 extern void free_score_map()
480 {
481     free(score_map);
482     score_map = NULL;
483 }
484
485 /* Write into "neighbors" scores of the immediate neighbors of the score_map
486  * cell at pos_i (array index), as found in the directions north-east, east,
487  * south-east etc. (clockwise order). Use kill_score for illegal neighborhoods
488  * (i.e. if direction would lead beyond the map's border).
489  */
490 static void get_neighbor_scores(uint16_t pos_i, uint16_t kill_score,
491                                 uint16_t * neighbors)
492 {
493     uint32_t map_size = maplength * maplength;
494     uint8_t open_north     = pos_i >= maplength;
495     uint8_t open_east      = pos_i + 1 % maplength;
496     uint8_t open_south     = pos_i + maplength < map_size;
497     uint8_t open_west      = pos_i % maplength;
498     uint8_t is_indented    = (pos_i / maplength) % 2;
499     uint8_t open_diag_west = is_indented || open_west;
500     uint8_t open_diag_east = !is_indented || open_east;
501     neighbors[0] = !(open_north && open_diag_east) ? kill_score :
502                    score_map[pos_i - maplength + is_indented];
503     neighbors[1] = !(open_east) ? kill_score : score_map[pos_i + 1];
504     neighbors[2] = !(open_south && open_diag_east) ? kill_score :
505                    score_map[pos_i + maplength + is_indented];
506     neighbors[3] = !(open_south && open_diag_west) ? kill_score :
507                    score_map[pos_i + maplength - !is_indented];
508     neighbors[4] = !(open_west) ? kill_score : score_map[pos_i - 1];
509     neighbors[5] = !(open_north && open_diag_west) ? kill_score :
510                    score_map[pos_i - maplength - !is_indented];
511 }
512
513 /* Call get_neighbor_scores() on neighbor_scores buffer. Return 1 on error. */
514 extern uint8_t ready_neighbor_scores(uint16_t pos)
515 {
516     if (!score_map)
517     {
518         return 1;
519     }
520     get_neighbor_scores(pos, UINT16_MAX, neighbor_scores);
521     return 0;
522 }
523
524 /* Return i-th position from neighbor_scores buffer.*/
525 extern uint16_t get_neighbor_score(uint8_t i)
526 {
527     return neighbor_scores[i];
528 }
529
530 /* Iterate over scored cells in score_map geometry. Compare each cell's score
531  * against the score of its immediate neighbors in 6 directions. If any
532  * neighbor's score is at least two points lower than the current cell's score,
533  * re-set it to 1 point higher than its lowest-scored neighbor. Repeat this
534  * whole process until all cells have settled on their final score. Ignore cells
535  * whose score is greater than UINT16_MAX - 1 (treat those as unreachable).
536  * Return 1 on error, else 0.
537  */
538 extern uint8_t dijkstra_map()
539 {
540     if (!score_map)
541     {
542         return 1;
543     }
544     uint16_t max_score = UINT16_MAX - 1;
545     uint32_t map_size = maplength * maplength;
546     uint32_t pos;
547     uint16_t i_scans, neighbors[6], min_neighbor;
548     uint8_t scores_still_changing = 1;
549     uint8_t i_dirs;
550     for (i_scans = 0; scores_still_changing; i_scans++)
551     {
552         scores_still_changing = 0;
553         for (pos = 0; pos < map_size; pos++)
554         {
555             if (score_map[pos] <= max_score)
556             {
557                 get_neighbor_scores(pos, max_score, neighbors);
558                 min_neighbor = max_score;
559                 for (i_dirs = 0; i_dirs < 6; i_dirs++)
560                 {
561                     if (min_neighbor > neighbors[i_dirs])
562                     {
563                         min_neighbor = neighbors[i_dirs];
564                     }
565                 }
566                 if (score_map[pos] > min_neighbor + 1)
567                 {
568                     score_map[pos] = min_neighbor + 1;
569                     scores_still_changing = 1;
570                 }
571             }
572         }
573     }
574     return 0;
575 }