1 /**
2 * @file
3 * @brief Travel stuff
4 **/
5 /* Known issues:
6 * Hardcoded dungeon features all over the place - this thing is a devil to
7 * refactor.
8 */
9 #include "AppHdr.h"
10
11 #include "travel.h"
12
13 #include <algorithm>
14 #include <cctype>
15 #include <cstdarg>
16 #include <cstdio>
17 #include <memory>
18 #include <set>
19 #include <sstream>
20
21 #include "branch.h"
22 #include "cloud.h"
23 #include "clua.h"
24 #include "command.h"
25 #include "coordit.h"
26 #include "daction-type.h"
27 #include "dactions.h"
28 #include "directn.h"
29 #include "delay.h"
30 #include "dgn-overview.h"
31 #include "english.h"
32 #include "env.h"
33 #include "files.h"
34 #include "format.h"
35 #include "god-abil.h"
36 #include "god-passive.h"
37 #include "hints.h"
38 #include "item-name.h"
39 #include "item-prop.h"
40 #include "item-status-flag-type.h"
41 #include "items.h"
42 #include "libutil.h"
43 #include "macro.h"
44 #include "mapmark.h"
45 #include "message.h"
46 #include "mon-death.h"
47 #include "nearby-danger.h"
48 #include "output.h"
49 #include "place.h"
50 #include "prompt.h"
51 #include "religion.h"
52 #include "stairs.h"
53 #include "state.h"
54 #include "stringutil.h"
55 #include "tag-version.h"
56 #include "terrain.h"
57 #include "tiles-build-specific.h"
58 #include "traps.h"
59 #include "travel-open-doors-type.h"
60 #include "unicode.h"
61 #include "unwind.h"
62 #include "view.h"
63
64 enum IntertravelDestination
65 {
66 // Go down a level
67 ID_DOWN = -100,
68
69 // Go up a level
70 ID_UP = -99,
71
72 // Repeat last travel
73 ID_REPEAT = -101,
74
75 // Altar as target
76 ID_ALTAR = -102,
77
78 // Cancel interlevel travel
79 ID_CANCEL = -1000,
80 };
81
82 TravelCache travel_cache;
83
84 // Tracks the distance between the target location on the target level and the
85 // stairs on the level.
86 static vector<stair_info> curr_stairs;
87
88 // Squares that are not safe to travel to on the current level.
89 exclude_set curr_excludes;
90
91 // This is where we last tried to take a stair during interlevel travel.
92 // Note that last_stair.id.depth should be set to -1 before initiating interlevel
93 // travel.
94 static level_pos last_stair;
95
96 // Where travel wants to get to.
97 static level_pos level_target;
98
99 // How many stairs there are between the source and destination of
100 // interlevel travel, as estimated by level_distance.
101 static int _Src_Dest_Level_Delta = -1;
102
103 // Source level where interlevel travel was last activated.
104 static level_id _Src_Level;
105
106 // Remember the last place explore stopped because autopickup failed.
107 static coord_def explore_stopped_pos;
108
109 // The place in the Vestibule of Hell where all portals to Hell land.
110 static level_pos travel_hell_entry;
111
112 static string trans_travel_dest;
113
114 // Array of points on the map, each value being the distance the character
115 // would have to travel to get there. Negative distances imply that the point
116 // is a) a trap or hostile terrain or b) only reachable by crossing a trap or
117 // hostile terrain.
118 travel_distance_grid_t travel_point_distance;
119
120 // Apply slime wall checks when checking if squares are travelsafe.
121 static bool g_Slime_Wall_Check = true;
122
123 static uint8_t curr_waypoints[GXM][GYM];
124
125 // If true, feat_is_traversable_now() returns the same as feat_is_traversable().
126 // FIXME: eliminate this. It's needed for RMODE_CONNECTIVITY.
127 static bool ignore_player_traversability = false;
128
129 // Map of terrain types that are forbidden.
130 static FixedVector<int8_t,NUM_FEATURES> forbidden_terrain;
131
132 // N.b. this #define only adds dprfs and so isn't very useful outside of a
133 // debug build. It also makes long travel extremely slow when enabled on a
134 // debug build.
135 //#define DEBUG_TRAVEL
136
137 /*
138 * Warn if interlevel travel is going to take you outside levels in
139 * the range [src,dest].
140 */
141 class deviant_route_warning
142 {
143 private:
144 level_pos target;
145 bool warned;
146
147 public:
deviant_route_warning()148 deviant_route_warning(): target(), warned(false)
149 {
150 }
151
152 void new_dest(const level_pos &dest);
153 bool warn_continue_travel(const level_pos &des,
154 const level_id &deviant);
155 };
156
new_dest(const level_pos & dest)157 void deviant_route_warning::new_dest(const level_pos &dest)
158 {
159 if (target != dest)
160 {
161 warned = false;
162 target = dest;
163 }
164 }
165
166 // Returns true if the player wants to continue travelling after the warning.
warn_continue_travel(const level_pos & dest,const level_id & deviant)167 bool deviant_route_warning::warn_continue_travel(
168 const level_pos &dest, const level_id &deviant)
169 {
170 // We've already prompted, don't ask again, on the player's head be it.
171 if (target == dest && warned)
172 return true;
173
174 target = dest;
175 const string prompt = make_stringf("Have to go through %s. Continue?",
176 deviant.describe().c_str());
177 // If the user says "Yes, shut up and take me there", we won't ask
178 // again for that destination. If the user says "No", we will
179 // prompt again.
180 return warned = yesno(prompt.c_str(), true, 'n', true, false);
181 }
182
183 static deviant_route_warning _Route_Warning;
184
185 static bool _find_transtravel_square(const level_pos &pos,
186 bool verbose = true);
187
188 static bool _loadlev_populate_stair_distances(const level_pos &target);
189 static void _populate_stair_distances(const level_pos &target);
190 static bool _is_greed_inducing_square(const LevelStashes *ls,
191 const coord_def &c, bool autopickup);
192 static bool _is_travelsafe_square(const coord_def& c,
193 bool ignore_hostile = false,
194 bool ignore_danger = false,
195 bool try_fallback = false);
196
197 // Returns true if there is a known trap at (x,y). Returns false for non-trap
198 // squares as also for undiscovered traps.
199 //
is_trap(const coord_def & c)200 static inline bool is_trap(const coord_def& c)
201 {
202 return feat_is_trap(env.map_knowledge(c).feat());
203 }
204
_is_safe_cloud(const coord_def & c)205 static inline bool _is_safe_cloud(const coord_def& c)
206 {
207 const cloud_type ctype = env.map_knowledge(c).cloud();
208 if (ctype == CLOUD_NONE)
209 return true;
210
211 // We can also safely run through smoke, or any of our own clouds if
212 // following Qazlal.
213 return !is_damaging_cloud(ctype, true, YOU_KILL(env.map_knowledge(c).cloudinfo()->killer));
214 }
215
216 // Returns an estimate for the time needed to cross this feature.
217 // This is done, so traps etc. will usually be circumvented where possible.
_feature_traverse_cost(dungeon_feature_type feature)218 static inline int _feature_traverse_cost(dungeon_feature_type feature)
219 {
220 if (feat_is_closed_door(feature)
221 // Higher cost for shallow water if species doesn't like water
222 || feature == DNGN_SHALLOW_WATER && (!player_likes_water(true)))
223 {
224 return 2;
225 }
226 else if (feat_is_trap(feature) && feature != DNGN_TRAP_SHAFT)
227 return 3;
228
229 return 1;
230 }
231
is_unknown_stair(const coord_def & p)232 bool is_unknown_stair(const coord_def &p)
233 {
234 dungeon_feature_type feat = env.map_knowledge(p).feat();
235
236 return feat_is_travelable_stair(feat) && !travel_cache.know_stair(p)
237 && feat != DNGN_EXIT_DUNGEON;
238 }
239
240 /**
241 * Does the player know this transporter's destination?
242 *
243 * @param p The location of the transporter.
244 * @returns True if the feature is a transporter with an unknown
245 * destination, false otherwise.
246 **/
is_unknown_transporter(const coord_def & p)247 bool is_unknown_transporter(const coord_def &p)
248 {
249 dungeon_feature_type feat = env.map_knowledge(p).feat();
250
251 return feat == DNGN_TRANSPORTER && !travel_cache.know_transporter(p);
252 }
253
254 // Returns true if the character can cross this dungeon feature, and
255 // the player hasn't requested that travel avoid the feature.
feat_is_traversable_now(dungeon_feature_type grid,bool try_fallback)256 bool feat_is_traversable_now(dungeon_feature_type grid, bool try_fallback)
257 {
258 if (!ignore_player_traversability)
259 {
260 // If the feature is in travel_avoid_terrain, respect that.
261 if (forbidden_terrain[grid])
262 return false;
263
264 // Swimmers and water-walkers get deep water.
265 if (grid == DNGN_DEEP_WATER
266 && (player_likes_water(true) || have_passive(passive_t::water_walk)))
267 {
268 return true;
269 }
270
271 // The player can safely walk over shafts.
272 if (grid == DNGN_TRAP_SHAFT)
273 return true;
274
275 // Permanently flying players can cross most hostile terrain.
276 if (grid == DNGN_DEEP_WATER || grid == DNGN_LAVA
277 || grid == DNGN_TOXIC_BOG)
278 {
279 return you.permanent_flight();
280 }
281 }
282
283 return feat_is_traversable(grid, try_fallback);
284 }
285
286 // Returns true if a generic character can cross this dungeon feature.
287 // Ignores swimming, flying, and travel_avoid_terrain.
feat_is_traversable(dungeon_feature_type feat,bool try_fallback)288 bool feat_is_traversable(dungeon_feature_type feat, bool try_fallback)
289 {
290 if (feat_is_trap(feat) && feat != DNGN_PASSAGE_OF_GOLUBRIA)
291 {
292 if (ignore_player_traversability)
293 return !(feat == DNGN_TRAP_TELEPORT || feat == DNGN_TRAP_TELEPORT_PERMANENT);
294 return false;
295 }
296 #if TAG_MAJOR_VERSION == 34
297 else if (feat == DNGN_TELEPORTER) // never ever enter it automatically
298 return false;
299 #endif
300 else if (feat_has_solid_floor(feat)
301 || feat_is_closed_door(feat)
302 && (!feat_is_sealed(feat) || try_fallback))
303 {
304 return true;
305 }
306 else
307 return false;
308 }
309
_run_mode_name(int runmode)310 static const char *_run_mode_name(int runmode)
311 {
312 return runmode == RMODE_TRAVEL ? "travel" :
313 runmode == RMODE_INTERLEVEL ? "intertravel" :
314 runmode == RMODE_EXPLORE ? "explore" :
315 runmode == RMODE_EXPLORE_GREEDY ? "explore_greedy" :
316 runmode > 0 ? "run"
317 : "";
318 }
319
is_waypoint(const coord_def & p)320 uint8_t is_waypoint(const coord_def &p)
321 {
322 if (!can_travel_interlevel())
323 return 0;
324 return curr_waypoints[p.x][p.y];
325 }
326
is_stash(const LevelStashes * ls,const coord_def & p)327 static inline bool is_stash(const LevelStashes *ls, const coord_def& p)
328 {
329 return ls && ls->find_stash(p);
330 }
331
_monster_blocks_travel(const monster_info * mons)332 static bool _monster_blocks_travel(const monster_info *mons)
333 {
334 return mons
335 && mons_class_is_stationary(mons->type)
336 && !fedhas_passthrough(mons);
337 }
338
339 // Returns true if the feature type "grid" is a closed door which
340 // autoexplore/travel will not normally approach in order to go through it.
_feat_is_blocking_door(const dungeon_feature_type grid)341 static bool _feat_is_blocking_door(const dungeon_feature_type grid)
342 {
343 if (Options.travel_open_doors == travel_open_doors_type::avoid)
344 return feat_is_closed_door(grid);
345 else
346 return feat_is_runed(grid);
347 }
348
349 // Returns {flag, barrier}.
350 // "flag" is true if the feature type "grid" is a closed door which autotravel
351 // will not pass through, false otherwise.
352 // "barrier" is a description of "grid" if autotravel will not pass through it,
353 // and no game time has passed since the player pressed (say) "o", "" otherwise.
354 // This function should only be used for the choice to open the door itself.
_feat_is_blocking_door_strict(const dungeon_feature_type grid)355 static pair<bool, string> _feat_is_blocking_door_strict(
356 const dungeon_feature_type grid)
357 {
358 if (Options.travel_open_doors == travel_open_doors_type::open
359 ? !feat_is_runed(grid) : !feat_is_closed_door(grid))
360 {
361 return {false, ""};
362 }
363
364 if (you.elapsed_time == you.elapsed_time_at_last_input)
365 {
366 string barrier;
367 if (feat_is_runed(grid))
368 return {true, "unopened runed door"};
369 else
370 return {true, "unopened door"};
371 }
372 return {true, ""};
373 }
374
375 /*
376 * Returns true if the square at (x,y) is a dungeon feature the character
377 * can't (under normal circumstances) safely cross.
378 *
379 * Note: is_reseedable can return true for dungeon features that is_traversable
380 * also returns true for. This is okay, because is_traversable always
381 * takes precedence over is_reseedable. is_reseedable is used only to
382 * decide which squares to reseed from when flood-filling outwards to
383 * colour the level map. It does not affect pathing of actual
384 * travel/explore.
385 */
_is_reseedable(const coord_def & c,bool ignore_danger=false)386 static bool _is_reseedable(const coord_def& c, bool ignore_danger = false)
387 {
388 map_cell &cell(env.map_knowledge(c));
389 const dungeon_feature_type grid = cell.feat();
390
391 if (feat_is_wall(grid) || feat_is_tree(grid))
392 return false;
393
394 if (!ignore_danger && is_excluded(c))
395 return true;
396
397 return feat_is_water(grid)
398 || grid == DNGN_LAVA
399 || _feat_is_blocking_door(grid)
400 || is_trap(c)
401 || !ignore_danger && _monster_blocks_travel(cell.monsterinfo())
402 || g_Slime_Wall_Check && slime_wall_neighbour(c)
403 || !_is_safe_cloud(c);
404 }
405
406 struct cell_travel_safety
407 {
408 bool safe;
409 bool safe_if_ignoring_hostile_terrain;
410
cell_travel_safetycell_travel_safety411 cell_travel_safety() : safe(false), safe_if_ignoring_hostile_terrain(false)
412 {
413 }
414 };
415
416 typedef FixedArray<cell_travel_safety, GXM, GYM> travel_safe_grid;
417 static unique_ptr<travel_safe_grid> _travel_safe_grid;
418
419 class precompute_travel_safety_grid
420 {
421 private:
422 bool did_compute;
423
424 public:
precompute_travel_safety_grid()425 precompute_travel_safety_grid() : did_compute(false)
426 {
427 if (!_travel_safe_grid)
428 {
429 did_compute = true;
430 auto tsgrid = make_unique<travel_safe_grid>();
431 travel_safe_grid &safegrid(*tsgrid);
432 for (rectangle_iterator ri(1); ri; ++ri)
433 {
434 const coord_def p(*ri);
435 cell_travel_safety &ts(safegrid(p));
436 ts.safe = _is_travelsafe_square(p, false);
437 ts.safe_if_ignoring_hostile_terrain =
438 _is_travelsafe_square(p, true);
439 }
440 _travel_safe_grid = move(tsgrid);
441 }
442 }
~precompute_travel_safety_grid()443 ~precompute_travel_safety_grid()
444 {
445 if (did_compute)
446 _travel_safe_grid.reset(nullptr);
447 }
448 };
449
is_stair_exclusion(const coord_def & p)450 bool is_stair_exclusion(const coord_def &p)
451 {
452 const auto f = env.map_knowledge(p).feat();
453 if (!feat_is_stair(f) || feat_stair_direction(f) == CMD_NO_CMD)
454 return false;
455
456 return get_exclusion_radius(p) == 1;
457 }
458
459 // Returns true if the square at (x,y) is okay to travel over. If ignore_hostile
460 // is true, returns true even for dungeon features the character can normally
461 // not cross safely (deep water, lava, traps).
_is_travelsafe_square(const coord_def & c,bool ignore_hostile,bool ignore_danger,bool try_fallback)462 static bool _is_travelsafe_square(const coord_def& c, bool ignore_hostile,
463 bool ignore_danger, bool try_fallback)
464 {
465 if (!in_bounds(c))
466 return false;
467
468 if (_travel_safe_grid)
469 {
470 const cell_travel_safety &cell((*_travel_safe_grid)(c));
471 return ignore_hostile? cell.safe_if_ignoring_hostile_terrain
472 : cell.safe;
473 }
474
475 if (!env.map_knowledge(c).known())
476 return false;
477
478 const dungeon_feature_type grid = env.map_knowledge(c).feat();
479
480 // Only try pathing through temporary obstructions we remember, not
481 // those we can actually see (since the latter are clearly still blockers)
482 try_fallback = try_fallback
483 && (!you.see_cell(c) || _feat_is_blocking_door(grid));
484
485 // Also make note of what's displayed on the level map for
486 // plant/fungus checks.
487 const map_cell& levelmap_cell = env.map_knowledge(c);
488
489 // Travel will not voluntarily cross squares blocked by immobile
490 // monsters.
491 if (!ignore_danger && !ignore_hostile)
492 {
493 const monster_info *minfo = levelmap_cell.monsterinfo();
494 if (minfo && _monster_blocks_travel(minfo))
495 return false;
496 }
497
498 // If 'ignore_hostile' is true, we're ignoring hazards that can be
499 // navigated over if the player is willing to take damage or fly.
500 if (ignore_hostile && _is_reseedable(c, true))
501 return true;
502
503 // Excluded squares are only safe if marking stairs, i.e. another level.
504 if (!ignore_danger && !ignore_hostile && is_excluded(c)
505 && !is_stair_exclusion(c))
506 {
507 return false;
508 }
509
510 if (g_Slime_Wall_Check && slime_wall_neighbour(c)
511 && !actor_slime_wall_immune(&you))
512 {
513 return false;
514 }
515
516 if (!_is_safe_cloud(c) && !try_fallback)
517 return false;
518
519 if (is_trap(c))
520 {
521 trap_def trap;
522 trap.pos = c;
523 trap.type = env.map_knowledge(c).trap();
524 trap.ammo_qty = 1;
525 if (trap.is_safe())
526 return true;
527 }
528
529 if (!try_fallback && _feat_is_blocking_door(levelmap_cell.feat()))
530 return false;
531
532 return feat_is_traversable_now(grid, try_fallback);
533 }
534
535 // Returns true if the location at (x,y) is monster-free and contains
536 // no clouds. Travel uses this to check if the square the player is
537 // about to move to is safe.
_is_safe_move(const coord_def & c)538 static bool _is_safe_move(const coord_def& c)
539 {
540 if (const monster* mon = monster_at(c))
541 {
542 // Stop before wasting energy on plants and fungi,
543 // unless worshipping Fedhas.
544 if (you.can_see(*mon)
545 && mons_class_is_firewood(mon->type)
546 && !fedhas_passthrough(mon))
547 {
548 return false;
549 }
550
551 // If this is any *other* monster, it'll be visible and
552 // a) Friendly, in which case we'll displace it, no problem.
553 // b) Unfriendly, in which case we're in deep trouble, since travel
554 // should have been aborted already by the checks in view.cc.
555 }
556
557 if (is_trap(c) && !trap_at(c)->is_safe())
558 return false;
559
560 return _is_safe_cloud(c);
561 }
562
travel_init_load_level()563 void travel_init_load_level()
564 {
565 curr_excludes.clear();
566 travel_cache.set_level_excludes();
567 travel_cache.update_waypoints();
568 }
569
570 // This is called after the player changes level.
travel_init_new_level()571 void travel_init_new_level()
572 {
573 // Clear run details, but preserve the runmode, because we might be in
574 // the middle of interlevel travel.
575 int runmode = you.running;
576 you.running.clear();
577 you.running = runmode;
578
579 travel_init_load_level();
580
581 explore_stopped_pos.reset();
582 }
583
584 // Given a dungeon feature description, returns the feature number. This is a
585 // crude hack and currently recognises only (deep/shallow) water. (XXX)
586 //
587 // Returns -1 if the feature named is not recognised, else returns the feature
588 // number (guaranteed to be 0-255).
_get_feature_type(const string & feature)589 static int _get_feature_type(const string &feature)
590 {
591 if (feature.find("deep water") != string::npos)
592 return DNGN_DEEP_WATER;
593 if (feature.find("shallow water") != string::npos)
594 return DNGN_SHALLOW_WATER;
595 return -1;
596 }
597
598 // Given a feature description, prevents travel to locations of that feature
599 // type.
prevent_travel_to(const string & feature)600 void prevent_travel_to(const string &feature)
601 {
602 int feature_type = _get_feature_type(feature);
603 if (feature_type != -1)
604 forbidden_terrain[feature_type] = 1;
605 }
606
_is_branch_stair(const coord_def & pos)607 static bool _is_branch_stair(const coord_def& pos)
608 {
609 const level_id curr = level_id::current();
610 const level_id next = level_id::get_next_level_id(pos);
611
612 return next.branch != curr.branch;
613 }
614
615 #define ES_item (Options.explore_stop & ES_ITEM)
616 #define ES_greedy (Options.explore_stop & ES_GREEDY_ITEM)
617 #define ES_glow (Options.explore_stop & ES_GLOWING_ITEM)
618 #define ES_art (Options.explore_stop & ES_ARTEFACT)
619 #define ES_rune (Options.explore_stop & ES_RUNE)
620 #define ES_shop (Options.explore_stop & ES_SHOP)
621 #define ES_stair (Options.explore_stop & ES_STAIR)
622 #define ES_transporter (Options.explore_stop & ES_TRANSPORTER)
623 #define ES_altar (Options.explore_stop & ES_ALTAR)
624 #define ES_portal (Options.explore_stop & ES_PORTAL)
625 #define ES_branch (Options.explore_stop & ES_BRANCH)
626 #define ES_rdoor (Options.explore_stop & ES_RUNED_DOOR)
627 #define ES_stack (Options.explore_stop & ES_GREEDY_VISITED_ITEM_STACK)
628
629 // Adds interesting stuff on the point p to explore_discoveries.
_check_interesting_square(const coord_def pos,explore_discoveries & ed)630 static inline void _check_interesting_square(const coord_def pos,
631 explore_discoveries &ed)
632 {
633 if ((ES_item || ES_greedy || ES_glow || ES_art || ES_rune)
634 && you.visible_igrd(pos) != NON_ITEM)
635 {
636 ed.found_item(pos, env.item[ you.visible_igrd(pos) ]);
637 }
638
639 ed.found_feature(pos, env.grid(pos));
640 }
641
_userdef_run_stoprunning_hook()642 static void _userdef_run_stoprunning_hook()
643 {
644 if (you.running)
645 clua.callfn("ch_stop_running", "s", _run_mode_name(you.running));
646 }
647
_userdef_run_startrunning_hook()648 static void _userdef_run_startrunning_hook()
649 {
650 if (you.running)
651 clua.callfn("ch_start_running", "s", _run_mode_name(you.running));
652 }
653
is_resting()654 bool is_resting()
655 {
656 return you.running.is_rest();
657 }
658
_slowest_ally_speed()659 static int _slowest_ally_speed()
660 {
661 vector<monster* > followers = get_on_level_followers();
662 int min_speed = INT_MAX;
663 for (auto fol : followers)
664 {
665 int speed = fol->speed * BASELINE_DELAY
666 / fol->action_energy(EUT_MOVE);
667 if (speed < min_speed)
668 min_speed = speed;
669 }
670 return min_speed;
671 }
672
_start_running()673 static void _start_running()
674 {
675 _userdef_run_startrunning_hook();
676 you.running.init_travel_speed();
677 you.running.turns_passed = 0;
678 const bool unsafe = Options.travel_one_unsafe_move &&
679 (you.running == RMODE_TRAVEL
680 || you.running == RMODE_INTERLEVEL);
681
682 if (you.running < 0)
683 start_delay<TravelDelay>(unsafe);
684 }
685
686 // Stops shift+running and all forms of travel.
stop_running(bool clear_delays)687 void stop_running(bool clear_delays)
688 {
689 you.running.stop(clear_delays);
690 }
691
_is_valid_explore_target(const coord_def & where)692 static bool _is_valid_explore_target(const coord_def& where)
693 {
694 // If a square in LOS is unmapped, it's valid.
695 for (radius_iterator ri(where, LOS_DEFAULT, true); ri; ++ri)
696 if (!env.map_knowledge(*ri).seen())
697 return true;
698
699 if (you.running == RMODE_EXPLORE_GREEDY)
700 {
701 LevelStashes *lev = StashTrack.find_current_level();
702 return lev && lev->needs_visit(where, can_autopickup());
703 }
704
705 return false;
706 }
707
708 enum explore_status_type
709 {
710 EST_FULLY_EXPLORED = 0,
711
712 // Could not explore because of hostile terrain
713 EST_PARTLY_EXPLORED = 1,
714
715 // Could not pick up interesting items because of hostile terrain. Note
716 // that this and EST_PARTLY_EXPLORED are not mutually exclusive.
717 EST_GREED_UNFULFILLED = 2,
718 };
719
_level_has_unknown_transporters()720 static bool _level_has_unknown_transporters()
721 {
722 LevelInfo *li = travel_cache.find_level_info(level_id::current());
723 ASSERT(li);
724
725 vector<transporter_info> transporters = li->get_transporters();
726 for (auto ti : transporters)
727 {
728 if (ti.destination.origin())
729 return true;
730 }
731 return false;
732 }
733
_set_target_square(const coord_def & target)734 static void _set_target_square(const coord_def &target)
735 {
736 you.running.pos = target;
737 }
738
_explore_find_target_square()739 static void _explore_find_target_square()
740 {
741 bool runed_door_pause = false;
742 bool closed_door_pause = false;
743
744 travel_pathfind tp;
745 tp.set_floodseed(you.pos(), true);
746
747 coord_def whereto =
748 tp.pathfind(static_cast<run_mode_type>(you.running.runmode));
749
750 // If we didn't find an explore target the first time, try fallback mode
751 // Do the same if the original target was a "hostile" place.
752 if (!whereto.x && !whereto.y
753 || 0 > travel_point_distance[whereto.x][whereto.y])
754 {
755 travel_pathfind fallback_tp;
756 fallback_tp.set_floodseed(you.pos(), true);
757 whereto = fallback_tp.pathfind(static_cast<run_mode_type>(you.running.runmode), true);
758
759 if (whereto.distance_from(you.pos()) == 1)
760 {
761 if (cell_is_runed(whereto))
762 {
763 runed_door_pause = true;
764 whereto.reset();
765 }
766 // use orig_terrain() as that's what cell_is_runed() does.
767 else if (Options.travel_open_doors == travel_open_doors_type::avoid
768 && feat_is_closed_door(orig_terrain(whereto)))
769 {
770 closed_door_pause = true;
771 whereto.reset();
772 }
773 }
774 }
775
776 if (whereto.x || whereto.y)
777 {
778 // Make sure this is a square that is reachable, since we asked
779 // travel_pathfind to give us even unreachable squares. The
780 // player's starting position may in some cases not have its
781 // travel_point_distance set, but we know it's reachable, since
782 // we're there.
783 if (travel_point_distance[whereto.x][whereto.y] <= 0
784 && whereto != you.pos())
785 {
786 whereto.reset();
787 }
788 }
789
790 if (whereto.x || whereto.y)
791 {
792 _set_target_square(whereto);
793 return;
794 }
795 else
796 {
797 // No place to go? Report to the player.
798 const int estatus = tp.explore_status();
799 const bool unknown_trans = _level_has_unknown_transporters();
800 if (!estatus && !unknown_trans)
801 {
802 mpr("Done exploring.");
803 learned_something_new(HINT_DONE_EXPLORE);
804 }
805 else
806 {
807 vector<const char *> reasons;
808 vector<const char *> inacc;
809 string inacc_desc = "";
810
811 if (runed_door_pause)
812 reasons.push_back("unopened runed door");
813
814 if (unknown_trans)
815 reasons.push_back("unvisited transporter");
816
817 if (closed_door_pause)
818 reasons.push_back("unopened door");
819
820 if (estatus & EST_GREED_UNFULFILLED)
821 inacc.push_back("items");
822 // A runed door already implies an unexplored place.
823 if (!runed_door_pause && !closed_door_pause &&
824 estatus & EST_PARTLY_EXPLORED)
825 {
826 inacc.push_back("places");
827 }
828
829 if (!inacc.empty())
830 {
831 inacc_desc = make_stringf("can't reach some %s",
832 comma_separated_line(inacc.begin(),
833 inacc.end()).c_str());
834 reasons.push_back(inacc_desc.c_str());
835 }
836 mprf("Partly explored, %s.",
837 comma_separated_line(reasons.begin(), reasons.end()).c_str());
838 }
839 stop_running();
840 }
841 }
842
explore_pickup_event(int did_pickup,int tried_pickup)843 void explore_pickup_event(int did_pickup, int tried_pickup)
844 {
845 if (!did_pickup && !tried_pickup)
846 return;
847
848 if (!you.running.is_explore())
849 return;
850
851 if (did_pickup)
852 {
853 const int estop =
854 (you.running == RMODE_EXPLORE_GREEDY) ? ES_GREEDY_PICKUP_MASK
855 : ES_NONE;
856
857 if (Options.explore_stop & estop)
858 stop_delay();
859 }
860
861 // Greedy explore has no good way to deal with an item that we can't
862 // pick up, so the only thing to do is to stop.
863 if (tried_pickup && you.running == RMODE_EXPLORE_GREEDY)
864 {
865 if (explore_stopped_pos == you.pos())
866 {
867 const string prompt =
868 make_stringf("Could not pick up %s here; shall I ignore %s?",
869 tried_pickup == 1? "an item" : "some items",
870 tried_pickup == 1? "it" : "them");
871
872 // Make Escape => 'n' and stop run.
873 explicit_keymap map;
874 map[ESCAPE] = 'n';
875 map[CONTROL('G')] = 'n';
876 if (yesno(prompt.c_str(), true, 'y', true, false, false, &map))
877 {
878 mark_items_non_pickup_at(you.pos());
879 // Don't stop explore.
880 return;
881 }
882 canned_msg(MSG_OK);
883 }
884 explore_stopped_pos = you.pos();
885 stop_delay();
886 }
887 }
888
889 /**
890 * Run the travel_pathfind algorithm with a destination with the aim of
891 * determining the next travel move. Try to avoid to let travel (including
892 * autoexplore) move the player right next to a lurking (previously unseen)
893 * monster.
894 *
895 * Pathfinding runs from you.running.pos to youpos, and the move contains the
896 * next movement relative to youpos to move closer to you.running.pos. If a
897 * runed door (or a closed door, if travel_open_doors isn't open) is encountered
898 * or a transporter needs to be taken, these are set to 0, and the caller checks
899 * for this.
900 *
901 * @param youpos The starting position.
902 * @param[out] move_x If we want a travel move, the x coordinate.
903 * @param[out] move_y If we want a travel move, the y coordinate.
904 */
_find_travel_pos(const coord_def & youpos,int * move_x,int * move_y)905 static void _find_travel_pos(const coord_def& youpos, int *move_x, int *move_y)
906 {
907 travel_pathfind tp;
908
909 tp.set_src_dst(youpos, you.running.pos);
910
911 coord_def dest = tp.pathfind(RMODE_TRAVEL, false);
912 if (dest.origin())
913 dest = tp.pathfind(RMODE_TRAVEL, true);
914 coord_def new_dest = dest;
915
916 // We'd either have to travel through a runed door, in which case we'll be
917 // stopping, or a transporter, in which case we need to issue a command to
918 // enter.
919 pair<bool, string> barrier;
920 if ((barrier = _feat_is_blocking_door_strict(env.grid(new_dest))).first
921 || env.grid(youpos) == DNGN_TRANSPORTER
922 && env.grid(new_dest) == DNGN_TRANSPORTER_LANDING
923 && youpos.distance_from(new_dest) > 1)
924 {
925 *move_x = 0;
926 *move_y = 0;
927 if (!barrier.second.empty())
928 {
929 mpr("Could not " + you.running.runmode_name() + ", "
930 + barrier.second + ".");
931 }
932 return;
933 }
934
935 // Check whether this step puts us adjacent to any grid we haven't ever
936 // seen
937 //
938 // .tx Moving onto t puts us adjacent to an unseen grid.
939 // ?#@ --> Pick x instead.
940 // Only applies to diagonal moves.
941 if (!dest.origin() && dest.x != youpos.x && dest.y != youpos.y)
942 {
943 coord_def unseen = coord_def();
944 for (adjacent_iterator ai(dest); ai; ++ai)
945 if (!you.see_cell(*ai) && !env.map_knowledge(*ai).seen())
946 {
947 unseen = *ai;
948 break;
949 }
950
951 if (unseen != coord_def())
952 {
953 // If so, try to use an orthogonally adjacent grid that is safe to
954 // enter.
955 if (youpos.x == unseen.x)
956 new_dest.y = youpos.y;
957 else if (youpos.y == unseen.y)
958 new_dest.x = youpos.x;
959
960 // If the new grid cannot be entered, reset to dest. This means
961 // that autoexplore will still sometimes move you next to a
962 // previously unseen monster but the same would happen by manual
963 // movement, so I don't think we need to worry about this. (jpeg)
964 if (!_is_travelsafe_square(new_dest)
965 || !feat_is_traversable_now(env.map_knowledge(new_dest).feat()))
966 {
967 new_dest = dest;
968 }
969 #ifdef DEBUG_SAFE_EXPLORE
970 mprf(MSGCH_DIAGNOSTICS, "youpos: (%d, %d), dest: (%d, %d), "
971 "unseen: (%d, %d), new_dest: (%d, %d)",
972 youpos.x, youpos.y, dest.x, dest.y, unseen.x, unseen.y,
973 new_dest.x, new_dest.y);
974 more();
975 #endif
976 }
977 }
978
979 if (new_dest.origin())
980 you.running = RMODE_NOT_RUNNING;
981
982 *move_x = new_dest.x - youpos.x;
983 *move_y = new_dest.y - youpos.y;
984 }
985
986 // Determine the necessary command when find_travel_pos() indicates that we
987 // shouldn't move.
_get_non_move_command()988 static command_type _get_non_move_command()
989 {
990 // Did we fail to get where we were going?
991 const bool fell_short = you.pos() != you.running.pos;
992
993 if (you.running == RMODE_EXPLORE)
994 return CMD_NO_CMD;
995
996 // Stop exploring if we fell short of our target (because of a runed
997 // door), but inspect the floor otherwise (because of an item that
998 // could not be picked up).
999 if (you.running == RMODE_EXPLORE_GREEDY)
1000 return fell_short ? CMD_NO_CMD : CMD_INSPECT_FLOOR;
1001
1002 const level_pos curr = level_pos(level_id::current(), you.pos());
1003
1004 // We've reached our travel destination.
1005 if (level_target == curr)
1006 return CMD_NO_CMD;
1007
1008 // If we we're not at our running position and we're not travelled to a
1009 // transporter, simply stop running.
1010 if (fell_short && env.grid(you.pos()) != DNGN_TRANSPORTER)
1011 return CMD_NO_CMD;
1012
1013 // We're trying to take the same stairs again, abort.
1014 if (last_stair == curr)
1015 return CMD_NO_CMD;
1016
1017 // Save the previous stair taken, so we can check that we're not trying to
1018 // retake them after this command.
1019 last_stair.id = level_id::current();
1020 last_stair.pos = you.pos();
1021
1022 return feat_stair_direction(env.grid(you.pos()));
1023 }
1024
1025 // Top-level travel control (called from input() in main.cc).
1026 //
1027 // travel() is responsible for making the individual moves that constitute
1028 // (interlevel) travel and explore and deciding when travel and explore
1029 // end.
1030 //
1031 // Don't call travel() if you.running >= 0.
travel()1032 command_type travel()
1033 {
1034 int holdx, holdy;
1035 int *move_x = &holdx;
1036 int *move_y = &holdy;
1037 holdx = holdy = 0;
1038
1039 command_type result = CMD_NO_CMD;
1040
1041 if (Options.travel_key_stop && kbhit())
1042 {
1043 mprf("Key pressed, stopping %s.", you.running.runmode_name().c_str());
1044 stop_running();
1045 return CMD_NO_CMD;
1046 }
1047
1048 if (you.confused())
1049 {
1050 mprf("You're confused, stopping %s.",
1051 you.running.runmode_name().c_str());
1052 stop_running();
1053 return CMD_NO_CMD;
1054 }
1055
1056 // Excluded squares are only safe if marking stairs, i.e. another level.
1057 if (is_excluded(you.pos()) && !is_stair_exclusion(you.pos()))
1058 {
1059 mprf("You're in a travel-excluded area, stopping %s.",
1060 you.running.runmode_name().c_str());
1061 stop_running();
1062 return CMD_NO_CMD;
1063 }
1064
1065 if (you.running.is_explore())
1066 {
1067 if (Options.explore_auto_rest && !you.is_sufficiently_rested())
1068 return CMD_WAIT;
1069
1070 // Exploring.
1071 if (env.grid(you.pos()) == DNGN_ENTER_SHOP
1072 && you.running == RMODE_EXPLORE_GREEDY)
1073 {
1074 LevelStashes *lev = StashTrack.find_current_level();
1075 if (lev && lev->shop_needs_visit(you.pos()))
1076 {
1077 you.running = 0;
1078 return CMD_GO_UPSTAIRS;
1079 }
1080 }
1081
1082 // Speed up explore by not doing a double-floodfill if we have
1083 // a valid target.
1084 if (!you.running.pos.x
1085 || you.running.pos == you.pos()
1086 || !_is_valid_explore_target(you.running.pos))
1087 {
1088 _explore_find_target_square();
1089 }
1090 }
1091
1092 // Interlevel travel. Since you.running.x is zero, we've either just
1093 // initiated travel, or we've just climbed or descended a staircase, and we
1094 // need to figure out where to travel to next.
1095 if (you.running == RMODE_INTERLEVEL && !you.running.pos.x)
1096 {
1097 #ifdef DEBUG_TRAVEL
1098 dprf("continuing translevel travel, branch %d depth %d, pos %d,%d",
1099 level_target.id.branch, level_target.id.depth, level_target.pos.x,
1100 level_target.pos.y);
1101 #endif
1102
1103 if (!_find_transtravel_square(level_target) || !you.running.pos.x)
1104 stop_running();
1105 else
1106 you.running.init_travel_speed();
1107 }
1108
1109 if (you.running < 0)
1110 {
1111 // Remember what run-mode we were in so that we can resume
1112 // explore/interlevel travel correctly.
1113 int runmode = you.running;
1114
1115 // Get the next step to make. If the travel command can't find a route,
1116 // we turn off travel (find_travel_pos does that automatically).
1117 _find_travel_pos(you.pos(), move_x, move_y);
1118
1119 // Stop greedy explore when visiting a stash for the first time.
1120 if ((*move_x || *move_y)
1121 && you.running == RMODE_EXPLORE_GREEDY
1122 && ES_stack)
1123 {
1124 const coord_def newpos = you.pos() + coord_def(*move_x, *move_y);
1125 if (newpos == you.running.pos)
1126 {
1127 const LevelStashes *lev = StashTrack.find_current_level();
1128 if (lev && lev->needs_stop(newpos))
1129 {
1130 explore_stopped_pos = newpos;
1131 stop_running();
1132 return direction_to_command(*move_x, *move_y);
1133 }
1134 }
1135 }
1136
1137 if (!*move_x && !*move_y)
1138 {
1139 // Re-apply the runmode, which allows for continue exploration or
1140 // proper triggering of lua hooks when running ceases. We don't
1141 // directly call stop_running() without restoring this because
1142 // you.running is probably 0, and stop_running() won't notify Lua
1143 // hooks if you.running == 0.
1144 you.running = runmode;
1145
1146 result = _get_non_move_command();
1147 if (result == CMD_NO_CMD)
1148 stop_running();
1149 // If taking stairs, the running destination will no longer be
1150 // valid on the new level. Reset the running pos so travel will
1151 // search for a new travel square next turn.
1152 else if (you.running == RMODE_INTERLEVEL)
1153 you.running.pos.reset();
1154
1155 return result;
1156
1157 }
1158 else if (you.running.is_explore() && Options.explore_delay > -1)
1159 delay(Options.explore_delay);
1160 else if (Options.travel_delay > 0)
1161 delay(Options.travel_delay);
1162 }
1163
1164 if (!you.running)
1165 return CMD_NO_CMD;
1166
1167 if (result != CMD_NO_CMD)
1168 return result; // TODO: apparently unreachable?
1169
1170 return direction_to_command(*move_x, *move_y);
1171 }
1172
direction_to_command(int x,int y)1173 command_type direction_to_command(int x, int y)
1174 {
1175 if (x == -1 && y == -1) return CMD_MOVE_UP_LEFT;
1176 if (x == -1 && y == 0) return CMD_MOVE_LEFT;
1177 if (x == -1 && y == 1) return CMD_MOVE_DOWN_LEFT;
1178 if (x == 0 && y == -1) return CMD_MOVE_UP;
1179 if (x == 0 && y == 1) return CMD_MOVE_DOWN;
1180 if (x == 1 && y == -1) return CMD_MOVE_UP_RIGHT;
1181 if (x == 1 && y == 0) return CMD_MOVE_RIGHT;
1182 if (x == 1 && y == 1) return CMD_MOVE_DOWN_RIGHT;
1183
1184 ASSERT(0);
1185 return CMD_NO_CMD;
1186 }
1187
_fill_exclude_radius(const travel_exclude & exc)1188 static void _fill_exclude_radius(const travel_exclude &exc)
1189 {
1190 const int radius = exc.radius;
1191 const coord_def &c = exc.pos;
1192 for (int y = c.y - radius; y <= c.y + radius; ++y)
1193 for (int x = c.x - radius; x <= c.x + radius; ++x)
1194 {
1195 const coord_def p(x, y);
1196 if (!map_bounds(x, y) || travel_point_distance[x][y])
1197 continue;
1198
1199 if (is_exclude_root(p))
1200 travel_point_distance[x][y] = PD_EXCLUDED;
1201 else if (is_excluded(p) && env.map_knowledge(p).known())
1202 travel_point_distance[x][y] = PD_EXCLUDED_RADIUS;
1203 }
1204 }
1205
1206 /////////////////////////////////////////////////////////////////////////////
1207 // travel_pathfind
1208
1209 FixedVector<coord_def, GXM * GYM> travel_pathfind::circumference[2];
1210
1211 // already defined in header
1212 // const int travel_pathfind::UNFOUND_DIST;
1213 // const int travel_pathfind::INFINITE_DIST;
1214
travel_pathfind()1215 travel_pathfind::travel_pathfind()
1216 : runmode(RMODE_NOT_RUNNING), start(), dest(), next_travel_move(),
1217 floodout(false), double_flood(false), ignore_hostile(false),
1218 ignore_danger(false), annotate_map(false), ls(nullptr),
1219 need_for_greed(false), autopickup(false),
1220 unexplored_place(), greedy_place(), unexplored_dist(0), greedy_dist(0),
1221 refdist(nullptr), reseed_points(), features(nullptr), unreachables(),
1222 point_distance(travel_point_distance), next_iter_points(0),
1223 traveled_distance(0), circ_index(0)
1224 {
1225 }
1226
~travel_pathfind()1227 travel_pathfind::~travel_pathfind()
1228 {
1229 }
1230
_is_greed_inducing_square(const LevelStashes * ls,const coord_def & c,bool autopickup)1231 static bool _is_greed_inducing_square(const LevelStashes *ls,
1232 const coord_def &c, bool autopickup)
1233 {
1234 return ls && ls->needs_visit(c, autopickup);
1235 }
1236
is_greed_inducing_square(const coord_def & c) const1237 bool travel_pathfind::is_greed_inducing_square(const coord_def &c) const
1238 {
1239 return _is_greed_inducing_square(ls, c, autopickup);
1240 }
1241
set_src_dst(const coord_def & src,const coord_def & dst)1242 void travel_pathfind::set_src_dst(const coord_def &src, const coord_def &dst)
1243 {
1244 // Yes, this is backwards - for travel, we always start from the destination
1245 // and search outwards for the starting position.
1246 start = dst;
1247 dest = src;
1248
1249 floodout = double_flood = false;
1250 }
1251
set_floodseed(const coord_def & seed,bool dblflood)1252 void travel_pathfind::set_floodseed(const coord_def &seed, bool dblflood)
1253 {
1254 start = seed;
1255 dest.reset();
1256
1257 floodout = true;
1258 double_flood = dblflood;
1259 }
1260
set_feature_vector(vector<coord_def> * feats)1261 void travel_pathfind::set_feature_vector(vector<coord_def> *feats)
1262 {
1263 features = feats;
1264
1265 if (features)
1266 {
1267 double_flood = true;
1268 annotate_map = true;
1269 }
1270 }
1271
explore_target() const1272 const coord_def travel_pathfind::explore_target() const
1273 {
1274 if (unexplored_dist != UNFOUND_DIST && greedy_dist != UNFOUND_DIST)
1275 {
1276 return unexplored_dist < greedy_dist ? unexplored_place
1277 : greedy_place;
1278 }
1279 else if (unexplored_dist != UNFOUND_DIST)
1280 return unexplored_place;
1281 else if (greedy_dist != UNFOUND_DIST)
1282 return greedy_place;
1283
1284 return coord_def(0, 0);
1285 }
1286
1287 // The travel algorithm is based on the NetHack travel code written by Warwick
1288 // Allison - used with his permission.
pathfind(run_mode_type rmode,bool fallback_explore)1289 coord_def travel_pathfind::pathfind(run_mode_type rmode, bool fallback_explore)
1290 {
1291 unwind_bool saved_ipt(ignore_player_traversability);
1292
1293 if (rmode == RMODE_INTERLEVEL)
1294 rmode = RMODE_TRAVEL;
1295
1296 runmode = rmode;
1297
1298 try_fallback = fallback_explore;
1299
1300 if (runmode == RMODE_CONNECTIVITY)
1301 ignore_player_traversability = true;
1302 else
1303 {
1304 ASSERTM(crawl_state.need_save,
1305 "Pathfind with mode %d without a game?", runmode);
1306
1307 if (runmode == RMODE_EXPLORE_GREEDY)
1308 {
1309 autopickup = can_autopickup();
1310 need_for_greed = autopickup;
1311 }
1312 }
1313
1314 if (!ls && (annotate_map || need_for_greed))
1315 ls = StashTrack.find_current_level();
1316
1317 next_travel_move.reset();
1318
1319 // For greedy explore, keep track of the closest unexplored territory and
1320 // the closest greedy square. Exploring to the nearest (unexplored / greedy)
1321 // square is easier, but it produces unintuitive explore behaviour where
1322 // grabbing items is not favoured over simple exploring.
1323 //
1324 // Greedy explore instead uses the explore_item_greed option to weight
1325 // greedy explore towards grabbing items over exploring. An
1326 // explore_item_greed set to 10, for instance, forces explore to prefer
1327 // items that are less than 10 squares farther away from the player than the
1328 // nearest unmapped square. Negative explore_item_greed values force greedy
1329 // explore to favour unexplored territory over picking up items. For the
1330 // most natural greedy explore behaviour, explore_item_greed should be set
1331 // to 10 or more.
1332 //
1333 unexplored_place = greedy_place = coord_def(0, 0);
1334 unexplored_dist = greedy_dist = UNFOUND_DIST;
1335
1336 refdist = (runmode == RMODE_CONNECTIVITY || Options.explore_item_greed > 0)
1337 ? &unexplored_dist : &greedy_dist;
1338
1339 // Zap out previous distances array: this must happen before the
1340 // early exit checks below, since callers may want to inspect
1341 // point_distance after this call returns.
1342 //
1343 // point_distance will hold the distance of all points from the starting
1344 // point, i.e. the distance travelled to get there.
1345 memset(point_distance, 0, sizeof(travel_distance_grid_t));
1346
1347 if (!in_bounds(start))
1348 return coord_def();
1349
1350 // Abort run if we're trying to go someplace evil. Travel to traps is
1351 // specifically allowed here if the player insists on it.
1352 if (!floodout
1353 && !_is_travelsafe_square(start, false, ignore_danger, true)
1354 && !is_trap(start)) // player likes pain
1355 {
1356 return coord_def();
1357 }
1358
1359 // Nothing to do?
1360 if (!floodout && start == dest)
1361 return start;
1362
1363 unwind_bool slime_wall_check(g_Slime_Wall_Check,
1364 !actor_slime_wall_immune(&you));
1365 unwind_slime_wall_precomputer slime_neighbours(g_Slime_Wall_Check);
1366
1367 // How many points we'll consider next iteration.
1368 next_iter_points = 0;
1369
1370 // How far we've travelled from (start_x, start_y), in moves (a diagonal move
1371 // is no longer than an orthogonal move).
1372 traveled_distance = 1;
1373
1374 // Which index of the circumference array are we currently looking at?
1375 circ_index = 0;
1376
1377 ignore_hostile = false;
1378
1379 // For each round, circumference will store all points that were discovered
1380 // in the previous round of a given distance. Because we check all grids of
1381 // a certain distance from the starting point in one round, and move
1382 // outwards in concentric circles, this is an implementation of Dijkstra.
1383 // We use an array of size 2, so we can comfortably switch between the list
1384 // of points to be investigated this round and the slowly growing list of
1385 // points to be inspected next round. Once we've finished with the current
1386 // round, i.e. there are no more points to be looked at in the current
1387 // array, we switch circ_index over to !circ_index (between 0 and 1), so
1388 // the "next round" becomes the current one, and the old points can be
1389 // overwritten with newer ones. Since we count the number of points for
1390 // next round in next_iter_points, we don't even need to reset the array.
1391 circumference[circ_index][0] = start;
1392
1393 bool found_target = false;
1394
1395 for (int points = 1; points > 0; ++traveled_distance,
1396 circ_index = !circ_index, points = next_iter_points,
1397 next_iter_points = 0)
1398 {
1399 for (int i = 0; i < points; ++i)
1400 {
1401 // Look at all neighbours of the current grid.
1402 // path_examine_point() returns true if the target is reached
1403 // and marked as such.
1404 if (path_examine_point(circumference[circ_index][i]))
1405 {
1406 if (runmode == RMODE_TRAVEL)
1407 return next_travel_move;
1408 else if (runmode == RMODE_CONNECTIVITY
1409 || !Options.explore_wall_bias)
1410 {
1411 return explore_target();
1412 }
1413 else
1414 found_target = true;
1415 }
1416 }
1417
1418 // Handle exploration with wall bias
1419 if (next_iter_points == 0 && found_target)
1420 return explore_target();
1421
1422 // If there are no more points to look at, we're done, but we did
1423 // not find a path to our target.
1424 if (next_iter_points == 0)
1425 {
1426 // Don't reseed unless we've found no target for explore, OR
1427 // we're doing map annotation or feature tracking.
1428 if ((runmode == RMODE_EXPLORE || runmode == RMODE_EXPLORE_GREEDY
1429 || runmode == RMODE_CONNECTIVITY)
1430 && double_flood
1431 && !ignore_hostile
1432 && !features
1433 && !annotate_map
1434 && (unexplored_dist != UNFOUND_DIST
1435 || greedy_dist != UNFOUND_DIST))
1436 {
1437 break;
1438 }
1439
1440 if (double_flood
1441 && !ignore_hostile
1442 && !reseed_points.empty())
1443 {
1444 // Reseed here
1445 for (unsigned i = 0, size = reseed_points.size(); i < size; ++i)
1446 circumference[!circ_index][i] = reseed_points[i];
1447
1448 next_iter_points = reseed_points.size();
1449 ignore_hostile = true;
1450 }
1451 }
1452 } // for (; points > 0 ...
1453
1454 if (features && floodout)
1455 {
1456 for (const auto &entry : curr_excludes)
1457 {
1458 const travel_exclude &exc = entry.second;
1459 // An exclude - wherever it is - is always a feature.
1460 if (find(features->begin(), features->end(), exc.pos)
1461 == features->end())
1462 {
1463 features->push_back(exc.pos);
1464 }
1465
1466 _fill_exclude_radius(exc);
1467 }
1468 }
1469
1470 return runmode == RMODE_TRAVEL ? next_travel_move
1471 : explore_target();
1472 }
1473
get_features()1474 void travel_pathfind::get_features()
1475 {
1476 ASSERT(features);
1477
1478 if (!ls && (annotate_map || need_for_greed))
1479 ls = StashTrack.find_current_level();
1480
1481 memset(point_distance, 0, sizeof(travel_distance_grid_t));
1482
1483 coord_def dc;
1484 for (dc.x = X_BOUND_1; dc.x <= X_BOUND_2; ++dc.x)
1485 for (dc.y = Y_BOUND_1; dc.y <= Y_BOUND_2; ++dc.y)
1486 {
1487 const dungeon_feature_type feature = env.map_knowledge(dc).feat();
1488
1489 if ((feature != DNGN_FLOOR
1490 && !feat_is_water(feature)
1491 && feature != DNGN_LAVA)
1492 || is_waypoint(dc)
1493 || is_stash(ls, dc)
1494 || is_trap(dc))
1495 {
1496 features->push_back(dc);
1497 }
1498 }
1499
1500 for (const auto &entry : curr_excludes)
1501 {
1502 const travel_exclude &exc = entry.second;
1503
1504 // An exclude - wherever it is - is always a feature.
1505 if (find(features->begin(), features->end(), exc.pos) == features->end())
1506 features->push_back(exc.pos);
1507
1508 _fill_exclude_radius(exc);
1509 }
1510 }
1511
square_slows_movement(const coord_def & c)1512 bool travel_pathfind::square_slows_movement(const coord_def &c)
1513 {
1514 // c is a known (explored) location - we never put unknown points in the
1515 // circumference vector, so we don't need to examine the map array, just the
1516 // grid array.
1517 const dungeon_feature_type feature = env.map_knowledge(c).feat();
1518
1519 // If this is a feature that'll take time to travel past, we simulate that
1520 // extra turn by taking this feature next turn, thereby artificially
1521 // increasing traveled_distance.
1522 //
1523 // Walking through shallow water and opening closed doors is considered to
1524 // have the cost of two normal moves for travel purposes.
1525 const int feat_cost = _feature_traverse_cost(feature);
1526 if (feat_cost > 1
1527 && point_distance[c.x][c.y] > traveled_distance - feat_cost)
1528 {
1529 circumference[!circ_index][next_iter_points++] = c;
1530 return true;
1531 }
1532
1533 return false;
1534 }
1535
check_square_greed(const coord_def & c)1536 void travel_pathfind::check_square_greed(const coord_def &c)
1537 {
1538 if (greedy_dist == UNFOUND_DIST
1539 && is_greed_inducing_square(c)
1540 && _is_travelsafe_square(c, ignore_hostile, ignore_danger))
1541 {
1542 int dist = traveled_distance;
1543
1544 // Penalize distance for negative explore_item_greed
1545 if (Options.explore_item_greed < 0)
1546 dist -= Options.explore_item_greed;
1547
1548 // The addition of explore_wall_bias makes items as interesting
1549 // as a room's perimeter (with one of four known adjacent walls).
1550 if (Options.explore_wall_bias)
1551 dist += Options.explore_wall_bias * 3;
1552
1553 greedy_dist = dist;
1554 greedy_place = c;
1555 }
1556 }
1557
path_flood(const coord_def & c,const coord_def & dc)1558 bool travel_pathfind::path_flood(const coord_def &c, const coord_def &dc)
1559 {
1560 if (!in_bounds(dc) || unreachables.count(dc))
1561 return false;
1562
1563 if (floodout
1564 && (runmode == RMODE_EXPLORE || runmode == RMODE_EXPLORE_GREEDY))
1565 {
1566 if (!env.map_knowledge(dc).seen())
1567 {
1568 if (ignore_hostile && !player_in_branch(BRANCH_SHOALS))
1569 {
1570 // This point is unexplored but unreachable. Let's find a
1571 // place from where we can see it.
1572 for (radius_iterator ri(dc, LOS_DEFAULT, true); ri; ++ri)
1573 {
1574 const int dist = point_distance[ri->x][ri->y];
1575 if (dist > 0
1576 && (dist < unexplored_dist || unexplored_dist < 0))
1577 {
1578 unexplored_dist = dist;
1579 unexplored_place = *ri;
1580 }
1581
1582 // We can't do better than that.
1583 if (unexplored_dist == 1)
1584 {
1585 _set_target_square(unexplored_place);
1586 return true;
1587 }
1588 }
1589
1590 // We can't even see the place.
1591 // Let's store it and look for another.
1592 if (unexplored_dist < 0)
1593 unreachables.insert(dc);
1594 else
1595 _set_target_square(unexplored_place);
1596 }
1597 else
1598 {
1599 // Found explore target!
1600 int dist = traveled_distance;
1601
1602 if (need_for_greed && Options.explore_item_greed > 0)
1603 {
1604 // Penalize distance to favour item pickup
1605 dist += Options.explore_item_greed;
1606 }
1607
1608 if (Options.explore_wall_bias)
1609 {
1610 dist += Options.explore_wall_bias * 4;
1611
1612 // Favour squares directly adjacent to walls
1613 for (int dir = 0; dir < 8; dir += 2)
1614 {
1615 const coord_def ddc = dc + Compass[dir];
1616
1617 if (feat_is_wall(env.map_knowledge(ddc).feat()))
1618 dist -= Options.explore_wall_bias;
1619 }
1620 }
1621
1622 // Replace old target if nearer (or less penalized)
1623 if (dist < unexplored_dist || unexplored_dist < 0)
1624 {
1625 unexplored_dist = dist;
1626 unexplored_place = c;
1627 }
1628 }
1629 }
1630
1631 // Short-circuit if we can. If traveled_distance (the current
1632 // distance from the centre of the floodfill) is greater
1633 // than the adjusted distance to the nearest greedy explore
1634 // target, we have a target. Note the adjusted distance is
1635 // the distance with explore_item_greed applied (if
1636 // explore_item_greed > 0, it is added to the distance to
1637 // unexplored terrain, if explore_item_greed < 0, it is
1638 // added to the distance to interesting items.
1639 //
1640 // We never short-circuit if ignore_hostile is true. This is
1641 // important so we don't need to do multiple floods to work out
1642 // whether explore is complete.
1643 if (need_for_greed
1644 && !ignore_hostile
1645 && *refdist != UNFOUND_DIST
1646 && traveled_distance > *refdist)
1647 {
1648 if (Options.explore_item_greed > 0)
1649 greedy_dist = INFINITE_DIST;
1650 else
1651 unexplored_dist = INFINITE_DIST;
1652 }
1653
1654 // greedy_dist is only ever set in greedy-explore so this check
1655 // implies greedy-explore.
1656 if (unexplored_dist != UNFOUND_DIST && greedy_dist != UNFOUND_DIST)
1657 return true;
1658 }
1659
1660 // We don't want to follow the transporter at c if it's excluded. We also
1661 // don't want to update point_distance for the destination based on
1662 // taking this transporter.
1663 if (!ignore_danger
1664 && is_excluded(c)
1665 && env.map_knowledge(c).feat() == DNGN_TRANSPORTER
1666 // We have to actually take the transporter to go from c to dc.
1667 && !adjacent(c, dc))
1668 {
1669 return false;
1670 }
1671 else if (dc == dest)
1672 {
1673 // Hallelujah, we're home!
1674 if (_is_safe_move(c))
1675 next_travel_move = c;
1676
1677 return true;
1678 }
1679 else if (!_is_travelsafe_square(dc, ignore_hostile, ignore_danger, try_fallback))
1680 {
1681 // This point is not okay to travel on, but if this is a
1682 // trap, we'll want to put it on the feature vector anyway.
1683 if (_is_reseedable(dc, ignore_danger)
1684 && !point_distance[dc.x][dc.y]
1685 && dc != start)
1686 {
1687 if (features && (is_trap(dc) || is_exclude_root(dc))
1688 && find(features->begin(), features->end(), dc)
1689 == features->end())
1690 {
1691 features->push_back(dc);
1692 }
1693
1694 if (double_flood)
1695 reseed_points.push_back(dc);
1696
1697 // Appropriate mystic number. Nobody else should check
1698 // this number, since this square is unsafe for travel.
1699 point_distance[dc.x][dc.y] =
1700 is_exclude_root(dc) ? PD_EXCLUDED :
1701 is_excluded(dc) ? PD_EXCLUDED_RADIUS :
1702 !_is_safe_cloud(dc) ? PD_CLOUD
1703 : PD_TRAP;
1704 }
1705 return false;
1706 }
1707
1708 if (!point_distance[dc.x][dc.y])
1709 {
1710 // This point is going to be on the agenda for the next
1711 // iteration
1712 circumference[!circ_index][next_iter_points++] = dc;
1713 point_distance[dc.x][dc.y] = traveled_distance;
1714
1715 // Negative distances here so that show_map can colour
1716 // the map differently for these squares.
1717 if (ignore_hostile)
1718 {
1719 point_distance[dc.x][dc.y] = -point_distance[dc.x][dc.y];
1720 if (is_exclude_root(dc))
1721 point_distance[dc.x][dc.y] = PD_EXCLUDED;
1722 else if (is_excluded(dc))
1723 point_distance[dc.x][dc.y] = PD_EXCLUDED_RADIUS;
1724 }
1725
1726 if (features && !ignore_hostile)
1727 {
1728 dungeon_feature_type feature = env.map_knowledge(dc).feat();
1729
1730 if (dc != start
1731 && (feature != DNGN_FLOOR
1732 && !feat_is_water(feature)
1733 && feature != DNGN_LAVA
1734 || is_waypoint(dc)
1735 || is_stash(ls, dc))
1736 && find(features->begin(), features->end(), dc)
1737 == features->end())
1738 {
1739 features->push_back(dc);
1740 }
1741 }
1742
1743 if (features && dc != start && is_exclude_root(dc)
1744 && find(features->begin(), features->end(), dc)
1745 == features->end())
1746 {
1747 features->push_back(dc);
1748 }
1749 }
1750
1751 return false;
1752 }
1753
good_square(const coord_def & c)1754 void travel_pathfind::good_square(const coord_def &c)
1755 {
1756 if (!point_distance[c.x][c.y])
1757 {
1758 // This point is going to be on the agenda for the next iteration.
1759 circumference[!circ_index][next_iter_points++] = c;
1760 point_distance[c.x][c.y] = traveled_distance;
1761 }
1762 }
1763
point_traverse_delay(const coord_def & c)1764 bool travel_pathfind::point_traverse_delay(const coord_def &c)
1765 {
1766 if (square_slows_movement(c))
1767 return true;
1768
1769 // Greedy explore check should happen on (x,y), not (dx,dy) as for
1770 // regular explore.
1771 if (need_for_greed)
1772 check_square_greed(c);
1773
1774 return false;
1775 }
1776
1777 // Checks all neighbours of c, adds them to next round's list of points
1778 // - happens in path_flood() - and returns true if one of them turns out
1779 // to be the target; otherwise, false.
path_examine_point(const coord_def & c)1780 bool travel_pathfind::path_examine_point(const coord_def &c)
1781 {
1782 // If we've run off the map, or are pathfinding from nowhere in particular
1783 if (!in_bounds(c))
1784 return false;
1785
1786 if (point_traverse_delay(c))
1787 return false;
1788
1789 bool found_target = false;
1790
1791 // For each point, we look at all surrounding points. Take them orthogonals
1792 // first so that the travel path doesn't zigzag all over the map. Note the
1793 // (dir = 1) is intentional assignment.
1794 for (int dir = 0; dir < 8; (dir += 2) == 8 && (dir = 1))
1795 if (path_flood(c, c + Compass[dir]))
1796 found_target = true;
1797
1798 // For travel, we want to pathfind through transporters. Floodout mode
1799 // proceeds from source, so we take transporters, but for determining moves
1800 // we work in reverse from destination back to source, so we pathfind
1801 // through the landing sites.
1802 if (runmode == RMODE_TRAVEL || runmode == RMODE_NOT_RUNNING)
1803 {
1804 if (floodout && env.grid(c) == DNGN_TRANSPORTER)
1805 {
1806 LevelInfo &li = travel_cache.get_level_info(level_id::current());
1807 transporter_info *ti = li.get_transporter(c);
1808 if (ti && ti->destination != INVALID_COORD)
1809 {
1810 if (path_flood(c, ti->destination))
1811 found_target = true;
1812 }
1813 }
1814 else if (!floodout && env.grid(c) == DNGN_TRANSPORTER_LANDING)
1815 {
1816 LevelInfo &li = travel_cache.get_level_info(level_id::current());
1817 vector<transporter_info> transporters = li.get_transporters();
1818 for (auto ti : transporters)
1819 {
1820 if (ti.destination == c)
1821 if (path_flood(c, ti.position))
1822 found_target = true;
1823 }
1824 }
1825 }
1826
1827 return found_target;
1828 }
1829
1830 // Determines if the level is fully explored.
1831 // This uses data provided by pathfind(), so that needs to be called first.
explore_status()1832 int travel_pathfind::explore_status()
1833 {
1834 int explore_status = 0;
1835
1836 const coord_def greed = greedy_place;
1837 if (greed.x || greed.y)
1838 explore_status |= EST_GREED_UNFULFILLED;
1839
1840 const coord_def unexplored = unexplored_place;
1841 if (unexplored.x || unexplored.y || !unreachables.empty())
1842 explore_status |= EST_PARTLY_EXPLORED;
1843
1844 return explore_status;
1845 }
1846
1847
1848 /**
1849 * Run the travel_pathfind algorithm, from the given position in floodout mode
1850 * to populate travel_point_distance relative to that starting point.
1851 *
1852 * @param youpos The starting position.
1853 * @param[in] features A vector of features to give to travel_pathfind.
1854 */
fill_travel_point_distance(const coord_def & youpos,vector<coord_def> * features)1855 void fill_travel_point_distance(const coord_def& youpos,
1856 vector<coord_def>* features)
1857 {
1858 travel_pathfind tp;
1859 tp.set_floodseed(youpos);
1860 tp.set_feature_vector(features);
1861
1862 // Calling pathfind() twice like this changes the order of *features, but
1863 // has no effect on travel_point_distance.
1864 if (features)
1865 tp.pathfind(RMODE_NOT_RUNNING, false);
1866 tp.pathfind(RMODE_NOT_RUNNING, true);
1867 }
1868
1869 extern map<branch_type, set<level_id> > stair_level;
1870
_find_parent_branch(branch_type br,branch_type * pb,int * pd)1871 static void _find_parent_branch(branch_type br, branch_type *pb, int *pd)
1872 {
1873 *pb = parent_branch(br); // Check depth before using *pb.
1874
1875 if (auto levels = map_find(stair_level, br))
1876 {
1877 if (levels->size() > 0)
1878 {
1879 *pd = levels->begin()->depth;
1880 return;
1881 }
1882 }
1883 *pd = 0;
1884 }
1885
1886 // Appends the passed in branch/depth to the given vector, then attempts to
1887 // repeat the operation with the parent branch of the given branch.
1888 //
1889 // As an example of what it does, assume this dungeon structure
1890 // Stairs to lair on D:11
1891 // Stairs to snake pit on lair:5
1892 //
1893 // If level 3 of the snake pit is the level we want to track back from,
1894 // we'd call _trackback(vec, BRANCH_SNAKE, 3), and the resulting vector will
1895 // look like:
1896 // { BRANCH_SNAKE, 3 }, { BRANCH_LAIR, 5 }, { BRANCH_DUNGEON, 11 }
1897 // (Assuming, of course, that the vector started out empty.)
1898 //
_trackback(vector<level_id> & vec,branch_type branch,int subdepth)1899 static void _trackback(vector<level_id> &vec, branch_type branch, int subdepth)
1900 {
1901 if (subdepth < 1)
1902 return;
1903 ASSERT(subdepth <= 27);
1904
1905 vec.emplace_back(branch, subdepth);
1906
1907 if (branch != root_branch)
1908 {
1909 branch_type pb;
1910 int pd;
1911 _find_parent_branch(branch, &pb, &pd);
1912 if (pd)
1913 _trackback(vec, pb, pd);
1914 }
1915 }
1916
_track_intersect(vector<level_id> & cur,vector<level_id> & targ,level_id * cx)1917 static void _track_intersect(vector<level_id> &cur, vector<level_id> &targ,
1918 level_id *cx)
1919 {
1920 cx->branch = BRANCH_DUNGEON;
1921 cx->depth = -1;
1922
1923 int us = int(cur.size()) - 1, them = int(targ.size()) - 1;
1924
1925 for (; us >= 0 && them >= 0; us--, them--)
1926 if (cur[us].branch != targ[them].branch)
1927 break;
1928
1929 us++, them++;
1930
1931 if (us < (int) cur.size() && them < (int) targ.size() && us >= 0
1932 && them >= 0)
1933 {
1934 *cx = targ[them];
1935 }
1936 }
1937
1938 // Returns the number of stairs the player would need to take to go from
1939 // the 'first' level to the 'second' level. If there's no obvious route between
1940 // 'first' and 'second', returns -1. If first == second, returns 0.
level_distance(level_id first,level_id second)1941 int level_distance(level_id first, level_id second)
1942 {
1943 if (first == second)
1944 return 0;
1945
1946 vector<level_id> fv, sv;
1947
1948 // If in the same branch, easy.
1949 if (first.branch == second.branch)
1950 return abs(first.depth - second.depth);
1951
1952 // Figure out the dungeon structure between the two levels.
1953 _trackback(fv, first.branch, first.depth);
1954 _trackback(sv, second.branch, second.depth);
1955
1956 level_id intersect;
1957 _track_intersect(fv, sv, &intersect);
1958
1959 if (intersect.depth == -1) // No common ground?
1960 return -1;
1961
1962 int distance = 0;
1963 // If the common branch is not the same as the current branch, we'll
1964 // have to walk up the branch tree until we get to the common branch.
1965 while (first.branch != intersect.branch)
1966 {
1967 distance += first.depth;
1968
1969 _find_parent_branch(first.branch, &first.branch, &first.depth);
1970 if (!first.depth)
1971 return -1;
1972 }
1973
1974 // Now first.branch == intersect.branch
1975 distance += abs(first.depth - intersect.depth);
1976
1977 bool ignore_end = true;
1978 for (int i = sv.size() - 1; i >= 0; --i)
1979 {
1980 if (ignore_end)
1981 {
1982 if (sv[i].branch == intersect.branch)
1983 ignore_end = false;
1984 continue;
1985 }
1986 distance += sv[i].depth;
1987 }
1988
1989 return distance;
1990 }
1991
_get_trans_travel_dest(const level_pos & target,bool skip_branch=false,bool skip_coord=false)1992 static string _get_trans_travel_dest(const level_pos &target,
1993 bool skip_branch = false,
1994 bool skip_coord = false)
1995 {
1996 const int branch_id = target.id.branch;
1997 const char *branch = branches[branch_id].abbrevname;
1998
1999 if (!branch)
2000 return "";
2001
2002 ostringstream dest;
2003
2004 if (!skip_branch)
2005 dest << branch;
2006 if (brdepth[branch_id] != 1)
2007 {
2008 if (!skip_branch)
2009 dest << ":";
2010 dest << target.id.depth;
2011 }
2012 if (target.pos.x != -1 && !skip_coord)
2013 dest << " @ (x,y)";
2014
2015 return dest.str();
2016 }
2017
2018 // Returns the level on the given branch that's closest to the player's
2019 // current location.
_get_nearest_level_depth(uint8_t branch)2020 static int _get_nearest_level_depth(uint8_t branch)
2021 {
2022 int depth = 1;
2023
2024 // Hell needs special treatment, because we can't walk up
2025 // Hell and its branches to the main dungeon.
2026 if (branch == BRANCH_DEPTHS && is_hell_branch(you.where_are_you))
2027 {
2028 // BUG: hell gates in the Lair
2029 return brentry[BRANCH_VESTIBULE].depth;
2030 }
2031
2032 level_id id = level_id::current();
2033 do
2034 {
2035 _find_parent_branch(id.branch, &id.branch, &id.depth);
2036 if (id.depth && id.branch == branch)
2037 {
2038 depth = id.depth;
2039 break;
2040 }
2041 }
2042 while (id.depth);
2043
2044 return depth;
2045 }
2046
2047 // Returns true if the player character knows of the existence of the given
2048 // branch (which would make the branch a valid target for interlevel travel).
is_known_branch_id(branch_type branch)2049 bool is_known_branch_id(branch_type branch)
2050 {
2051 // The main dungeon is always known
2052 if (branch == root_branch)
2053 return true;
2054
2055 // If we're in the branch, it darn well is known.
2056 if (player_in_branch(branch))
2057 return true;
2058
2059 // The Vestibule is special: there are no stairs to it, just a
2060 // portal.
2061 if (branch == BRANCH_VESTIBULE)
2062 return overview_knows_portal(branch);
2063
2064 // Guaranteed portal vault, don't show in interlevel travel.
2065 if (branch == BRANCH_ZIGGURAT)
2066 return false;
2067
2068 // If the overview knows the stairs to this branch, we know the branch.
2069 return stair_level.find(static_cast<branch_type>(branch))
2070 != stair_level.end() && stair_level[branch].size();
2071 }
2072
_is_known_branch(const Branch & br)2073 static bool _is_known_branch(const Branch &br)
2074 {
2075 return is_known_branch_id(br.id);
2076 }
2077
2078 // Returns a list of the branches that the player knows the location of the
2079 // stairs to, in the same order as dgn-overview.cc lists them.
_get_branches(bool (* selector)(const Branch &))2080 static vector<branch_type> _get_branches(bool (*selector)(const Branch &))
2081 {
2082 vector<branch_type> result;
2083
2084 for (branch_iterator it; it; ++it)
2085 if (selector(**it))
2086 result.push_back(it->id);
2087
2088 return result;
2089 }
2090
_is_valid_branch(const Branch & br)2091 static bool _is_valid_branch(const Branch &br)
2092 {
2093 return br.shortname != nullptr
2094 && brdepth[br.id] != -1
2095 && !branch_is_unfinished(br.id);
2096 }
2097
_is_disconnected_branch(const Branch & br)2098 static bool _is_disconnected_branch(const Branch &br)
2099 {
2100 return !is_connected_branch(br.id);
2101 }
2102
_prompt_travel_branch(int prompt_flags)2103 static int _prompt_travel_branch(int prompt_flags)
2104 {
2105 int branch = BRANCH_DUNGEON; // Default
2106 vector<branch_type> brs =
2107 _get_branches(
2108 (prompt_flags & TPF_SHOW_ALL_BRANCHES) ? _is_valid_branch :
2109 (prompt_flags & TPF_SHOW_PORTALS_ONLY) ? _is_disconnected_branch
2110 : _is_known_branch);
2111
2112 // Don't kill the prompt even if the only branch we know is the main dungeon
2113 // This keeps things consistent for the player.
2114 if (brs.size() < 1)
2115 return branch;
2116
2117 const bool allow_waypoints = (prompt_flags & TPF_ALLOW_WAYPOINTS);
2118 const bool allow_updown = (prompt_flags & TPF_ALLOW_UPDOWN);
2119 const bool remember_targ = (prompt_flags & TPF_REMEMBER_TARGET);
2120
2121 bool waypoint_list = false;
2122 const int waycount = allow_waypoints? travel_cache.get_waypoint_count() : 0;
2123
2124 level_id curr = level_id::current();
2125 while (true)
2126 {
2127 clear_messages();
2128
2129 if (waypoint_list)
2130 travel_cache.list_waypoints();
2131 else
2132 {
2133 int linec = 0;
2134 string line;
2135 for (branch_type br : brs)
2136 {
2137 if (linec == 4)
2138 {
2139 linec = 0;
2140 mpr(line);
2141 line = "";
2142 }
2143 line += make_stringf("(%c) %-14s ",
2144 branches[br].travel_shortcut,
2145 branches[br].shortname);
2146 ++linec;
2147 }
2148 if (!line.empty())
2149 mpr(line);
2150 }
2151
2152 string shortcuts = "(";
2153 {
2154 vector<string> segs;
2155 if (allow_waypoints)
2156 {
2157 if (waypoint_list)
2158 segs.emplace_back("* - list branches");
2159 else if (waycount)
2160 segs.emplace_back("* - list waypoints");
2161 }
2162
2163 if (!trans_travel_dest.empty() && remember_targ)
2164 {
2165 segs.push_back(
2166 make_stringf("Enter - %s", trans_travel_dest.c_str()));
2167 }
2168
2169 segs.emplace_back("? - help");
2170
2171 shortcuts += comma_separated_line(segs.begin(), segs.end(),
2172 ", ", ", ");
2173 shortcuts += ") ";
2174 }
2175 mprf(MSGCH_PROMPT, "Where to? %s",
2176 shortcuts.c_str());
2177
2178 int keyin = get_ch();
2179 switch (keyin)
2180 {
2181 CASE_ESCAPE
2182 return ID_CANCEL;
2183 case '?':
2184 show_interlevel_travel_branch_help();
2185 redraw_screen();
2186 update_screen();
2187 break;
2188 case '_':
2189 return ID_ALTAR;
2190 case '\n': case '\r':
2191 return ID_REPEAT;
2192 case '<':
2193 return allow_updown ? ID_UP : ID_CANCEL;
2194 case '>':
2195 return allow_updown ? ID_DOWN : ID_CANCEL;
2196 case CONTROL('P'):
2197 {
2198 const branch_type parent = parent_branch(curr.branch);
2199 if (parent < NUM_BRANCHES)
2200 return parent;
2201 }
2202 break;
2203 case '.':
2204 return curr.branch;
2205 case '*':
2206 if (waypoint_list || waycount)
2207 waypoint_list = !waypoint_list;
2208 break;
2209 default:
2210 // Is this a branch hotkey?
2211 for (branch_type br : brs)
2212 {
2213 if (toupper_safe(keyin) == branches[br].travel_shortcut)
2214 {
2215 #ifdef WIZARD
2216 const Branch &target = branches[br];
2217 string msg;
2218
2219 if (!brentry[br].is_valid()
2220 && is_random_subbranch(br)
2221 && you.wizard) // don't leak mimics
2222 {
2223 msg += "Branch not generated this game. ";
2224 }
2225
2226 if (target.entry_stairs == NUM_FEATURES
2227 && br != BRANCH_DUNGEON)
2228 {
2229 msg += "Branch has no entry stairs. ";
2230 }
2231
2232 if (!msg.empty())
2233 {
2234 msg += "Go there anyway?";
2235 if (!yesno(msg.c_str(), true, 'n'))
2236 return ID_CANCEL;
2237 }
2238 #endif
2239 return br;
2240 }
2241 }
2242
2243 // Possibly a waypoint number?
2244 if (allow_waypoints && keyin >= '0' && keyin <= '9')
2245 return -1 - (keyin - '0');
2246
2247 return ID_CANCEL;
2248 }
2249 }
2250 }
2251
_god_from_initial(const char god_initial)2252 static god_type _god_from_initial(const char god_initial)
2253 {
2254 switch (toupper_safe(god_initial))
2255 {
2256 case '1': return GOD_SHINING_ONE;
2257 case 'A': return GOD_ASHENZARI;
2258 case 'B': return GOD_BEOGH;
2259 case 'C': return GOD_CHEIBRIADOS;
2260 case 'D': return GOD_DITHMENOS;
2261 case 'E': return GOD_ELYVILON;
2262 case 'F': return GOD_FEDHAS;
2263 case 'G': return GOD_GOZAG;
2264 case 'H': return GOD_HEPLIAKLQANA;
2265 case 'J': return GOD_JIYVA;
2266 case 'K': return GOD_KIKUBAAQUDGHA;
2267 case 'L': return GOD_LUGONU;
2268 case 'M': return GOD_MAKHLEB;
2269 case 'N': return GOD_NEMELEX_XOBEH;
2270 case 'O': return GOD_OKAWARU;
2271 #if TAG_MAJOR_VERSION == 34
2272 case 'P': return GOD_PAKELLAS;
2273 #endif
2274 case 'Q': return GOD_QAZLAL;
2275 case 'R': return GOD_RU;
2276 case 'S': return GOD_SIF_MUNA;
2277 case 'T': return GOD_TROG;
2278 case 'U': return GOD_USKAYAW;
2279 case 'V': return GOD_VEHUMET;
2280 case 'W': return GOD_WU_JIAN;
2281 case 'X': return GOD_XOM;
2282 case 'Y': return GOD_YREDELEMNUL;
2283 case 'Z': return GOD_ZIN;
2284 default: return GOD_NO_GOD;
2285 }
2286 }
2287
_prompt_travel_altar()2288 static level_pos _prompt_travel_altar()
2289 {
2290 extern map<level_pos, god_type> altars_present;
2291
2292 if (altars_present.empty())
2293 return level_pos();
2294
2295 level_pos nearest_altars[NUM_GODS];
2296 const level_id curr = level_id::current();
2297
2298 // Populate nearest_altars[] with nearest altars
2299 for (const auto &entry : altars_present)
2300 {
2301 // This is necessary because faded altars (i.e., GOD_ECUMENICAL)
2302 // are also recorded in altars_present
2303 if (entry.second >= NUM_GODS)
2304 continue;
2305
2306 int dist = level_distance(curr, entry.first.id);
2307 if (dist == -1)
2308 continue;
2309
2310 level_pos *best = &nearest_altars[entry.second];
2311 int old_dist = best->id.is_valid() ? level_distance(curr, best->id) : INT_MAX;
2312
2313 if (dist < old_dist)
2314 *best = entry.first;
2315 }
2316
2317 while (true)
2318 {
2319 clear_messages();
2320
2321 int col = 0;
2322 string line;
2323 string altar_name;
2324 char god_initial;
2325 vector<god_type> god_list = temple_god_list();
2326 vector<god_type> nt_god_list = nontemple_god_list();
2327 god_list.insert(god_list.end(), nt_god_list.begin(), nt_god_list.end());
2328
2329 // list gods in the same order as dgn-overview.cc lists them.
2330 for (const god_type god : god_list)
2331 {
2332 if (!nearest_altars[god].is_valid())
2333 continue;
2334
2335 // "The Shining One" is too long to keep the same G menu layout
2336 altar_name = god == GOD_SHINING_ONE ? "TSO" : god_name(god);
2337 god_initial = god == GOD_SHINING_ONE ? '1' : altar_name.at(0);
2338
2339 if (col == 4)
2340 {
2341 col = 0;
2342 mpr(line);
2343 line = "";
2344 }
2345 line += make_stringf("(%c) %-14s ", god_initial, altar_name.c_str());
2346 ++col;
2347 }
2348 if (!line.empty())
2349 mpr(line);
2350
2351 mprf(MSGCH_PROMPT, "Go to which altar? (? - help) ");
2352
2353 int keyin = get_ch();
2354 switch (keyin)
2355 {
2356 CASE_ESCAPE
2357 return level_pos();
2358 case '?':
2359 show_interlevel_travel_altar_help();
2360 redraw_screen();
2361 update_screen();
2362 break;
2363 case '\n': case '\r':
2364 return level_target;
2365 default:
2366 const level_pos altar_pos = nearest_altars[_god_from_initial(keyin)];
2367 if (altar_pos.is_valid())
2368 return altar_pos;
2369
2370 return level_pos();
2371 }
2372 }
2373 }
2374
find_up_level(level_id curr,bool up_branch)2375 level_id find_up_level(level_id curr, bool up_branch)
2376 {
2377 --curr.depth;
2378
2379 if (up_branch)
2380 curr.depth = 0;
2381
2382 if (curr.depth < 1)
2383 {
2384 if (curr.branch != BRANCH_DUNGEON && curr.branch != root_branch)
2385 {
2386 level_id parent;
2387 _find_parent_branch(curr.branch, &parent.branch, &parent.depth);
2388 if (parent.depth > 0)
2389 return parent;
2390 else if (curr.branch == BRANCH_VESTIBULE)
2391 return brentry[BRANCH_VESTIBULE];
2392 }
2393 return level_id();
2394 }
2395
2396 return curr;
2397 }
2398
_find_up_level()2399 static level_id _find_up_level()
2400 {
2401 return find_up_level(level_id::current());
2402 }
2403
find_down_level(level_id curr)2404 level_id find_down_level(level_id curr)
2405 {
2406 if (curr.depth < brdepth[curr.branch])
2407 ++curr.depth;
2408 return curr;
2409 }
2410
find_deepest_explored(level_id curr)2411 level_id find_deepest_explored(level_id curr)
2412 {
2413 ASSERT(curr.branch != NUM_BRANCHES);
2414
2415 for (int i = brdepth[curr.branch]; i > 0; --i)
2416 {
2417 const level_id lid(curr.branch, i);
2418 LevelInfo *linf = travel_cache.find_level_info(lid);
2419 if (linf && !linf->empty())
2420 return lid;
2421 }
2422
2423 // If the player's currently in the same place, report their current
2424 // level_id if the travel cache hasn't been updated.
2425 const level_id player_level = level_id::current();
2426 if (player_level == curr.branch)
2427 return player_level;
2428
2429 return curr;
2430 }
2431
branch_entered(branch_type branch)2432 bool branch_entered(branch_type branch)
2433 {
2434 const level_id lid(branch, 1);
2435 LevelInfo *linf = travel_cache.find_level_info(lid);
2436 return linf && !linf->empty();
2437 }
2438
_find_down_level()2439 static level_id _find_down_level()
2440 {
2441 return find_down_level(level_id::current());
2442 }
2443
_travel_depth_keyfilter(int & c)2444 static keyfun_action _travel_depth_keyfilter(int &c)
2445 {
2446 switch (c)
2447 {
2448 case '<': case '>': case '?': case '$': case '^':
2449 return KEYFUN_BREAK;
2450 case '-':
2451 case CONTROL('P'): case 'p':
2452 c = '-'; // Make uniform.
2453 return KEYFUN_BREAK;
2454 default:
2455 return KEYFUN_PROCESS;
2456 }
2457 }
2458
_find_entrance(const level_pos & from)2459 static level_pos _find_entrance(const level_pos &from)
2460 {
2461 level_id lid(from.id);
2462 coord_def pos(-1, -1);
2463 branch_type target_branch = lid.branch;
2464
2465 lid.depth = 1;
2466 level_id new_lid = find_up_level(lid);
2467
2468 if (new_lid.is_valid())
2469 {
2470 LevelInfo &li = travel_cache.get_level_info(new_lid);
2471 vector<stair_info> &stairs = li.get_stairs();
2472 for (const auto &stair : stairs)
2473 if (stair.destination.id.branch == target_branch)
2474 {
2475 pos = stair.position;
2476 break;
2477 }
2478 #ifdef DEBUG_TRAVEL
2479 dprf("found entrance in %d depth %d at %d,%d", new_lid.branch,
2480 new_lid.depth, pos.x, pos.y);
2481 #endif
2482 return level_pos(new_lid, pos);
2483 }
2484 else
2485 {
2486 LevelInfo &li = travel_cache.get_level_info(lid);
2487 vector<stair_info> &stairs = li.get_stairs();
2488 for (const auto &stair : stairs)
2489 if (!stair.destination.id.is_valid())
2490 {
2491 pos = stair.position;
2492 break;
2493 }
2494 #ifdef DEBUG_TRAVEL
2495 dprf("found entrance in %d depth %d at %d,%d", lid.branch, lid.depth,
2496 pos.x, pos.y);
2497 #endif
2498 return level_pos(lid, pos);
2499 }
2500 }
2501
2502 /*
2503 * Given a string and a starting target, find a `level_pos` to travel to.
2504 *
2505 * @param s a string consisting of a number representing depth, or 0 to go to
2506 * the branch entrance.
2507 * @param targ an initial default `level_pos` to potentially modify.
2508 *
2509 * @return the resulting `level_pos`.
2510 */
_parse_travel_target(string s,const level_pos & targ)2511 static level_pos _parse_travel_target(string s, const level_pos &targ)
2512 {
2513 trim_string(s);
2514 level_pos result(targ);
2515
2516 if (!s.empty())
2517 {
2518 result.id.depth = atoi(s.c_str());
2519 result.pos.x = result.pos.y = -1;
2520 }
2521
2522 if (!result.id.depth)
2523 result = _find_entrance(result);
2524
2525 return result;
2526 }
2527
2528 /*
2529 * Interpret the player's input to the interlevel travel prompt.
2530 * This input consists either of a numeric string, or one of several special
2531 * characters that manipulate a destination that can be triggered by enter.
2532 * This function can process both at the same time, though simple numeric input
2533 * without a special key is handled separately in `_prompt_travel_depth`.
2534 *
2535 * @param munge_method a non-level special key input at the prompt to process.
2536 * @param s a numeric depth input at the prompt to process.
2537 * @param targ an input `level_pos` representing the current default
2538 * target.
2539 *
2540 * @return a `level_pos` indicating the resulting target, potentially the same
2541 * as `targ`.
2542 */
_travel_depth_munge(int munge_method,const string & s,const level_pos & targ)2543 static level_pos _travel_depth_munge(int munge_method, const string &s,
2544 const level_pos &targ)
2545 {
2546 level_pos result(targ.id); // drop any coords in `targ`.
2547 result = _parse_travel_target(s, result);
2548
2549 switch (munge_method)
2550 {
2551 case '?':
2552 show_interlevel_travel_depth_help();
2553 redraw_screen();
2554 update_screen();
2555 return level_pos(targ); // no change
2556 case '<':
2557 result.id = find_up_level(result.id);
2558 break;
2559 case '>':
2560 result.id = find_down_level(result.id);
2561 break;
2562 case '-':
2563 result.id = find_up_level(result.id, true);
2564 break;
2565 case '$':
2566 result.id = find_deepest_explored(result.id);
2567 break;
2568 case '^':
2569 result = _find_entrance(result);
2570 break;
2571 }
2572 if (result.id.depth < 1)
2573 result.id.depth = 1;
2574 return result;
2575 }
2576
_prompt_travel_depth(const level_id & id)2577 static level_pos _prompt_travel_depth(const level_id &id)
2578 {
2579 level_pos target = level_pos(id);
2580
2581 // Handle one-level branches by not prompting.
2582 if (single_level_branch(target.id.branch))
2583 return level_pos(level_id(target.id.branch, 1));
2584
2585 target.id.depth = _get_nearest_level_depth(target.id.branch);
2586 while (true)
2587 {
2588 clear_messages();
2589 mprf(MSGCH_PROMPT, "What level of %s? "
2590 "(default %s, ? - help) ",
2591 branches[target.id.branch].longname,
2592 _get_trans_travel_dest(target, true).c_str());
2593
2594 char buf[100];
2595 const int response =
2596 cancellable_get_line(buf, sizeof buf, nullptr,
2597 _travel_depth_keyfilter, "", "travel_depth");
2598
2599 if (!response)
2600 return _parse_travel_target(buf, target);
2601
2602 if (key_is_escape(response))
2603 return level_pos(level_id(BRANCH_DUNGEON, 0));
2604
2605 target = _travel_depth_munge(response, buf, target);
2606 }
2607 }
2608
prompt_translevel_target(int prompt_flags,string & dest_name)2609 level_pos prompt_translevel_target(int prompt_flags, string& dest_name)
2610 {
2611 level_pos target;
2612 int branch = _prompt_travel_branch(prompt_flags);
2613 const bool remember_targ = (prompt_flags & TPF_REMEMBER_TARGET);
2614
2615 if (branch == ID_CANCEL)
2616 return target;
2617
2618 if (branch == ID_ALTAR)
2619 return _prompt_travel_altar();
2620
2621 // If user chose to repeat last travel, return that.
2622 if (branch == ID_REPEAT)
2623 return level_target;
2624
2625 if (branch == ID_UP)
2626 {
2627 target = _find_up_level();
2628 if (target.id.depth > 0 && remember_targ)
2629 dest_name = _get_trans_travel_dest(target);
2630 return target;
2631 }
2632
2633 if (branch == ID_DOWN)
2634 {
2635 target = _find_down_level();
2636 if (target.id.depth > 0 && remember_targ)
2637 dest_name = _get_trans_travel_dest(target);
2638 return target;
2639 }
2640
2641 if (branch < 0)
2642 {
2643 target = travel_cache.get_waypoint(-branch - 1);
2644 if (target.id.depth > 0 && remember_targ)
2645 dest_name = _get_trans_travel_dest(target);
2646 return target;
2647 }
2648
2649 target.id.branch = static_cast<branch_type>(branch);
2650
2651 // User's chosen a branch, so now we ask for a level.
2652 target = _prompt_travel_depth(target.id);
2653
2654 if (target.id.depth < 1
2655 || target.id.depth > brdepth[target.id.branch])
2656 {
2657 target.id.depth = -1;
2658 }
2659
2660 if (target.id.depth > -1 && remember_targ)
2661 dest_name = _get_trans_travel_dest(target);
2662
2663 #ifdef DEBUG_TRAVEL
2664 dprf("level target is %d depth %d, pos %d,%d", target.id.branch,
2665 target.id.branch, target.pos.x, target.pos.y);
2666 #endif
2667
2668 return target;
2669 }
2670
_start_translevel_travel()2671 static void _start_translevel_travel()
2672 {
2673 // Update information for this level.
2674 travel_cache.get_level_info(level_id::current()).update();
2675
2676 if (level_id::current() == level_target.id)
2677 {
2678 if (level_target.pos.x == -1 &&
2679 level_target.id.depth == branches[level_target.id.branch].numlevels)
2680 {
2681 mpr("You're already at the bottom of this branch!");
2682 return;
2683 }
2684 else if (level_target.pos.x == -1 || level_target.pos == you.pos())
2685 {
2686 mpr("You're already here!");
2687 return;
2688 }
2689 }
2690
2691 #ifdef DEBUG_TRAVEL
2692 dprf("starting translevel travel, branch %d depth %d, pos %d,%d",
2693 level_target.id.branch, level_target.id.depth, level_target.pos.x,
2694 level_target.pos.y);
2695 #endif
2696
2697 if (level_target.id.depth > 0)
2698 {
2699 you.running = RMODE_INTERLEVEL;
2700 you.running.pos.reset();
2701 last_stair.id.depth = -1;
2702 last_stair.pos.reset();
2703
2704 _Route_Warning.new_dest(level_target);
2705
2706 _Src_Level = level_id::current();
2707 _Src_Dest_Level_Delta = level_distance(_Src_Level,
2708 level_target.id);
2709
2710 _start_running();
2711 }
2712 }
2713
start_translevel_travel(const level_pos & pos)2714 void start_translevel_travel(const level_pos &pos)
2715 {
2716 if (!can_travel_to(pos.id))
2717 {
2718 if (!can_travel_interlevel())
2719 mpr("Sorry, you can't auto-travel out of here.");
2720 else
2721 mpr("Sorry, I don't know how to get there.");
2722 return;
2723 }
2724
2725 if (pos.is_valid() && !in_bounds(pos.pos))
2726 {
2727 mpr("Sorry, I don't know how to get there.");
2728 return;
2729 }
2730
2731 // Remember where we're going so we can easily go back if interrupted.
2732 you.travel_x = pos.pos.x;
2733 you.travel_y = pos.pos.y;
2734 you.travel_z = pos.id;
2735
2736 #ifdef DEBUG_TRAVEL
2737 dprf("going to %d depth %d, pos %d,%d", pos.id.branch, pos.id.depth,
2738 pos.pos.x, pos.pos.y);
2739 #endif
2740
2741 if (!can_travel_interlevel())
2742 {
2743 start_travel(pos.pos);
2744 return;
2745 }
2746
2747 level_target = pos;
2748
2749 // Check that it's level + position, not just level.
2750 if (pos.is_valid())
2751 {
2752 if (pos.id != level_id::current())
2753 {
2754 if (!_loadlev_populate_stair_distances(pos))
2755 {
2756 mpr("Level memory is imperfect, aborting.");
2757 return ;
2758 }
2759 }
2760 else
2761 _populate_stair_distances(pos);
2762 }
2763
2764 trans_travel_dest = _get_trans_travel_dest(level_target);
2765
2766 if (!Options.travel_one_unsafe_move && !i_feel_safe(true, true))
2767 return;
2768 if (you.confused())
2769 {
2770 canned_msg(MSG_TOO_CONFUSED);
2771 return;
2772 }
2773
2774 _start_translevel_travel();
2775 }
2776
_start_translevel_travel_prompt()2777 static void _start_translevel_travel_prompt()
2778 {
2779 // Update information for this level. We need it even for the prompts, so
2780 // we can't wait to confirm that the user chose to initiate travel.
2781 travel_cache.get_level_info(level_id::current()).update();
2782
2783 level_pos target = prompt_translevel_target(TPF_DEFAULT_OPTIONS,
2784 trans_travel_dest);
2785 if (target.id.depth <= 0)
2786 {
2787 canned_msg(MSG_OK);
2788 return;
2789 }
2790
2791 start_translevel_travel(target);
2792 }
2793
_target_distance_from(const coord_def & pos)2794 static int _target_distance_from(const coord_def &pos)
2795 {
2796 for (const stair_info &stair : curr_stairs)
2797 if (stair.position == pos)
2798 return stair.distance;
2799
2800 return -1;
2801 }
2802
2803 /*
2804 * Sets best_stair to the coordinates of the best stair on the player's current
2805 * level to take to get to the 'target' level. Should be called with 'distance'
2806 * set to 0, 'stair' set to (you.x_pos, you.y_pos) and 'best_distance' set to
2807 * -1. 'cur' should be the player's current level.
2808 *
2809 * If best_stair remains unchanged when this function returns, there is no
2810 * travel-safe path between the player's current level and the target level OR
2811 * the player's current level *is* the target level.
2812 *
2813 * This function relies on the travel_point_distance array being correctly
2814 * populated with a floodout call to find_travel_pos starting from the player's
2815 * location.
2816 *
2817 * This function has undefined behaviour when the target position is not
2818 * traversable.
2819 */
_find_transtravel_stair(const level_id & cur,const level_pos & target,int distance,const coord_def & stair,level_id & closest_level,int & best_level_distance,coord_def & best_stair,int search_depth=0)2820 static int _find_transtravel_stair(const level_id &cur,
2821 const level_pos &target,
2822 int distance,
2823 // This is actually the current position
2824 // on cur, not necessarily a stair.
2825 const coord_def &stair,
2826 level_id &closest_level,
2827 int &best_level_distance,
2828 coord_def &best_stair,
2829 int search_depth = 0)
2830 {
2831 int local_distance = -1;
2832 level_id player_level = level_id::current();
2833
2834 LevelInfo &li = travel_cache.get_level_info(cur);
2835
2836 // Have we reached the target level?
2837 if (cur == target.id)
2838 {
2839 // Are we in an exclude? If so, bail out. Unless it is just a stair exclusion.
2840 if (is_excluded(stair, li.get_excludes()) && !is_stair_exclusion(stair))
2841 return -1;
2842
2843 // If there's no target position on the target level, or we're on the
2844 // target, we're home.
2845 if (target.pos.x == -1 || target.pos == stair)
2846 return distance;
2847
2848 // If there *is* a target position, we need to work out our distance
2849 // from it.
2850 int deltadist = _target_distance_from(stair);
2851
2852 if (deltadist == -1 && cur == player_level)
2853 {
2854 // Okay, we don't seem to have a distance available to us, which
2855 // means we're either (a) not standing on stairs or (b) whoever
2856 // initiated interlevel travel didn't call
2857 // _populate_stair_distances. Assuming we're not on stairs, that
2858 // situation can arise only if interlevel travel has been triggered
2859 // for a location on the same level. If that's the case, we can get
2860 // the distance off the travel_point_distance matrix.
2861 deltadist = travel_point_distance[target.pos.x][target.pos.y];
2862 if (!deltadist && stair != target.pos)
2863 deltadist = -1;
2864 }
2865
2866 if (deltadist != -1)
2867 {
2868 local_distance = distance + deltadist;
2869
2870 // See if this is a degenerate case of interlevel travel:
2871 // A degenerate case of interlevel travel decays to normal travel;
2872 // we identify this by checking if:
2873 // a. The current level is the target level.
2874 // b. The target square is reachable from the 'current' square.
2875 // c. The current square is where the player is.
2876 //
2877 // Note that even if this *is* degenerate, interlevel travel may
2878 // still be able to find a shorter route, since it can consider
2879 // routes that leave and reenter the current level.
2880 if (player_level == target.id && stair == you.pos())
2881 best_stair = target.pos;
2882
2883 // The local_distance is already set, but there may actually be
2884 // stairs we can take that'll get us to the target faster than the
2885 // direct route, so we also try the stairs.
2886 }
2887 }
2888
2889 vector<stair_info> &stairs = li.get_stairs();
2890
2891 // this_stair being nullptr is perfectly acceptable, since we start with
2892 // coords as the player coords, and the player need not be standing on
2893 // stairs.
2894 stair_info *this_stair = li.get_stair(stair);
2895
2896 if (!this_stair && cur != player_level)
2897 {
2898 // Whoops, there's no stair in the travel cache for the current
2899 // position, and we're not on the player's current level (i.e., there
2900 // certainly *should* be a stair here). Since we can't proceed in any
2901 // reasonable way, bail out.
2902 return local_distance;
2903 }
2904
2905 for (stair_info &si : stairs)
2906 {
2907 if (stairs_destination_is_excluded(si))
2908 continue;
2909
2910 // Skip placeholders and excluded stairs.
2911 if (!si.can_travel() || is_excluded(si.position, li.get_excludes()))
2912 continue;
2913
2914 int deltadist = li.distance_between(this_stair, &si);
2915
2916 if (!this_stair)
2917 {
2918 deltadist = travel_point_distance[si.position.x][si.position.y];
2919 if (!deltadist && you.pos() != si.position)
2920 deltadist = -1;
2921 }
2922 // deltadist == 0 is legal (if this_stair is nullptr), since the player
2923 // may be standing on the stairs. If two stairs are disconnected,
2924 // deltadist has to be negative.
2925 if (deltadist < 0)
2926 continue;
2927
2928 int dist2stair = distance + deltadist;
2929 if (si.distance == -1 || si.distance > dist2stair)
2930 {
2931 si.distance = dist2stair;
2932
2933 // Account for the cost of taking the stairs
2934 dist2stair += 500; // XXX: this seems large?
2935
2936 // Already too expensive? Short-circuit.
2937 if (local_distance != -1 && dist2stair >= local_distance)
2938 continue;
2939
2940 const level_pos &dest = si.destination;
2941
2942 // Never use escape hatches as the last leg of the trip, since
2943 // that will leave the player unable to retrace their path.
2944 // This does not apply if we have a destination with a specific
2945 // position on the target level travel wants to get to.
2946 if (feat_is_escape_hatch(si.grid)
2947 && target.pos.x == -1
2948 && dest.id == target.id)
2949 {
2950 continue;
2951 }
2952
2953 // We can only short-circuit the stair-following process if we
2954 // have no exact target location. If there *is* an exact target
2955 // location, we can't follow stairs for which we have incomplete
2956 // information.
2957 if (target.pos.x == -1
2958 && dest.id == target.id)
2959 {
2960 if (local_distance == -1 || local_distance > dist2stair)
2961 {
2962 local_distance = dist2stair;
2963 if (cur == player_level && you.pos() == stair)
2964 best_stair = si.position;
2965 }
2966 continue;
2967 }
2968
2969 if (dest.id.depth > -1) // We have a valid level descriptor.
2970 {
2971 int dist = level_distance(dest.id, target.id);
2972 if (dist != -1 && (dist < best_level_distance
2973 || best_level_distance == -1))
2974 {
2975 best_level_distance = dist;
2976 closest_level = dest.id;
2977 }
2978 }
2979
2980 // If we don't know where these stairs go, we can't take them.
2981 if (!dest.is_valid())
2982 continue;
2983
2984 // Don't try hell branches if we are not already in one or targeting
2985 // one. When you actually enter the vestibule, the branch entry
2986 // point is adjusted to be the portal you entered through, but
2987 // autotravel needs to simulate this somehow, or it can find (fake)
2988 // paths through hell that are shortcuts in depths, because the
2989 // vestibule side of the portals do map to particular portals
2990 // scattered throughout depths, even if those mappings won't be
2991 // used while exiting from the vestibule.
2992 if (is_hell_branch(dest.id.branch)
2993 && !(is_hell_branch(target.id.branch)
2994 || is_hell_branch(cur.branch)))
2995 {
2996 continue;
2997 }
2998
2999 // We need to get the stairs at the new location and set the
3000 // distance on them as well.
3001 LevelInfo &lo = travel_cache.get_level_info(dest.id);
3002 if (stair_info *so = lo.get_stair(dest.pos))
3003 {
3004 if (so->distance == -1 || so->distance > dist2stair)
3005 so->distance = dist2stair;
3006 else
3007 continue; // We've already been here.
3008 }
3009 #ifdef DEBUG_TRAVEL
3010 string indent(search_depth, '.');
3011 dprf("%strying stairs at %d,%d, dest is %d depth %d, pos %d,%d",
3012 indent.c_str(), si.position.x, si.position.y, dest.id.branch,
3013 dest.id.depth, dest.pos.x, dest.pos.y);
3014 #endif
3015
3016 // Okay, take these stairs and keep going.
3017 const int newdist =
3018 _find_transtravel_stair(dest.id, target,
3019 dist2stair, dest.pos, closest_level,
3020 best_level_distance, best_stair,
3021 search_depth + 1);
3022 if (newdist != -1
3023 && (local_distance == -1 || local_distance > newdist))
3024 {
3025 local_distance = newdist;
3026 if (cur == player_level && you.pos() == stair)
3027 best_stair = si.position;
3028 }
3029 }
3030 }
3031 return local_distance;
3032 }
3033
_loadlev_populate_stair_distances(const level_pos & target)3034 static bool _loadlev_populate_stair_distances(const level_pos &target)
3035 {
3036 level_excursion excursion;
3037 excursion.go_to(target.id);
3038 _populate_stair_distances(target);
3039 return true;
3040 }
3041
_populate_stair_distances(const level_pos & target)3042 static void _populate_stair_distances(const level_pos &target)
3043 {
3044 // Populate travel_point_distance.
3045 fill_travel_point_distance(target.pos);
3046
3047 curr_stairs.clear();
3048 for (stair_info si : travel_cache.get_level_info(target.id).get_stairs())
3049 {
3050 si.distance = travel_point_distance[si.position.x][si.position.y];
3051 if (!si.distance && target.pos != si.position
3052 || si.distance < -1)
3053 {
3054 si.distance = -1;
3055 }
3056
3057 curr_stairs.push_back(si);
3058 }
3059 }
3060
_find_transtravel_square(const level_pos & target,bool verbose)3061 static bool _find_transtravel_square(const level_pos &target, bool verbose)
3062 {
3063 level_id current = level_id::current();
3064
3065 coord_def best_stair(-1, -1);
3066 coord_def cur_stair(you.pos());
3067
3068 level_id closest_level;
3069 int best_level_distance = -1;
3070 travel_cache.clear_distances();
3071
3072 fill_travel_point_distance(you.pos());
3073
3074 // either off-level, or traversable and on-level
3075 // TODO: actually check this when the square is off-level? The current
3076 // behaviour is that it will go to the level and then fail.
3077 const bool maybe_traversable = (target.id != current
3078 || (in_bounds(target.pos)
3079 && feat_is_traversable_now(env.map_knowledge(target.pos).feat())));
3080
3081 if (maybe_traversable)
3082 {
3083 _find_transtravel_stair(current, target,
3084 0, cur_stair, closest_level,
3085 best_level_distance, best_stair);
3086 dprf("found stair at %d,%d", best_stair.x, best_stair.y);
3087 }
3088 // even without _find_transtravel_stair called, the values are initialized
3089 // enough for the rest of this to go forward.
3090
3091 if (best_stair.x != -1 && best_stair.y != -1)
3092 {
3093 // Is this stair going offlevel?
3094 if ((level_target.id != current
3095 || level_target.pos != best_stair)
3096 && _Src_Dest_Level_Delta != -1)
3097 {
3098 // If so, is the original level closer to the target level than
3099 // the destination of the stair?
3100 LevelInfo &li = travel_cache.get_level_info(current);
3101 const stair_info *dest_stair = li.get_stair(best_stair);
3102
3103 if (dest_stair && dest_stair->destination.id.is_valid())
3104 {
3105 if ((_Src_Dest_Level_Delta <
3106 level_distance(dest_stair->destination.id,
3107 level_target.id)
3108 || _Src_Dest_Level_Delta <
3109 level_distance(dest_stair->destination.id,
3110 _Src_Level))
3111 && !_Route_Warning.warn_continue_travel(
3112 level_target,
3113 dest_stair->destination.id))
3114 {
3115 canned_msg(MSG_OK);
3116 return false;
3117 }
3118 }
3119 }
3120
3121 you.running.pos = best_stair;
3122 return true;
3123 }
3124 else if (best_level_distance != -1 && closest_level != current
3125 && target.pos.x == -1)
3126 {
3127 int current_dist = level_distance(current, target.id);
3128 level_pos newlev;
3129 newlev.id = closest_level;
3130 if (newlev.id != target.id
3131 && (current_dist == -1 || best_level_distance < current_dist))
3132 {
3133 return _find_transtravel_square(newlev, verbose);
3134 }
3135 }
3136
3137 if (verbose)
3138 {
3139 if (target.id != current
3140 || target.pos.x != -1 && target.pos != you.pos())
3141 {
3142 if (!maybe_traversable)
3143 mpr("Sorry, I don't know how to traverse that place.");
3144 else
3145 mpr("Sorry, I don't know how to get there.");
3146 }
3147 }
3148
3149 return false;
3150 }
3151
start_travel(const coord_def & p)3152 void start_travel(const coord_def& p)
3153 {
3154 // Redundant target?
3155 if (p == you.pos())
3156 return;
3157
3158 // Can we even travel to this square?
3159 if (!in_bounds(p))
3160 return;
3161
3162 if (!_is_travelsafe_square(p, true))
3163 return;
3164
3165 you.travel_x = p.x;
3166 you.travel_y = p.y;
3167 you.travel_z = level_id::current();
3168
3169 you.running.pos = p;
3170 level_target = level_pos(level_id::current(), p);
3171
3172 if (!can_travel_interlevel())
3173 {
3174 if (!Options.travel_one_unsafe_move && !i_feel_safe(true, true))
3175 return;
3176 if (you.confused())
3177 {
3178 canned_msg(MSG_TOO_CONFUSED);
3179 return;
3180 }
3181
3182 // Start running
3183 you.running = RMODE_TRAVEL;
3184 _start_running();
3185 }
3186 else
3187 start_translevel_travel(level_target);
3188 }
3189
start_explore(bool grab_items)3190 void start_explore(bool grab_items)
3191 {
3192 if (Hints.hints_explored)
3193 Hints.hints_explored = false;
3194
3195 if (!i_feel_safe(true, true))
3196 return;
3197
3198 you.running = (grab_items ? RMODE_EXPLORE_GREEDY : RMODE_EXPLORE);
3199
3200 for (rectangle_iterator ri(0); ri; ++ri)
3201 if (env.map_knowledge(*ri).seen())
3202 env.map_seen.set(*ri);
3203
3204 you.running.pos.reset();
3205 _start_running();
3206 }
3207
do_explore_cmd()3208 void do_explore_cmd()
3209 {
3210 if (you.berserk())
3211 mpr("Calm down first, please.");
3212 else // Start exploring
3213 start_explore(Options.explore_greedy);
3214 }
3215
3216 //////////////////////////////////////////////////////////////////////////
3217 // Interlevel travel classes
3218
current()3219 level_id level_id::current()
3220 {
3221 const level_id id(you.where_are_you, you.depth);
3222 return id;
3223 }
3224
absdepth() const3225 int level_id::absdepth() const
3226 {
3227 return absdungeon_depth(branch, depth);
3228 }
3229
get_next_level_id(const coord_def & pos)3230 level_id level_id::get_next_level_id(const coord_def &pos)
3231 {
3232 int gridc = env.grid(pos);
3233 level_id id = current();
3234
3235 if (gridc == branches[id.branch].exit_stairs)
3236 return stair_destination(pos);
3237 #if TAG_MAJOR_VERSION == 34
3238 if (gridc == DNGN_ENTER_PORTAL_VAULT)
3239 return stair_destination(pos);
3240 #endif
3241 if (gridc == DNGN_EXIT_THROUGH_ABYSS)
3242 return level_id(BRANCH_ABYSS, 1);
3243
3244 for (branch_iterator it; it; ++it)
3245 {
3246 if (gridc == it->entry_stairs)
3247 {
3248 id.branch = it->id;
3249 id.depth = 1;
3250 break;
3251 }
3252 }
3253
3254 switch (gridc)
3255 {
3256 case DNGN_STONE_STAIRS_DOWN_I: case DNGN_STONE_STAIRS_DOWN_II:
3257 case DNGN_STONE_STAIRS_DOWN_III: case DNGN_ESCAPE_HATCH_DOWN:
3258 case DNGN_ABYSSAL_STAIR:
3259 id.depth++;
3260 break;
3261 case DNGN_STONE_STAIRS_UP_I: case DNGN_STONE_STAIRS_UP_II:
3262 case DNGN_STONE_STAIRS_UP_III: case DNGN_ESCAPE_HATCH_UP:
3263 id.depth--;
3264 break;
3265 default:
3266 break;
3267 }
3268 return id;
3269 }
3270
describe(bool long_name,bool with_number) const3271 string level_id::describe(bool long_name, bool with_number) const
3272 {
3273 string result = (long_name ? branches[branch].longname
3274 : branches[branch].abbrevname);
3275
3276 if (with_number && brdepth[branch] != 1)
3277 {
3278 if (long_name)
3279 {
3280 // decapitalise 'the'
3281 if (starts_with(result, "The"))
3282 result[0] = 't';
3283 result = make_stringf("Level %d of %s",
3284 depth, result.c_str());
3285 }
3286 else if (depth)
3287 result = make_stringf("%s:%d", result.c_str(), depth);
3288 else
3289 result = make_stringf("%s:$", result.c_str());
3290 }
3291 return result;
3292 }
3293
parse_level_id(const string & s)3294 level_id level_id::parse_level_id(const string &s)
3295 {
3296 string::size_type cpos = s.find(':');
3297 string brname = (cpos != string::npos? s.substr(0, cpos) : s);
3298 string brlev = (cpos != string::npos? s.substr(cpos + 1) : "");
3299
3300 branch_type br = branch_by_abbrevname(brname);
3301
3302 if (br == NUM_BRANCHES)
3303 {
3304 throw bad_level_id_f("Invalid branch \"%s\" in spec \"%s\"",
3305 brname.c_str(), s.c_str());
3306 }
3307
3308 // Branch:$ uses static data -- it never comes from the current game.
3309 const int dep = (brlev.empty() ? 1 :
3310 brlev == "$" ? branches[br].numlevels
3311 : atoi(brlev.c_str()));
3312
3313 // The branch might have been longer when the save has been created.
3314 if (dep < 0 || dep > brdepth[br] && dep > branches[br].numlevels)
3315 {
3316 throw bad_level_id_f("Invalid depth for %s in spec \"%s\"",
3317 brname.c_str(), s.c_str());
3318 }
3319
3320 return level_id(br, dep);
3321 }
3322
save(writer & outf) const3323 void level_id::save(writer& outf) const
3324 {
3325 marshall_level_id(outf, *this);
3326 }
3327
load(reader & inf)3328 void level_id::load(reader& inf)
3329 {
3330 (*this) = unmarshall_level_id(inf);
3331 }
3332
current()3333 level_pos level_pos::current()
3334 {
3335 return level_pos(level_id::current(), you.pos());
3336 }
3337
3338 // NOTE: see also marshall_level_pos
save(writer & outf) const3339 void level_pos::save(writer& outf) const
3340 {
3341 id.save(outf);
3342 marshallCoord(outf, pos);
3343 }
3344
load(reader & inf)3345 void level_pos::load(reader& inf)
3346 {
3347 id.load(inf);
3348 pos = unmarshallCoord(inf);
3349 }
3350
save(writer & outf) const3351 void transporter_info::save(writer& outf) const
3352 {
3353 marshallCoord(outf, position);
3354 marshallCoord(outf, destination);
3355 marshallByte(outf, type);
3356 }
3357
save(writer & outf) const3358 void stair_info::save(writer& outf) const
3359 {
3360 marshallCoord(outf, position);
3361 marshallShort(outf, grid);
3362 destination.save(outf);
3363 marshallByte(outf, guessed_pos? 1 : 0);
3364 marshallByte(outf, type);
3365 }
3366
load(reader & inf)3367 void transporter_info::load(reader& inf)
3368 {
3369 position = unmarshallCoord(inf);
3370 destination = unmarshallCoord(inf);
3371 type = static_cast<transporter_type>(unmarshallByte(inf));
3372 }
3373
load(reader & inf)3374 void stair_info::load(reader& inf)
3375 {
3376 position = unmarshallCoord(inf);
3377 grid = static_cast<dungeon_feature_type>(unmarshallShort(inf));
3378 destination.load(inf);
3379 guessed_pos = unmarshallByte(inf) != 0;
3380 type = static_cast<stair_type>(unmarshallByte(inf));
3381 }
3382
describe() const3383 string stair_info::describe() const
3384 {
3385 if (destination.is_valid())
3386 {
3387 const level_pos &lp(destination);
3388 return make_stringf(" (-> %s@(%d,%d)%s%s)", lp.id.describe().c_str(),
3389 lp.pos.x, lp.pos.y,
3390 guessed_pos? " guess" : "",
3391 type == PLACEHOLDER ? " placeholder" : "");
3392 }
3393 else if (destination.id.is_valid())
3394 return make_stringf(" (->%s (?))", destination.id.describe().c_str());
3395
3396 return " (?)";
3397 }
3398
set_level_excludes()3399 void LevelInfo::set_level_excludes()
3400 {
3401 curr_excludes = excludes;
3402 init_exclusion_los();
3403 }
3404
empty() const3405 bool LevelInfo::empty() const
3406 {
3407 return stairs.empty() && excludes.empty();
3408 }
3409
update_excludes()3410 void LevelInfo::update_excludes()
3411 {
3412 excludes = curr_excludes;
3413 }
3414
update()3415 void LevelInfo::update()
3416 {
3417 // First, set excludes, so that stair distances will be correctly populated.
3418 excludes = curr_excludes;
3419
3420 // First, we get all known stairs.
3421 vector<coord_def> stair_positions;
3422 get_stairs(stair_positions);
3423
3424 // Make sure our stair list is correct.
3425 correct_stair_list(stair_positions);
3426
3427 sync_all_branch_stairs();
3428
3429 // If the player isn't immune to slimy walls, precalculate
3430 // neighbours of slimy walls now.
3431 unwind_slime_wall_precomputer slime_wall_neighbours(
3432 !actor_slime_wall_immune(&you));
3433 precompute_travel_safety_grid travel_safety_calc;
3434 update_stair_distances();
3435
3436 vector<coord_def> transporter_positions;
3437 get_transporters(transporter_positions);
3438 correct_transporter_list(transporter_positions);
3439
3440 update_daction_counters(this);
3441 }
3442
set_distance_between_stairs(int a,int b,int dist)3443 void LevelInfo::set_distance_between_stairs(int a, int b, int dist)
3444 {
3445 // Note dist == 0 is illegal because we can't have two stairs on
3446 // the same square.
3447 if (dist <= 0 && a != b)
3448 dist = -1;
3449 stair_distances[a * stairs.size() + b] = dist;
3450 stair_distances[b * stairs.size() + a] = dist;
3451 }
3452
update_stair_distances()3453 void LevelInfo::update_stair_distances()
3454 {
3455 const int nstairs = stairs.size();
3456 // Now we update distances for all the stairs, relative to all other
3457 // stairs.
3458 for (int s = 0; s < nstairs - 1; ++s)
3459 {
3460 set_distance_between_stairs(s, s, 0);
3461
3462 // For each stair, we need to ask travel to populate the distance
3463 // array.
3464 fill_travel_point_distance(stairs[s].position);
3465
3466 // Assume movement distance between stairs is commutative,
3467 // i.e. going from a->b is the same distance as b->a.
3468 for (int other = s + 1; other < nstairs; ++other)
3469 {
3470 const coord_def op = stairs[other].position;
3471 const int dist = travel_point_distance[op.x][op.y];
3472 set_distance_between_stairs(s, other, dist);
3473 }
3474 }
3475 if (nstairs)
3476 set_distance_between_stairs(nstairs - 1, nstairs - 1, 0);
3477 }
3478
update_transporter(const coord_def & transpos,const coord_def & dest)3479 void LevelInfo::update_transporter(const coord_def& transpos,
3480 const coord_def& dest)
3481 {
3482 transporter_info *si = get_transporter(transpos);
3483 if (si)
3484 si->destination = dest;
3485 else
3486 transporters.push_back(transporter_info(transpos, dest,
3487 transporter_info::PHYSICAL));
3488 }
3489
update_stair(const coord_def & stairpos,const level_pos & p,bool guess)3490 void LevelInfo::update_stair(const coord_def& stairpos, const level_pos &p,
3491 bool guess)
3492 {
3493 stair_info *si = get_stair(stairpos);
3494
3495 // What 'guess' signifies: whenever you take a stair from A to B, the
3496 // travel code knows that the stair takes you from A->B. In that case,
3497 // update_stair() is called with guess == false.
3498 //
3499 // Unfortunately, Crawl doesn't guarantee that A->B implies B->A, but the
3500 // travel code has to assume that anyway (because that's what the player
3501 // will expect), and call update_stair() again with guess == true.
3502 //
3503 // The idea of using 'guess' is that we'll update the stair's destination
3504 // with a guess only if we know that the currently set destination is
3505 // itself a guess.
3506 //
3507 if (si && (si->guessed_pos || !guess))
3508 {
3509 si->destination = p;
3510 si->guessed_pos = guess;
3511
3512 if (!guess && p.id.branch == BRANCH_VESTIBULE
3513 && id.branch == BRANCH_DEPTHS)
3514 {
3515 travel_hell_entry = p;
3516 }
3517
3518 // All branch stairs land on the same place on the destination level,
3519 // update the cache accordingly (but leave guessed_pos = true). This
3520 // applies for both branch exits (the usual case) and branch entrances.
3521 if (si->destination.id.branch != id.branch)
3522 sync_branch_stairs(si);
3523 }
3524 else if (!si && guess)
3525 create_placeholder_stair(stairpos, p);
3526 }
3527
create_placeholder_stair(const coord_def & stair,const level_pos & dest)3528 void LevelInfo::create_placeholder_stair(const coord_def &stair,
3529 const level_pos &dest)
3530 {
3531 // If there are any existing placeholders with the same 'dest', zap them.
3532 erase_if(stairs, [&dest](const stair_info& old_stair)
3533 { return old_stair.type == stair_info::PLACEHOLDER
3534 && old_stair.destination == dest; });
3535
3536 stair_info placeholder;
3537 placeholder.position = stair;
3538 placeholder.grid = DNGN_FLOOR;
3539 placeholder.destination = dest;
3540 placeholder.type = stair_info::PLACEHOLDER;
3541 stairs.push_back(placeholder);
3542
3543 resize_stair_distances();
3544 }
3545
3546 // If a stair leading out of or into a branch has a known destination, all
3547 // stairs of the same type on this level should have the same destination set
3548 // as guessed_pos == true.
sync_all_branch_stairs()3549 void LevelInfo::sync_all_branch_stairs()
3550 {
3551 set<int> synced;
3552
3553 for (const stair_info& si : stairs)
3554 {
3555 if (si.destination.id.branch != id.branch && si.destination.is_valid()
3556 && !synced.count(si.grid))
3557 {
3558 synced.insert(si.grid);
3559 sync_branch_stairs(&si);
3560 }
3561 }
3562 }
3563
sync_branch_stairs(const stair_info * si)3564 void LevelInfo::sync_branch_stairs(const stair_info *si)
3565 {
3566 for (stair_info &sother : stairs)
3567 {
3568 if (si == &sother || !sother.guessed_pos || si->grid != sother.grid
3569 || sother.destination.is_valid())
3570 {
3571 continue;
3572 }
3573 sother.destination = si->destination;
3574 }
3575 }
3576
clear_stairs(dungeon_feature_type grid)3577 void LevelInfo::clear_stairs(dungeon_feature_type grid)
3578 {
3579 for (stair_info &si : stairs)
3580 {
3581 if (si.grid != grid)
3582 continue;
3583
3584 si.destination.id.depth = -1;
3585 si.destination.pos.x = -1;
3586 si.destination.pos.y = -1;
3587 si.guessed_pos = true;
3588 }
3589 }
3590
know_transporter(const coord_def & c) const3591 bool LevelInfo::know_transporter(const coord_def &c) const
3592 {
3593 const int index = get_transporter_index(c);
3594 if (index == -1)
3595 return false;
3596
3597 return !transporters[index].destination.origin();
3598 }
3599
know_stair(const coord_def & c) const3600 bool LevelInfo::know_stair(const coord_def &c) const
3601 {
3602 const int index = get_stair_index(c);
3603 if (index == -1)
3604 return false;
3605
3606 const level_pos &lp = stairs[index].destination;
3607 return lp.is_valid();
3608 }
3609
get_transporter(const coord_def & pos)3610 transporter_info *LevelInfo::get_transporter(const coord_def &pos)
3611 {
3612 int index = get_transporter_index(pos);
3613 return index != -1 ? &transporters[index] : nullptr;
3614 }
3615
get_stair(const coord_def & pos)3616 stair_info *LevelInfo::get_stair(const coord_def &pos)
3617 {
3618 int index = get_stair_index(pos);
3619 return index != -1? &stairs[index] : nullptr;
3620 }
3621
get_transporter_index(const coord_def & pos) const3622 int LevelInfo::get_transporter_index(const coord_def &pos) const
3623 {
3624 for (int i = static_cast<int>(transporters.size()) - 1; i >= 0; --i)
3625 if (transporters[i].position == pos)
3626 return i;
3627
3628 return -1;
3629 }
3630
get_stair_index(const coord_def & pos) const3631 int LevelInfo::get_stair_index(const coord_def &pos) const
3632 {
3633 for (int i = static_cast<int>(stairs.size()) - 1; i >= 0; --i)
3634 if (stairs[i].position == pos)
3635 return i;
3636
3637 return -1;
3638 }
3639
correct_stair_list(const vector<coord_def> & s)3640 void LevelInfo::correct_stair_list(const vector<coord_def> &s)
3641 {
3642 stair_distances.clear();
3643
3644 // Fix up the grid for the placeholder stair.
3645 for (stair_info &stair : stairs)
3646 stair.grid = env.grid(stair.position);
3647
3648 // First we kill any stairs in 'stairs' that aren't there in 's'.
3649 for (int i = ((int) stairs.size()) - 1; i >= 0; --i)
3650 {
3651 if (stairs[i].type == stair_info::PLACEHOLDER)
3652 continue;
3653
3654 bool found = false;
3655 for (int j = s.size() - 1; j >= 0; --j)
3656 {
3657 if (s[j] == stairs[i].position)
3658 {
3659 found = true;
3660 break;
3661 }
3662 }
3663
3664 if (!found)
3665 stairs.erase(stairs.begin() + i);
3666 }
3667
3668 // For each stair in 's', make sure we have a corresponding stair
3669 // in 'stairs'.
3670 for (coord_def pos : s)
3671 {
3672 int found = -1;
3673 for (int j = stairs.size() - 1; j >= 0; --j)
3674 {
3675 if (pos == stairs[j].position)
3676 {
3677 found = j;
3678 break;
3679 }
3680 }
3681
3682 if (found == -1)
3683 {
3684 stair_info si;
3685 si.position = pos;
3686 si.grid = env.grid(si.position);
3687 si.destination.id = level_id::get_next_level_id(pos);
3688 if (si.destination.id.branch == BRANCH_VESTIBULE
3689 && id.branch == BRANCH_DEPTHS
3690 && travel_hell_entry.is_valid())
3691 {
3692 si.destination = travel_hell_entry;
3693 }
3694 if (!env.map_knowledge(pos).seen())
3695 si.type = stair_info::MAPPED;
3696
3697 // We don't know where on the next level these stairs go to, but
3698 // that can't be helped. That information will have to be filled
3699 // in whenever the player takes these stairs.
3700 stairs.push_back(si);
3701 }
3702 else
3703 stairs[found].type = env.map_knowledge(pos).seen() ? stair_info::PHYSICAL : stair_info::MAPPED;
3704 }
3705
3706 resize_stair_distances();
3707 }
3708
correct_transporter_list(const vector<coord_def> & t)3709 void LevelInfo::correct_transporter_list(const vector<coord_def> &t)
3710 {
3711 // First we kill any transporters in 'transporters' that aren't there in 't'.
3712 for (int i = ((int) transporters.size()) - 1; i >= 0; --i)
3713 {
3714 bool found = false;
3715 for (int j = t.size() - 1; j >= 0; --j)
3716 {
3717 if (t[j] == transporters[i].position)
3718 {
3719 found = true;
3720 break;
3721 }
3722 }
3723
3724 if (!found)
3725 transporters.erase(transporters.begin() + i);
3726 }
3727
3728 // For each transporter in 't', make sure we have a corresponding stair
3729 // in 'transporters'.
3730 for (coord_def pos : t)
3731 {
3732 int found = -1;
3733 for (int j = transporters.size() - 1; j >= 0; --j)
3734 {
3735 if (pos == transporters[j].position)
3736 {
3737 found = j;
3738 break;
3739 }
3740 }
3741
3742 transporter_info::transporter_type type =
3743 env.map_knowledge(pos).seen() ? transporter_info::PHYSICAL
3744 : transporter_info::MAPPED;
3745 if (found == -1)
3746 transporters.push_back(transporter_info(pos, coord_def(), type));
3747 else
3748 transporters[found].type = type;
3749 }
3750 }
3751
resize_stair_distances()3752 void LevelInfo::resize_stair_distances()
3753 {
3754 const int nstairs = stairs.size();
3755 stair_distances.reserve(nstairs * nstairs);
3756 stair_distances.resize(nstairs * nstairs, 0);
3757 }
3758
distance_between(const stair_info * s1,const stair_info * s2) const3759 int LevelInfo::distance_between(const stair_info *s1, const stair_info *s2)
3760 const
3761 {
3762 if (!s1 || !s2)
3763 return 0;
3764 if (s1 == s2)
3765 return 0;
3766
3767 int i1 = get_stair_index(s1->position),
3768 i2 = get_stair_index(s2->position);
3769 if (i1 == -1 || i2 == -1)
3770 return 0;
3771
3772 return stair_distances[ i1 * stairs.size() + i2 ];
3773 }
3774
get_transporters(vector<coord_def> & tr)3775 void LevelInfo::get_transporters(vector<coord_def> &tr)
3776 {
3777 for (rectangle_iterator ri(1); ri; ++ri)
3778 {
3779 const dungeon_feature_type feat = env.grid(*ri);
3780
3781 if (feat == DNGN_TRANSPORTER
3782 && (*ri == you.pos() || env.map_knowledge(*ri).known())
3783 && env.map_knowledge(*ri).seen())
3784 {
3785 tr.push_back(*ri);
3786 }
3787 }
3788 }
3789
get_stairs(vector<coord_def> & st)3790 void LevelInfo::get_stairs(vector<coord_def> &st)
3791 {
3792 for (rectangle_iterator ri(1); ri; ++ri)
3793 {
3794 const dungeon_feature_type feat = env.grid(*ri);
3795
3796 if ((*ri == you.pos() || env.map_knowledge(*ri).known())
3797 && feat_is_travelable_stair(feat)
3798 && (env.map_knowledge(*ri).seen() || !_is_branch_stair(*ri)))
3799 {
3800 st.push_back(*ri);
3801 }
3802 }
3803 }
3804
clear_distances()3805 void LevelInfo::clear_distances()
3806 {
3807 for (stair_info &stair : stairs)
3808 stair.clear_distance();
3809 }
3810
is_known_branch(uint8_t branch) const3811 bool LevelInfo::is_known_branch(uint8_t branch) const
3812 {
3813 for (const stair_info &stair : stairs)
3814 if (stair.destination.id.branch == branch)
3815 return true;
3816
3817 return false;
3818 }
3819
save(writer & outf) const3820 void LevelInfo::save(writer& outf) const
3821 {
3822 int stair_count = stairs.size();
3823 // How many stairs do we know of?
3824 marshallShort(outf, stair_count);
3825 for (int i = 0; i < stair_count; ++i)
3826 stairs[i].save(outf);
3827
3828 if (stair_count)
3829 {
3830 // Save stair distances as short ints.
3831 const int sz = stair_distances.size();
3832 for (int i = 0, n = stair_count * stair_count; i < n; ++i)
3833 {
3834 if (i >= sz)
3835 marshallShort(outf, -1);
3836 else
3837 marshallShort(outf, stair_distances[i]);
3838 }
3839 }
3840
3841 int transporter_count = transporters.size();
3842 marshallShort(outf, transporter_count);
3843 for (int i = 0; i < transporter_count; ++i)
3844 transporters[i].save(outf);
3845
3846 marshallExcludes(outf, excludes);
3847
3848 marshallByte(outf, NUM_DACTION_COUNTERS);
3849 for (int i = 0; i < NUM_DACTION_COUNTERS; i++)
3850 marshallShort(outf, daction_counters[i]);
3851 }
3852
load(reader & inf,int minorVersion)3853 void LevelInfo::load(reader& inf, int minorVersion)
3854 {
3855 stairs.clear();
3856 int stair_count = unmarshallShort(inf);
3857 for (int i = 0; i < stair_count; ++i)
3858 {
3859 stair_info si;
3860 si.load(inf);
3861 stairs.push_back(si);
3862
3863 if (id.branch == BRANCH_DUNGEON
3864 && si.destination.id.branch == BRANCH_VESTIBULE
3865 && !travel_hell_entry.is_valid()
3866 && si.destination.is_valid())
3867 {
3868 travel_hell_entry = si.destination;
3869 }
3870 }
3871
3872 stair_distances.clear();
3873 if (stair_count)
3874 {
3875 stair_distances.reserve(stair_count * stair_count);
3876 for (int i = stair_count * stair_count - 1; i >= 0; --i)
3877 stair_distances.push_back(unmarshallShort(inf));
3878 }
3879
3880 transporters.clear();
3881 #if TAG_MAJOR_VERSION == 34
3882 if (minorVersion >= TAG_MINOR_TRANSPORTERS)
3883 {
3884 #endif
3885 int transporter_count = unmarshallShort(inf);
3886 for (int i = 0; i < transporter_count; ++i)
3887 {
3888 transporter_info ti;
3889 ti.load(inf);
3890 transporters.push_back(ti);
3891 }
3892 #if TAG_MAJOR_VERSION == 34
3893 }
3894 #endif
3895
3896 unmarshallExcludes(inf, minorVersion, excludes);
3897
3898 int n_count = unmarshallByte(inf);
3899 ASSERT_RANGE(n_count, 0, NUM_DACTION_COUNTERS + 1);
3900 for (int i = 0; i < n_count; i++)
3901 daction_counters[i] = unmarshallShort(inf);
3902 }
3903
fixup()3904 void LevelInfo::fixup()
3905 {
3906 // The only fixup we do now is for the hell entry.
3907 if (id.branch != BRANCH_DEPTHS || !travel_hell_entry.is_valid())
3908 return;
3909
3910 for (stair_info &si : stairs)
3911 {
3912 if (si.destination.id.branch == BRANCH_VESTIBULE
3913 && !si.destination.is_valid())
3914 {
3915 si.destination = travel_hell_entry;
3916 }
3917 }
3918 }
3919
update_stone_stair(const coord_def & c)3920 void TravelCache::update_stone_stair(const coord_def &c)
3921 {
3922 if (!env.map_knowledge(c).seen())
3923 return;
3924 LevelInfo *li = find_level_info(level_id::current());
3925 if (!li)
3926 return;
3927 stair_info *si = li->get_stair(c);
3928 // Don't bother proceeding further if we already know where the stair goes.
3929 if (si && si->destination.is_valid())
3930 return;
3931 const dungeon_feature_type feat1 = env.grid(c);
3932 ASSERT(feat_is_stone_stair(feat1));
3933 // Compute the corresponding feature type on the other side of the stairs.
3934 const dungeon_feature_type feat2 = (dungeon_feature_type)
3935 (feat1 + (feat_is_stone_stair_up(feat1) ? 1 : -1)
3936 * (DNGN_STONE_STAIRS_DOWN_I - DNGN_STONE_STAIRS_UP_I));
3937 LevelInfo *li2 = find_level_info(level_id::get_next_level_id(c));
3938 if (!li2)
3939 return;
3940 for (int i = static_cast<int>(li2->stairs.size()) - 1; i >= 0; --i)
3941 {
3942 if (li2->stairs[i].grid == feat2)
3943 {
3944 if (li2->stairs[i].type == stair_info::MAPPED)
3945 return;
3946 // If we haven't added these stairs to our LevelInfo yet, do so
3947 // before trying to update them.
3948 if (!si)
3949 {
3950 stair_info si2;
3951 si2.position = c;
3952 si2.grid = env.grid(si2.position);
3953 li->stairs.push_back(si2);
3954 }
3955 li->update_stair(c,level_pos(li2->id,li2->stairs[i].position));
3956 // Add the other stair direction too so that X[]ing to the other
3957 // level will be correct immediately.
3958 li2->update_stair(li2->stairs[i].position,level_pos(li->id,c));
3959 return;
3960 }
3961 }
3962 }
3963
update_transporter(const coord_def & c)3964 void TravelCache::update_transporter(const coord_def &c)
3965 {
3966 const dungeon_feature_type feat = env.grid(c);
3967 ASSERT(feat == DNGN_TRANSPORTER);
3968
3969 if (!env.map_knowledge(c).seen())
3970 return;
3971
3972 LevelInfo *li = find_level_info(level_id::current());
3973 if (!li)
3974 return;
3975
3976 transporter_info *ti = li->get_transporter(c);
3977 if (!ti)
3978 {
3979 li->transporters.push_back(transporter_info(c, coord_def(),
3980 transporter_info::transporter_type::PHYSICAL));
3981 }
3982 }
3983
know_transporter(const coord_def & c)3984 bool TravelCache::know_transporter(const coord_def &c)
3985 {
3986 if (env.grid(c) == DNGN_TRANSPORTER)
3987 update_transporter(c);
3988 auto i = levels.find(level_id::current());
3989 return i == levels.end() ? false : i->second.know_transporter(c);
3990 }
3991
know_stair(const coord_def & c)3992 bool TravelCache::know_stair(const coord_def &c)
3993 {
3994 if (feat_is_stone_stair(env.grid(c)))
3995 update_stone_stair(c);
3996 auto i = levels.find(level_id::current());
3997 return i == levels.end() ? false : i->second.know_stair(c);
3998 }
3999
list_waypoints() const4000 void TravelCache::list_waypoints() const
4001 {
4002 string line;
4003 string dest;
4004 char choice[50];
4005 int count = 0;
4006
4007 for (int i = 0; i < TRAVEL_WAYPOINT_COUNT; ++i)
4008 {
4009 if (waypoints[i].id.depth == -1)
4010 continue;
4011
4012 dest = _get_trans_travel_dest(waypoints[i], false, true);
4013
4014 snprintf(choice, sizeof choice, "(%d) %-9s", i, dest.c_str());
4015 line += choice;
4016 if (!(++count % 5))
4017 {
4018 mpr(line);
4019 line = "";
4020 }
4021 }
4022 if (!line.empty())
4023 mpr(line);
4024 }
4025
is_waypoint(const level_pos & lp) const4026 uint8_t TravelCache::is_waypoint(const level_pos &lp) const
4027 {
4028 for (int i = 0; i < TRAVEL_WAYPOINT_COUNT; ++i)
4029 if (lp == waypoints[i])
4030 return '0' + i;
4031
4032 return 0;
4033 }
4034
update_waypoints() const4035 void TravelCache::update_waypoints() const
4036 {
4037 level_pos lp;
4038 lp.id = level_id::current();
4039
4040 memset(curr_waypoints, 0, sizeof curr_waypoints);
4041 for (lp.pos.x = 1; lp.pos.x < GXM; ++lp.pos.x)
4042 for (lp.pos.y = 1; lp.pos.y < GYM; ++lp.pos.y)
4043 {
4044 uint8_t wpc = is_waypoint(lp);
4045 if (wpc)
4046 curr_waypoints[lp.pos.x][lp.pos.y] = wpc;
4047 }
4048 }
4049
delete_waypoint()4050 void TravelCache::delete_waypoint()
4051 {
4052 if (!get_waypoint_count())
4053 return;
4054
4055 while (get_waypoint_count())
4056 {
4057 clear_messages();
4058 mpr("Existing waypoints:");
4059 list_waypoints();
4060 mprf(MSGCH_PROMPT, "Delete which waypoint? (* - delete all, Esc - exit) ");
4061
4062 int key = getchm();
4063 if (key >= '0' && key <= '9')
4064 {
4065 key -= '0';
4066 if (waypoints[key].is_valid())
4067 {
4068 waypoints[key].clear();
4069 update_waypoints();
4070 continue;
4071 }
4072 }
4073 else if (key == '*')
4074 {
4075 for (int i = 0; i < TRAVEL_WAYPOINT_COUNT; ++i)
4076 waypoints[i].clear();
4077
4078 update_waypoints();
4079 break;
4080 }
4081
4082 canned_msg(MSG_OK);
4083 return;
4084 }
4085
4086 clear_messages();
4087 mpr("All waypoints deleted. Have a nice day!");
4088 }
4089
add_waypoint(int x,int y)4090 void TravelCache::add_waypoint(int x, int y)
4091 {
4092 if (!can_travel_interlevel())
4093 {
4094 mpr("Sorry, you can't set a waypoint here.");
4095 return;
4096 }
4097
4098 clear_messages();
4099
4100 const bool waypoints_exist = get_waypoint_count();
4101 if (waypoints_exist)
4102 {
4103 mpr("Existing waypoints:");
4104 list_waypoints();
4105 }
4106
4107 mprf(MSGCH_PROMPT, "Assign waypoint to what number? (0-9%s) ",
4108 waypoints_exist? ", D - delete waypoint" : "");
4109
4110 int keyin = toalower(get_ch());
4111
4112 if (waypoints_exist && keyin == 'd')
4113 {
4114 delete_waypoint();
4115 return;
4116 }
4117
4118 if (keyin < '0' || keyin > '9')
4119 {
4120 canned_msg(MSG_OK);
4121 return;
4122 }
4123
4124 set_waypoint(keyin - '0', x, y);
4125
4126 }
4127
set_waypoint(int waynum,int x,int y)4128 void TravelCache::set_waypoint(int waynum, int x, int y)
4129 {
4130 ASSERT_RANGE(waynum, 0, TRAVEL_WAYPOINT_COUNT);
4131 coord_def pos(x,y);
4132 if (x == -1 || y == -1)
4133 pos = you.pos();
4134
4135 const level_id &lid = level_id::current();
4136
4137 const bool overwrite = waypoints[waynum].is_valid();
4138
4139 string old_dest =
4140 overwrite ? _get_trans_travel_dest(waypoints[waynum], false, true) : "";
4141 level_id old_lid = (overwrite ? waypoints[waynum].id : lid);
4142
4143 waypoints[waynum].id = lid;
4144 waypoints[waynum].pos = pos;
4145
4146 string new_dest = _get_trans_travel_dest(waypoints[waynum], false, true);
4147 clear_messages();
4148 if (overwrite)
4149 {
4150 if (lid == old_lid) // same level
4151 mprf("Waypoint %d re-assigned to %s.", waynum, new_dest.c_str());
4152 else
4153 {
4154 mprf("Waypoint %d re-assigned from %s to %s.",
4155 waynum, old_dest.c_str(), new_dest.c_str());
4156 }
4157 }
4158 else
4159 mprf("Waypoint %d assigned to %s.", waynum, new_dest.c_str());
4160
4161 update_waypoints();
4162 }
4163
get_waypoint_count() const4164 int TravelCache::get_waypoint_count() const
4165 {
4166 int count = 0;
4167 for (int i = 0; i < TRAVEL_WAYPOINT_COUNT; ++i)
4168 if (waypoints[i].is_valid())
4169 count++;
4170
4171 return count;
4172 }
4173
clear_distances()4174 void TravelCache::clear_distances()
4175 {
4176 for (auto &entry : levels)
4177 entry.second.clear_distances();
4178 }
4179
is_known_branch(uint8_t branch) const4180 bool TravelCache::is_known_branch(uint8_t branch) const
4181 {
4182 return any_of(begin(levels), end(levels),
4183 [branch] (const pair<level_id, LevelInfo> &entry)
4184 { return entry.second.is_known_branch(branch); });
4185 }
4186
save(writer & outf) const4187 void TravelCache::save(writer& outf) const
4188 {
4189 write_save_version(outf, save_version::current());
4190
4191 // Write level count.
4192 marshallShort(outf, levels.size());
4193
4194 for (const auto &entry : levels)
4195 {
4196 entry.first.save(outf);
4197 entry.second.save(outf);
4198 }
4199
4200 for (int wp = 0; wp < TRAVEL_WAYPOINT_COUNT; ++wp)
4201 waypoints[wp].save(outf);
4202 }
4203
load(reader & inf,int minorVersion)4204 void TravelCache::load(reader& inf, int minorVersion)
4205 {
4206 levels.clear();
4207
4208 // Check version. If not compatible, we just ignore the file altogether.
4209 const auto version = get_save_version(inf);
4210 const auto major = version.major, minor = version.minor;
4211 if (major != TAG_MAJOR_VERSION || minor > TAG_MINOR_VERSION)
4212 return;
4213
4214 int level_count = unmarshallShort(inf);
4215 for (int i = 0; i < level_count; ++i)
4216 {
4217 level_id id;
4218 id.load(inf);
4219
4220 LevelInfo linfo;
4221 // Must set id before load, or travel_hell_entry will not be
4222 // correctly set.
4223 linfo.id = id;
4224 linfo.load(inf, minorVersion);
4225
4226 levels[id] = linfo;
4227 }
4228
4229 for (int wp = 0; wp < TRAVEL_WAYPOINT_COUNT; ++wp)
4230 waypoints[wp].load(inf);
4231
4232 fixup_levels();
4233 }
4234
set_level_excludes()4235 void TravelCache::set_level_excludes()
4236 {
4237 get_level_info(level_id::current()).set_level_excludes();
4238 }
4239
update_excludes()4240 void TravelCache::update_excludes()
4241 {
4242 get_level_info(level_id::current()).update_excludes();
4243 }
4244
update()4245 void TravelCache::update()
4246 {
4247 get_level_info(level_id::current()).update();
4248 }
4249
update_daction_counters()4250 void TravelCache::update_daction_counters()
4251 {
4252 ::update_daction_counters(&get_level_info(level_id::current()));
4253 }
4254
query_daction_counter(daction_type c)4255 unsigned int TravelCache::query_daction_counter(daction_type c)
4256 {
4257 // other levels are up to date, the current one not necessarily so
4258 update_daction_counters();
4259
4260 unsigned int sum = 0;
4261
4262 for (const auto &entry : levels)
4263 sum += entry.second.daction_counters[c];
4264
4265 return sum;
4266 }
4267
clear_daction_counter(daction_type c)4268 void TravelCache::clear_daction_counter(daction_type c)
4269 {
4270 for (auto &entry : levels)
4271 entry.second.daction_counters[c] = 0;
4272 }
4273
fixup_levels()4274 void TravelCache::fixup_levels()
4275 {
4276 for (auto &entry : levels)
4277 entry.second.fixup();
4278 }
4279
known_levels() const4280 vector<level_id> TravelCache::known_levels() const
4281 {
4282 vector<level_id> levs;
4283
4284 for (const auto &entry : levels)
4285 levs.push_back(entry.first);
4286
4287 return levs;
4288 }
4289
can_travel_to(const level_id & id)4290 bool can_travel_to(const level_id &id)
4291 {
4292 return is_connected_branch(id) && can_travel_interlevel()
4293 || id == level_id::current();
4294 }
4295
can_travel_interlevel()4296 bool can_travel_interlevel()
4297 {
4298 return player_in_connected_branch();
4299 }
4300
4301 /////////////////////////////////////////////////////////////////////////////
4302 // Shift-running and resting.
4303
runrest()4304 runrest::runrest()
4305 : runmode(0), mp(0), hp(0), pos(0,0), turns_passed(0)
4306 {
4307 }
4308
4309 // Initialise is only called for resting/shift-running. We should eventually
4310 // include travel and wrap it all in.
initialise(int dir,int mode)4311 void runrest::initialise(int dir, int mode)
4312 {
4313 // Note HP and MP for reference.
4314 hp = you.hp;
4315 mp = you.magic_points;
4316 direction = dir;
4317 notified_hp_full = false;
4318 notified_mp_full = false;
4319 notified_ancestor_hp_full = false;
4320 turns_passed = 0;
4321 init_travel_speed();
4322
4323 if (dir == RDIR_REST)
4324 {
4325 pos.reset();
4326 runmode = mode;
4327 }
4328 else
4329 {
4330 ASSERT_RANGE(dir, 0, 8);
4331
4332 pos = Compass[dir];
4333 runmode = mode;
4334
4335 // Get the compass point to the left/right of intended travel:
4336 const int left = (dir - 1 < 0) ? 7 : (dir - 1);
4337 const int right = (dir + 1 > 7) ? 0 : (dir + 1);
4338
4339 // Record the direction and starting tile type for later reference:
4340 set_run_check(0, left);
4341 set_run_check(1, dir);
4342 set_run_check(2, right);
4343 }
4344
4345 if (runmode == RMODE_REST_DURATION || runmode == RMODE_WAIT_DURATION)
4346 start_delay<RestDelay>();
4347 else
4348 start_delay<RunDelay>();
4349 }
4350
init_travel_speed()4351 void runrest::init_travel_speed()
4352 {
4353 if (you.travel_ally_pace)
4354 travel_speed = _slowest_ally_speed();
4355 else
4356 travel_speed = 0;
4357 }
4358
operator int() const4359 runrest::operator int () const
4360 {
4361 return runmode;
4362 }
4363
operator =(int newrunmode)4364 const runrest &runrest::operator = (int newrunmode)
4365 {
4366 runmode = newrunmode;
4367 return *this;
4368 }
4369
_base_feat_type(dungeon_feature_type grid)4370 static dungeon_feature_type _base_feat_type(dungeon_feature_type grid)
4371 {
4372 // Merge walls.
4373 if (feat_is_wall(grid))
4374 return DNGN_ROCK_WALL;
4375
4376 return grid;
4377 }
4378
set_run_check(int index,int dir)4379 void runrest::set_run_check(int index, int dir)
4380 {
4381 run_check[index].delta = Compass[dir];
4382
4383 const coord_def p = you.pos() + Compass[dir];
4384 run_check[index].grid = _base_feat_type(env.map_knowledge(p).feat());
4385 }
4386
check_stop_running()4387 bool runrest::check_stop_running()
4388 {
4389 if (runmode > 0 && runmode != RMODE_START && run_should_stop())
4390 {
4391 stop();
4392 return true;
4393 }
4394 return false;
4395 }
4396
4397 // This function creates "equivalence classes" so that changes
4398 // in wall and floor type aren't running stopping points.
run_should_stop() const4399 bool runrest::run_should_stop() const
4400 {
4401 const coord_def targ = you.pos() + pos;
4402 const map_cell& tcell = env.map_knowledge(targ);
4403
4404 // XXX: probably this should ignore cosmetic clouds (non-opaque)
4405 if (tcell.cloud() != CLOUD_NONE
4406 && !you.cloud_immune())
4407 {
4408 return true;
4409 }
4410
4411 if (is_excluded(targ) && !is_stair_exclusion(targ))
4412 {
4413 #ifndef USE_TILE_LOCAL
4414 // XXX: Remove this once exclusions are visible.
4415 mprf(MSGCH_WARN, "Stopped running for exclusion.");
4416 #endif
4417 return true;
4418 }
4419
4420 const monster_info* mon = tcell.monsterinfo();
4421 if (mon && !fedhas_passthrough(tcell.monsterinfo()))
4422 return true;
4423
4424 if (count_adjacent_slime_walls(targ))
4425 return true;
4426
4427 for (int i = 0; i < 3; i++)
4428 {
4429 const coord_def p = you.pos() + run_check[i].delta;
4430 const dungeon_feature_type feat =
4431 _base_feat_type(env.map_knowledge(p).feat());
4432
4433 if (run_check[i].grid != feat)
4434 return true;
4435 }
4436
4437 bool is_running_diag = (direction % 2 == 1);
4438 if (is_running_diag && diag_run_passes_door())
4439 return true;
4440
4441 return false;
4442 }
4443
4444 // Checks whether the player passes a door when running diagonally, since
4445 // in certain situations those could be overlooked by only checking "left"
4446 // and "right".
4447 // Can be extended if other features should lead to stopping as well.
diag_run_passes_door() const4448 bool runrest::diag_run_passes_door() const
4449 {
4450 const int diag_left = (direction + 6) % 8;
4451 const int diag_right = (direction + 2) % 8;
4452 const int diag_dirs[2] = { diag_left, diag_right };
4453 for (int dir : diag_dirs)
4454 {
4455 const coord_def p = you.pos() + Compass[dir];
4456 const auto feat = env.map_knowledge(p).feat();
4457 if (feat_is_door(feat))
4458 return true;
4459 }
4460
4461 return false;
4462 }
4463
stop(bool clear_delays)4464 void runrest::stop(bool clear_delays)
4465 {
4466 bool need_redraw =
4467 (runmode > 0 || runmode < 0 && Options.travel_delay == -1);
4468 _userdef_run_stoprunning_hook();
4469 runmode = RMODE_NOT_RUNNING;
4470
4471 // Kill the delay; this is fine because it's not possible to stack
4472 // run/rest/travel on top of other delays.
4473 if (clear_delays)
4474 stop_delay();
4475
4476 #ifdef USE_TILE_LOCAL
4477 if (Options.tile_runrest_rate > 0)
4478 tiles.set_need_redraw();
4479 #endif
4480
4481 quiver::set_needs_redraw();
4482 if (need_redraw)
4483 {
4484 viewwindow();
4485 print_stats();
4486 update_screen();
4487 }
4488 }
4489
is_rest() const4490 bool runrest::is_rest() const
4491 {
4492 return runmode > 0 && pos.origin();
4493 }
4494
is_explore() const4495 bool runrest::is_explore() const
4496 {
4497 return runmode == RMODE_EXPLORE || runmode == RMODE_EXPLORE_GREEDY;
4498 }
4499
is_any_travel() const4500 bool runrest::is_any_travel() const
4501 {
4502 switch (runmode)
4503 {
4504 case RMODE_INTERLEVEL:
4505 case RMODE_EXPLORE_GREEDY:
4506 case RMODE_EXPLORE:
4507 case RMODE_TRAVEL:
4508 return true;
4509 default:
4510 return false;
4511 }
4512 }
4513
runmode_name() const4514 string runrest::runmode_name() const
4515 {
4516 switch (runmode)
4517 {
4518 case RMODE_EXPLORE:
4519 case RMODE_EXPLORE_GREEDY:
4520 return "explore";
4521 case RMODE_INTERLEVEL:
4522 case RMODE_TRAVEL:
4523 return "travel";
4524 default:
4525 if (runmode > 0)
4526 return pos.origin()? "rest" : "run";
4527 return "";
4528 }
4529 }
4530
rest()4531 void runrest::rest()
4532 {
4533 // stop_running() Lua hooks will never see rest stops.
4534 if (runmode > 0)
4535 --runmode;
4536 }
4537
clear()4538 void runrest::clear()
4539 {
4540 runmode = RMODE_NOT_RUNNING;
4541 pos.reset();
4542 mp = hp = travel_speed = 0;
4543 turns_passed = 0;
4544 notified_hp_full = false;
4545 notified_mp_full = false;
4546 notified_ancestor_hp_full = false;
4547 }
4548
4549 /////////////////////////////////////////////////////////////////////////////
4550 // explore_discoveries
4551
explore_discoveries()4552 explore_discoveries::explore_discoveries()
4553 : can_autopickup(::can_autopickup()),
4554 es_flags(0),
4555 current_level(nullptr), items(), stairs(), portals(), shops(), altars(),
4556 runed_doors()
4557 {
4558 }
4559
cleaned_feature_description(const coord_def & pos) const4560 string explore_discoveries::cleaned_feature_description(
4561 const coord_def &pos) const
4562 {
4563 string s = lowercase_first(feature_description_at(pos));
4564 // TODO: can feature_description_at()'s return value still end in '.'?
4565 if (s.length() && s[s.length() - 1] == '.')
4566 s.erase(s.length() - 1);
4567 if (starts_with(s, "a "))
4568 s = s.substr(2);
4569 else if (starts_with(s, "an "))
4570 s = s.substr(3);
4571 return s;
4572 }
4573
merge_feature(vector<explore_discoveries::named_thing<int>> & v,const explore_discoveries::named_thing<int> & feat) const4574 bool explore_discoveries::merge_feature(
4575 vector< explore_discoveries::named_thing<int> > &v,
4576 const explore_discoveries::named_thing<int> &feat) const
4577 {
4578 for (explore_discoveries::named_thing<int> &nt: v)
4579 if (feat == nt)
4580 {
4581 ++nt.thing;
4582 return true;
4583 }
4584
4585 return false;
4586 }
4587
_feat_is_branchlike(dungeon_feature_type feat)4588 static bool _feat_is_branchlike(dungeon_feature_type feat)
4589 {
4590 return feat_is_branch_entrance(feat)
4591 || feat == DNGN_ENTER_HELL
4592 || feat == DNGN_ENTER_ABYSS
4593 || feat == DNGN_EXIT_THROUGH_ABYSS
4594 || feat == DNGN_ENTER_PANDEMONIUM;
4595 }
4596
found_feature(const coord_def & pos,dungeon_feature_type feat)4597 void explore_discoveries::found_feature(const coord_def &pos,
4598 dungeon_feature_type feat)
4599 {
4600 if (feat == DNGN_ENTER_SHOP && ES_shop)
4601 {
4602 shops.emplace_back(shop_name(*shop_at(pos)), feat);
4603 es_flags |= ES_SHOP;
4604 }
4605 else if (feat_is_stair(feat) && ES_stair)
4606 {
4607 const named_thing<int> stair(cleaned_feature_description(pos), 1);
4608 add_stair(stair);
4609 es_flags |= ES_STAIR;
4610 }
4611 else if (_feat_is_branchlike(feat) && ES_branch)
4612 {
4613 const named_thing<int> stair(cleaned_feature_description(pos), 1);
4614 add_stair(stair);
4615 es_flags |= ES_BRANCH;
4616 }
4617 else if (feat_is_portal(feat) && ES_portal)
4618 {
4619 const named_thing<int> portal(cleaned_feature_description(pos), 1);
4620 add_stair(portal);
4621 es_flags |= ES_PORTAL;
4622 }
4623 else if (feat_is_runed(feat))
4624 {
4625 seen_tracked_feature(feat);
4626 if (ES_rdoor)
4627 {
4628 for (orth_adjacent_iterator ai(pos); ai; ++ai)
4629 {
4630 // If any neighbours have been seen (and thus announced)
4631 // before, skip. For parts seen for the first time this turn,
4632 // announce only the upper leftmost cell.
4633 if (feat_is_runed(env.map_knowledge(*ai).feat())
4634 && (env.map_seen(*ai) || *ai < pos))
4635 {
4636 return;
4637 }
4638 }
4639
4640 string desc = env.markers.property_at(pos, MAT_ANY, "stop_explore");
4641 if (desc.empty())
4642 desc = cleaned_feature_description(pos);
4643 runed_doors.emplace_back(desc, 1);
4644 es_flags |= ES_RUNED_DOOR;
4645 }
4646 }
4647 else if (feat == DNGN_TRANSPORTER)
4648 {
4649 seen_tracked_feature(feat);
4650 if (ES_transporter)
4651 {
4652 for (orth_adjacent_iterator ai(pos); ai; ++ai)
4653 {
4654 // If any neighbours have been seen (and thus announced) before,
4655 // skip. For parts seen for the first time this turn, announce
4656 // only the upper leftmost cell.
4657 if (env.map_knowledge(*ai).feat() == DNGN_TRANSPORTER
4658 && (env.map_seen(*ai) || *ai < pos))
4659 {
4660 return;
4661 }
4662 }
4663
4664 string desc = env.markers.property_at(pos, MAT_ANY, "stop_explore");
4665 if (desc.empty())
4666 desc = cleaned_feature_description(pos);
4667 transporters.emplace_back(desc, 1);
4668 es_flags |= ES_TRANSPORTER;
4669 }
4670 }
4671 else if (feat_is_altar(feat) && ES_altar)
4672 {
4673 const named_thing<int> altar(cleaned_feature_description(pos), 1);
4674 if (!merge_feature(altars, altar))
4675 altars.push_back(altar);
4676 es_flags |= ES_ALTAR;
4677 }
4678 // Would checking for a marker for all discovered cells slow things
4679 // down too much?
4680 else if (feat_is_statuelike(feat))
4681 {
4682 const string feat_stop_msg =
4683 env.markers.property_at(pos, MAT_ANY, "stop_explore_msg");
4684 if (!feat_stop_msg.empty())
4685 {
4686 marker_msgs.push_back(feat_stop_msg);
4687 return;
4688 }
4689
4690 const string feat_stop = env.markers.property_at(pos, MAT_ANY,
4691 "stop_explore");
4692 if (!feat_stop.empty())
4693 {
4694 string desc = lowercase_first(feature_description_at(pos));
4695 marked_feats.push_back(desc + ".");
4696 return;
4697 }
4698 }
4699 }
4700
add_stair(const explore_discoveries::named_thing<int> & stair)4701 void explore_discoveries::add_stair(
4702 const explore_discoveries::named_thing<int> &stair)
4703 {
4704 if (merge_feature(stairs, stair) || merge_feature(portals, stair))
4705 return;
4706
4707 // Hackadelic
4708 if (stair.name.find("stair") != string::npos)
4709 stairs.push_back(stair);
4710 else
4711 portals.push_back(stair);
4712 }
4713
add_item(const item_def & i)4714 void explore_discoveries::add_item(const item_def &i)
4715 {
4716 item_def copy = i;
4717 copy.quantity = 1;
4718 const string cname = copy.name(DESC_PLAIN);
4719
4720 // Try to find something to stack it with, stacking by name.
4721 for (named_thing<item_def> &item : items)
4722 {
4723 const int orig_quantity = item.thing.quantity;
4724 item.thing.quantity = 1;
4725 if (cname == item.thing.name(DESC_PLAIN))
4726 {
4727 item.thing.quantity = orig_quantity + i.quantity;
4728 item.name = item.thing.name(DESC_A, false, false, true,
4729 !is_stackable_item(i));
4730 return;
4731 }
4732 item.thing.quantity = orig_quantity;
4733 }
4734
4735 string itemname = menu_colour_item_name(i, DESC_A);
4736 monster* mon = monster_at(i.pos);
4737 if (mon && mons_species(mon->type) == MONS_BUSH)
4738 itemname += " (under bush)";
4739 else if (mon && mon->type == MONS_PLANT)
4740 itemname += " (under plant)";
4741
4742 items.emplace_back(itemname, i);
4743
4744 // First item of this type?
4745 // XXX: Only works when travelling.
4746 hints_first_item(i);
4747 }
4748
found_item(const coord_def & pos,const item_def & i)4749 void explore_discoveries::found_item(const coord_def &pos, const item_def &i)
4750 {
4751 if (you.running == RMODE_EXPLORE_GREEDY)
4752 {
4753 // The things we need to do...
4754 if (!current_level)
4755 current_level = StashTrack.find_current_level();
4756
4757 if (current_level)
4758 {
4759 const bool greed_inducing = _is_greed_inducing_square(current_level,
4760 pos,
4761 can_autopickup);
4762
4763 if (greed_inducing && (Options.explore_stop & ES_GREEDY_ITEM))
4764 ; // Stop for this condition
4765 else if (!greed_inducing
4766 && (Options.explore_stop & ES_ITEM
4767 || Options.explore_stop & ES_GLOWING_ITEM
4768 && i.flags & ISFLAG_COSMETIC_MASK
4769 || Options.explore_stop & ES_ARTEFACT
4770 && i.flags & ISFLAG_ARTEFACT_MASK
4771 || Options.explore_stop & ES_RUNE
4772 && i.base_type == OBJ_RUNES))
4773 {
4774 ; // More conditions to stop for
4775 }
4776 else
4777 return; // No conditions met, don't stop for this item
4778 }
4779 } // if (you.running == RMODE_EXPLORE_GREEDY)
4780
4781 add_item(i);
4782 es_flags |=
4783 (you.running == RMODE_EXPLORE_GREEDY) ? ES_GREEDY_PICKUP_MASK :
4784 (Options.explore_stop & ES_ITEM) ? ES_ITEM : ES_NONE;
4785 }
4786
4787 // Expensive O(n^2) duplicate search, but we can live with that.
has_duplicates(citer begin,citer end) const4788 template <class citer> bool explore_discoveries::has_duplicates(
4789 citer begin, citer end) const
4790 {
4791 for (citer s = begin; s != end; ++s)
4792 for (citer z = s + 1; z != end; ++z)
4793 {
4794 if (*s == *z)
4795 return true;
4796 }
4797
4798 return false;
4799 }
4800
say_any(const C & coll,const char * category) const4801 template <class C> void explore_discoveries::say_any(
4802 const C &coll, const char *category) const
4803 {
4804 if (coll.empty())
4805 return;
4806
4807 const int size = coll.size();
4808
4809 string plural = pluralise(category);
4810 if (size != 1)
4811 category = plural.c_str();
4812
4813 if (has_duplicates(coll.begin(), coll.end()))
4814 {
4815 mprf("Found %s %s.", number_in_words(size).c_str(), category);
4816 return;
4817 }
4818
4819 const auto message = formatted_string::parse_string("Found " +
4820 comma_separated_line(coll.begin(), coll.end()) + ".");
4821
4822 if (message.width() >= get_number_of_cols())
4823 mprf("Found %s %s.", number_in_words(size).c_str(), category);
4824 else
4825 mpr(message);
4826 }
4827
apply_quantities(const vector<named_thing<int>> & v) const4828 vector<string> explore_discoveries::apply_quantities(
4829 const vector< named_thing<int> > &v) const
4830 {
4831 static const char *feature_plural_qualifiers[] =
4832 {
4833 " leading ", " back to ", " to ", " of ", " in ", " out of",
4834 " from ", " back into ", nullptr
4835 };
4836
4837 vector<string> things;
4838 for (const named_thing<int> &nt : v)
4839 {
4840 if (nt.thing == 1)
4841 things.push_back(article_a(nt.name));
4842 else
4843 {
4844 things.push_back(number_in_words(nt.thing)
4845 + " "
4846 + pluralise(nt.name, feature_plural_qualifiers));
4847 }
4848 }
4849 return things;
4850 }
4851
stop_explore() const4852 bool explore_discoveries::stop_explore() const
4853 {
4854 const bool marker_stop = !marker_msgs.empty() || !marked_feats.empty();
4855
4856 for (const string &msg : marker_msgs)
4857 mpr(msg);
4858
4859 for (const string &marked : marked_feats)
4860 mprf("Found %s", marked.c_str());
4861
4862 if (!es_flags)
4863 return marker_stop;
4864
4865 say_any(items, "item");
4866 say_any(shops, "shop");
4867 say_any(apply_quantities(altars), "altar");
4868 say_any(apply_quantities(portals), "portal");
4869 say_any(apply_quantities(stairs), "stair");
4870 say_any(apply_quantities(transporters), "transporter");
4871 say_any(apply_quantities(runed_doors), "runed door");
4872
4873 return true;
4874 }
4875
do_interlevel_travel()4876 void do_interlevel_travel()
4877 {
4878 if (Hints.hints_travel)
4879 Hints.hints_travel = 0;
4880
4881 if (!can_travel_interlevel())
4882 {
4883 if (you.running.pos == you.pos())
4884 {
4885 mpr("You're already here!");
4886 return;
4887 }
4888 else if (!you.running.pos.x || !you.running.pos.y)
4889 {
4890 mpr("Sorry, you can't auto-travel out of here.");
4891 return;
4892 }
4893
4894 // Don't ask for a destination if you can only travel
4895 // within level anyway.
4896 start_travel(you.running.pos);
4897 }
4898 else
4899 _start_translevel_travel_prompt();
4900
4901 if (you.running)
4902 clear_messages();
4903 }
4904
4905 #ifdef USE_TILE
4906 // (0,0) = same position is handled elsewhere.
4907 const int dir_dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
4908 const int dir_dy[8] = { 1, 1, 1, 0, 0, -1, -1, -1};
4909
4910 const int cmd_array[8] =
4911 {
4912 CMD_MOVE_DOWN_LEFT, CMD_MOVE_DOWN, CMD_MOVE_DOWN_RIGHT,
4913 CMD_MOVE_LEFT, CMD_MOVE_RIGHT,
4914 CMD_MOVE_UP_LEFT, CMD_MOVE_UP, CMD_MOVE_UP_RIGHT,
4915 };
4916
_adjacent_cmd(const coord_def & gc,bool force)4917 static int _adjacent_cmd(const coord_def &gc, bool force)
4918 {
4919 const coord_def dir = gc - you.pos();
4920 for (int i = 0; i < 8; i++)
4921 {
4922 if (dir_dx[i] != dir.x || dir_dy[i] != dir.y)
4923 continue;
4924
4925 int cmd = cmd_array[i];
4926 if (force)
4927 {
4928 if (feat_is_open_door(env.grid(gc))
4929 && !env.map_knowledge(gc).monsterinfo())
4930 {
4931 cmd += CMD_CLOSE_DOOR_LEFT - CMD_MOVE_LEFT;
4932 }
4933 else
4934 cmd += CMD_ATTACK_LEFT - CMD_MOVE_LEFT;
4935 }
4936
4937 return cmd;
4938 }
4939
4940 return CK_MOUSE_CMD;
4941 }
4942
click_travel_safe(const coord_def & gc)4943 bool click_travel_safe(const coord_def &gc)
4944 {
4945 return (!is_excluded(gc) || is_stair_exclusion(gc))
4946 && (!is_excluded(you.pos()) || is_stair_exclusion(you.pos()))
4947 && i_feel_safe(false, false, false, false);
4948 }
4949
click_travel(const coord_def & gc,bool force)4950 int click_travel(const coord_def &gc, bool force)
4951 {
4952 if (!in_bounds(gc))
4953 return CK_MOUSE_CMD;
4954
4955 const int cmd = _adjacent_cmd(gc, force);
4956 if (cmd != CK_MOUSE_CMD)
4957 return cmd;
4958
4959 if (click_travel_safe(gc))
4960 {
4961 map_cell &cell(env.map_knowledge(gc));
4962 // If there's a monster that would block travel,
4963 // don't start traveling.
4964 if (!_monster_blocks_travel(cell.monsterinfo()))
4965 {
4966 start_travel(gc);
4967 return CK_MOUSE_CMD;
4968 }
4969 }
4970
4971 // If not safe, then take one step towards the click.
4972 travel_pathfind tp;
4973 tp.set_src_dst(you.pos(), gc);
4974 tp.set_ignore_danger();
4975 const coord_def dest = tp.pathfind(RMODE_TRAVEL);
4976
4977 if (!dest.x && !dest.y)
4978 return CK_MOUSE_CMD;
4979
4980 return _adjacent_cmd(dest, force);
4981 }
4982 #endif
4983
check_for_interesting_features()4984 bool check_for_interesting_features()
4985 {
4986 // Scan through the shadow map, compare it with the actual map, and if
4987 // there are any squares of the shadow map that have just been
4988 // discovered and contain an item, or have an interesting dungeon
4989 // feature, announce the discovery and return true.
4990 explore_discoveries discoveries;
4991 for (vision_iterator ri(you); ri; ++ri)
4992 {
4993 const coord_def p(*ri);
4994
4995 // Find just noticed squares.
4996 if (env.map_knowledge(p).flags & MAP_SEEN_FLAG
4997 && !env.map_seen(p))
4998 {
4999 // Update the shadow map
5000 env.map_seen.set(p);
5001
5002 // But don't stop if we knew about it previously
5003 if (!env.map_forgotten
5004 || !((*env.map_forgotten)(p).flags & MAP_SEEN_FLAG))
5005 {
5006 _check_interesting_square(p, discoveries);
5007 }
5008 }
5009 }
5010
5011 return discoveries.stop_explore();
5012 }
5013
clear_level_target()5014 void clear_level_target()
5015 {
5016 level_target.clear();
5017 trans_travel_dest.clear();
5018 }
5019
clear_travel_trail()5020 void clear_travel_trail()
5021 {
5022 #ifdef USE_TILE_WEB
5023 for (coord_def c : env.travel_trail)
5024 tiles.update_minimap(c);
5025 #endif
5026 env.travel_trail.clear();
5027 }
5028
travel_trail_index(const coord_def & gc)5029 int travel_trail_index(const coord_def& gc)
5030 {
5031 unsigned int idx = find(env.travel_trail.begin(), env.travel_trail.end(), gc)
5032 - env.travel_trail.begin();
5033 if (idx < env.travel_trail.size())
5034 return idx;
5035 else
5036 return -1;
5037 }
5038
stairs_destination_is_excluded(const stair_info & si)5039 bool stairs_destination_is_excluded(const stair_info &si)
5040 {
5041 level_pos dest = si.destination;
5042 if (LevelInfo *dest_li = travel_cache.find_level_info(dest.id))
5043 {
5044 if (is_unknown_stair(si.position)
5045 || !is_excluded(dest.pos, dest_li->get_excludes()))
5046 {
5047 return false;
5048 }
5049
5050 // Check for exclusions that cover the stair destination, but ignore
5051 // those that have radius 1: those exclude travel in the _other_
5052 // direction only (from the destination to here, not from here to the
5053 // destination)
5054 const exclude_set &excludes = dest_li->get_excludes();
5055 for (auto entry : excludes)
5056 {
5057 const travel_exclude &ex = entry.second;
5058 if (ex.in_bounds(dest.pos) && ex.radius > 1)
5059 return true;
5060 }
5061 }
5062
5063 return false;
5064 }
5065