1 /*
2 * fov.c
3 * Copyright (C) 2009-2018 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 <string.h>
21 #include "fov.h"
22 #include "game.h"
23 #include "map.h"
24 #include "extdefs.h"
25 #include "position.h"
26
27 static void fov_calculate_octant(fov *fv, map *m, position center,
28 gboolean infravision, int row,
29 float start, float end, int radius,
30 int xx, int xy, int yx, int yy);
31
32 static gint fov_visible_monster_sort(gconstpointer a, gconstpointer b, gpointer center);
33
34 struct _fov
35 {
36 /* the actual field of vision */
37 guchar data[MAP_MAX_Y][MAP_MAX_X];
38
39 /* the center of the fov */
40 position center;
41
42 /* The list of visible monsters - it's a hash as fields may get visited
43 twice, which means that monsters may get added to the list multiple
44 times. The hash overwrites duplicate values. */
45 GHashTable *mlist;
46 };
47
fov_new()48 fov *fov_new()
49 {
50 fov *nfov = g_malloc0(sizeof(fov));
51 nfov->center = pos_invalid;
52 nfov->mlist = g_hash_table_new(g_direct_hash, g_direct_equal);
53
54 return nfov;
55 }
56 /* this and the function fov_calculate_octant() have been
57 * ported from python to c using the example at
58 * http://roguebasin.roguelikedevelopment.org/index.php?title=Python_shadowcasting_implementation
59 */
fov_calculate(fov * fv,map * m,position pos,int radius,gboolean infravision)60 void fov_calculate(fov *fv, map *m, position pos, int radius, gboolean infravision)
61 {
62 const int mult[4][8] =
63 {
64 { 1, 0, 0, -1, -1, 0, 0, 1 },
65 { 0, 1, -1, 0, 0, -1, 1, 0 },
66 { 0, 1, 1, 0, 0, -1, -1, 0 },
67 { 1, 0, 0, 1, -1, 0, 0, -1 }
68 };
69
70 /* reset the entire fov to unseen */
71 fov_reset(fv);
72
73 /* set the center of the fov */
74 fv->center = pos;
75
76 /* determine which fields are visible */
77 for (int octant = 0; octant < 8; octant++)
78 {
79 fov_calculate_octant(fv, m, pos, infravision,
80 1, 1.0, 0.0, radius,
81 mult[0][octant], mult[1][octant],
82 mult[2][octant], mult[3][octant]);
83 }
84
85 fov_set(fv, pos, TRUE, infravision, TRUE);
86 }
87
fov_get(fov * fv,position pos)88 gboolean fov_get(fov *fv, position pos)
89 {
90 g_assert (fv != NULL);
91 g_assert (pos_valid(pos));
92
93 return fv->data[Y(pos)][X(pos)];
94 }
95
fov_set(fov * fv,position pos,guchar visible,gboolean infravision,gboolean mchk)96 void fov_set(fov *fv, position pos, guchar visible,
97 gboolean infravision, gboolean mchk)
98 {
99 g_assert (fv != NULL);
100 g_assert (pos_valid(pos));
101
102 fv->data[Y(pos)][X(pos)] = visible;
103 monster *mon;
104
105 /* If advised to do so, check if there is a monster at that
106 position. Must not be an unknown mimic or invisible. */
107 if (mchk && (mon = map_get_monster_at(game_map(nlarn, Z(pos)), pos))
108 && !monster_unknown(mon)
109 && (!monster_flags(mon, INVISIBLE) || infravision))
110 {
111 /* found a visible monster -> add it to the list */
112 g_hash_table_insert(fv->mlist, mon, 0);
113 }
114 }
115
fov_reset(fov * fv)116 void fov_reset(fov *fv)
117 {
118 g_assert (fv != NULL);
119
120 /* set fov_data to FALSE */
121 memset(fv->data, 0, MAP_MAX_Y * MAP_MAX_X * sizeof(guchar));
122
123 /* set the center to an invalid position */
124 fv->center = pos_invalid;
125
126 /* clean list of visible monsters */
127 g_hash_table_remove_all(fv->mlist);
128 }
129
fov_get_closest_monster(fov * fv)130 monster *fov_get_closest_monster(fov *fv)
131 {
132 monster *closest_monster = NULL;
133
134 if (g_hash_table_size(fv->mlist) > 0)
135 {
136 GList *mlist;
137
138 /* get the list of all visible monsters */
139 mlist = g_hash_table_get_keys(fv->mlist);
140
141 /* sort the monsters list by distance */
142 mlist = g_list_sort_with_data(mlist, fov_visible_monster_sort,
143 &fv->center);
144
145 /* get the first element in the list */
146 closest_monster = mlist->data;
147
148 g_list_free(mlist);
149 }
150
151 return closest_monster;
152 }
153
fov_get_visible_monsters(fov * fv)154 GList *fov_get_visible_monsters(fov *fv)
155 {
156 GList *mlist = NULL;
157
158 if (g_hash_table_size(fv->mlist) != 0)
159 {
160 /* get a GList of all visible monster all */
161 mlist = g_hash_table_get_keys(fv->mlist);
162
163 /* sort the list of monster by distance */
164 mlist = g_list_sort_with_data(mlist, fov_visible_monster_sort,
165 &fv->center);
166 }
167
168 return mlist;
169 }
170
fov_free(fov * fv)171 void fov_free(fov *fv)
172 {
173 g_assert (fv != NULL);
174
175 /* free the allocated memory */
176 g_hash_table_destroy(fv->mlist);
177 g_free(fv);
178 }
179
fov_calculate_octant(fov * fv,map * m,position center,gboolean infravision,int row,float start,float end,int radius,int xx,int xy,int yx,int yy)180 static void fov_calculate_octant(fov *fv, map *m, position center,
181 gboolean infravision, int row,
182 float start, float end, int radius,
183 int xx, int xy, int yx, int yy)
184 {
185 int radius_squared;
186 int X, Y;
187 float l_slope, r_slope;
188 float new_start = 0;
189
190 if (start < end)
191 return;
192
193 radius_squared = radius * radius;
194
195 for (int j = row; j <= radius + 1; j++)
196 {
197 int dx = -j - 1;
198 int dy = -j;
199
200 int blocked = FALSE;
201
202 while (dx <= 0)
203 {
204 dx += 1;
205
206 /* Translate the dx, dy coordinates into map coordinates: */
207 X = X(center) + dx * xx + dy * xy;
208 Y = Y(center) + dx * yx + dy * yy;
209
210 /* check if coordinated are within bounds */
211 if ((X < 0) || (X >= MAP_MAX_X))
212 continue;
213
214 if ((Y < 0) || (Y >= MAP_MAX_Y))
215 continue;
216
217 /* l_slope and r_slope store the slopes of the left and right
218 * extremities of the square we're considering: */
219 l_slope = (dx - 0.5) / (dy + 0.5);
220 r_slope = (dx + 0.5) / (dy - 0.5);
221
222 if (start < r_slope)
223 {
224 continue;
225 }
226 else if (end > l_slope)
227 {
228 break;
229 }
230 else
231 {
232 position pos = { { X, Y, m->nlevel } };
233
234 /* Our light beam is touching this square; light it */
235 if ((dx * dx + dy * dy) < radius_squared)
236 {
237 fov_set(fv, pos, TRUE, infravision, TRUE);
238 }
239
240 if (blocked)
241 {
242 /* we're scanning a row of blocked squares */
243 if (!map_pos_transparent(m, pos))
244 {
245 new_start = r_slope;
246 continue;
247 }
248 else
249 {
250 blocked = FALSE;
251 start = new_start;
252 }
253 }
254 else
255 {
256 if (!map_pos_transparent(m, pos) && (j < radius))
257 {
258 /* This is a blocking square, start a child scan */
259 blocked = TRUE;
260 }
261
262 fov_calculate_octant(fv, m, center, infravision,
263 j + 1, start, l_slope,
264 radius, xx, xy, yx, yy);
265
266 new_start = r_slope;
267 }
268 }
269 }
270
271 /* Row is scanned; do next row unless last square was blocked */
272 if (blocked)
273 {
274 break;
275 }
276 }
277 }
278
fov_visible_monster_sort(gconstpointer a,gconstpointer b,gpointer center)279 static gint fov_visible_monster_sort(gconstpointer a, gconstpointer b, gpointer center)
280 {
281 monster *ma, *mb;
282
283 ma = (monster*)a;
284 mb = (monster*)b;
285
286 int da = pos_distance(*(position *)center, monster_pos(ma));
287 int db = pos_distance(*(position *)center, monster_pos(mb));
288
289 if (da < db)
290 return -1;
291
292 if (da > db)
293 return 1;
294
295 return 0;
296 }
297