1 /**
2 * @file
3 * @brief Line-of-sight algorithm.
4 *
5 *
6 *
7 * == Definition of visibility ==
8 *
9 * Two cells are in view of each other if there is any straight
10 * line that meets both cells and that doesn't meet any opaque
11 * cell in between, and if the cells are in LOS range of each
12 * other.
13 *
14 * Here, to "meet" a cell means to intersect the interior. In
15 * particular, rays can pass between to diagonally adjacent
16 * walls (as can the player).
17 *
18 * == Terminology ==
19 *
20 * A _ray_ is a line, specified by starting point (accx, accy)
21 * and slope. A ray determines its _footprint_: the sequence of
22 * cells whose interiour it meets.
23 *
24 * Any prefix of the footprint of a ray is called a _cellray_.
25 *
26 * For the purposes of LOS calculation, only the footprints
27 * are relevant, but rays are also used for shooting beams,
28 * which may travel beyond LOS and which can be reflected.
29 * See ray.cc.
30 *
31 * == Overview ==
32 *
33 * At first use, the LOS code makes some precomputations,
34 * filling a list of all relevant rays in one quadrant,
35 * and filling data structures that allow calculating LOS
36 * in a quadrant without checking each ray.
37 *
38 * The code provides functions for filling LOS information
39 * around a given center efficiently, and for querying rays
40 * between two given cells.
41 **/
42
43 #include "AppHdr.h"
44
45 #include "los.h"
46
47 #include <algorithm>
48 #include <cmath>
49
50 #include "areas.h"
51 #include "coord.h"
52 #include "coordit.h"
53 #include "env.h"
54 #include "losglobal.h"
55 #include "mon-act.h"
56 #include "mpr.h"
57
58 // These determine what rays are cast in the precomputation,
59 // and affect start-up time significantly.
60 // XXX: Argue that these values are sufficient.
61 #define LOS_MAX_ANGLE (2*LOS_MAX_RANGE-2)
62 #define LOS_INTERCEPT_MULT (2)
63
64 // These store all unique (in terms of footprint) full rays.
65 // The footprint of ray=fullray[i] consists of ray.length cells,
66 // stored in ray_coords[ray.start..ray.length-1].
67 // These are filled during precomputation (_register_ray).
68 // XXX: fullrays is not needed anymore after precomputation.
69 struct los_ray;
70 static vector<los_ray> fullrays;
71 static vector<coord_def> ray_coords;
72
73 // These store all unique minimal cellrays. For each i,
74 // cellray i ends in cellray_ends[i] and passes through
75 // thoses cells p that have blockrays(p)[i] set. In other
76 // words, blockrays(p)[i] is set iff an opaque cell p blocks
77 // the cellray with index i.
78 static vector<coord_def> cellray_ends;
79 typedef FixedArray<bit_vector*, LOS_MAX_RANGE+1, LOS_MAX_RANGE+1> blockrays_t;
80 static blockrays_t blockrays;
81
82 // We also store the minimal cellrays by target position
83 // for efficient retrieval by find_ray.
84 // XXX: Consider condensing this representation.
85 struct cellray;
86 static FixedArray<vector<cellray>, LOS_MAX_RANGE+1, LOS_MAX_RANGE+1> min_cellrays;
87
88 // Temporary arrays used in losight() to track which rays
89 // are blocked or have seen a smoke cloud.
90 // Allocated when doing the precomputations.
91 static bit_vector *dead_rays = nullptr;
92 static bit_vector *smoke_rays = nullptr;
93
94 class quadrant_iterator : public rectangle_iterator
95 {
96 public:
quadrant_iterator()97 quadrant_iterator()
98 : rectangle_iterator(coord_def(0,0),
99 coord_def(LOS_MAX_RANGE, LOS_MAX_RANGE))
100 {
101 }
102 };
103
clear_rays_on_exit()104 void clear_rays_on_exit()
105 {
106 delete dead_rays;
107 delete smoke_rays;
108 for (quadrant_iterator qi; qi; ++qi)
109 delete blockrays(*qi);
110 }
111
112 // LOS radius.
113 int los_radius = LOS_DEFAULT_RANGE;
114
115 static void _handle_los_change();
116
set_los_radius(int r)117 void set_los_radius(int r)
118 {
119 ASSERT(r <= LOS_RADIUS);
120 los_radius = r;
121 invalidate_los();
122 _handle_los_change();
123 }
124
get_los_radius()125 int get_los_radius()
126 {
127 return los_radius;
128 }
129
double_is_zero(const double x)130 bool double_is_zero(const double x)
131 {
132 return x > -EPSILON_VALUE && x < EPSILON_VALUE;
133 }
134
135 struct los_ray : public ray_def
136 {
137 // The footprint of this ray is stored in
138 // ray_coords[start..start+length-1].
139 unsigned int start;
140 unsigned int length;
141
los_raylos_ray142 los_ray(geom::ray _r)
143 : ray_def(_r), start(0), length(0)
144 {
145 }
146
147 // Shoot a ray from the given start point (accx, accy) with the given
148 // slope, bounded by the pre-calc bounds shape.
149 // Returns the cells it travels through, excluding the origin.
150 // Returns an empty vector if this was a bad ray.
footprintlos_ray151 vector<coord_def> footprint()
152 {
153 vector<coord_def> cs;
154 los_ray copy = *this;
155 coord_def c;
156 coord_def old;
157 int cellnum;
158 for (cellnum = 0; true; ++cellnum)
159 {
160 old = c;
161 if (!copy.advance())
162 {
163 // dprf("discarding corner ray (%f,%f) + t*(%f,%f)",
164 // r.start.x, r.start.y, r.dir.x, r.dir.y);
165 cs.clear();
166 break;
167 }
168 c = copy.pos();
169 if (c.rdist() > LOS_RADIUS)
170 break;
171 cs.push_back(c);
172 ASSERT((c - old).rdist() == 1);
173 }
174 return cs;
175 }
176
operator []los_ray177 coord_def operator[](unsigned int i)
178 {
179 ASSERT(i < length);
180 return ray_coords[start+i];
181 }
182 };
183
184 // Check if the passed rays have identical footprint.
_is_same_ray(los_ray ray,vector<coord_def> newray)185 static bool _is_same_ray(los_ray ray, vector<coord_def> newray)
186 {
187 if (ray.length != newray.size())
188 return false;
189 for (unsigned int i = 0; i < ray.length; i++)
190 if (ray[i] != newray[i])
191 return false;
192 return true;
193 }
194
195 // Check if the passed ray has already been created.
_is_duplicate_ray(vector<coord_def> newray)196 static bool _is_duplicate_ray(vector<coord_def> newray)
197 {
198 for (los_ray lray : fullrays)
199 if (_is_same_ray(lray, newray))
200 return true;
201 return false;
202 }
203
204 // A cellray given by fullray and index of end-point.
205 struct cellray
206 {
207 // A cellray passes through cells ray_coords[ray.start..ray.start+end].
208 los_ray ray;
209 unsigned int end; // Relative index (inside ray) of end cell.
210
cellraycellray211 cellray(const los_ray& r, unsigned int e)
212 : ray(r), end(e), imbalance(-1), first_diag(false)
213 {
214 }
215
216 // The end-point's index inside ray_coord.
indexcellray217 int index() const { return ray.start + end; }
218
219 // The end-point.
targetcellray220 coord_def target() const { return ray_coords[index()]; }
221
222 // XXX: Currently ray/cellray[0] is the first point outside the origin.
operator []cellray223 coord_def operator[](unsigned int i)
224 {
225 ASSERT(i <= end);
226 return ray_coords[ray.start+i];
227 }
228
229 // Parameters used in find_ray. These need to be calculated
230 // only for the minimal cellrays.
231 int imbalance;
232 bool first_diag;
233
234 void calc_params();
235 };
236
237 // Compare two cellrays to the same target.
238 // This determines which ray is considered better by find_ray,
239 // used with list::sort.
240 // Returns true if a is strictly better than b, false else.
_is_better(const cellray & a,const cellray & b)241 static bool _is_better(const cellray& a, const cellray& b)
242 {
243 // Only compare cellrays with equal target.
244 ASSERT(a.target() == b.target());
245 // calc_params() has been called.
246 ASSERT(a.imbalance >= 0);
247 ASSERT(b.imbalance >= 0);
248 if (a.imbalance < b.imbalance)
249 return true;
250 else if (a.imbalance > b.imbalance)
251 return false;
252 else
253 return a.first_diag && !b.first_diag;
254 }
255
256 enum class compare_type
257 {
258 neither,
259 subray,
260 superray,
261 };
262
263 // Check whether one of the passed cellrays is a subray of the
264 // other in terms of footprint.
_compare_cellrays(const cellray & a,const cellray & b)265 static compare_type _compare_cellrays(const cellray& a, const cellray& b)
266 {
267 if (a.target() != b.target())
268 return compare_type::neither;
269
270 int cura = a.ray.start;
271 int curb = b.ray.start;
272 int enda = cura + a.end;
273 int endb = curb + b.end;
274 bool maybe_sub = true;
275 bool maybe_super = true;
276
277 while (cura < enda && curb < endb && (maybe_sub || maybe_super))
278 {
279 coord_def pa = ray_coords[cura];
280 coord_def pb = ray_coords[curb];
281 if (pa.x > pb.x || pa.y > pb.y)
282 {
283 maybe_super = false;
284 curb++;
285 }
286 if (pa.x < pb.x || pa.y < pb.y)
287 {
288 maybe_sub = false;
289 cura++;
290 }
291 if (pa == pb)
292 {
293 cura++;
294 curb++;
295 }
296 }
297 maybe_sub = maybe_sub && cura == enda;
298 maybe_super = maybe_super && curb == endb;
299
300 if (maybe_sub)
301 return compare_type::subray; // includes equality
302 else if (maybe_super)
303 return compare_type::superray;
304 else
305 return compare_type::neither;
306 }
307
308 // Determine all minimal cellrays.
309 // They're stored globally by target in min_cellrays,
310 // and returned as a list of indices into ray_coords.
_find_minimal_cellrays()311 static vector<int> _find_minimal_cellrays()
312 {
313 FixedArray<list<cellray>, LOS_MAX_RANGE+1, LOS_MAX_RANGE+1> minima;
314 list<cellray>::iterator min_it;
315
316 for (los_ray ray : fullrays)
317 {
318 for (unsigned int i = 0; i < ray.length; ++i)
319 {
320 // Is the cellray ray[0..i] duplicated so far?
321 bool dup = false;
322 cellray c(ray, i);
323 list<cellray>& min = minima(c.target());
324
325 bool erased = false;
326 for (min_it = min.begin();
327 min_it != min.end() && !dup;)
328 {
329 switch (_compare_cellrays(*min_it, c))
330 {
331 case compare_type::subray:
332 dup = true;
333 break;
334 case compare_type::superray:
335 min_it = min.erase(min_it);
336 erased = true;
337 // clear this should be added, but might have
338 // to erase more
339 break;
340 case compare_type::neither:
341 default:
342 break;
343 }
344 if (!erased)
345 ++min_it;
346 else
347 erased = false;
348 }
349 if (!dup)
350 min.push_back(c);
351 }
352 }
353
354 vector<int> result;
355 for (quadrant_iterator qi; qi; ++qi)
356 {
357 list<cellray>& min = minima(*qi);
358 for (min_it = min.begin(); min_it != min.end(); ++min_it)
359 {
360 // Calculate imbalance and slope difference for sorting.
361 min_it->calc_params();
362 result.push_back(min_it->index());
363 }
364 min.sort(_is_better);
365 min_cellrays(*qi) = vector<cellray>(min.begin(), min.end());
366 }
367 return result;
368 }
369
370 // Create and register the ray defined by the arguments.
_register_ray(geom::ray r)371 static void _register_ray(geom::ray r)
372 {
373 los_ray ray = los_ray(r);
374 vector<coord_def> coords = ray.footprint();
375
376 if (coords.empty() || _is_duplicate_ray(coords))
377 return;
378
379 ray.start = ray_coords.size();
380 ray.length = coords.size();
381 for (coord_def c : coords)
382 ray_coords.push_back(c);
383 fullrays.push_back(ray);
384 }
385
_create_blockrays()386 static void _create_blockrays()
387 {
388 // First, we calculate blocking information for all cell rays.
389 // Cellrays are numbered according to the index of their end
390 // cell in ray_coords.
391 const int n_cellrays = ray_coords.size();
392 blockrays_t all_blockrays;
393 for (quadrant_iterator qi; qi; ++qi)
394 all_blockrays(*qi) = new bit_vector(n_cellrays);
395
396 for (los_ray ray : fullrays)
397 {
398 for (unsigned int i = 0; i < ray.length; ++i)
399 {
400 // Every cell is contained in (thus blocks)
401 // all following cellrays.
402 for (unsigned int j = i + 1; j < ray.length; ++j)
403 all_blockrays(ray[i])->set(ray.start + j);
404 }
405 }
406
407 // We've built the basic blockray array; now compress it, keeping
408 // only the nonduplicated cellrays.
409
410 // Determine minimal cellrays and store their indices in ray_coords.
411 vector<int> min_indices = _find_minimal_cellrays();
412 const int n_min_rays = min_indices.size();
413 cellray_ends.resize(n_min_rays);
414 for (int i = 0; i < n_min_rays; ++i)
415 cellray_ends[i] = ray_coords[min_indices[i]];
416
417 // Compress blockrays accordingly.
418 for (quadrant_iterator qi; qi; ++qi)
419 {
420 blockrays(*qi) = new bit_vector(n_min_rays);
421 for (int i = 0; i < n_min_rays; ++i)
422 {
423 blockrays(*qi)->set(i, all_blockrays(*qi)
424 ->get(min_indices[i]));
425 }
426 }
427
428 // We can throw away all_blockrays now.
429 for (quadrant_iterator qi; qi; ++qi)
430 delete all_blockrays(*qi);
431
432 dead_rays = new bit_vector(n_min_rays);
433 smoke_rays = new bit_vector(n_min_rays);
434
435 dprf("Cellrays: %d Fullrays: %u Minimal cellrays: %u",
436 n_cellrays, (unsigned int)fullrays.size(), n_min_rays);
437 }
438
_gcd(int x,int y)439 static int _gcd(int x, int y)
440 {
441 int tmp;
442 while (y != 0)
443 {
444 x %= y;
445 tmp = x;
446 x = y;
447 y = tmp;
448 }
449 return x;
450 }
451
_complexity_lt(const pair<int,int> & lhs,const pair<int,int> & rhs)452 static bool _complexity_lt(const pair<int,int>& lhs, const pair<int,int>& rhs)
453 {
454 return lhs.first * lhs.second < rhs.first * rhs.second;
455 }
456
457 // Cast all rays
raycast()458 static void raycast()
459 {
460 static bool done_raycast = false;
461 if (done_raycast)
462 return;
463
464 // Creating all rays for first quadrant
465 // We have a considerable amount of overkill.
466 done_raycast = true;
467
468 // register perpendiculars FIRST, to make them top choice
469 // when selecting beams
470 _register_ray(geom::ray(0.5, 0.5, 0.0, 1.0));
471 _register_ray(geom::ray(0.5, 0.5, 1.0, 0.0));
472
473 // For a slope of M = y/x, every x we move on the X axis means
474 // that we move y on the y axis. We want to look at the resolution
475 // of x/y: in that case, every step on the X axis means an increase
476 // of 1 in the Y axis at the intercept point. We can assume gcd(x,y)=1,
477 // so we look at steps of 1/y.
478
479 // Changing the order a bit. We want to order by the complexity
480 // of the beam, which is log(x) + log(y) ~ xy.
481 vector<pair<int,int> > xyangles;
482 for (int xangle = 1; xangle <= LOS_MAX_ANGLE; ++xangle)
483 for (int yangle = 1; yangle <= LOS_MAX_ANGLE; ++yangle)
484 {
485 if (_gcd(xangle, yangle) == 1)
486 xyangles.emplace_back(xangle, yangle);
487 }
488
489 sort(xyangles.begin(), xyangles.end(), _complexity_lt);
490 for (auto xyangle : xyangles)
491 {
492 const int xangle = xyangle.first;
493 const int yangle = xyangle.second;
494
495 for (int intercept = 1; intercept < LOS_INTERCEPT_MULT*yangle; ++intercept)
496 {
497 double xstart = ((double)intercept) / (LOS_INTERCEPT_MULT*yangle);
498 double ystart = 0.5;
499
500 _register_ray(geom::ray(xstart, ystart, xangle, yangle));
501 // also draw the identical ray in octant 2
502 _register_ray(geom::ray(ystart, xstart, yangle, xangle));
503 }
504 }
505
506 // Now create the appropriate blockrays array
507 _create_blockrays();
508 }
509
_imbalance(ray_def ray,const coord_def & target)510 static int _imbalance(ray_def ray, const coord_def& target)
511 {
512 int imb = 0;
513 int diags = 0, straights = 0;
514 while (ray.pos() != target)
515 {
516 coord_def old = ray.pos();
517 if (!ray.advance())
518 die("can't advance ray");
519 switch ((ray.pos() - old).abs())
520 {
521 case 1:
522 diags = 0;
523 if (++straights > imb)
524 imb = straights;
525 break;
526 case 2:
527 straights = 0;
528 if (++diags > imb)
529 imb = diags;
530 break;
531 default:
532 die("ray imbalance out of range");
533 }
534 }
535 return imb;
536 }
537
calc_params()538 void cellray::calc_params()
539 {
540 coord_def trg = target();
541 imbalance = _imbalance(ray, trg);
542 first_diag = ((*this)[0].abs() == 2);
543 }
544
545 // Find ray in positive quadrant.
546 // opc has been translated for this quadrant.
547 // XXX: Allow finding ray of minimum opacity.
_find_ray_se(const coord_def & target,ray_def & ray,const opacity_func & opc,int range,bool cycle)548 static bool _find_ray_se(const coord_def& target, ray_def& ray,
549 const opacity_func& opc, int range, bool cycle)
550 {
551 ASSERT(target.x >= 0);
552 ASSERT(target.y >= 0);
553 ASSERT(!target.origin());
554 if (target.rdist() > range)
555 return false;
556
557 ASSERT(target.rdist() <= LOS_RADIUS);
558
559 // Ensure the precalculations have been done.
560 raycast();
561
562 const vector<cellray> &min = min_cellrays(target);
563 ASSERT(!min.empty());
564 cellray c = min[0]; // XXX: const cellray &c ?
565 unsigned int index = 0;
566
567 if (cycle)
568 dprf("cycling from %d (total %u)", ray.cycle_idx, (unsigned int)min.size());
569
570 unsigned int start = cycle ? ray.cycle_idx + 1 : 0;
571 ASSERT(start <= min.size());
572
573 int blocked = OPC_OPAQUE;
574 for (unsigned int i = start;
575 (blocked >= OPC_OPAQUE) && (i < start + min.size()); i++)
576 {
577 index = i % min.size();
578 c = min[index];
579 blocked = OPC_CLEAR;
580 // Check all inner points.
581 for (unsigned int j = 0; j < c.end && blocked < OPC_OPAQUE; j++)
582 blocked += opc(c[j]);
583 }
584 if (blocked >= OPC_OPAQUE)
585 return false;
586
587 ray = c.ray;
588 ray.cycle_idx = index;
589
590 return true;
591 }
592
593 // Coordinate transformation so we can find_ray quadrant-by-quadrant.
594 struct opacity_trans : public opacity_func
595 {
596 const coord_def& source;
597 int signx, signy;
598 const opacity_func& orig;
599
opacity_transopacity_trans600 opacity_trans(const opacity_func& opc, const coord_def& s, int sx, int sy)
601 : source(s), signx(sx), signy(sy), orig(opc)
602 {
603 }
604
CLONEopacity_trans605 CLONE(opacity_trans)
606
607 opacity_type operator()(const coord_def &l) const override
608 {
609 return orig(transform(l));
610 }
611
transformopacity_trans612 coord_def transform(const coord_def &l) const
613 {
614 return coord_def(source.x + signx*l.x, source.y + signy*l.y);
615 }
616 };
617
618 // Find a nonblocked ray from source to target. Return false if no
619 // such ray could be found, otherwise return true and fill ray
620 // appropriately.
621 // if range is too great or all rays are blocked.
622 // If cycle is false, find the first fitting ray. If it is true,
623 // assume that ray is appropriately filled in, and look for the next
624 // ray. We only ever use ray.cycle_idx.
find_ray(const coord_def & source,const coord_def & target,ray_def & ray,const opacity_func & opc,int range,bool cycle)625 bool find_ray(const coord_def& source, const coord_def& target,
626 ray_def& ray, const opacity_func& opc, int range,
627 bool cycle)
628 {
629 if (target == source || !map_bounds(source) || !map_bounds(target))
630 return false;
631
632 const int signx = ((target.x - source.x >= 0) ? 1 : -1);
633 const int signy = ((target.y - source.y >= 0) ? 1 : -1);
634 const int absx = signx * (target.x - source.x);
635 const int absy = signy * (target.y - source.y);
636 const coord_def abs = coord_def(absx, absy);
637 opacity_trans opc_trans = opacity_trans(opc, source, signx, signy);
638
639 if (!_find_ray_se(abs, ray, opc_trans, range, cycle))
640 return false;
641
642 if (signx < 0)
643 ray.r.start.x = 1.0 - ray.r.start.x;
644 if (signy < 0)
645 ray.r.start.y = 1.0 - ray.r.start.y;
646 ray.r.dir.x *= signx;
647 ray.r.dir.y *= signy;
648
649 ray.r.start.x += source.x;
650 ray.r.start.y += source.y;
651
652 return true;
653 }
654
exists_ray(const coord_def & source,const coord_def & target,const opacity_func & opc,int range)655 bool exists_ray(const coord_def& source, const coord_def& target,
656 const opacity_func& opc, int range)
657 {
658 ray_def ray;
659 return find_ray(source, target, ray, opc, range);
660 }
661
662 // Assuming that target is in view of source, but line of
663 // fire is blocked, what is it blocked by?
ray_blocker(const coord_def & source,const coord_def & target)664 dungeon_feature_type ray_blocker(const coord_def& source,
665 const coord_def& target)
666 {
667 ray_def ray;
668 if (!find_ray(source, target, ray, opc_default))
669 return NUM_FEATURES;
670
671 ray.advance();
672 int blocked = 0;
673 while (ray.pos() != target)
674 {
675 blocked += opc_solid_see(ray.pos());
676 if (blocked >= OPC_OPAQUE)
677 return env.grid(ray.pos());
678 ray.advance();
679 }
680 ASSERT(false);
681 return NUM_FEATURES;
682 }
683
684 // Returns a straight ray from source to target.
fallback_ray(const coord_def & source,const coord_def & target,ray_def & ray)685 void fallback_ray(const coord_def& source, const coord_def& target,
686 ray_def& ray)
687 {
688 ray.r.start.x = source.x + 0.5;
689 ray.r.start.y = source.y + 0.5;
690 coord_def diff = target - source;
691 ray.r.dir.x = diff.x;
692 ray.r.dir.y = diff.y;
693 ray.on_corner = false;
694 }
695
696 // Count the number of matching features between two points along
697 // a beam-like path; the path will pass through solid features.
698 // By default, it excludes end points from the count.
699 // If just_check is true, the function will return early once one
700 // such feature is encountered.
num_feats_between(const coord_def & source,const coord_def & target,dungeon_feature_type min_feat,dungeon_feature_type max_feat,bool exclude_endpoints,bool just_check)701 int num_feats_between(const coord_def& source, const coord_def& target,
702 dungeon_feature_type min_feat,
703 dungeon_feature_type max_feat,
704 bool exclude_endpoints, bool just_check)
705 {
706 ray_def ray;
707 int count = 0;
708 int max_dist = grid_distance(source, target);
709
710 ASSERT(map_bounds(source));
711 ASSERT(map_bounds(target));
712
713 if (source == target)
714 return 0; // XXX: might want to count the cell.
715
716 // We don't need to find the shortest beam, any beam will suffice.
717 fallback_ray(source, target, ray);
718
719 if (exclude_endpoints && ray.pos() == source)
720 {
721 ray.advance();
722 max_dist--;
723 }
724
725 int dist = 0;
726 bool reached_target = false;
727 while (dist++ <= max_dist)
728 {
729 const dungeon_feature_type feat = env.grid(ray.pos());
730
731 if (ray.pos() == target)
732 reached_target = true;
733
734 if (feat >= min_feat && feat <= max_feat
735 && (!exclude_endpoints || !reached_target))
736 {
737 count++;
738
739 if (just_check) // Only needs to be > 0.
740 return count;
741 }
742
743 if (reached_target)
744 break;
745
746 ray.advance();
747 }
748
749 return count;
750 }
751
752 // Is p2 visible from p1, disregarding half-opaque objects?
cell_see_cell_nocache(const coord_def & p1,const coord_def & p2)753 bool cell_see_cell_nocache(const coord_def& p1, const coord_def& p2)
754 {
755 return exists_ray(p1, p2, opc_fullyopaque);
756 }
757
758 // We use raycasting. The algorithm:
759 // PRECOMPUTATION:
760 // Create a large bundle of rays and cast them.
761 // Mark, for each one, which cells kill it (and where.)
762 // Also, for each one, note which cells it passes.
763 // ACTUAL LOS:
764 // Unite the ray-killers for the given map; this tells you which rays
765 // are dead.
766 // Look up which cells the surviving rays have, and that's your LOS!
767 // OPTIMIZATIONS:
768 // WLOG, we can assume that we're in a specific quadrant - say the
769 // first quadrant - and just mirror everything after that. We can
770 // likely get away with a single octant, but we don't do that. (To
771 // do...)
772 // Rays are actually split by each cell they pass. So each "ray" only
773 // identifies a single cell, and we can do logical ORs. Once a cell
774 // kills a cellray, it will kill all remaining cellrays of that ray.
775 // Also, rays are checked to see if they are duplicates of each
776 // other. If they are, they're eliminated.
777 // Some cellrays can also be eliminated. In general, a cellray is
778 // unnecessary if there is another cellray with the same coordinates,
779 // and whose path (up to those coordinates) is a subset, not necessarily
780 // proper, of the original path. We still store the original cellrays
781 // fully for beam detection and such.
782 // PERFORMANCE:
783 // With reasonable values we have around 6000 cellrays, meaning
784 // around 600Kb (75 KB) of data. This gets cut down to 700 cellrays
785 // after removing duplicates. That means that we need to do
786 // around 22*100*4 ~ 9,000 memory reads + writes per LOS call on a
787 // 32-bit system. Not too bad.
788 // IMPROVEMENTS:
789 // Smoke will now only block LOS after two cells of smoke. This is
790 // done by updating with a second array.
791
_losight_quadrant(los_grid & sh,const los_param & dat,int sx,int sy)792 static void _losight_quadrant(los_grid& sh, const los_param& dat, int sx, int sy)
793 {
794 const unsigned int num_cellrays = cellray_ends.size();
795
796 dead_rays->reset();
797 smoke_rays->reset();
798
799 for (quadrant_iterator qi; qi; ++qi)
800 {
801 coord_def p = coord_def(sx*(qi->x), sy*(qi->y));
802 if (!dat.los_bounds(p))
803 continue;
804
805 switch (dat.opacity(p))
806 {
807 case OPC_OPAQUE:
808 // Block the appropriate rays.
809 *dead_rays |= *blockrays(*qi);
810 break;
811 case OPC_HALF:
812 // Block rays which have already seen a cloud.
813 *dead_rays |= (*smoke_rays & *blockrays(*qi));
814 *smoke_rays |= *blockrays(*qi);
815 break;
816 default:
817 break;
818 }
819 }
820
821 // Ray calculation done. Now work out which cells in this
822 // quadrant are visible.
823 for (unsigned int rayidx = 0; rayidx < num_cellrays; ++rayidx)
824 {
825 // make the cells seen by this ray at this point visible
826 if (!dead_rays->get(rayidx))
827 {
828 // This ray is alive, thus the end cell is visible.
829 const coord_def p = coord_def(sx * cellray_ends[rayidx].x,
830 sy * cellray_ends[rayidx].y);
831 if (dat.los_bounds(p))
832 sh(p) = true;
833 }
834 }
835 }
836
837 struct los_param_funcs : public los_param
838 {
839 coord_def center;
840 const opacity_func& opc;
841 const circle_def& bounds;
842
los_param_funcslos_param_funcs843 los_param_funcs(const coord_def& c,
844 const opacity_func& o, const circle_def& b)
845 : center(c), opc(o), bounds(b)
846 {
847 }
848
los_boundslos_param_funcs849 bool los_bounds(const coord_def& p) const override
850 {
851 return map_bounds(p + center) && bounds.contains(p);
852 }
853
opacitylos_param_funcs854 opacity_type opacity(const coord_def& p) const override
855 {
856 return opc(p + center);
857 }
858 };
859
losight(los_grid & sh,const coord_def & center,const opacity_func & opc,const circle_def & bounds)860 void losight(los_grid& sh, const coord_def& center,
861 const opacity_func& opc, const circle_def& bounds)
862 {
863 const los_param& dat = los_param_funcs(center, opc, bounds);
864
865 sh.init(false);
866
867 // Do precomputations if necessary.
868 raycast();
869
870 const int quadrant_x[4] = { 1, -1, -1, 1 };
871 const int quadrant_y[4] = { 1, 1, -1, -1 };
872 for (int q = 0; q < 4; ++q)
873 _losight_quadrant(sh, dat, quadrant_x[q], quadrant_y[q]);
874
875 // Center is always visible.
876 const coord_def o = coord_def(0,0);
877 sh(o) = true;
878 }
879
mons_opacity(const monster * mon,los_type how)880 opacity_type mons_opacity(const monster* mon, los_type how)
881 {
882 // no regard for LOS_ARENA
883 if (mons_species(mon->type) == MONS_BUSH
884 && how != LOS_SOLID)
885 {
886 return OPC_HALF;
887 }
888
889 return OPC_CLEAR;
890 }
891
892 /////////////////////////////////////
893 // A start at tracking LOS changes.
894
895 // Something that affects LOS (with default parameters)
896 // has changed somewhere.
_handle_los_change()897 static void _handle_los_change()
898 {
899 invalidate_agrid();
900 }
901
_mons_block_sight(const monster * mons)902 static bool _mons_block_sight(const monster* mons)
903 {
904 // must be the least permissive one
905 return mons_opacity(mons, LOS_SOLID_SEE) != OPC_CLEAR;
906 }
907
los_actor_moved(const actor * act,const coord_def & oldpos)908 void los_actor_moved(const actor* act, const coord_def& oldpos)
909 {
910 if (act->is_monster() && _mons_block_sight(act->as_monster()))
911 {
912 invalidate_los_around(oldpos);
913 invalidate_los_around(act->pos());
914 _handle_los_change();
915 }
916 }
917
los_monster_died(const monster * mon)918 void los_monster_died(const monster* mon)
919 {
920 if (_mons_block_sight(mon))
921 {
922 invalidate_los_around(mon->pos());
923 _handle_los_change();
924 }
925 }
926
927 // Might want to pass new/old terrain.
los_terrain_changed(const coord_def & p)928 void los_terrain_changed(const coord_def& p)
929 {
930 invalidate_los_around(p);
931 _handle_los_change();
932 }
933
los_changed()934 void los_changed()
935 {
936 mons_reset_just_seen();
937 invalidate_los();
938 _handle_los_change();
939 }
940