1 /**
2 * @file
3 * @brief Code related to travel exclusions.
4 **/
5
6 #include "AppHdr.h"
7
8 #include "exclude.h"
9
10 #include <algorithm>
11 #include <sstream>
12
13 #include "cloud.h"
14 #include "coord.h"
15 #include "coordit.h"
16 #include "dgn-overview.h"
17 #include "english.h"
18 #include "env.h"
19 #include "hints.h"
20 #include "libutil.h"
21 #include "mon-util.h"
22 #include "options.h"
23 #include "stringutil.h"
24 #include "tags.h"
25 #include "terrain.h"
26 #include "tiles-build-specific.h"
27 #include "travel.h"
28 #include "view.h"
29
30 // defined in dgn-overview.cc
31 extern set<pair<string, level_id> > auto_unique_annotations;
32
_mon_needs_auto_exclude(const monster * mon,bool sleepy=false)33 static bool _mon_needs_auto_exclude(const monster* mon, bool sleepy = false)
34 {
35 // These include the base monster's name in their name, but we don't
36 // want things in the auto_exclude option to match them.
37 if (mon->type == MONS_PILLAR_OF_SALT || mon->type == MONS_BLOCK_OF_ICE
38 || mons_class_is_test(mon->type)) // don't autoexclude test statues/spawners
39 {
40 return false;
41 }
42
43 if (mon->is_stationary())
44 return !sleepy;
45
46 // Auto exclusion only makes sense if the monster is still asleep.
47 return mon->asleep();
48 }
49
50 // Check whether a given monster is listed in the auto_exclude option.
_need_auto_exclude(const monster * mon,bool sleepy=false)51 static bool _need_auto_exclude(const monster* mon, bool sleepy = false)
52 {
53 // This only works if the name is lowercased.
54 string name = mon->name(DESC_BASENAME, mon->is_stationary()
55 && testbits(mon->flags, MF_SEEN));
56 lowercase(name);
57
58 for (const text_pattern &pat : Options.auto_exclude)
59 {
60 if (pat.matches(name)
61 && _mon_needs_auto_exclude(mon, sleepy)
62 && (mon->attitude == ATT_HOSTILE))
63 {
64 return true;
65 }
66 }
67
68 return false;
69 }
70
71 // Nightstalker reduces LOS, so reducing the maximum exclusion radius
72 // only makes sense. This is only possible because it's a permanent
73 // mutation; other sources of LOS reduction should not have this effect.
74 // Similarly, Barachim's LOS increase.
_get_full_exclusion_radius()75 static int _get_full_exclusion_radius()
76 {
77 // XXX: dedup with update_vision_range()!
78 return LOS_DEFAULT_RANGE - you.get_mutation_level(MUT_NIGHTSTALKER)
79 + (you.species == SP_BARACHI ? 1 : 0);
80 }
81
82 /**
83 * Adds auto-exclusions for any monsters in LOS that need them.
84 */
add_auto_excludes()85 void add_auto_excludes()
86 {
87 if (!is_map_persistent() || !map_bounds(you.pos()))
88 return;
89
90 vector<monster*> mons;
91 for (radius_iterator ri(you.pos(), LOS_DEFAULT); ri; ++ri)
92 {
93 monster *mon = monster_at(*ri);
94 if (!mon || mon->is_summoned())
95 continue;
96 // Something of a speed hack, but some vaults have a TON of plants.
97 if (mon->type == MONS_PLANT)
98 continue;
99 if (_need_auto_exclude(mon) && !is_exclude_root(*ri))
100 {
101 int radius = _get_full_exclusion_radius();
102 set_exclude(*ri, radius, true);
103 mons.emplace_back(mon);
104 }
105 }
106
107 if (mons.empty())
108 return;
109
110 mprf(MSGCH_WARN, "Marking area around %s as unsafe for travelling.",
111 describe_monsters_condensed(mons).c_str());
112 learned_something_new(HINT_AUTO_EXCLUSION);
113 }
114
travel_exclude(const coord_def & p,int r,bool autoexcl,string dsc,bool vaultexcl)115 travel_exclude::travel_exclude(const coord_def &p, int r,
116 bool autoexcl, string dsc, bool vaultexcl)
117 : pos(p), radius(r),
118 uptodate(false), autoex(autoexcl), desc(dsc), vault(vaultexcl)
119 {
120 const monster* m = monster_at(p);
121 if (m)
122 {
123 // Don't exclude past glass for stationary monsters.
124 if (m->is_stationary())
125 los = los_def(p, opc_fully_no_trans, circle_def(r, C_SQUARE));
126 else
127 los = los_def(p, opc_excl, circle_def(r, C_SQUARE));
128 }
129 else
130 los = los_def(p, opc_excl, circle_def(r, C_SQUARE));
131 set_los();
132 }
133
134 // For exclude_map[p] = foo;
travel_exclude()135 travel_exclude::travel_exclude()
136 : pos(-1, -1), radius(-1),
137 los(coord_def(-1, -1), opc_excl, circle_def(-1, C_SQUARE)),
138 uptodate(false), autoex(false), desc(""), vault(false)
139 {
140 }
141
142 extern exclude_set curr_excludes; // in travel.cc
143
set_los()144 void travel_exclude::set_los()
145 {
146 uptodate = true;
147 if (radius > 1)
148 {
149 // Radius might have been changed, and this is cheap.
150 los.set_bounds(circle_def(radius, C_SQUARE));
151 los.update();
152 }
153 }
154
affects(const coord_def & p) const155 bool travel_exclude::affects(const coord_def& p) const
156 {
157 if (!uptodate)
158 {
159 mprf(MSGCH_ERROR, "exclusion not up-to-date: e (%d,%d) p (%d,%d)",
160 pos.x, pos.y, p.x, p.y);
161 }
162 if (radius == 0)
163 return p == pos;
164 else if (radius == 1)
165 return (p - pos).rdist() <= 1;
166 else
167 return los.see_cell(p);
168 }
169
in_bounds(const coord_def & p) const170 bool travel_exclude::in_bounds(const coord_def &p) const
171 {
172 return radius == 0 && p == pos
173 || radius == 1 && (p - pos).rdist() <= 1
174 || los.in_bounds(p);
175 }
176
177 /////////////////////////////////////////////////////////////////////////
178
exclude_set()179 exclude_set::exclude_set()
180 {
181 }
182
clear()183 void exclude_set::clear()
184 {
185 exclude_roots.clear();
186 exclude_points.clear();
187 }
188
erase(const coord_def & p)189 void exclude_set::erase(const coord_def &p)
190 {
191 auto it = exclude_roots.find(p);
192
193 if (it == exclude_roots.end())
194 return;
195
196 travel_exclude old_ex = it->second;
197 exclude_roots.erase(it);
198
199 recompute_excluded_points();
200 }
201
add_exclude(travel_exclude & ex)202 void exclude_set::add_exclude(travel_exclude &ex)
203 {
204 add_exclude_points(ex);
205 exclude_roots[ex.pos] = ex;
206 }
207
add_exclude(const coord_def & p,int radius,bool autoexcl,string desc,bool vaultexcl)208 void exclude_set::add_exclude(const coord_def &p, int radius,
209 bool autoexcl, string desc,
210 bool vaultexcl)
211 {
212 travel_exclude ex(p, radius, autoexcl, desc, vaultexcl);
213 add_exclude(ex);
214 }
215
add_exclude_points(travel_exclude & ex)216 void exclude_set::add_exclude_points(travel_exclude& ex)
217 {
218 if (ex.radius == 0)
219 {
220 exclude_points.insert(ex.pos);
221 return;
222 }
223
224 if (!ex.uptodate)
225 ex.set_los();
226 else
227 ex.los.update();
228
229 for (radius_iterator ri(ex.pos, ex.radius, C_SQUARE); ri; ++ri)
230 if (ex.affects(*ri))
231 exclude_points.insert(*ri);
232 }
233
update_excluded_points(bool recompute_los)234 void exclude_set::update_excluded_points(bool recompute_los)
235 {
236 for (iterator it = exclude_roots.begin(); it != exclude_roots.end(); ++it)
237 {
238 travel_exclude &ex = it->second;
239 if (!ex.uptodate)
240 {
241 recompute_excluded_points(recompute_los);
242 return;
243 }
244 }
245 }
246
recompute_excluded_points(bool recompute_los)247 void exclude_set::recompute_excluded_points(bool recompute_los)
248 {
249 exclude_points.clear();
250 for (iterator it = exclude_roots.begin(); it != exclude_roots.end(); ++it)
251 {
252 travel_exclude &ex = it->second;
253 if (recompute_los)
254 ex.set_los();
255 add_exclude_points(ex);
256 }
257 }
258
is_excluded(const coord_def & p) const259 bool exclude_set::is_excluded(const coord_def &p) const
260 {
261 return exclude_points.count(p);
262 }
263
is_exclude_root(const coord_def & p) const264 bool exclude_set::is_exclude_root(const coord_def &p) const
265 {
266 return exclude_roots.count(p);
267 }
268
get_exclude_root(const coord_def & p)269 travel_exclude* exclude_set::get_exclude_root(const coord_def &p)
270 {
271 return map_find(exclude_roots, p);
272 }
273
size() const274 size_t exclude_set::size() const
275 {
276 return exclude_roots.size();
277 }
278
empty() const279 bool exclude_set::empty() const
280 {
281 return exclude_roots.empty();
282 }
283
begin() const284 exclude_set::const_iterator exclude_set::begin() const
285 {
286 return exclude_roots.begin();
287 }
288
end() const289 exclude_set::const_iterator exclude_set::end() const
290 {
291 return exclude_roots.end();
292 }
293
begin()294 exclude_set::iterator exclude_set::begin()
295 {
296 return exclude_roots.begin();
297 }
298
end()299 exclude_set::iterator exclude_set::end()
300 {
301 return exclude_roots.end();
302 }
303
304 /////////////////////////////////////////////////////////////////////////
305
_mark_excludes_non_updated(const coord_def & p)306 static void _mark_excludes_non_updated(const coord_def &p)
307 {
308 for (auto &entry : curr_excludes)
309 {
310 travel_exclude &ex = entry.second;
311 ex.uptodate = ex.uptodate && !ex.in_bounds(p);
312 }
313 }
314
init_exclusion_los()315 void init_exclusion_los()
316 {
317 curr_excludes.recompute_excluded_points(true);
318 }
319
320 /*
321 * Update exclusions' LOS to reflect changes within their range.
322 * "changed" is a list of coordinates that have been changed.
323 * Only exclusions that might have one of the changed points
324 * in view are updated.
325 */
update_exclusion_los(vector<coord_def> changed)326 void update_exclusion_los(vector<coord_def> changed)
327 {
328 if (changed.empty())
329 return;
330
331 for (coord_def c : changed)
332 _mark_excludes_non_updated(c);
333
334 curr_excludes.update_excluded_points(true);
335 }
336
is_excluded(const coord_def & p,const exclude_set & exc)337 bool is_excluded(const coord_def &p, const exclude_set &exc)
338 {
339 return exc.is_excluded(p);
340 }
341
is_exclude_root(const coord_def & p)342 bool is_exclude_root(const coord_def &p)
343 {
344 return curr_excludes.get_exclude_root(p);
345 }
346
get_exclusion_radius(const coord_def & p)347 int get_exclusion_radius(const coord_def &p)
348 {
349 if (travel_exclude *exc = curr_excludes.get_exclude_root(p))
350 {
351 if (!exc->radius)
352 return 1;
353 else
354 return exc->radius;
355 }
356 return 0;
357 }
358
get_exclusion_desc(const coord_def & p)359 string get_exclusion_desc(const coord_def &p)
360 {
361 if (travel_exclude *exc = curr_excludes.get_exclude_root(p))
362 return exc->desc;
363 return "";
364 }
365
366 #ifdef USE_TILE
367 // update Gmap for squares surrounding exclude centre
_tile_exclude_gmap_update(const coord_def & p)368 static void _tile_exclude_gmap_update(const coord_def &p)
369 {
370 for (int x = -8; x <= 8; x++)
371 for (int y = -8; y <= 8; y++)
372 {
373 const coord_def pc(p.x + x, p.y + y);
374 tiles.update_minimap(pc);
375 }
376 }
377 #endif
378
_exclude_update()379 static void _exclude_update()
380 {
381 set_level_exclusion_annotation(curr_excludes.get_exclusion_desc());
382 travel_cache.update_excludes();
383 }
384
_exclude_update(const coord_def & p)385 static void _exclude_update(const coord_def &p)
386 {
387 #ifdef USE_TILE
388 _tile_exclude_gmap_update(p);
389 #else
390 UNUSED(p);
391 #endif
392 _exclude_update();
393 }
394
395 // Catch up exclude updates from set_exclude with defer_updates=true.
396 //
397 // Warning: For tiles, this assumes all changed exclude centres
398 // are still there, so this won't work as is for
399 // del_exclude.
deferred_exclude_update()400 void deferred_exclude_update()
401 {
402 _exclude_update();
403 #ifdef USE_TILE
404 for (const auto &entry : curr_excludes)
405 _tile_exclude_gmap_update(entry.second.pos);
406 #endif
407 }
408
clear_excludes()409 void clear_excludes()
410 {
411 #ifdef USE_TILE
412 // Tiles needs to update the minimap for each exclusion that is removed,
413 // but the exclusions need to be removed first. Therefore, make a copy
414 // of the current set of exclusions and iterate through the copy below.
415 exclude_set excludes = curr_excludes;
416 #endif
417
418 curr_excludes.clear();
419 clear_level_exclusion_annotation();
420
421 #ifdef USE_TILE
422 for (const auto &entry : excludes)
423 _tile_exclude_gmap_update(entry.second.pos);
424 #endif
425
426 _exclude_update();
427 }
428
_exclude_gate(const coord_def & p,bool del=false)429 static void _exclude_gate(const coord_def &p, bool del = false)
430 {
431 set<coord_def> all_doors;
432 find_connected_identical(p, all_doors, true);
433 for (const auto &dc : all_doors)
434 {
435 if (del)
436 del_exclude(dc);
437 else
438 set_exclude(dc, 0);
439 }
440 }
441
442 // Cycles the radius of an exclusion, including "off" state;
443 // may start at 0 < radius < LOS_RADIUS, but won't cycle there.
cycle_exclude_radius(const coord_def & p)444 void cycle_exclude_radius(const coord_def &p)
445 {
446 if (travel_exclude *exc = curr_excludes.get_exclude_root(p))
447 {
448 if (feat_is_door(env.grid(p)) && env.map_knowledge(p).known())
449 {
450 _exclude_gate(p, exc->radius == 0);
451 return;
452 }
453 if (exc->radius > 0)
454 set_exclude(p, 0);
455 else
456 del_exclude(p);
457 }
458 else
459 set_exclude(p, _get_full_exclusion_radius());
460 }
461
462 // Remove a possible exclude.
del_exclude(const coord_def & p)463 void del_exclude(const coord_def &p)
464 {
465 curr_excludes.erase(p);
466 _exclude_update(p);
467 }
468
469 // Set or update an exclude.
set_exclude(const coord_def & p,int radius,bool autoexcl,bool vaultexcl,bool defer_updates)470 void set_exclude(const coord_def &p, int radius, bool autoexcl, bool vaultexcl,
471 bool defer_updates)
472 {
473 if (!is_map_persistent())
474 return;
475
476 if (!in_bounds(p))
477 return;
478
479 if (travel_exclude *exc = curr_excludes.get_exclude_root(p))
480 {
481 if (exc->desc.empty() && defer_updates)
482 {
483 if (cloud_struct* cloud = cloud_at(p))
484 exc->desc = cloud->cloud_name(true) + " cloud";
485 }
486 else if (exc->radius == radius)
487 return;
488
489 exc->radius = radius;
490 exc->uptodate = false;
491 curr_excludes.recompute_excluded_points();
492 }
493 else
494 {
495 string desc = "";
496 if (!defer_updates)
497 {
498 // Don't list a monster in the exclusion annotation if the
499 // exclusion was triggered by e.g. the flamethrowers' lua check.
500 const map_cell& cell = env.map_knowledge(p);
501 if (cell.monster() != MONS_NO_MONSTER)
502 {
503 desc = mons_type_name(cell.monster(), DESC_PLAIN);
504 if (cell.detected_monster())
505 desc += " (detected)";
506 }
507 else
508 {
509 // Maybe it's a door or staircase?
510 const dungeon_feature_type feat = cell.feat();
511 if (feat_is_door(feat))
512 desc = "door";
513 else
514 {
515 const command_type dir = feat_stair_direction(feat);
516 if (dir == CMD_GO_UPSTAIRS)
517 desc = "upstairs";
518 else if (dir == CMD_GO_DOWNSTAIRS)
519 desc = "downstairs";
520 }
521 }
522 }
523 else if (cloud_struct* cloud = cloud_at(p))
524 desc = cloud->cloud_name(true) + " cloud";
525
526 curr_excludes.add_exclude(p, radius, autoexcl, desc, vaultexcl);
527 }
528
529 if (!defer_updates)
530 _exclude_update(p);
531 }
532
533 // If a cell that was placed automatically no longer contains the original
534 // monster (or it is invisible), or if the player is no longer vulnerable to a
535 // damaging cloud, then remove the exclusion.
maybe_remove_autoexclusion(const coord_def & p)536 void maybe_remove_autoexclusion(const coord_def &p)
537 {
538 if (travel_exclude *exc = curr_excludes.get_exclude_root(p))
539 {
540 if (!exc->autoex)
541 return;
542
543 const monster* m = monster_at(p);
544 // We don't want to remove excluded clouds, check exc desc
545 // XXX: This conditional is a mess.
546 string desc = exc->desc;
547 bool cloudy_exc = ends_with(desc, "cloud");
548 if ((!m || !you.can_see(*m)
549 || !_need_auto_exclude(m)
550 || mons_type_name(m->type, DESC_PLAIN) != desc)
551 && !cloudy_exc)
552 {
553 del_exclude(p);
554 }
555 else if (cloudy_exc && you.cloud_immune())
556 del_exclude(p);
557 }
558 }
559
560 // Lists all exclusions on the current level.
get_exclusion_desc()561 string exclude_set::get_exclusion_desc()
562 {
563 vector<string> desc;
564 int count_other = 0;
565 for (auto &entry : exclude_roots)
566 {
567 travel_exclude &ex = entry.second;
568
569 // Don't count cloud exclusions.
570 if (strstr(ex.desc.c_str(), "cloud"))
571 continue;
572
573 // Don't duplicate if there's already an annotation from unique monsters.
574 auto ma = auto_unique_annotations.find(make_pair(ex.desc,
575 level_id::current()));
576 if (ma != auto_unique_annotations.end())
577 continue;
578
579 if (!ex.desc.empty())
580 desc.push_back(ex.desc);
581 else
582 count_other++;
583 }
584
585 if (desc.size() > 1)
586 {
587 // Combine identical descriptions.
588 sort(desc.begin(), desc.end());
589 vector<string> help = desc;
590 desc.clear();
591 string old_desc = "";
592 int count = 1;
593 for (unsigned int i = 0; i < help.size(); ++i)
594 {
595 string tmp = help[i];
596 if (i == 0)
597 old_desc = tmp;
598 else
599 {
600 if (strcmp(tmp.c_str(), old_desc.c_str()) == 0)
601 count++;
602 else
603 {
604 if (count == 1)
605 desc.push_back(old_desc);
606 else
607 {
608 desc.push_back(make_stringf("%d %s",
609 count, pluralise(old_desc).c_str()));
610 count = 1;
611 }
612 old_desc = tmp;
613 }
614 }
615 }
616 if (count == 1)
617 desc.push_back(old_desc);
618 else
619 {
620 desc.push_back(make_stringf("%d %s",
621 count, pluralise(old_desc).c_str()));
622 }
623 }
624
625 if (count_other > 0)
626 {
627 desc.push_back(make_stringf("%d %sexclusion%s",
628 count_other, desc.empty() ? "" : "more ",
629 count_other > 1 ? "s" : ""));
630 }
631 else if (desc.empty())
632 return "";
633
634 string desc_str = "";
635 if (desc.size() > 1 || count_other == 0)
636 {
637 desc_str += "exclusion";
638 if (desc.size() > 1)
639 desc_str += "s";
640 desc_str += ": ";
641 }
642 return desc_str + comma_separated_line(desc.begin(), desc.end(),
643 " and ", ", ");
644 }
645
marshallExcludes(writer & outf,const exclude_set & excludes)646 void marshallExcludes(writer& outf, const exclude_set& excludes)
647 {
648 marshallShort(outf, excludes.size());
649 if (excludes.size())
650 {
651 for (const auto &entry : excludes)
652 {
653 const travel_exclude &ex = entry.second;
654 marshallCoord(outf, ex.pos);
655 marshallShort(outf, ex.radius);
656 marshallBoolean(outf, ex.autoex);
657 marshallString(outf, ex.desc);
658 // XXX: marshall travel_exclude::vault?
659 }
660 }
661 }
662
unmarshallExcludes(reader & inf,int minorVersion,exclude_set & excludes)663 void unmarshallExcludes(reader& inf, int minorVersion, exclude_set &excludes)
664 {
665 UNUSED(minorVersion);
666 excludes.clear();
667 int nexcludes = unmarshallShort(inf);
668 if (nexcludes)
669 {
670 for (int i = 0; i < nexcludes; ++i)
671 {
672 const coord_def c = unmarshallCoord(inf);
673 const int radius = unmarshallShort(inf);
674 const bool autoexcl = unmarshallBoolean(inf);
675 const string desc = unmarshallString(inf);
676 excludes.add_exclude(c, radius, autoexcl, desc);
677 }
678 }
679 }
680