1 /*
2 C-Dogs SDL
3 A port of the legendary (and fun) action/arcade cdogs.
4 Copyright (c) 2013-2016, 2018 Cong Xu
5 All rights reserved.
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
9
10 Redistributions of source code must retain the above copyright notice, this
11 list of conditions and the following disclaimer.
12 Redistributions in binary form must reproduce the above copyright notice,
13 this list of conditions and the following disclaimer in the documentation
14 and/or other materials provided with the distribution.
15
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 POSSIBILITY OF SUCH DAMAGE.
27 */
28 #include "los.h"
29
30 #include "actors.h"
31 #include "algorithms.h"
32 #include "game_events.h"
33 #include "net_util.h"
34
35
LOSInit(Map * map)36 void LOSInit(Map *map)
37 {
38 CArrayInit(&map->LOS.LOS, sizeof(bool));
39 CArrayInit(&map->LOS.Explored, sizeof(bool));
40 struct vec2i v;
41 for (v.y = 0; v.y < map->Size.y; v.y++)
42 {
43 for (v.x = 0; v.x < map->Size.x; v.x++)
44 {
45 const bool f = false;
46 CArrayPushBack(&map->LOS.LOS, &f);
47 CArrayPushBack(&map->LOS.Explored, &f);
48 }
49 }
50 }
LOSTerminate(LineOfSight * los)51 void LOSTerminate(LineOfSight *los)
52 {
53 CArrayTerminate(&los->LOS);
54 CArrayTerminate(&los->Explored);
55 }
56
57 // Reset lines of sight by setting all cells to unseen
LOSReset(LineOfSight * los)58 void LOSReset(LineOfSight *los)
59 {
60 CArrayFillZero(&los->LOS);
61 CArrayFillZero(&los->Explored);
62 }
63
64 typedef struct
65 {
66 Map *Map;
67 struct vec2i Center;
68 int SightRange2;
69 bool Explore;
70 } LOSData;
71 // Calculate LOS cells from a certain start position
72 // Sight range based on config
73 static void SetLOSVisible(Map *map, const struct vec2i pos, const bool explore);
74 static bool IsNextTileBlockedAndSetVisibility(void *data, struct vec2i pos);
75 static void SetObstructionVisible(
76 Map *map, const struct vec2i pos, const bool explore);
77
LOSSetAllVisible(LineOfSight * los)78 void LOSSetAllVisible(LineOfSight *los)
79 {
80 CA_FOREACH(bool, l, los->LOS)
81 *l = true;
82 CA_FOREACH_END()
83 RECT_FOREACH(Rect2iNew(svec2i_zero(), gMap.Size))
84 SetLOSVisible(&gMap, _v, false);
85 RECT_FOREACH_END()
86 }
87
LOSCalcFrom(Map * map,const struct vec2i pos,const bool explore)88 void LOSCalcFrom(Map *map, const struct vec2i pos, const bool explore)
89 {
90 // Perform LOS by casting rays from the centre to the edges, terminating
91 // whenever an obstruction or out-of-range is reached.
92
93 CArrayFillZero(&map->LOS.Explored);
94
95 // First mark center tile and all adjacent tiles as visible
96 // +-+-+-+
97 // |V|V|V|
98 // +-+-+-+
99 // |V|C|V|
100 // +-+-+-+
101 // |V|V|V| (C=center, V=visible)
102 // +-+-+-+
103 struct vec2i end;
104 for (end.x = pos.x - 1; end.x <= pos.x + 1; end.x++)
105 {
106 for (end.y = pos.y - 1; end.y <= pos.y + 1; end.y++)
107 {
108 SetLOSVisible(map, end, explore);
109 }
110 }
111
112 const int sightRange = ConfigGetInt(&gConfig, "Game.SightRange");
113 if (sightRange == 0) return;
114
115 // Limit the perimeter to the sight range
116 const struct vec2i origin = svec2i(pos.x - sightRange, pos.y - sightRange);
117 const struct vec2i perimSize = svec2i_scale(svec2i_subtract(pos, origin), 2);
118
119 LOSData data;
120 data.Map = map;
121 data.Center = pos;
122 data.SightRange2 = sightRange * sightRange;
123 data.Explore = explore;
124
125 // Start from the top-left cell, and proceed clockwise around
126 end = origin;
127 HasClearLineData lineData;
128 lineData.IsBlocked = IsNextTileBlockedAndSetVisibility;
129 lineData.data = &data;
130 // Top edge
131 for (; end.x < origin.x + perimSize.x; end.x++)
132 {
133 HasClearLineJMRaytrace(pos, end, &lineData);
134 }
135 // right edge
136 for (; end.y < origin.y + perimSize.y; end.y++)
137 {
138 HasClearLineJMRaytrace(pos, end, &lineData);
139 }
140 // bottom edge
141 for (; end.x > origin.x; end.x--)
142 {
143 HasClearLineJMRaytrace(pos, end, &lineData);
144 }
145 // left edge
146 for (; end.y > origin.y; end.y--)
147 {
148 HasClearLineJMRaytrace(pos, end, &lineData);
149 }
150
151 // Second pass: make any non-visible obstructions that are adjacent to
152 // visible non-obstructions visible too
153 // This is to ensure runs of walls stay visible
154 for (end.y = origin.y; end.y < origin.y + perimSize.y; end.y++)
155 {
156 for (end.x = origin.x; end.x < origin.x + perimSize.x; end.x++)
157 {
158 const Tile *tile = MapGetTile(map, end);
159 if (!tile || !TileIsOpaque(tile))
160 {
161 continue;
162 }
163 // Check sight range
164 if (svec2i_distance_squared(pos, end) >= data.SightRange2)
165 {
166 continue;
167 }
168 SetObstructionVisible(map, end, explore);
169 }
170 }
171
172 // Find all the newly visible tiles and set events for them
173 GameEvent e = GameEventNew(GAME_EVENT_EXPLORE_TILES);
174 e.u.ExploreTiles.Runs_count = 0;
175 e.u.ExploreTiles.Runs[0].Run = 0;
176 bool run = false;
177 for (end.y = 0; end.y < map->Size.y; end.y++)
178 {
179 for (end.x = 0; end.x < map->Size.x; end.x++)
180 {
181 if (LOSAddRun(
182 &e.u.ExploreTiles, &run, end,
183 *((bool *)CArrayGet(&map->LOS.Explored, end.y * map->Size.x + end.x))))
184 {
185 GameEventsEnqueue(&gGameEvents, e);
186 e.u.ExploreTiles.Runs_count = 0;
187 e.u.ExploreTiles.Runs[0].Run = 0;
188 run = false;
189 }
190 }
191 }
192 if (e.u.ExploreTiles.Runs_count > 0)
193 {
194 GameEventsEnqueue(&gGameEvents, e);
195 }
196 CArrayFillZero(&map->LOS.Explored);
197 }
SetLOSVisible(Map * map,const struct vec2i pos,const bool explore)198 static void SetLOSVisible(Map *map, const struct vec2i pos, const bool explore)
199 {
200 const Tile *t = MapGetTile(map, pos);
201 if (t == NULL) return;
202 *((bool *)CArrayGet(&map->LOS.LOS, pos.y * map->Size.x + pos.x)) = true;
203 if (!t->isVisited && explore)
204 {
205 // Cache the newly explored tile
206 *((bool *)CArrayGet(&map->LOS.Explored, pos.y * map->Size.x + pos.x)) = true;
207 }
208 // Mark any actors on this tile as visible
209 // This affects some AI
210 CA_FOREACH(ThingId, tid, t->things)
211 const Thing *ti = ThingIdGetThing(tid);
212 if (ti->kind == KIND_CHARACTER)
213 {
214 TActor *a = CArrayGet(&gActors, ti->id);
215 a->flags |= FLAGS_VISIBLE;
216 }
217 CA_FOREACH_END()
218 }
IsNextTileBlockedAndSetVisibility(void * data,struct vec2i pos)219 static bool IsNextTileBlockedAndSetVisibility(void *data, struct vec2i pos)
220 {
221 LOSData *lData = data;
222 // Check sight range
223 if (svec2i_distance_squared(lData->Center, pos) >= lData->SightRange2) return true;
224 // Check map range
225 const Tile *t = MapGetTile(lData->Map, pos);
226 if (t == NULL) return true;
227 SetLOSVisible(lData->Map, pos, lData->Explore);
228 // Check if this tile is an obstruction
229 return TileIsOpaque(t);
230 }
231 static bool IsTileVisibleNonObstruction(Map *map, const struct vec2i pos);
SetObstructionVisible(Map * map,const struct vec2i pos,const bool explore)232 static void SetObstructionVisible(
233 Map *map, const struct vec2i pos, const bool explore)
234 {
235 struct vec2i d;
236 for (d.x = -1; d.x < 2; d.x++)
237 {
238 for (d.y = -1; d.y < 2; d.y++)
239 {
240 if (IsTileVisibleNonObstruction(map, svec2i_add(pos, d)))
241 {
242 SetLOSVisible(map, pos, explore);
243 return;
244 }
245 }
246 }
247 }
IsTileVisibleNonObstruction(Map * map,const struct vec2i pos)248 static bool IsTileVisibleNonObstruction(Map *map, const struct vec2i pos)
249 {
250 const Tile *t = MapGetTile(map, pos);
251 if (t == NULL) return false;
252 return !TileIsOpaque(t) && LOSTileIsVisible(map, pos);
253 }
254
LOSAddRun(NExploreTiles * runs,bool * run,const struct vec2i tile,const bool explored)255 bool LOSAddRun(
256 NExploreTiles *runs, bool *run, const struct vec2i tile, const bool explored)
257 {
258 if (explored)
259 {
260 if (!*run)
261 {
262 // Start of new run
263 runs->Runs_count++;
264 runs->Runs[runs->Runs_count - 1].Tile = Vec2i2Net(tile);
265 runs->Runs[runs->Runs_count - 1].Run = 0;
266 }
267 runs->Runs[runs->Runs_count - 1].has_Tile = true;
268 runs->Runs[runs->Runs_count - 1].Run++;
269 *run = true;
270 }
271 else
272 {
273 // End of run
274 // If we have too many runs, send off the event and start a new one
275 if (runs->Runs_count == sizeof runs->Runs / sizeof runs->Runs[0])
276 {
277 return true;
278 }
279 *run = false;
280 }
281 return false;
282 }
283
LOSTileIsVisible(Map * map,const struct vec2i pos)284 bool LOSTileIsVisible(Map *map, const struct vec2i pos)
285 {
286 if (MapGetTile(map, pos) == NULL) return false;
287 return *((bool *)CArrayGet(&map->LOS.LOS, pos.y * map->Size.x + pos.x));
288 }
289