Revert "Track who destroys an item; incur Nemelex penance for deck destruction."
[crawl.git] / crawl-ref / source / abyss.cc
1 /**
2  * @file
3  * @brief Misc abyss specific functions.
4 **/
5
6 #include "AppHdr.h"
7
8 #include <cmath>
9 #include <cstdlib>
10 #include <algorithm>
11 #include <queue>
12
13 #include "abyss.h"
14 #include "areas.h"
15 #include "artefact.h"
16 #include "branch.h"
17 #include "cloud.h"
18 #include "colour.h"
19 #include "coordit.h"
20 #include "dbg-scan.h"
21 #include "dgn-proclayouts.h"
22 #include "dungeon.h"
23 #include "env.h"
24 #include "files.h"
25 #include "itemprop.h"
26 #include "items.h"
27 #include "l_defs.h"
28 #include "libutil.h"
29 #include "los.h"
30 #include "makeitem.h"
31 #include "mapmark.h"
32 #include "maps.h"
33 #include "message.h"
34 #include "mgen_data.h"
35 #include "misc.h"
36 #include "mon-abil.h"
37 #include "mon-iter.h"
38 #include "mon-pathfind.h"
39 #include "mon-pick.h"
40 #include "mon-place.h"
41 #include "mon-transit.h"
42 #include "mon-util.h"
43 #include "notes.h"
44 #include "player.h"
45 #include "random.h"
46 #include "religion.h"
47 #include "shopping.h"
48 #include "stash.h"
49 #include "state.h"
50 #include "terrain.h"
51 #include "tiledef-dngn.h"
52 #include "tileview.h"
53 #include "traps.h"
54 #include "travel.h"
55 #include "view.h"
56 #include "viewgeom.h"
57 #include "xom.h"
58
59 const coord_def ABYSS_CENTRE(GXM / 2, GYM / 2);
60
61 static const int ABYSSAL_RUNE_MAX_ROLL = 200;
62 static const int ABYSSAL_RUNE_MIN_LEVEL = 3;
63
64 abyss_state abyssal_state;
65
66 static ProceduralLayout *abyssLayout = nullptr, *levelLayout = nullptr;
67
68 typedef priority_queue<ProceduralSample, vector<ProceduralSample>, ProceduralSamplePQCompare> sample_queue;
69
70 static sample_queue abyss_sample_queue;
71 static vector<dungeon_feature_type> abyssal_features;
72 static list<monster*> displaced_monsters;
73
74 static void abyss_area_shift(void);
75 static void _push_items(void);
76
77 // If not_seen is true, don't place the feature where it can be seen from
78 // the centre.  Returns the chosen location, or INVALID_COORD if it
79 // could not be placed.
80 static coord_def _place_feature_near(const coord_def &centre,
81                                      int radius,
82                                      dungeon_feature_type candidate,
83                                      dungeon_feature_type replacement,
84                                      int tries, bool not_seen = false)
85 {
86     coord_def cp = INVALID_COORD;
87     const int radius2 = radius * radius + 1;
88     for (int i = 0; i < tries; ++i)
89     {
90         cp = centre + coord_def(random_range(-radius, radius),
91                                 random_range(-radius, radius));
92
93         if (cp == centre || (cp - centre).abs() > radius2 || !in_bounds(cp))
94             continue;
95
96         if (not_seen && cell_see_cell_nocache(cp, centre))
97             continue;
98
99         if (grd(cp) == candidate)
100         {
101             dprf("Placing %s at (%d,%d)",
102                  dungeon_feature_name(replacement),
103                  cp.x, cp.y);
104             grd(cp) = replacement;
105             return cp;
106         }
107     }
108     return INVALID_COORD;
109 }
110
111 // Returns a feature suitable for use in the proto-Abyss level.
112 static dungeon_feature_type _abyss_proto_feature()
113 {
114     return random_choose_weighted(3000, DNGN_FLOOR,
115                                    600, DNGN_ROCK_WALL,
116                                    300, DNGN_STONE_WALL,
117                                    100, DNGN_METAL_WALL,
118                                      1, DNGN_CLOSED_DOOR,
119                                      0);
120 }
121
122 static void _write_abyssal_features()
123 {
124     if (abyssal_features.empty())
125         return;
126
127     const int count = abyssal_features.size();
128     ASSERT(count == 213);
129     const int scalar = 0xFF;
130     int index = 0;
131     for (int x = -LOS_RADIUS; x <= LOS_RADIUS; x++)
132     {
133         for (int y = -LOS_RADIUS; y <= LOS_RADIUS; y++)
134         {
135             coord_def p(x, y);
136             const int dist = p.abs();
137             if (dist > LOS_RADIUS * LOS_RADIUS + 1)
138                 continue;
139             p += ABYSS_CENTRE;
140
141             int chance = pow(0.98, dist) * scalar;
142             if (!map_masked(p, MMT_VAULT))
143             {
144                 if (dist < 4 || x_chance_in_y(chance, scalar))
145                 {
146                     if (abyssal_features[index] != DNGN_UNSEEN)
147                     {
148                         grd(p) = abyssal_features[index];
149                         env.level_map_mask(p) = MMT_VAULT;
150                     }
151                 }
152                 else
153                 {
154                     //Entombing the player is lame.
155                     grd(p) = DNGN_FLOOR;
156                 }
157             }
158
159             ++index;
160         }
161     }
162
163     _push_items();
164     abyssal_features.clear();
165 }
166
167 // Returns the roll to use to check if we want to create an abyssal rune.
168 static int _abyssal_rune_roll()
169 {
170     if (you.runes[RUNE_ABYSSAL] || you.depth < ABYSSAL_RUNE_MIN_LEVEL)
171         return -1;
172     const bool lugonu_favoured =
173         (you.religion == GOD_LUGONU && !player_under_penance()
174          && you.piety >= piety_breakpoint(4));
175
176     const double depth = you.depth + lugonu_favoured;
177
178     return (int) pow(100.0, depth/(1 + brdepth[BRANCH_ABYSS]));
179 }
180
181 static void _abyss_fixup_vault(const vault_placement *vp)
182 {
183     for (vault_place_iterator vi(*vp); vi; ++vi)
184     {
185         const coord_def p(*vi);
186         const dungeon_feature_type feat(grd(p));
187         if (feat_is_stair(feat)
188             && feat != DNGN_EXIT_ABYSS
189             && feat != DNGN_ENTER_PORTAL_VAULT)
190         {
191             grd(p) = DNGN_FLOOR;
192         }
193
194         tile_init_flavour(p);
195     }
196 }
197
198 static bool _abyss_place_map(const map_def *mdef)
199 {
200     // This is to prevent the player position from being updated by vaults
201     // until after everything is done.
202     unwind_bool gen(Generating_Level, true);
203
204     const bool did_place = dgn_safe_place_map(mdef, true, false, INVALID_COORD);
205     if (did_place)
206         _abyss_fixup_vault(env.level_vaults[env.level_vaults.size() - 1]);
207
208     return did_place;
209 }
210
211 static bool _abyss_place_vault_tagged(const map_bitmask &abyss_genlevel_mask,
212                                       const string &tag)
213 {
214     const map_def *map = random_map_for_tag(tag, false, true);
215     if (map)
216     {
217         unwind_vault_placement_mask vaultmask(&abyss_genlevel_mask);
218         return _abyss_place_map(map);
219     }
220     return false;
221 }
222
223 static void _abyss_postvault_fixup()
224 {
225     fixup_misplaced_items();
226     link_items();
227     env.markers.activate_all();
228 }
229
230 static bool _abyss_place_rune_vault(const map_bitmask &abyss_genlevel_mask)
231 {
232     // Make sure we're not about to link bad items.
233     debug_item_scan();
234
235     const bool result = _abyss_place_vault_tagged(abyss_genlevel_mask,
236                                                   "abyss_rune");
237
238     // Make sure the rune is linked.
239     _abyss_postvault_fixup();
240     return result;
241 }
242
243 static bool _abyss_place_rune(const map_bitmask &abyss_genlevel_mask,
244                               bool use_vaults)
245 {
246     // Use a rune vault if there's one.
247     if (use_vaults && _abyss_place_rune_vault(abyss_genlevel_mask))
248         return true;
249
250     coord_def chosen_spot;
251     int places_found = 0;
252
253     // Pick a random spot to drop the rune. We specifically do not use
254     // random_in_bounds and similar, because we may be dealing with a
255     // non-rectangular region, and we want to place the rune fairly.
256     for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
257     {
258         const coord_def p(*ri);
259         if (abyss_genlevel_mask(p)
260             && grd(p) == DNGN_FLOOR && igrd(p) == NON_ITEM
261             && one_chance_in(++places_found))
262         {
263             chosen_spot = p;
264         }
265     }
266
267     if (places_found)
268     {
269         dprf("Placing abyssal rune at (%d,%d)", chosen_spot.x, chosen_spot.y);
270         int thing_created = items(1, OBJ_MISCELLANY,
271                                   MISC_RUNE_OF_ZOT, true, 0, 0);
272         if (thing_created != NON_ITEM)
273         {
274             mitm[thing_created].plus = RUNE_ABYSSAL;
275             item_colour(mitm[thing_created]);
276         }
277         move_item_to_grid(&thing_created, chosen_spot);
278         return (thing_created != NON_ITEM);
279     }
280
281     return false;
282 }
283
284 // Returns true if items can be generated on the given square.
285 static bool _abyss_square_accepts_items(const map_bitmask &abyss_genlevel_mask,
286                                         coord_def p)
287 {
288     return (abyss_genlevel_mask(p)
289             && grd(p) == DNGN_FLOOR
290             && igrd(p) == NON_ITEM
291             && !map_masked(p, MMT_VAULT));
292 }
293
294 static int _abyss_create_items(const map_bitmask &abyss_genlevel_mask,
295                                bool placed_abyssal_rune,
296                                bool use_vaults)
297 {
298     // During game start, number and level of items mustn't be higher than
299     // that on level 1.
300     int num_items = 150, items_level = 52;
301     int items_placed = 0;
302
303     if (you.char_direction == GDT_GAME_START)
304     {
305         num_items   = 3 + roll_dice(3, 11);
306         items_level = 0;
307     }
308
309     const int abyssal_rune_roll = _abyssal_rune_roll();
310     bool should_place_abyssal_rune = false;
311     vector<coord_def> chosen_item_places;
312     for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
313     {
314         if (_abyss_square_accepts_items(abyss_genlevel_mask, *ri))
315         {
316             if (items_placed < num_items && one_chance_in(200))
317             {
318                 // [ds] Don't place abyssal rune in this loop to avoid
319                 // biasing rune placement toward the north-west of the
320                 // abyss level. Instead, make a note of whether we
321                 // decided to place the abyssal rune at all, and if we
322                 // did, place it randomly somewhere in the map at the
323                 // end of the item-gen pass. We may as a result create
324                 // (num_items + 1) items instead of num_items, which
325                 // is acceptable.
326                 if (!placed_abyssal_rune && !should_place_abyssal_rune
327                     && abyssal_rune_roll != -1
328                     && you.char_direction != GDT_GAME_START
329                     && x_chance_in_y(abyssal_rune_roll, ABYSSAL_RUNE_MAX_ROLL))
330                 {
331                     should_place_abyssal_rune = true;
332                 }
333
334                 chosen_item_places.push_back(*ri);
335             }
336         }
337     }
338
339     if (!placed_abyssal_rune && should_place_abyssal_rune)
340     {
341         if (_abyss_place_rune(abyss_genlevel_mask, use_vaults))
342             ++items_placed;
343     }
344
345     for (int i = 0, size = chosen_item_places.size(); i < size; ++i)
346     {
347         const coord_def place(chosen_item_places[i]);
348         if (_abyss_square_accepts_items(abyss_genlevel_mask, place))
349         {
350             int thing_created = items(1, OBJ_RANDOM, OBJ_RANDOM,
351                                       true, items_level, 250);
352             move_item_to_grid(&thing_created, place);
353             if (thing_created != NON_ITEM)
354             {
355                 items_placed++;
356                 if (one_chance_in(ITEM_MIMIC_CHANCE))
357                     mitm[thing_created].flags |= ISFLAG_MIMIC;
358             }
359         }
360     }
361
362     return items_placed;
363 }
364
365 void push_features_to_abyss()
366 {
367     abyssal_features.clear();
368
369     for (int x = -LOS_RADIUS; x <= LOS_RADIUS; x++)
370     {
371         for (int y = -LOS_RADIUS; y <= LOS_RADIUS; y++)
372         {
373             coord_def p(x, y);
374             if (p.abs() > LOS_RADIUS * LOS_RADIUS + 1)
375                 continue;
376
377             p += you.pos();
378
379             dungeon_feature_type feature = map_bounds(p) ? grd(p) : DNGN_UNSEEN;
380             feature = sanitize_feature(feature);
381                  abyssal_features.push_back(feature);
382         }
383     }
384 }
385
386 static bool _abyss_check_place_feat(coord_def p,
387                                     const int feat_chance,
388                                     int *feats_wanted,
389                                     bool *use_map,
390                                     dungeon_feature_type which_feat,
391                                     const map_bitmask &abyss_genlevel_mask)
392 {
393     if (!which_feat)
394         return false;
395
396     const bool place_feat = feat_chance && one_chance_in(feat_chance);
397
398     if (place_feat && feats_wanted)
399         ++*feats_wanted;
400
401     // Don't place features in bubbles.
402     int wall_count = 0;
403     for (adjacent_iterator ai(p); ai; ++ai)
404         wall_count += feat_is_solid(grd(p));
405     if (wall_count > 6)
406         return false;
407
408     // There's no longer a need to check for features under items,
409     // since we're working on fresh grids that are guaranteed
410     // item-free.
411     if (place_feat || (feats_wanted && *feats_wanted > 0))
412     {
413         dprf("Placing abyss feature: %s.", dungeon_feature_name(which_feat));
414
415         // When placing Abyss exits, try to use a vault if we have one.
416         if (which_feat == DNGN_EXIT_ABYSS
417             && use_map && *use_map
418             && _abyss_place_vault_tagged(abyss_genlevel_mask, "abyss_exit"))
419         {
420             *use_map = false;
421
422             // Link the vault-placed items.
423             _abyss_postvault_fixup();
424         }
425         else
426             grd(p) = which_feat;
427
428         if (feats_wanted)
429             --*feats_wanted;
430         return true;
431     }
432     return false;
433 }
434
435 static dungeon_feature_type _abyss_pick_altar()
436 {
437     // Lugonu has a flat 50% chance of corrupting the altar.
438     if (coinflip())
439         return DNGN_ALTAR_LUGONU;
440
441     god_type god;
442
443     do
444         god = random_god();
445     while (is_good_god(god));
446
447     return altar_for_god(god);
448 }
449
450 static bool _abyssal_rune_at(const coord_def p)
451 {
452     for (stack_iterator si(p); si; ++si)
453         if (item_is_rune(*si, RUNE_ABYSSAL))
454             return true;
455     return false;
456 }
457
458 class xom_abyss_feature_amusement_check
459 {
460 private:
461     bool exit_was_near;
462     bool rune_was_near;
463
464 private:
465     bool abyss_exit_nearness() const
466     {
467         // env.map_knowledge().known() doesn't work on unmappable levels because
468         // mapping flags are not set on such levels.
469         for (radius_iterator ri(you.pos(), LOS_RADIUS); ri; ++ri)
470             if (grd(*ri) == DNGN_EXIT_ABYSS && env.map_knowledge(*ri).seen())
471                 return true;
472
473         return false;
474     }
475
476     bool abyss_rune_nearness() const
477     {
478         // See above comment about env.map_knowledge().known().
479         for (radius_iterator ri(you.pos(), LOS_RADIUS); ri; ++ri)
480             if (env.map_knowledge(*ri).seen() && _abyssal_rune_at(*ri))
481                 return true;
482         return false;
483     }
484
485 public:
486     xom_abyss_feature_amusement_check()
487     {
488         exit_was_near = abyss_exit_nearness();
489         rune_was_near = abyss_rune_nearness();
490     }
491
492     // If the player was almost to the exit when it disappeared, Xom
493     // is extremely amused. He's also extremely amused if the player
494     // winds up right next to an exit when there wasn't one there
495     // before. The same applies to Abyssal runes.
496     ~xom_abyss_feature_amusement_check()
497     {
498         // Update known terrain
499         viewwindow();
500
501         const bool exit_is_near = abyss_exit_nearness();
502         const bool rune_is_near = abyss_rune_nearness();
503
504         if (exit_was_near && !exit_is_near || rune_was_near && !rune_is_near)
505             xom_is_stimulated(200, "Xom snickers loudly.", true);
506
507         if (!rune_was_near && rune_is_near || !exit_was_near && exit_is_near)
508             xom_is_stimulated(200);
509     }
510 };
511
512 static void _abyss_lose_monster(monster& mons)
513 {
514     if (mons.needs_abyss_transit())
515         mons.set_transit(level_id(BRANCH_ABYSS));
516
517     mons.destroy_inventory();
518     monster_cleanup(&mons);
519 }
520
521 // If a sanctuary exists and is in LOS, moves it to keep it in the
522 // same place relative to the player's location after a shift. If the
523 // sanctuary is not in player LOS, removes it.
524 static void _abyss_move_sanctuary(const coord_def abyss_shift_start_centre,
525                                   const coord_def abyss_shift_end_centre)
526 {
527     if (env.sanctuary_time > 0 && in_bounds(env.sanctuary_pos))
528     {
529         if (you.see_cell(env.sanctuary_pos))
530         {
531             env.sanctuary_pos += (abyss_shift_end_centre -
532                                   abyss_shift_start_centre);
533         }
534         else
535             remove_sanctuary(false);
536     }
537 }
538
539 static void _push_displaced_monster(monster* mon)
540 {
541     displaced_monsters.push_back(mon);
542 }
543
544 static void _place_displaced_monsters()
545 {
546     list<monster*>::iterator mon_itr;
547
548     for (mon_itr = displaced_monsters.begin();
549          mon_itr != displaced_monsters.end(); ++mon_itr)
550     {
551         monster* mon = *mon_itr;
552         if (mon->alive() && !mon->find_home_near_place(mon->pos()))
553         {
554             maybe_bloodify_square(mon->pos());
555             if (you.can_see(mon))
556             {
557                 simple_monster_message(mon, " is pulled into the abyss.",
558                         MSGCH_BANISHMENT);
559             }
560             _abyss_lose_monster(*mon);
561
562         }
563     }
564
565     displaced_monsters.clear();
566 }
567
568 static bool _pushy_feature(dungeon_feature_type feat)
569 {
570     // Only completely impassible features and lava will push items.
571     // In particular, deep water will not push items, because the item
572     // will eventually become accessible again through abyss morphing.
573
574     // Perhaps this should instead be merged with (the complement of)
575     // _item_safe_square() in terrain.cc.  Unlike this function, that
576     // one treats traps as unsafe, but closed doors as safe.
577     return (feat_is_solid(feat) || feat == DNGN_LAVA);
578 }
579
580 static void _push_items()
581 {
582     for (int i = 0; i < MAX_ITEMS; i++)
583     {
584         item_def& item(mitm[i]);
585         if (!item.defined() || !in_bounds(item.pos) || item.held_by_monster())
586             continue;
587
588         if (!_pushy_feature(grd(item.pos)))
589             continue;
590
591         for (distance_iterator di(item.pos); di; ++di)
592             if (!_pushy_feature(grd(*di)))
593             {
594                 move_item_to_grid(&i, *di, true);
595                 break;
596             }
597     }
598 }
599
600 // Deletes everything on the level at the given position.
601 // Things that are wiped:
602 // 1. Dungeon terrain (set to DNGN_UNSEEN)
603 // 2. Monsters (the player is unaffected)
604 // 3. Items
605 // 4. Clouds
606 // 5. Terrain properties
607 // 6. Terrain colours
608 // 7. Vault (map) mask
609 // 8. Vault id mask
610 // 9. Map markers
611
612 static void _abyss_wipe_square_at(coord_def p, bool saveMonsters=false)
613 {
614     // Nuke terrain.
615     destroy_shop_at(p);
616     destroy_trap(p);
617
618     // Nuke vault flag.
619     if (map_masked(p, MMT_VAULT))
620         env.level_map_mask(p) &= ~MMT_VAULT;
621
622     grd(p) = DNGN_UNSEEN;
623
624     // Nuke items.
625     if (igrd(p) != NON_ITEM)
626         dprf(DIAG_ABYSS, "Nuke item stack at (%d, %d)", p.x, p.y);
627     lose_item_stack(p);
628
629     // Nuke monster.
630     if (monster* mon = monster_at(p))
631     {
632         if (saveMonsters)
633             _push_displaced_monster(mon);
634         else
635             _abyss_lose_monster(*mon);
636     }
637
638     // Delete cloud.
639     delete_cloud_at(p);
640
641     env.pgrid(p)        = 0;
642     env.grid_colours(p) = 0;
643 #ifdef USE_TILE
644     env.tile_bk_fg(p)   = 0;
645     env.tile_bk_bg(p)   = 0;
646     env.tile_bk_cloud(p)= 0;
647 #endif
648     tile_clear_flavour(p);
649     tile_init_flavour(p);
650
651     env.level_map_mask(p) = 0;
652     env.level_map_ids(p)  = INVALID_MAP_INDEX;
653
654     remove_markers_and_listeners_at(p);
655
656     env.map_knowledge(p).clear();
657     StashTrack.update_stash(p);
658 }
659
660 // Removes monsters, clouds, dungeon features, and items from the
661 // level, torching all squares for which the supplied mask is false.
662 static void _abyss_wipe_unmasked_area(const map_bitmask &abyss_preserve_mask)
663 {
664     for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
665         if (!abyss_preserve_mask(*ri))
666             _abyss_wipe_square_at(*ri);
667 }
668
669 // Moves everything at src to dst.
670 static void _abyss_move_entities_at(coord_def src, coord_def dst)
671 {
672     dgn_move_entities_at(src, dst, true, true, true);
673 }
674
675 // Move all vaults within the mask by the specified delta.
676 static void _abyss_move_masked_vaults_by_delta(const coord_def delta)
677 {
678     set<int> vault_indexes;
679     for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
680     {
681         const int vi = env.level_map_ids(*ri);
682         if (vi != INVALID_MAP_INDEX)
683             vault_indexes.insert(vi);
684     }
685
686     for (set<int>::const_iterator i = vault_indexes.begin();
687          i != vault_indexes.end(); ++i)
688     {
689         vault_placement &vp(*env.level_vaults[*i]);
690 #ifdef DEBUG_DIAGNOSTICS
691         const coord_def oldp = vp.pos;
692 #endif
693         vp.pos += delta;
694         dprf("Moved vault (%s) from (%d,%d)-(%d,%d)",
695              vp.map.name.c_str(), oldp.x, oldp.y, vp.pos.x, vp.pos.y);
696     }
697 }
698
699 // Moves the player, monsters, terrain and items in the square (circle
700 // in movement distance) around the player with the given radius to
701 // the square centred on target_centre.
702 //
703 // Assumes:
704 // a) target can be truncated if not fully in bounds
705 // b) source and target areas may overlap
706 //
707 static void _abyss_move_entities(coord_def target_centre,
708                                  map_bitmask *shift_area_mask)
709 {
710     const coord_def source_centre = you.pos();
711     const coord_def delta = (target_centre - source_centre).sgn();
712
713     // When moving a region, walk backward to handle overlapping
714     // ranges correctly.
715     coord_def direction = -delta;
716
717     if (!direction.x)
718         direction.x = 1;
719     if (!direction.y)
720         direction.y = 1;
721
722     coord_def start(MAPGEN_BORDER, MAPGEN_BORDER);
723     coord_def end(GXM - 1 - MAPGEN_BORDER, GYM - 1 - MAPGEN_BORDER);
724
725     if (direction.x == -1)
726         swap(start.x, end.x);
727     if (direction.y == -1)
728         swap(start.y, end.y);
729
730     end += direction;
731
732     for (int y = start.y; y != end.y; y += direction.y)
733     {
734         for (int x = start.x; x != end.x; x += direction.x)
735         {
736             const coord_def src(x, y);
737             if (!shift_area_mask->get(src))
738                 continue;
739
740             shift_area_mask->set(src, false);
741
742             const coord_def dst = src - source_centre + target_centre;
743             if (map_bounds_with_margin(dst, MAPGEN_BORDER))
744             {
745                 shift_area_mask->set(dst);
746                 // Wipe the dstination clean before dropping things on it.
747                 _abyss_wipe_square_at(dst);
748                 _abyss_move_entities_at(src, dst);
749             }
750             else
751             {
752                 // Wipe the source clean even if the dst is not in bounds.
753                 _abyss_wipe_square_at(src);
754             }
755         }
756     }
757
758     _abyss_move_masked_vaults_by_delta(target_centre - source_centre);
759 }
760
761 static void _abyss_expand_mask_to_cover_vault(map_bitmask *mask,
762                                               int map_index)
763 {
764     dprf("Expanding mask to cover vault %d (nvaults: %u)",
765          map_index, (unsigned int)env.level_vaults.size());
766     const vault_placement &vp = *env.level_vaults[map_index];
767     for (vault_place_iterator vpi(vp); vpi; ++vpi)
768         mask->set(*vpi);
769 }
770
771 // Identifies the smallest square around the given source that can be
772 // shifted without breaking up any vaults.
773 static void _abyss_identify_area_to_shift(coord_def source, int radius,
774                                           map_bitmask *mask)
775 {
776     mask->reset();
777
778     set<int> affected_vault_indexes;
779     for (radius_iterator ri(source, radius, C_SQUARE); ri; ++ri)
780     {
781         if (!map_bounds_with_margin(*ri, MAPGEN_BORDER))
782             continue;
783
784         mask->set(*ri);
785
786         const int map_index = env.level_map_ids(*ri);
787         if (map_index != INVALID_MAP_INDEX)
788             affected_vault_indexes.insert(map_index);
789     }
790
791     for (set<int>::const_iterator i = affected_vault_indexes.begin();
792          i != affected_vault_indexes.end(); ++i)
793     {
794         _abyss_expand_mask_to_cover_vault(mask, *i);
795     }
796 }
797
798 static void _abyss_invert_mask(map_bitmask *mask)
799 {
800     for (rectangle_iterator ri(0); ri; ++ri)
801         mask->set(*ri, !mask->get(*ri));
802 }
803
804 // Moves everything in the given radius around the player (where radius=0 =>
805 // only the player) to another part of the level, centred on target_centre.
806 // Everything not in the given radius is wiped to DNGN_UNSEEN and the provided
807 // map_bitmask is set to true for all wiped squares.
808 //
809 // Things that are moved:
810 // 1. Dungeon terrain
811 // 2. Actors (player + monsters)
812 // 3. Items
813 // 4. Clouds
814 // 5. Terrain properties
815 // 6. Terrain colours
816 // 7. Vaults
817 // 8. Vault (map) mask
818 // 9. Vault id mask
819 // 10. Map markers
820 //
821 // After the shift, any vaults that are no longer referenced in the id
822 // mask will be discarded. If those vaults had any unique tags or
823 // names, the tag/name will NOT be unregistered.
824 //
825 // Assumes:
826 // a) radius >= LOS_RADIUS
827 // b) All points in the source and target areas are in bounds.
828 static void _abyss_shift_level_contents_around_player(
829     int radius,
830     coord_def target_centre,
831     map_bitmask &abyss_destruction_mask)
832 {
833     const coord_def source_centre = you.pos();
834
835     abyssal_state.major_coord += (source_centre - ABYSS_CENTRE);
836
837     ASSERT(radius >= LOS_RADIUS);
838     // This should only really happen due to wizmode blink/movement.
839     // 1KB: ... yet at least Xom "swap with monster" triggers it.
840     //ASSERT(map_bounds_with_margin(source_centre, radius));
841     //ASSERT(map_bounds_with_margin(target_centre, radius));
842
843     _abyss_identify_area_to_shift(source_centre, radius,
844                                   &abyss_destruction_mask);
845
846     // Shift sanctuary centre if it's close.
847     _abyss_move_sanctuary(you.pos(), target_centre);
848
849     // Zap everything except the area we're shifting, so that there's
850     // nothing in the way of moving stuff.
851     _abyss_wipe_unmasked_area(abyss_destruction_mask);
852
853     // Move stuff to its new home. This will also move the player.
854     _abyss_move_entities(target_centre, &abyss_destruction_mask);
855
856     // [ds] Rezap everything except the shifted area. NOTE: the old
857     // code did not do this, leaving a repeated swatch of Abyss behind
858     // at the old location for every shift; discussions between Linley
859     // and dpeg on ##crawl confirm that this (repeated swatch of
860     // terrain left behind) was not intentional.
861     _abyss_wipe_unmasked_area(abyss_destruction_mask);
862
863     // So far we've used the mask to track the portions of the level we're
864     // preserving. The inverse of the mask represents the area to be filled
865     // with brand new abyss:
866     _abyss_invert_mask(&abyss_destruction_mask);
867
868     // Update env.level_vaults to discard any vaults that are no longer in
869     // the picture.
870     dgn_erase_unused_vault_placements();
871 }
872
873 static void _abyss_generate_monsters(int nmonsters)
874 {
875     if (crawl_state.disables[DIS_SPAWNS])
876         return;
877
878     mgen_data mg;
879     mg.proximity = PROX_ANYWHERE;
880
881     for (int mcount = 0; mcount < nmonsters; mcount++)
882     {
883         mg.cls = pick_random_monster(level_id::current());
884         if (!invalid_monster_type(mg.cls))
885             mons_place(mg);
886     }
887 }
888
889 static bool _abyss_teleport_within_level()
890 {
891     // Try to find a good spot within the shift zone.
892     for (int i = 0; i < 100; i++)
893     {
894         const coord_def newspot =
895             dgn_random_point_in_margin(MAPGEN_BORDER
896                                        + ABYSS_AREA_SHIFT_RADIUS
897                                        + 1);
898
899         if ((grd(newspot) == DNGN_FLOOR
900              || grd(newspot) == DNGN_SHALLOW_WATER)
901             && !monster_at(newspot)
902             && env.cgrid(newspot) == EMPTY_CLOUD)
903         {
904             dprf(DIAG_ABYSS, "Abyss same-area teleport to (%d,%d).",
905                  newspot.x, newspot.y);
906             you.moveto(newspot);
907             return true;
908         }
909     }
910     return false;
911 }
912
913 void maybe_shift_abyss_around_player()
914 {
915     ASSERT(player_in_branch(BRANCH_ABYSS));
916     if (map_bounds_with_margin(you.pos(),
917                                MAPGEN_BORDER + ABYSS_AREA_SHIFT_RADIUS + 1))
918     {
919         return;
920     }
921
922     dprf("Shifting abyss at (%d,%d)", you.pos().x, you.pos().y);
923
924     abyss_area_shift();
925     if (you.pet_target != MHITYOU)
926         you.pet_target = MHITNOT;
927
928 #ifdef DEBUG_DIAGNOSTICS
929     int j = 0;
930     for (int i = 0; i < MAX_ITEMS; ++i)
931         if (mitm[i].defined())
932             ++j;
933
934     dprf("Number of items present: %d", j);
935
936     j = 0;
937     for (monster_iterator mi; mi; ++mi)
938         ++j;
939
940     dprf("Number of monsters present: %d", j);
941     dprf("Number of clouds present: %d", env.cloud_no);
942 #endif
943 }
944
945 void save_abyss_uniques()
946 {
947     for (monster_iterator mi; mi; ++mi)
948         if (mi->needs_abyss_transit()
949             && !testbits(mi->flags, MF_TAKING_STAIRS))
950         {
951             mi->set_transit(level_id(BRANCH_ABYSS));
952         }
953 }
954
955 static bool _in_wastes(const coord_def &p)
956 {
957     return (p.x > 0 && p.x < 0x7FFFFFF && p.y > 0 && p.y < 0x7FFFFFF);
958 }
959
960 static level_id _get_real_level()
961 {
962     push_rng_state();
963     seed_rng(abyssal_state.seed);
964     vector<level_id> levels;
965     for (int i = BRANCH_MAIN_DUNGEON; i < NUM_BRANCHES; ++i)
966     {
967         if (i == BRANCH_SHOALS || i == BRANCH_ABYSS)
968             continue;
969         for (int j = 0; j < brdepth[i]; ++j)
970         {
971             const level_id id(static_cast<branch_type>(i), j);
972             if (is_existing_level(id))
973                 levels.push_back(id);
974         }
975     }
976     if (levels.empty())
977     {
978         // Let this fail later on.
979         return level_id(static_cast<branch_type>(BRANCH_MAIN_DUNGEON), 1);
980     }
981     int pick = random2(levels.size());
982     pop_rng_state();
983     return levels[pick];
984 }
985
986 /**************************************************************/
987 /* Fixed layouts (ie, those that depend only on abyss coords) */
988 /**************************************************************/
989 const static WastesLayout wastes;
990 const static DiamondLayout diamond30(3,0);
991 const static DiamondLayout diamond21(2,1);
992 const static ColumnLayout column2(2);
993 const static ColumnLayout column26(2,6);
994 const static ProceduralLayout* regularLayouts[] =
995 {
996     &diamond30, &diamond21, &column2, &column26,
997 };
998 const static vector<const ProceduralLayout*> layout_vec(regularLayouts,
999     regularLayouts + 5);
1000 const static WorleyLayout worleyL(123456, layout_vec);
1001 const static RoilingChaosLayout chaosA(8675309, 450);
1002 const static RoilingChaosLayout chaosB(7654321, 400);
1003 const static RoilingChaosLayout chaosC(24324,   380);
1004 const static RoilingChaosLayout chaosD(24816,   500);
1005 const static NewAbyssLayout newAbyssLayout(7629);
1006 const static ProceduralLayout* mixedLayouts[] =
1007 {
1008     &chaosA, &worleyL, &chaosB, &chaosC, &chaosD, &newAbyssLayout,
1009 };
1010 const static vector<const ProceduralLayout*> mixed_vec(mixedLayouts, mixedLayouts + 6);
1011 const static WorleyLayout layout(4321, mixed_vec);
1012 const static ProceduralLayout* baseLayouts[] = { &newAbyssLayout, &layout };
1013 const static vector<const ProceduralLayout*> base_vec(baseLayouts, baseLayouts + 2);
1014 const static WorleyLayout baseLayout(314159, base_vec, 5.0);
1015 const static RiverLayout rivers(1800, baseLayout);
1016 // This one is not fixed: [0] is a level pulled from the current game
1017 static vector<const ProceduralLayout*> complex_vec(2);
1018
1019 static ProceduralSample _abyss_grid(const coord_def &p)
1020 {
1021     const coord_def pt = p + abyssal_state.major_coord;
1022
1023     if (_in_wastes(pt))
1024     {
1025         ProceduralSample sample = wastes(pt, abyssal_state.depth);
1026         abyss_sample_queue.push(sample);
1027         return sample;
1028     }
1029
1030     if (abyssLayout == NULL)
1031     {
1032         const level_id lid = _get_real_level();
1033         levelLayout = new LevelLayout(lid, 5, rivers);
1034         complex_vec[0] = levelLayout;
1035         complex_vec[1] = &rivers; // const
1036         abyssLayout = new WorleyLayout(23571113, complex_vec, 6.1);
1037     }
1038
1039     const ProceduralSample sample = (*abyssLayout)(pt, abyssal_state.depth);
1040     ASSERT(sample.feat() > DNGN_UNSEEN);
1041
1042     abyss_sample_queue.push(sample);
1043     return sample;
1044 }
1045
1046 static cloud_type _cloud_from_feat(const dungeon_feature_type &ft)
1047 {
1048     switch (ft)
1049     {
1050         case DNGN_CLOSED_DOOR:
1051         case DNGN_METAL_WALL:
1052             return CLOUD_GREY_SMOKE;
1053         case DNGN_GREEN_CRYSTAL_WALL:
1054         case DNGN_ROCK_WALL:
1055         case DNGN_SLIMY_WALL:
1056         case DNGN_STONE_WALL:
1057         case DNGN_PERMAROCK_WALL:
1058             return (coinflip() ? CLOUD_BLUE_SMOKE : CLOUD_PURPLE_SMOKE);
1059         case DNGN_CLEAR_ROCK_WALL:
1060         case DNGN_CLEAR_STONE_WALL:
1061         case DNGN_CLEAR_PERMAROCK_WALL:
1062         case DNGN_GRATE:
1063             return CLOUD_MIST;
1064         case DNGN_ORCISH_IDOL:
1065         case DNGN_GRANITE_STATUE:
1066         case DNGN_LAVA:
1067             return CLOUD_BLACK_SMOKE;
1068         case DNGN_DEEP_WATER:
1069         case DNGN_SHALLOW_WATER:
1070         case DNGN_FOUNTAIN_BLUE:
1071             return (one_chance_in(5) ? CLOUD_RAIN : CLOUD_BLUE_SMOKE);
1072         case DNGN_FOUNTAIN_SPARKLING:
1073             return CLOUD_RAIN;
1074         default:
1075             return CLOUD_NONE;
1076     }
1077 }
1078
1079 static dungeon_feature_type _veto_dangerous_terrain(dungeon_feature_type feat)
1080 {
1081     if (feat == DNGN_DEEP_WATER)
1082         return DNGN_SHALLOW_WATER;
1083     if (feat == DNGN_LAVA)
1084         return DNGN_FLOOR;
1085
1086     return feat;
1087 }
1088
1089 static void _update_abyss_terrain(const coord_def &p,
1090     const map_bitmask &abyss_genlevel_mask, bool morph)
1091 {
1092     const coord_def rp = p - abyssal_state.major_coord;
1093     // ignore dead coordinates
1094     if (!in_bounds(rp))
1095         return;
1096
1097     const dungeon_feature_type currfeat = grd(rp);
1098
1099     // Don't decay vaults.
1100     if (map_masked(rp, MMT_VAULT))
1101         return;
1102
1103     switch (currfeat)
1104     {
1105         case DNGN_EXIT_ABYSS:
1106         case DNGN_ABYSSAL_STAIR:
1107             return;
1108         default:
1109             break;
1110     }
1111
1112     if (feat_is_altar(currfeat))
1113         return;
1114
1115     if (!abyss_genlevel_mask(rp))
1116         return;
1117
1118     if (currfeat != DNGN_UNSEEN && !morph)
1119         return;
1120
1121     // What should have been there previously?  It might not be because
1122     // of external changes such as digging.
1123     const ProceduralSample sample = _abyss_grid(rp);
1124
1125     // Enqueue the update, but don't morph.
1126     if (_abyssal_rune_at(rp))
1127         return;
1128
1129     dungeon_feature_type feat = sample.feat();
1130
1131     // Don't replace open doors with closed doors!
1132     if (feat_is_door(currfeat) && feat_is_door(feat))
1133         return;
1134
1135     // Veto dangerous terrain.
1136     if (you.pos() == rp)
1137         feat = _veto_dangerous_terrain(feat);
1138
1139     // If the selected grid is already there, *or* if we're morphing and
1140     // the selected grid should have been there, do nothing.
1141     if (feat != currfeat)
1142     {
1143         grd(rp) = feat;
1144         if (feat == DNGN_FLOOR && in_los_bounds_g(rp))
1145         {
1146             cloud_type cloud = _cloud_from_feat(currfeat);
1147             int cloud_life = (_in_wastes(abyssal_state.major_coord) ? 5 : 2) + random2(2);
1148             if (cloud != CLOUD_NONE)
1149                 check_place_cloud(_cloud_from_feat(currfeat), rp, cloud_life, 0, 3);
1150         }
1151         monster* mon = monster_at(rp);
1152         if (mon && !monster_habitable_grid(mon, feat))
1153             _push_displaced_monster(mon);
1154     }
1155 }
1156
1157 static int _abyssal_stair_chance()
1158 {
1159     return (you.char_direction == GDT_GAME_START ? 0 : 3500 - (200 * you.depth / 3));
1160 }
1161
1162 static void _nuke_all_terrain(bool vaults)
1163 {
1164     for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
1165     {
1166         if (vaults && env.level_map_mask(*ri) & MMT_VAULT)
1167             continue;
1168         env.level_map_mask(*ri) = MMT_NUKED;
1169     }
1170 }
1171
1172 static void _abyss_apply_terrain(const map_bitmask &abyss_genlevel_mask,
1173                                  bool morph = false, bool now = false)
1174 {
1175     // The chance is reciprocal to these numbers.
1176     const int exit_chance = you.runes[RUNE_ABYSSAL] ? 1250
1177                             : 7500 - 1250 * (you.depth - 1);
1178
1179     // Except for the altar on the starting position, don't place any altars.
1180     const int altar_chance = you.char_direction != GDT_GAME_START? 10000 : 0;
1181
1182     int exits_wanted  = 0;
1183     int altars_wanted = 0;
1184     bool use_abyss_exit_map = true;
1185     bool used_queue = false;
1186     if (morph && !abyss_sample_queue.empty())
1187     {
1188         int ii = 0;
1189         used_queue = true;
1190         while (!abyss_sample_queue.empty()
1191             && abyss_sample_queue.top().changepoint() < abyssal_state.depth)
1192         {
1193             ++ii;
1194             coord_def p = abyss_sample_queue.top().coord();
1195             _update_abyss_terrain(p, abyss_genlevel_mask, morph);
1196             abyss_sample_queue.pop();
1197         }
1198 /*
1199         if (ii)
1200             dprf(DIAG_ABYSS, "Examined %d features.", ii);
1201 */
1202     }
1203
1204     int ii = 0;
1205     int delta = you.time_taken * (you.abyss_speed + 40) / 200;
1206     for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
1207     {
1208         const coord_def p(*ri);
1209         const coord_def abyss_coord = p + abyssal_state.major_coord;
1210         bool nuked = map_masked(p, MMT_NUKED);
1211         if (used_queue && !nuked)
1212             continue;
1213
1214         if (nuked && (now || x_chance_in_y(delta, 50)) || !nuked && !used_queue)
1215         {
1216             ++ii;
1217             _update_abyss_terrain(abyss_coord, abyss_genlevel_mask, morph);
1218             env.level_map_mask(p) &= ~MMT_NUKED;
1219         }
1220         if (morph)
1221             continue;
1222
1223         // Place abyss exits, stone arches, and altars to liven up the scene
1224         // (only on area creation, not on morphing).
1225         (_abyss_check_place_feat(p, exit_chance,
1226                                 &exits_wanted,
1227                                 &use_abyss_exit_map,
1228                                 DNGN_EXIT_ABYSS,
1229                                 abyss_genlevel_mask)
1230         ||
1231         _abyss_check_place_feat(p, altar_chance,
1232                                 &altars_wanted,
1233                                 NULL,
1234                                 _abyss_pick_altar(),
1235                                 abyss_genlevel_mask)
1236         ||
1237         (level_id::current().depth < brdepth[BRANCH_ABYSS] &&
1238         _abyss_check_place_feat(p, _abyssal_stair_chance(), NULL, NULL,
1239                                 DNGN_ABYSSAL_STAIR,
1240                                 abyss_genlevel_mask)));
1241     }
1242     if (ii)
1243         dprf(DIAG_ABYSS, "Nuked %d features", ii);
1244     dungeon_feature_type feat = grd(you.pos());
1245     if (!you.can_pass_through_feat(feat) || is_feat_dangerous(feat))
1246     {
1247         bool shoved = you.shove();
1248         ASSERT(shoved);
1249     }
1250     for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
1251         ASSERT_RANGE(grd(*ri), DNGN_UNSEEN + 1, NUM_FEATURES);
1252 }
1253
1254 static int _abyss_place_vaults(const map_bitmask &abyss_genlevel_mask)
1255 {
1256     unwind_vault_placement_mask vaultmask(&abyss_genlevel_mask);
1257
1258     int vaults_placed = 0;
1259
1260     const int maxvaults = 6;
1261     int tries = 0;
1262     while (vaults_placed < maxvaults)
1263     {
1264         const map_def *map = random_map_for_tag("abyss", false, true);
1265         if (!map)
1266             break;
1267
1268         if (!_abyss_place_map(map) || map->has_tag("extra"))
1269         {
1270             if (tries++ >= 100)
1271                 break;
1272
1273             continue;
1274         }
1275
1276         if (!one_chance_in(2 + (++vaults_placed)))
1277             break;
1278     }
1279
1280     return vaults_placed;
1281 }
1282
1283 static void _generate_area(const map_bitmask &abyss_genlevel_mask)
1284 {
1285     // Any rune on the floor prevents the abyssal rune from being generated.
1286     const bool placed_abyssal_rune =
1287         find_floor_item(OBJ_MISCELLANY, MISC_RUNE_OF_ZOT);
1288
1289     dprf(DIAG_ABYSS, "_generate_area(). turns_on_level: %d, rune_on_floor: %s",
1290          env.turns_on_level, placed_abyssal_rune? "yes" : "no");
1291
1292     _abyss_apply_terrain(abyss_genlevel_mask);
1293
1294     bool use_vaults = you.char_direction != GDT_GAME_START;
1295
1296     if (use_vaults)
1297     {
1298         // Make sure we're not about to link bad items.
1299         debug_item_scan();
1300         _abyss_place_vaults(abyss_genlevel_mask);
1301
1302         // Link the vault-placed items.
1303         _abyss_postvault_fixup();
1304     }
1305     _abyss_create_items(abyss_genlevel_mask, placed_abyssal_rune, use_vaults);
1306     setup_environment_effects();
1307
1308     // Abyss has a constant density.
1309     env.density = 0;
1310 }
1311
1312 static void _initialize_abyss_state()
1313 {
1314     abyssal_state.major_coord.x = random_int() & 0x7FFFFFFF;
1315     abyssal_state.major_coord.y = random_int() & 0x7FFFFFFF;
1316     abyssal_state.seed = random_int() & 0x7FFFFFFF;
1317     abyssal_state.phase = 0.0;
1318     abyssal_state.depth = random_int() & 0x7FFFFFFF;
1319     abyssal_state.nuke_all = false;
1320     abyss_sample_queue = sample_queue(ProceduralSamplePQCompare());
1321 }
1322
1323 void set_abyss_state(coord_def coord, uint32_t depth)
1324 {
1325     abyssal_state.major_coord = coord;
1326     abyssal_state.depth = depth;
1327     abyssal_state.seed = random_int() & 0x7FFFFFFF;
1328     abyssal_state.phase = 0.0;
1329     abyssal_state.nuke_all = true;
1330     abyss_sample_queue = sample_queue(ProceduralSamplePQCompare());
1331     you.moveto(ABYSS_CENTRE);
1332     map_bitmask abyss_genlevel_mask(true);
1333     _abyss_apply_terrain(abyss_genlevel_mask, true, true);
1334 }
1335
1336 static void abyss_area_shift(void)
1337 {
1338     dprf(DIAG_ABYSS, "area_shift() - player at pos (%d, %d)",
1339          you.pos().x, you.pos().y);
1340
1341     {
1342         xom_abyss_feature_amusement_check xomcheck;
1343
1344         // Use a map mask to track the areas that the shift destroys and
1345         // that must be regenerated by _generate_area.
1346         map_bitmask abyss_genlevel_mask;
1347         _abyss_shift_level_contents_around_player(
1348             ABYSS_AREA_SHIFT_RADIUS, ABYSS_CENTRE, abyss_genlevel_mask);
1349         forget_map(true);
1350         _generate_area(abyss_genlevel_mask);
1351
1352         // Update LOS at player's new abyssal vacation retreat.
1353         los_changed();
1354     }
1355
1356     // Place some monsters to keep the abyss party going.
1357     int num_monsters = 15 + you.depth * (1 + coinflip());
1358     _abyss_generate_monsters(num_monsters);
1359
1360     // And allow monsters in transit another chance to return.
1361     place_transiting_monsters();
1362     place_transiting_items();
1363
1364     check_map_validity();
1365 }
1366
1367 void destroy_abyss()
1368 {
1369     if (abyssLayout)
1370     {
1371         delete abyssLayout;
1372         abyssLayout = nullptr;
1373         delete levelLayout;
1374         levelLayout = nullptr;
1375     }
1376 }
1377
1378 static colour_t _roll_abyss_floor_colour()
1379 {
1380     return random_choose_weighted(
1381          108, BLUE,
1382          632, GREEN,
1383          // no CYAN (silence)
1384          932, RED,
1385          488, MAGENTA,
1386          433, BROWN,
1387         3438, LIGHTGRAY,
1388          // no DARKGREY (out of LOS)
1389          766, LIGHTBLUE,
1390          587, LIGHTGREEN,
1391          794, LIGHTCYAN,
1392          566, LIGHTRED,
1393          313, LIGHTMAGENTA,
1394          // no YELLOW (halo)
1395          890, WHITE,
1396           50, ETC_FIRE,
1397     0);
1398 }
1399
1400 static colour_t _roll_abyss_rock_colour()
1401 {
1402     return random_choose_weighted(
1403          130, BLUE,
1404          409, GREEN,
1405          // no CYAN (metal)
1406          770, RED,
1407          522, MAGENTA,
1408         1292, BROWN,
1409          // no LIGHTGRAY (stone)
1410          // no DARKGREY (out of LOS)
1411          570, LIGHTBLUE,
1412          705, LIGHTGREEN,
1413          // no LIGHTCYAN (glass)
1414         1456, LIGHTRED,
1415          377, LIGHTMAGENTA,
1416          105, YELLOW,
1417          101, WHITE,
1418           60, ETC_FIRE,
1419     0);
1420 }
1421
1422 static void _abyss_generate_new_area()
1423 {
1424     _initialize_abyss_state();
1425     dprf("Abyss Coord (%d, %d)", abyssal_state.major_coord.x, abyssal_state.major_coord.y);
1426     remove_sanctuary(false);
1427
1428     env.floor_colour = _roll_abyss_floor_colour();
1429     env.rock_colour = _roll_abyss_rock_colour();
1430     tile_init_flavour();
1431
1432     map_bitmask abyss_genlevel_mask;
1433     _abyss_wipe_unmasked_area(abyss_genlevel_mask);
1434     dgn_erase_unused_vault_placements();
1435
1436     you.moveto(ABYSS_CENTRE);
1437     abyss_genlevel_mask.init(true);
1438     _generate_area(abyss_genlevel_mask);
1439     if (one_chance_in(5))
1440     {
1441         _place_feature_near(you.pos(), LOS_RADIUS,
1442                             DNGN_FLOOR, DNGN_ALTAR_LUGONU, 50);
1443     }
1444
1445     los_changed();
1446     place_transiting_monsters();
1447     place_transiting_items();
1448 }
1449
1450 // Check if there is a path between the abyss centre and an exit location.
1451 static bool _abyss_has_path(const coord_def &to)
1452 {
1453     ASSERT(grd(to) == DNGN_EXIT_ABYSS);
1454
1455     monster_pathfind pf;
1456     return pf.init_pathfind(ABYSS_CENTRE, to);
1457 }
1458
1459 // Generate the initial (proto) Abyss level. The proto Abyss is where
1460 // the player lands when they arrive in the Abyss from elsewhere.
1461 // _generate_area generates all other Abyss areas.
1462 void generate_abyss()
1463 {
1464     env.level_build_method += " abyss";
1465     env.level_layout_types.insert("abyss");
1466     destroy_abyss();
1467
1468 retry:
1469     _initialize_abyss_state();
1470
1471     dprf("generate_abyss(); turn_on_level: %d", env.turns_on_level);
1472
1473     // Generate the initial abyss without vaults. Vaults are horrifying.
1474     _abyss_generate_new_area();
1475     _write_abyssal_features();
1476     map_bitmask abyss_genlevel_mask(true);
1477     _abyss_apply_terrain(abyss_genlevel_mask);
1478
1479     grd(you.pos()) = _veto_dangerous_terrain(grd(you.pos()));
1480
1481     for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
1482         ASSERT(grd(*ri) > DNGN_UNSEEN);
1483     check_map_validity();
1484
1485     // If we're starting out in the Abyss, make sure the starting grid is
1486     // an altar to Lugonu and there's an exit near-by.
1487     // Otherwise, we start out on floor and there's a chance there's an
1488     // altar near-by.
1489     if (you.char_direction == GDT_GAME_START)
1490     {
1491         grd(ABYSS_CENTRE) = DNGN_ALTAR_LUGONU;
1492         const coord_def eloc = _place_feature_near(ABYSS_CENTRE, LOS_RADIUS + 2,
1493                                                    DNGN_FLOOR, DNGN_EXIT_ABYSS,
1494                                                    50, true);
1495         // Now make sure there is a path from the abyss centre to the exit.
1496         // If for some reason an exit could not be placed, don't bother.
1497         if (eloc == INVALID_COORD || !_abyss_has_path(eloc))
1498             goto retry;
1499     }
1500     else
1501     {
1502         grd(ABYSS_CENTRE) = DNGN_FLOOR;
1503         if (one_chance_in(5))
1504         {
1505             _place_feature_near(ABYSS_CENTRE, LOS_RADIUS,
1506                                 DNGN_FLOOR, DNGN_ALTAR_LUGONU, 50);
1507         }
1508     }
1509
1510     setup_environment_effects();
1511 }
1512
1513 static void _increase_depth()
1514 {
1515     int delta = you.time_taken * (you.abyss_speed + 40) / 200;
1516     if (you.religion != GOD_CHEIBRIADOS || you.penance[GOD_CHEIBRIADOS])
1517         delta *= 2;
1518     if (you.duration[DUR_TELEPORT])
1519         delta *= 5;
1520     const double theta = abyssal_state.phase;
1521     double depth_change = delta * (0.2 + 2.8 * pow(sin(theta/2), 10.0));
1522     abyssal_state.depth += depth_change;
1523     abyssal_state.phase += delta / 100.0;
1524     if (abyssal_state.phase > M_PI)
1525         abyssal_state.phase -= M_PI;
1526 }
1527
1528 void abyss_morph(double duration)
1529 {
1530     if (abyssal_state.nuke_all)
1531     {
1532         _nuke_all_terrain(false);
1533         abyssal_state.nuke_all = false;
1534     }
1535     if (!player_in_branch(BRANCH_ABYSS))
1536         return;
1537     _increase_depth();
1538     map_bitmask abyss_genlevel_mask(true);
1539     dgn_erase_unused_vault_placements();
1540     _abyss_apply_terrain(abyss_genlevel_mask, true);
1541     _place_displaced_monsters();
1542     _push_items();
1543     los_changed();
1544 }
1545
1546 void abyss_teleport(bool new_area)
1547 {
1548     xom_abyss_feature_amusement_check xomcheck;
1549     if (!new_area)
1550     {
1551         _abyss_teleport_within_level();
1552         abyss_area_shift();
1553         _initialize_abyss_state();
1554         _nuke_all_terrain(true);
1555         forget_map(false);
1556         clear_excludes();
1557         more();
1558         return;
1559     }
1560
1561     dprf(DIAG_ABYSS, "New area Abyss teleport.");
1562     _abyss_generate_new_area();
1563     _write_abyssal_features();
1564     grd(you.pos()) = _veto_dangerous_terrain(grd(you.pos()));
1565     forget_map(false);
1566     clear_excludes();
1567     more();
1568 }
1569
1570 //////////////////////////////////////////////////////////////////////////////
1571 // Abyss effects in other levels, courtesy Lugonu.
1572
1573 struct corrupt_env
1574 {
1575     int rock_colour, floor_colour;
1576     corrupt_env(): rock_colour(BLACK), floor_colour(BLACK) { }
1577 };
1578
1579 static void _place_corruption_seed(const coord_def &pos, int duration)
1580 {
1581     env.markers.add(new map_corruption_marker(pos, duration));
1582     // Corruption markers don't need activation, though we might
1583     // occasionally miss other unactivated markers by clearing.
1584     env.markers.clear_need_activate();
1585 }
1586
1587 static void _initialise_level_corrupt_seeds(int power)
1588 {
1589     const int low = power * 40 / 100, high = power * 140 / 100;
1590     const int nseeds = random_range(-1, min(2 + power / 110, 4), 2);
1591
1592     const int aux_seed_radius = 4;
1593
1594     dprf("Placing %d corruption seeds (power: %d)", nseeds, power);
1595
1596     // The corruption centreed on the player is free.
1597     _place_corruption_seed(you.pos(), high + 300);
1598
1599     for (int i = 0; i < nseeds; ++i)
1600     {
1601         coord_def where;
1602         int tries = 100;
1603         while (tries-- > 0)
1604         {
1605             where = dgn_random_point_from(you.pos(), aux_seed_radius, 2);
1606             if (grd(where) == DNGN_FLOOR && !env.markers.find(where, MAT_ANY))
1607                 break;
1608             where.reset();
1609         }
1610
1611         if (!where.origin())
1612             _place_corruption_seed(where, random_range(low, high, 2) + 300);
1613     }
1614 }
1615
1616 static bool _incorruptible(monster_type mt)
1617 {
1618     return mons_is_abyssal_only(mt) || mons_class_holiness(mt) == MH_HOLY;
1619 }
1620
1621 // Create a corruption spawn at the given position. Returns false if further
1622 // monsters should not be placed near this spot (overcrowding), true if
1623 // more monsters can fit in.
1624 static bool _spawn_corrupted_servant_near(const coord_def &pos)
1625 {
1626     const beh_type beh =
1627         x_chance_in_y(100, 200 + you.skill(SK_INVOCATIONS, 25)) ? BEH_HOSTILE
1628         : BEH_NEUTRAL;
1629
1630     // [ds] No longer summon hostiles -- don't create the monster if
1631     // it would be hostile.
1632     if (beh == BEH_HOSTILE)
1633         return true;
1634
1635     // Thirty tries for a place.
1636     for (int i = 0; i < 30; ++i)
1637     {
1638         const int offsetX = random2avg(4, 3) + random2(3);
1639         const int offsetY = random2avg(4, 3) + random2(3);
1640         const coord_def p(pos.x + (coinflip()? offsetX : -offsetX),
1641                           pos.y + (coinflip()? offsetY : -offsetY));
1642         if (!in_bounds(p) || actor_at(p)
1643             || !feat_compatible(DNGN_FLOOR, grd(p)))
1644         {
1645             continue;
1646         }
1647
1648         monster_type mons = pick_monster(level_id(BRANCH_ABYSS), _incorruptible);
1649         ASSERT(mons);
1650         mgen_data mg(mons, beh, 0, 5, 0, p);
1651         mg.non_actor_summoner = "Lugonu's corruption";
1652         mg.place = BRANCH_ABYSS;
1653         return create_monster(mg);
1654     }
1655
1656     return false;
1657 }
1658
1659 static void _apply_corruption_effect(map_marker *marker, int duration)
1660 {
1661     if (!duration)
1662         return;
1663
1664     map_corruption_marker *cmark = dynamic_cast<map_corruption_marker*>(marker);
1665     if (cmark->duration < 1)
1666         return;
1667
1668     const int neffects = max(div_rand_round(duration, 5), 1);
1669
1670     for (int i = 0; i < neffects; ++i)
1671     {
1672         if (x_chance_in_y(cmark->duration, 4000)
1673             && !_spawn_corrupted_servant_near(cmark->pos))
1674         {
1675             break;
1676         }
1677     }
1678     cmark->duration -= duration;
1679 }
1680
1681 void run_corruption_effects(int duration)
1682 {
1683     vector<map_marker*> markers = env.markers.get_all(MAT_CORRUPTION_NEXUS);
1684
1685     for (int i = 0, size = markers.size(); i < size; ++i)
1686     {
1687         map_marker *mark = markers[i];
1688         if (mark->get_type() != MAT_CORRUPTION_NEXUS)
1689             continue;
1690
1691         _apply_corruption_effect(mark, duration);
1692     }
1693 }
1694
1695 static bool _is_grid_corruptible(const coord_def &c)
1696 {
1697     if (c == you.pos())
1698         return false;
1699
1700     const dungeon_feature_type feat = grd(c);
1701
1702     // Stairs and portals cannot be corrupted.
1703     if (feat_stair_direction(feat) != CMD_NO_CMD)
1704         return false;
1705
1706     switch (feat)
1707     {
1708     case DNGN_PERMAROCK_WALL:
1709     case DNGN_CLEAR_PERMAROCK_WALL:
1710         return false;
1711
1712     case DNGN_METAL_WALL:
1713     case DNGN_GREEN_CRYSTAL_WALL:
1714         return one_chance_in(4);
1715
1716     case DNGN_STONE_WALL:
1717     case DNGN_CLEAR_STONE_WALL:
1718         return one_chance_in(3);
1719
1720     case DNGN_ROCK_WALL:
1721     case DNGN_CLEAR_ROCK_WALL:
1722         return !one_chance_in(3);
1723
1724     default:
1725         return true;
1726     }
1727 }
1728
1729 // Returns true if the square has <= 4 traversable neighbours.
1730 static bool _is_crowded_square(const coord_def &c)
1731 {
1732     int neighbours = 0;
1733     for (int xi = -1; xi <= 1; ++xi)
1734         for (int yi = -1; yi <= 1; ++yi)
1735         {
1736             if (!xi && !yi)
1737                 continue;
1738
1739             const coord_def n(c.x + xi, c.y + yi);
1740             if (!in_bounds(n) || !feat_is_traversable(grd(n)))
1741                 continue;
1742
1743             if (++neighbours > 4)
1744                 return false;
1745         }
1746
1747     return true;
1748 }
1749
1750 // Returns true if the square has all opaque neighbours.
1751 static bool _is_sealed_square(const coord_def &c)
1752 {
1753     for (adjacent_iterator ai(c); ai; ++ai)
1754         if (!feat_is_opaque(grd(*ai)))
1755             return false;
1756
1757     return true;
1758 }
1759
1760 static void _corrupt_square(const corrupt_env &cenv, const coord_def &c)
1761 {
1762     // To prevent the destruction of, say, branch entries.
1763     bool preserve_feat = true;
1764     dungeon_feature_type feat = DNGN_UNSEEN;
1765     if (feat_altar_god(grd(c)) != GOD_NO_GOD)
1766     {
1767         // altars may be safely overwritten, ha!
1768         preserve_feat = false;
1769         if (!one_chance_in(3))
1770             feat = DNGN_ALTAR_LUGONU;
1771     }
1772     else
1773         feat = _abyss_proto_feature();
1774
1775     if (feat_is_trap(feat, true)
1776         || feat == DNGN_UNSEEN
1777         || (feat_is_traversable(grd(c)) && !feat_is_traversable(feat)
1778             && coinflip()))
1779     {
1780         feat = DNGN_FLOOR;
1781     }
1782
1783     if (feat_is_traversable(grd(c)) && !feat_is_traversable(feat)
1784         && _is_crowded_square(c))
1785     {
1786         return;
1787     }
1788
1789     if (!feat_is_traversable(grd(c)) && feat_is_traversable(feat)
1790         && _is_sealed_square(c))
1791     {
1792         return;
1793     }
1794
1795     if (feat == DNGN_EXIT_ABYSS)
1796         feat = DNGN_ENTER_ABYSS;
1797
1798     // If we are trying to place a wall on top of a creature or item, try to
1799     // move it aside. If this fails, simply place floor instead.
1800     actor* act = actor_at(c);
1801     if (feat_is_solid(feat) && (igrd(c) != NON_ITEM || act))
1802     {
1803         coord_def newpos;
1804         get_push_space(c, newpos, act, true);
1805         if (!newpos.origin())
1806         {
1807             move_items(c, newpos);
1808             if (act)
1809                 actor_at(c)->move_to_pos(newpos);
1810         }
1811         else
1812             feat = DNGN_FLOOR;
1813     }
1814
1815     dungeon_terrain_changed(c, feat, true, preserve_feat, true);
1816     if (feat == DNGN_ROCK_WALL)
1817         env.grid_colours(c) = cenv.rock_colour;
1818     else if (feat == DNGN_FLOOR)
1819         env.grid_colours(c) = cenv.floor_colour;
1820
1821     if (feat == DNGN_ROCK_WALL)
1822     {
1823         tileidx_t idx = tile_dngn_coloured(TILE_WALL_ABYSS,
1824                                            cenv.floor_colour);
1825         env.tile_flv(c).wall = idx + random2(tile_dngn_count(idx));
1826     }
1827     else if (feat == DNGN_FLOOR)
1828     {
1829         tileidx_t idx = tile_dngn_coloured(TILE_FLOOR_NERVES,
1830                                            cenv.floor_colour);
1831         env.tile_flv(c).floor = idx + random2(tile_dngn_count(idx));
1832     }
1833 }
1834
1835 static void _corrupt_level_features(const corrupt_env &cenv)
1836 {
1837     vector<coord_def> corrupt_seeds;
1838     vector<map_marker*> corrupt_markers =
1839         env.markers.get_all(MAT_CORRUPTION_NEXUS);
1840
1841     for (int i = 0, size = corrupt_markers.size(); i < size; ++i)
1842         corrupt_seeds.push_back(corrupt_markers[i]->pos);
1843
1844     for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
1845     {
1846         int idistance2 = GXM * GXM + GYM * GYM;
1847         for (int i = 0, size = corrupt_seeds.size(); i < size; ++i)
1848         {
1849             const int idist2 = (*ri - corrupt_seeds[i]).abs();
1850             if (idist2 < idistance2)
1851                 idistance2 = idist2;
1852         }
1853
1854         const int ground_zero_radius2 = 7;
1855
1856         // Corruption odds are 100% within about 2 squares, decaying to 30%
1857         // at LOS range (radius 8). Even if the corruption roll is made,
1858         // the feature still gets a chance to resist if it's a wall.
1859         const int corrupt_perc_chance =
1860             idistance2 <= ground_zero_radius2 ? 100 :
1861             max(1, 100 - (idistance2 - ground_zero_radius2) * 70 / 57);
1862
1863         if (random2(100) < corrupt_perc_chance && _is_grid_corruptible(*ri))
1864             _corrupt_square(cenv, *ri);
1865     }
1866 }
1867
1868 static bool _is_level_corrupted()
1869 {
1870     if (player_in_branch(BRANCH_ABYSS))
1871         return true;
1872
1873     return !!env.markers.find(MAT_CORRUPTION_NEXUS);
1874 }
1875
1876 bool is_level_incorruptible(bool quiet)
1877 {
1878     if (_is_level_corrupted())
1879     {
1880         if (!quiet)
1881             mpr("This place is already infused with evil and corruption.");
1882         return true;
1883     }
1884
1885     return false;
1886 }
1887
1888 static void _corrupt_choose_colours(corrupt_env *cenv)
1889 {
1890     colour_t colour = BLACK;
1891     do
1892         colour = random_uncommon_colour();
1893     while (colour == env.rock_colour || colour == LIGHTGREY || colour == WHITE);
1894     cenv->rock_colour = colour;
1895
1896     do
1897         colour = random_uncommon_colour();
1898     while (colour == env.floor_colour || colour == LIGHTGREY
1899            || colour == WHITE);
1900     cenv->floor_colour = colour;
1901 }
1902
1903 bool lugonu_corrupt_level(int power)
1904 {
1905     if (is_level_incorruptible())
1906         return false;
1907
1908     simple_god_message("'s Hand of Corruption reaches out!");
1909     take_note(Note(NOTE_MESSAGE, 0, 0, make_stringf("Corrupted %s",
1910               level_id::current().describe().c_str()).c_str()));
1911
1912     flash_view(MAGENTA);
1913
1914     _initialise_level_corrupt_seeds(power);
1915
1916     corrupt_env cenv;
1917     _corrupt_choose_colours(&cenv);
1918     _corrupt_level_features(cenv);
1919     run_corruption_effects(300);
1920
1921 #ifndef USE_TILE_LOCAL
1922     // Allow extra time for the flash to linger.
1923     delay(1000);
1924 #endif
1925
1926     return true;
1927 }